Quesiton about classes/dynamic allocation.

This is a discussion on Quesiton about classes/dynamic allocation. within the C++ Programming forums, part of the General Programming Boards category; I'm making a binary tree class with a lot of pointers to objects. The thing is they aren't allocated using ...

  1. #1
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901

    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?
    Last edited by indigo0086; 12-21-2006 at 07:04 AM.

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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?
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.
    My best code is written with the delete key.

  4. #4
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    Well the actual Nodes are Classes, they only contain three members, two for the children, and one for the data. The actual tree class has a pointer to a Node for the head and that should be it. Everything works off pointers, but nothing is stored in arrays or something.

    Edit: By "calling code deal with the memory" is this something I should implement or is this a compiler specific call.

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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?
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  6. #6
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    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.

  7. #7
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,471
    Quote 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?
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  8. #8
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    Well there's a node class and a tree class. All the node classes are contained within the tree class so I guess when the tree class goes out of scope all the node classes get destroyed. So the class itself would be destroyed when it goes out of scope. I was just wondering if I needed to do any special type of destruction of each node down to the child, or do I just let the default synthesized destructor do all the work without worry of a memory leak.

  9. #9
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,471
    Could you post your add function? and tree class definition?
    I personally cannot answer the quetion without seeing the code
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  10. #10
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    I haven't started writing the tree implementations yet, I wanted to know before I wrote them if there would be a conflict. It really is a node question because when the tree is destroyed so are the nodes.

    Code:
    #define NULL 0
    
    class Node
    {
        public:
            Node(int d = 0): left(NULL), right(NULL), data(d) {}
            Node(const Node&);
            Node& operator=(const Node&);
            ~Node() { remove_children(this); }
    
            Node *l_child() const { return left; }
            Node *r_child() const { return right; }
            Node get_data() const { return data; }
    
            bool has_children() const { return (left != NULL) || (right != NULL); }
            bool leaf() const { return (left == NULL) && (right == NULL); }
    
        private:
            Node *left, *right;
            int data;
    
            void remove_children(Node*);
    };
    Code:
    #include "bintree.h"
    
    //========================= Node Implementation ================================
    
    //copy constructor
    Node::Node(const Node& aNode)
        :left(aNode.left), right(aNode.right), data(aNode.data) {}
    
    
    Node& Node::operator=(const Node& aNode)
    {
        if(&aNode != this)
        {
            if(has_children())
                remove_children(this);
            left = aNode.left;
            right = aNode.right;
            data = aNode.data;
        }
        return *this;
    }
    
    void Node::remove_children(Node* n)
    {
        n->left = n->right = NULL;
    }

  11. #11
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,471
    Currently - because you don't allocate memory in any function - you don't need to free it...
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  12. #12
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    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.
    My best code is written with the delete key.

  13. #13
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    cool.

  14. #14
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    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?
    Last edited by indigo0086; 12-22-2006 at 10:06 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. dynamic allocation from 1 instead of zero
    By cfdprogrammer in forum C Programming
    Replies: 27
    Last Post: 04-28-2009, 08:21 AM
  2. pointer to array with dynamic allocation
    By cfdprogrammer in forum C Programming
    Replies: 22
    Last Post: 04-07-2009, 09:56 AM
  3. Allocation from "static array"
    By Petike in forum C Programming
    Replies: 6
    Last Post: 10-12-2008, 03:17 AM
  4. Difference between straight and dynamic allocation?
    By darsunt in forum C++ Programming
    Replies: 10
    Last Post: 06-04-2008, 05:47 PM
  5. redundant allocation
    By George2 in forum C++ Programming
    Replies: 22
    Last Post: 03-06-2008, 05:43 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21