Memory allocation and deallocation

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

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.

It's more difficuilt to have the AVL both allocate and destroy the memory. But I don't see any easy way to avoid this, besides of course having a make_node function. But then you'd still run into problems because you mijght want each templated data type to be created a different way. C libraries don't have this problem. So, in C you could have a make_node and destroy_node that would call malloc and delete, respectively, or perhaps a user defined allocator and deallocator.

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?

For example datastructure, forcing the client to use "new" saves the author from writing iterator classes, but what STL does is to be preferred, I think. Basically, STL leaves the allocation and the deallocation of the contained elements to the client. wxwidgets, on the other hand, by requiring all window allocation with "new", is like to the AVL tree, but there are some other benefits to this approach such as having both modal and non-modal dialog boxes being allocated and destroyed the same way.

Thanks for the reply okinrus. I must say I hoped there would be other opinions here... too bad.

Thanks

- Micko

I agree that having the tree delete the pointers is not as good of a solution as other solutions might have been. There is very little flexibility in a design that requires data to be allocated on the heap. Especially in C++, where often raw pointers are rare. Even in situations where you would want to store a heap based object, using a smart pointer would be preferred but not allowed due to the tree delete code.

I prefer the STL's (generally tree-based) set container, which can, for example, store ints without the need to allocate memory for them dynamically, and can store shared_ptrs if one wants automatic deletion.

Maybe the reason you didn't get many replies is that this seems obvious. I can't see the benefit of the implementation of that tree except in the specific circumstance where you want to store dynamically allocated memory, have it cleaned up automatically, and you don't want to use the appropriate smart pointer.