none
Memory leak... please help me...... RRS feed

  • Question

  • Hi~

    I just want to build a Binary Tree class. I want that using one method to achieve the insert action of my BTree (in my code it is create() ). However, I made a lot of memory leak in my way. It is hard to clean the pointer.... Can anyone help me? Thanks in advance.

    here is my little code:

    #include <iostream> using namespace std; struct TNode { int data; TNode *left,*right; }; class MyBTree { public: MyBTree(); ~MyBTree(); void create(int); // my insert data function void display(){preOrder(*root);cout<<endl;} // just a display function void preOrder(TNode&); // i just assign every new data to left branch, because i'm lazy... TNode* root; }; MyBTree::MyBTree() { root = NULL; } MyBTree::~MyBTree() { } void MyBTree::create(int a) { TNode *newNode = new TNode; newNode->data = a; newNode->right = newNode->left = NULL; if(root == NULL) root = newNode; else { TNode *next =new TNode; TNode *here = root; while (here!= NULL) // cycle ends when it reach the end of the TNode. { next = here; here = here->left; } next->left = newNode; //append the data to the last pointer } } void MyBTree::preOrder(TNode &p) { if(p.data != NULL) { cout<<p.data<<" "; preOrder(*(p.left)); } } int _tmain(int argc, _TCHAR* argv[]) { MyBTree *b1 = new MyBTree(); b1->create(10); b1->create(20); b1->create(30); b1->display();

    delete b1;

    return 0; }


    • Edited by V.Ravnos Wednesday, July 31, 2013 4:14 PM edit ...
    Wednesday, July 31, 2013 4:11 PM

Answers

  • Oops.  You have many flaws due to carelessness.

    Like this block, for example:

    TNode *next =new TNode;
    TNode *here = root;
    while (here!= NULL)    // cycle ends when it reach the end of the TNode.
    {
    	next = here;
    	here = here->left;
    }
    next->left = newNode;  //append the data to the last pointer

    Consider what happens above when root is non-null.

    1. You allocate a new TNode, and store it in the local variable next.
    2. You have a non-null root, which you assign to here.
    3. You overwrite the value of next with the value of here.  You have now orphaned the TNode that you allocated at the start of the function, because you no longer have any pointers that point to it.  You used to have a value stored in next, but that was the only place you kept the address of the TNode you created.  Once you overwrite that pointer, you'll never get the address back to delete it and it will continue to live on in isolation with your program having no pointer value by which to access it... a so-called memory leak.

    Also, just because you delete b1 doesn't mean that it automatically deletes objects that b1's member variables point to.  It just deletes the storage for the TNode that b1 points to -- that's it.  To automatically delete the things that the node points to (its children), you'll have to create a destructor for TNode that deletes its left and right children.  Those delete calls will then recursively delete their children and so on.  But without a destructor, the delete won't do this automatically.  To do it manually, you'll have to walk the tree and delete all the nodes yourself.

    You're doing well so far.  But you do need to improve your diligence.  I suggest you make diagrams that help you visualize what storage you have and what you've stored in each variable.  Use boxes to represent objects you've allocated, and use slots within those boxes to visualize member variable storage, and use lines to represent pointers to other objects.

    Something like this:

    Or this, or this.

    Once you are an expert at keeping track of all your memory, and you can remember to "dot all the i's and cross all the t's" so-to-speak, then you can simplify your diagrams by dropping all the labels, and then omitting the storage boxes for the pointers nodes and just use lines like this:

    You'll know by convention that arrows that go to the left are the "left" pointer and arrows that go to the "right" are the right pointer and arrows you didn't draw are pointers that hold the value null.  But you should still make diagrams.  And it's a good idea to include the root pointer in your diagrams.  Even though it isn't stored in a TNode, it's stored in a MyBTree.  It's still there.  Also the ultimate pointer to all those thing, b1, is stored as a local variable on the stack in the _tmain function.  It's a good idea to visualize that in your diagram as well.

    Furthermore, you should walk through your code and consider all the cases.  Consider both the true and false cases for all your if statements.  Find out what happens and consider all the state.  Make assertions if necessary, and devise test cases that exercise these code paths.

    Convince yourself that your loops will terminate.  Make sure that pointer variables are initialized to null.  It would be much better to do so in a constructor for the TNode class rather than in the few hand-rolled statements following your call to new TNode.  An uninitialized pointer can have any value.  It may be null, may point to some other node, may point to something that has been deleted, or may point to garbage or even memory used for something else.  As a beginner, it's a really good idea to avoid having uninitialized data anywhere at all.  Get into the habit of initializing all your data members in a constructor for the class.

    Once you get good at this, you'll want to start making use of classes that automatically handle this for you.  Automatic pointers and the RAII pattern etc.  But if you're just learning, then it's a good experience to go through the motions of keeping track of everything yourself so that you know what's going on.

    Good luck!

    • Marked as answer by V.Ravnos Wednesday, August 7, 2013 4:18 PM
    Wednesday, July 31, 2013 5:27 PM
  • In Addition to above mentioned suggestion .You should simply use smart pointer inside your class . So once your class goes out of scope it will automatically free all the allocated memory.

    Thnaks


    Rupesh Shukla

    • Proposed as answer by Pintu Shukla Wednesday, July 31, 2013 7:45 PM
    • Marked as answer by V.Ravnos Wednesday, August 7, 2013 4:18 PM
    Wednesday, July 31, 2013 4:54 PM
  • Assuming you never create cycles in your tree (i.e. never have a tree node that has a child that is also one of its ancestors, directly or indirectly), then you can have each tree node delete its children.

    struct TNode
    {
       int data;
       TNode *left,*right;
    
       // Default constructor initializes left and right child
       // pointers to null.
       TNode() : left(nullptr), right(nullptr) {}
    
       // Destructor will delete left and right child nodes
       // and by recursion, the entire subtrees will be
       // deleted too.
       ~TNode()
       {
          delete left;
          delete right;
       }
    };

    This is the bare minimum that you should do to avoid your leaks.  There are still ways to create leaks, particularly if you copy or assign node values, and other ways to go about it.  But this is a good start for a non-expert.

    You'll also want to add code into MyBTree::~MyBTree() that deletes the root node.

    MyBTree::~MyBTree()
    {
       delete root;
    }

    Others are proposing that, instead of a "raw" pointer, you should actually make use of a smart pointer class that does the initialization to null and delete on destroy automatically.  Selecting the right kind of smart pointer class further hinges on the precondition that each node owns what it points to (see std::unique_ptr).  If you move to a more general graph, then each node may have multiple ancestors, so the ownership is shared (see std::shared_ptr).  And depending on the complexity of the graph operations you will be performing, using a shared pointer may be unnecessarily inefficient if the lifetime of all the nodes is known a priori, you can allocate and deallocate storage for nodes all at once, or in groups rather than individually, but this is definitely getting into advanced implementations.


    • Proposed as answer by Anna Cc Wednesday, August 7, 2013 9:29 AM
    • Marked as answer by V.Ravnos Wednesday, August 7, 2013 4:17 PM
    Tuesday, August 6, 2013 3:08 PM

