• Advertisement
Sign in to follow this  

"push_back" calls destructor?

This topic is 3765 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a class, let's call it Tree that contains a pointer to the root of a binary tree. (the root has pointers to its kids who have pointers to theirs...). Now, in the destructor of Tree I have a function that recursively deallocates the memory used by the tree. Something like this:
class Node{
private:
   bool IsLeaf;
   Node* child1, child2;
public:
   Node();
   void DeleteChildren();
};

void Node::DeleteChildren()
{
    if(!IsLeaf)
    {
        child1->DeleteChildren();
        child2->DeleteChildren();
        delete child1;
        delete child2;
    }
}
class Tree{
private:
   Node *Root;
public:
   Tree();
   ~Tree();
};

Tree::~Tree
{
   Root->DeleteChildren();
   delete Root;
}


Now, I wanted to make a std vector of trees so I did this: Tree Tree1; vector<Tree> Trees; Trees.push_back(Tree1); But for some reason the program crashed. Sp I ran the debugger and found that in the first line Tree1 was initialized and set up properly, but for some reason, as soon as I called the third line Tree1.~Tree was called and it was all erased. Why does this happen? Thanks.

Share this post


Link to post
Share on other sites
Advertisement
push_back may copy-construct and destruct any number of elements of the vector any number of times. Therefore, it is imperative that copy construction of your objects is safe.

In your case, it isn't, because your ownership policy is sloppy (the sub-trees are owned by the Tree object as well as any of its copies, which makes it impossible to copy your objects without a crash).

Share this post


Link to post
Share on other sites
As std::vector resizes, it will use the copy constructor to create new instances of the objects it contains before destructing the 'old' instances. As you delete the tree in the destructor, the new instance doesn't have good memory to listen to.

I'm guessing the easiest fix would be to drop the manual memory-handling and use smart pointers instead (as, I think, there would then be no need for writing a custom copy-constructor, which is the other option).

...

Also, note that I might be completely wrong (but I think I'm right).

EDIT: Ninja-ed by one minute. On the upside, I was right.

Share this post


Link to post
Share on other sites
Simple answer is because it is supposed to and you are supposed to supply a copy constructor and assignment operator to allow deep copies.
google shallow copy and deep copy.

Share this post


Link to post
Share on other sites
Quote:
Original post by daniel_i_l
Thanks for the replys. How can I improve my ownership policy?
Thanks.


Either write a sane copy-constructor (and assignment operator) or don't manually handle memory when you don't have to — use a smart pointer instead (which will manually delete the memory when it's no longer being used).

In terms of actually improving the state of affairs rather than just fixing the bug, you're better doing both (such that each object owns its own copy of the tree, which is then automatically deleted when that instance is destructed without you having to do anything like provide a manual destructor or have a DeleteNode member which manually uses delete).

Share this post


Link to post
Share on other sites
The Node should call it's own DeleteChildren method in its destructor. And DeleteChildren should delete child1 and 2 only if they're not null.

Share this post


Link to post
Share on other sites
You can also use Reference Counting. That should also fix that problem when implementing a proper copy constructor. Though this way it is easier to write buggy code without smart pointers.

Share this post


Link to post
Share on other sites
Quote:
Original post by Cranky
You can also use Reference Counting. That should also fix that problem when implementing a proper copy constructor.


Whilst a smart pointer saves you having to roll-your-own, which will doubtless end up poorer in some way than those provided in, say, Boost.

EDIT: Note: this post was written before you edited your post.

Share this post


Link to post
Share on other sites
How do I write a copy constructor that copies the whole tree? And is that the only solution? Because I've seen many tutorials that build trees this way and they never mentioned the need for a copy constructor.
Thanks.

Share this post


Link to post
Share on other sites
You could dynamically allocate the tree (Tree* = new Tree()) and then store pointers to trees in your vector. If you don't implement a copy constructor, I'd recommend making a private and empty copy constructor and assignment operator.

private:
Tree(Tree &t){}
void operator=(Tree&){}

To implement these operations so that they actually work, you can use recursion to copy the entire tree. Make a copy of the root node, which copies its children, and so on. For operator= you'll want to delete the old root once you have the new one.

Share this post


Link to post
Share on other sites
Vorpy, if I dynamically allocate Trees then do I still need a copy constructor? And what does it help to make an empty one?
Thanks.

Share this post


Link to post
Share on other sites
Quote:
Original post by KOzymandias
And DeleteChildren should delete child1 and 2 only if they're not null.


Calling delete on a NULL pointer is not an error, it is guaranteed to be safe. Calling child1->DeleteChildren(); when child1 is NULL, however...

Quote:
Original post by daniel_i_l
And what does it help to make an empty one?


The important part of what Vorpy did is not the empty copy c-tor and assignment operator, but the fact that they are private. This prevents non-member and non-friend functions from accessing them, effectively making the objects non-copyable.

Share this post


Link to post
Share on other sites
To add to Driv3MeFar's statment about the copy constructor by expicity declaring the copy constructor you stop C++ from automatically creating its own copy constructor.

Share this post


Link to post
Share on other sites
OK, listen up, because I'm not going to repeat it (in this thread anyway ;) )


class Node {
private:
// No need to store information about whether this is a leaf; calculate it.
Node* child1, child2;
public:
Node();
Node(const Node& other);
Node& operator=(const Node& rhs);
~Node();
};

// I like to be explicit about this, though IIRC it's not strictly necessary.
// This is due to a personal paranoia about uninitialized stuff; usually I
// avoid explicitness as much as possible ;)
Node::Node() : child1(0), child2(0) {}

Node::~Node() {
// There is no need to check for the null-ness of the pointers.
delete child1;
delete child2;
// That will implicitly call the destructors of children, where they exist.
}

// Copy construct by initializing the children as copies of the other Node's
// children, recursively.
Node::Node(const Node& other) :
child1(other.child1 ? new Node(*(other.child1)) : 0),
child2(other.child2 ? new Node(*(other.child2)) : 0) {}

// Assign using the copy-and-swap idiom.
Node& operator=(const Node& rhs) {
Node other(rhs);
std::swap(child1, other.child1);
std::swap(child2, other.child2);
return *this;
}

class Tree {
private:
Node root; // not a pointer :) Unless you want support for empty trees too.
public:
// Probably no need for a default constructor or destructor.
};



The node does all the dirty work, so that the Tree becomes a very thin wrapper (you might not even need the separate concept).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement