Hello, I remember one thread in which I created linked list and wrote appropriate functions. Then, I had dillema how to write functions, especially how to handle memory issue. For example I thought that function that insert new item in linked list should allocate and initialize new node and then add that node in linked list structure by playing with pointers . I asked for advice and Prelude wrote this:
Originally Posted by
Prelude
There are two schools of thought on the matter. The first feels that a data structure "owns" the data used to organize content (ie. nodes or cells) and it's the responsibility of the data structure to handle memory for that data. The second school of thought believes that data structures are just a means of organizing data that is owned by another entity (ie. the calling function in this case). As with functions that work with a string being passed to it, the memory is assumed to exist and be large enough, as well as initialized in all of the right places for the functions to work with it safely and effectively. It's the responsibility of the owner to handle memory.
Which is better? Who knows? Because I prefer to have control over my data structures, and I dole out pointers to nodes for ease of use instead of opting for data hiding, the second school of thought works better for me in many situations. A more object driven approach would suit the first school of thought better, and I find myself using that quite a bit as well. For the tutorial I chose the the former so that I could more easily profile for performance. malloc and free have a tendency of getting in the way of a good performance test.
Now I have similar problem. I've downloaded template class AVL tree from the Internet and I want to use it to insert item, process them etc. At first I came accross one nasty run time error. Header file is in attachment because of lengthy code.
By examining this code I saw this prototype:
Code:
TreeData * Insert(TreeData *item);
and decide to test this tree with the following code
Code:
#include "ttree.h"
#include <iostream>
#include <string>
using namespace std;
static int CMyTree_compare(const string* it1, const string* it2)
{
if (*it1 == *it2)
return 0;
else if (*it1 > *it2)
return 1;
else
return -1;
}
class CMyTree : public CTTree <string>
{
public:
CMyTree() : CTTree<string>(CMyTree_compare){}
};
//}
int main()
{
CMyTree m;
string s1("Micko");
m.Insert(&s1);
}
At the end of this program there was a run time error (exception) _BLOCK_TYPE_IS_VALID.... in dbgdel.cpp so I knew it's something fishy about memory.
Then I tested with this code
Code:
int main()
{
CMyTree m;
string * ps1= new string("Micko");
m.Insert(ps1);
}
And everything worked fine.
By examining ttree.h I noticed that memory is deleted in destructor, so that's why there was an excaption at the end of the program.
Object was created on stack, passed by address and destructor try to delete it producing run time error.
So in esence this AVL tree structure is organize that way (if I'm not mistaken) that it must receive pointer to object on the heap and deallocate memory automatically. So this structure do not allocate memory but deallocate it.
I found this implementation very unintuitive to use, and since I don't have any real life programming experience I would like to ak you to comment this. If this practice usual and what do you think about this code?
Thank you very much
- Micko