Thread: Quesiton about classes/dynamic allocation.

I'm making a binary tree class with a lot of pointers to objects. The thing is they aren't allocated using new. I have a node class with a Node* for left and right, and whenever I add a node it just uses uses the rules of a binary search tree to point the pointers to the added node. The thing is when I want to destroy them. I know that the synthesized destructor doesn't get rid of the objects being pointed to, but if they aren't allocated with new should I be worried about the cleanup?

So basically what I'm saying is lets say I add nodes and have a tree of like height 5. Would just destroying the link from the head to all descendants suffice, or does my destructor need to recursively deconstruct the objects?

whenever I add a node it just uses uses the rules of a binary search tree to point the pointers to the added node.

So where are the nodes stored? What makes them persistent?

>if they aren't allocated with new should I be worried about the cleanup?
If you don't control allocation, you shouldn't be expected to worry about release. Just snip the node out of your structure and let the calling code deal with the memory. The big thing I would worry about is node corruption. Because you don't control the memory, it's possible that a node will be released while still linked to the tree.

It's a requirement on the user of your tree.

But you haven't answered my question: where are the nodes stored, if not on the heap?

Originally Posted by indigo0086

I'm guessing the same place other classes are stored when not dynamically allocated.

I create a head node, initially it has a set value and two node pointers, I insert another node by constructing it initially with null children, and a value, and insert it as a BST, then point the head node to that, then so on and so on.

When clas is not dynamically allocated it is stored in the stack
When this variable exits the scope - the class is destroyed.

Are you saying that in your class you just point to the local variables that are actually destroyed after function exits

or the add function of the tree does something smarter than that?

Could you post your add function? and tree class definition?
I personally cannot answer the quetion without seeing the code

Currently - because you don't allocate memory in any function - you don't need to free it...

Okay, there are basically two ways to handle the nodes in a tree (or in any linked data structure). You can completely control the memory for nodes by creating them and destroying them internally:

Code:

// Insert an owned node
node *add ( node *root, int data )
{
  if ( root == 0 )
    root = new node ( data );
  else {
    int dir = root->data < data;
    root->link[dir] = add ( root->link[dir], data );
  }

  return root;
}

This is preferred simply because the memory is under your control and you don't have to worry about some yoyo in another module screwing with it. The other option is to accept existing nodes and simply handle the links to fit it into your structure:

Code:

// Insert an unowned node
node *add ( node *root, node *obj )
{
  if ( root == 0 )
    root = obj;
  else {
    int dir = root->data < obj->data;
    root->link[dir] = add ( root->link[dir], obj );
  }

  return root;
}

This is useful if you want to support non-dynamic nodes (nodes created on the stack) and it makes working with free lists easier because you move the maintenance of the free list elsewhere and can focus on the tree algorithms.

Better question, I've noticed that if I do re-direct pointers the objecst still won't be destroyed until after the call to main finishes, is there a way to destroy the objects when I disconnect the pointers to the node classes?