All replies

  • Well you do allocate a new TNode in each call to your MyBTree create function that is never deleted.  That will certainly leak memory -- in fact it is the definition of leaking memory.

    If you are going to use raw pointers (generally a bad idea, but I suspect this is a homework assignment whose point may be dealing with pointers), then you need to clean them up in the owning object's destructor.  In this case, MyBTree is the owning object, so ~MyBTree needs to traverse all the nodes in the tree and call delete on each one in order to avoid leaking memory.

    Also, I don't think your binary tree is ever going to look very tree like as it currently seems to just make a linked list based on the left hand node.

    • Proposed as answer by dlafleur Wednesday, July 31, 2013 5:28 PM
    • Unproposed as answer by V.Ravnos Friday, August 2, 2013 6:12 PM
    Wednesday, July 31, 2013 4:39 PM
  • In Addition to above mentioned suggestion .You should simply use smart pointer inside your class . So once your class goes out of scope it will automatically free all the allocated memory.

    Thnaks


    Rupesh Shukla

    • Proposed as answer by Pintu Shukla Wednesday, July 31, 2013 7:45 PM
    • Marked as answer by V.Ravnos Wednesday, August 7, 2013 4:18 PM
    Wednesday, July 31, 2013 4:54 PM
  • Oops.  You have many flaws due to carelessness.

    Like this block, for example:

    TNode *next =new TNode;
    TNode *here = root;
    while (here!= NULL)    // cycle ends when it reach the end of the TNode.
    {
    	next = here;
    	here = here->left;
    }
    next->left = newNode;  //append the data to the last pointer

    Consider what happens above when root is non-null.

    1. You allocate a new TNode, and store it in the local variable next.
    2. You have a non-null root, which you assign to here.
    3. You overwrite the value of next with the value of here.  You have now orphaned the TNode that you allocated at the start of the function, because you no longer have any pointers that point to it.  You used to have a value stored in next, but that was the only place you kept the address of the TNode you created.  Once you overwrite that pointer, you'll never get the address back to delete it and it will continue to live on in isolation with your program having no pointer value by which to access it... a so-called memory leak.

    Also, just because you delete b1 doesn't mean that it automatically deletes objects that b1's member variables point to.  It just deletes the storage for the TNode that b1 points to -- that's it.  To automatically delete the things that the node points to (its children), you'll have to create a destructor for TNode that deletes its left and right children.  Those delete calls will then recursively delete their children and so on.  But without a destructor, the delete won't do this automatically.  To do it manually, you'll have to walk the tree and delete all the nodes yourself.

    You're doing well so far.  But you do need to improve your diligence.  I suggest you make diagrams that help you visualize what storage you have and what you've stored in each variable.  Use boxes to represent objects you've allocated, and use slots within those boxes to visualize member variable storage, and use lines to represent pointers to other objects.

    Something like this:

    Or this, or this.

    Once you are an expert at keeping track of all your memory, and you can remember to "dot all the i's and cross all the t's" so-to-speak, then you can simplify your diagrams by dropping all the labels, and then omitting the storage boxes for the pointers nodes and just use lines like this:

    You'll know by convention that arrows that go to the left are the "left" pointer and arrows that go to the "right" are the right pointer and arrows you didn't draw are pointers that hold the value null.  But you should still make diagrams.  And it's a good idea to include the root pointer in your diagrams.  Even though it isn't stored in a TNode, it's stored in a MyBTree.  It's still there.  Also the ultimate pointer to all those thing, b1, is stored as a local variable on the stack in the _tmain function.  It's a good idea to visualize that in your diagram as well.

    Furthermore, you should walk through your code and consider all the cases.  Consider both the true and false cases for all your if statements.  Find out what happens and consider all the state.  Make assertions if necessary, and devise test cases that exercise these code paths.

    Convince yourself that your loops will terminate.  Make sure that pointer variables are initialized to null.  It would be much better to do so in a constructor for the TNode class rather than in the few hand-rolled statements following your call to new TNode.  An uninitialized pointer can have any value.  It may be null, may point to some other node, may point to something that has been deleted, or may point to garbage or even memory used for something else.  As a beginner, it's a really good idea to avoid having uninitialized data anywhere at all.  Get into the habit of initializing all your data members in a constructor for the class.

    Once you get good at this, you'll want to start making use of classes that automatically handle this for you.  Automatic pointers and the RAII pattern etc.  But if you're just learning, then it's a good experience to go through the motions of keeping track of everything yourself so that you know what's going on.

    Good luck!

    • Marked as answer by V.Ravnos Wednesday, August 7, 2013 4:18 PM
    Wednesday, July 31, 2013 5:27 PM
  • Hi,SimonRev,thanks for your comments. This is not homework. I just want to get out it on my way.

    Hi,Rupesh thanks very much for the suggestion. I will try it. I'm not familiar with C11. Maybe a good docment about such way of using pointer will be better.

    Friday, August 2, 2013 6:12 PM
  • Hi, Wyck. You are great! Thank you very much for the way of TNode destruction. I will try that. I am trying to do the honest way of instantiation and pointer manager. So I will try again with your guide. Thanks again.
    Friday, August 2, 2013 6:23 PM
  • Hello V Ravnos you can look on MSDN or on google there are so many good article for smart pointer. Just proceed with them. And Pretty good explanation by Wyck you can proceed with it .

    Thanks


     


    Rupesh Shukla

    Friday, August 2, 2013 8:57 PM
  • Hi,

    I got the crash because I use the uninitialized pointer here:

    if(p.data != NULL)
    	{
    		cout<<p.data<<" ";
    		preOrder(*(p.left));
    	}

    Adding judgment before using data: if(p.left!=NULL), it will not crash.

    For the destruction function, can it be write as: "delete this;" ?

    Sunday, August 4, 2013 5:28 PM
  • Assuming you never create cycles in your tree (i.e. never have a tree node that has a child that is also one of its ancestors, directly or indirectly), then you can have each tree node delete its children.

    struct TNode
    {
       int data;
       TNode *left,*right;
    
       // Default constructor initializes left and right child
       // pointers to null.
       TNode() : left(nullptr), right(nullptr) {}
    
       // Destructor will delete left and right child nodes
       // and by recursion, the entire subtrees will be
       // deleted too.
       ~TNode()
       {
          delete left;
          delete right;
       }
    };

    This is the bare minimum that you should do to avoid your leaks.  There are still ways to create leaks, particularly if you copy or assign node values, and other ways to go about it.  But this is a good start for a non-expert.

    You'll also want to add code into MyBTree::~MyBTree() that deletes the root node.

    MyBTree::~MyBTree()
    {
       delete root;
    }

    Others are proposing that, instead of a "raw" pointer, you should actually make use of a smart pointer class that does the initialization to null and delete on destroy automatically.  Selecting the right kind of smart pointer class further hinges on the precondition that each node owns what it points to (see std::unique_ptr).  If you move to a more general graph, then each node may have multiple ancestors, so the ownership is shared (see std::shared_ptr).  And depending on the complexity of the graph operations you will be performing, using a shared pointer may be unnecessarily inefficient if the lifetime of all the nodes is known a priori, you can allocate and deallocate storage for nodes all at once, or in groups rather than individually, but this is definitely getting into advanced implementations.


    • Proposed as answer by Anna Cc Wednesday, August 7, 2013 9:29 AM
    • Marked as answer by V.Ravnos Wednesday, August 7, 2013 4:17 PM
    Tuesday, August 6, 2013 3:08 PM
  • Thank you Wyck.
    Wednesday, August 7, 2013 4:18 PM