C++ Copy Constructor + Pointer Object

Question

I'm trying to learn "big three" in C++.. I managed to do very simple program for "big three".. but I'm not sure how to use the object pointer.. The following is my first attempt.

I have a doubt when I was writing this...

Questions

1. Is this the correct way to implement the default constructor? I'm not sure whether I need to have it or not. But what I found in another thread about copy constructor with pointer is that I need to allocate the space for that pointer before copying the address in copy constructor..
2. How to assign the pointer variable in the copy constructor? The way that I wrote in Copy Constructor might be wrong.
3. Do I need to implement the same code (except return ) for both copy constructor and operatior=?

4. Am I correct in saying that I need to delete the pointer in destructor?

   class TreeNode
   {
   public:  
      TreeNode(); 
      TreeNode(const TreeNode& node);
      TreeNode& operator= (const TreeNode& node);
      ~TreeNode();
   private:
      string data;
      TreeNode* left;
      TreeNode* right;
      friend class MyAnotherClass;
   };
   

Implementation

TreeNode::TreeNode(){

    data = "";  

}

TreeNode::TreeNode(const TreeNode& node){
     data = node.data;

     left = new TreeNode();
     right = new TreeNode();

     left = node.left; 
     right = node.right;
}

TreeNode& TreeNode::operator= (const TreeNode& node){
     data = node.data;
     left = node.left;
     right = node.right;
     return *this;
}

TreeNode::~TreeNode(){
     delete left;
     delete right;
}

Thanks in advance.

Adventitia

It's unnecessary to assign an empty string to data in your TreeNode constructor, since the default constructor of std::string will do that itself. – Charlet

Your copy constructor and assignment operator have slightly differing copy semantics. That's very confusing to users of your class. – Omasum

hi sbi, You mean, I should use the exact copy of the same code for both copy constructor and operator? – Adventitia

See below. For a version that provides the Strong Exception Guarantee. The current version above leaks (left and right) on both copy construction and during assignment. – Annal

(You need to properly @address people in comment responses, otherwise your replies won't show up in their responses tab.) No, you shouldn't. A copy constructor initializes members by invoking their constructors, while an assignment operator assigns new values to already constructed members. Independently of that, you can perform deep copying or shallow copying, and your code is a unhealthy mix of these. – Omasum

Answer 1

Am I correct in saying that I need to delete the pointer in destructor?

Whenever designing an object like this, you first need to answer the question: Does the object own the memory pointed to by that pointer? If yes, then obviously the object's destructor needs to clean up that memory, so yes it needs to call delete. And this seems to be your intent with the given code.

However in some cases, you might want to have pointers that refer to other objects whose lifetime is supposed to be managed by something else. In that case you don't want to call delete because it is the duty of some other part of the program to do so. Furthermore, that changes all the subsequent design that goes into the copy constructor and assignment operator.

I'll proceed with answering the rest of the questions under the assumption that you do want each TreeNode object to have ownership of the left and right objects.

Is this the correct way to implement the default constructor?

No. You need to initialize the left and right pointers to NULL (or 0 if you prefer). This is necessary because unintialized pointers could have any arbitrary value. If your code ever default constructs a TreeNode and then destroys it without ever assigning anything to those pointers, then delete would be called on whatever that initial value is. So in this design, if those pointers aren't pointing at anything, then you must guarantee that they are set to NULL.

How to assign the pointer variable in the copy constructor? The way that I wrote in Copy Constructor might be wrong.

The line left = new TreeNode(); creates a new TreeNode object and sets left to point to it. The line left = node.left; reassigns that pointer to point to whatever TreeNode object node.left points to. There are two problems with that.

Problem 1: Nothing now points to that new TreeNode. It is lost and becomes a memory leak because nothing can ever destroy it.

Problem 2: Now both left and node.left end up pointing to the same TreeNode. That means the object being copy constructed and the object it's taking values from will both think they own that same TreeNode and will both call delete on it in their destructors. Calling delete twice on the same object is always a bug and will cause problems (including possibly crashes or memory corruption).

Since each TreeNode owns its left and right nodes, then probably the most reasonable thing to do is make copies. So you would write something similar to:

TreeNode::TreeNode(const TreeNode& node)
    : left(NULL), right(NULL)
{
    data = node.data;

    if(node.left)
        left = new TreeNode(*node.left);
    if(node.right)
        right = new TreeNode(*node.right);
}

Do I need to implement the same code (except return ) for both copy constructor and operatior=?

Almost certainly. Or at least, the code in each should have the same end result. It would be very confusing if copy construction and assignment had different effects.

EDIT - The above paragraph should be: The code in each should have the same end result in that the data is copied from the other object. This will often involve very similar code. However, the assignment operator probably needs to check if anything has already been assigned to left and right and so clean those up. As a consequence, it may also need to watch out for self-assignment or else be written in a way that doesn't cause anything bad to happen during self-assignment.

In fact, there are ways to implement one using the other so that the actual code that manipulates the member variables is only written in one place. Other questions on SO have discussed that, such as this one.

Intendant

How were you the only one to point out the new TreeNode(); memory leak? – Ambrogio

+1 for understanding the problem and giving a good solution. This answer is definitely better than that of mine. :) – Mahmud

Before assigning to left you should probably delete the old value (dito for right) – Annal

Oh right, I totally forgot about the assignment operator needing to watch out for and properly clean up anything previously assigned to left and right. – Intendant

Answer 2

Even better, I think

 TreeNode::TreeNode():left(NULL), right(NULL)
 {
   // data is already set to "" if it is std::string
 }

plus you have to delete the pointers 'left' and 'right' in the assignment operation, or you'll have a memory leak

Jenny

Answer 3

This is how I would do it:
Because you are managing two resources in the same object doing this correctly becomes a bit more complex (Which is why I recommend never managing more than one resource in an object). If you use the copy/swap idiom then the complexity is limited to the copy constructor (which is non trivial to get correct for the strong exception guarantee).

TreeNode::TreeNode()
    :left(NULL)
    ,right(NULL)
{}

/*
 * Use the copy and swap idium
 * Note: The parameter is by value to auto generate the copy.
 *       The copy uses the copy constructor above where the complex code is.
 *       Then the swap means that we release this tree correctly.
 */ 
TreeNode& TreeNode::operator= (const TreeNode node)
{
     std::swap(data,  node.data);
     std::swap(left,  node.left);
     std::swap(right, node.right);
     return *this;
}

TreeNode::~TreeNode()
{
     delete left;
     delete right;
}

The hard part now:

/*
 * The copy constructor is a bit harder than normal.
 * This is because you want to provide the `Strong Exception Guarantee`
 * If something goes wrong you definitely don't want the object to be
 * in some indeterminate state.
 *
 * Simplified this a bit. Do the work that can generate an exception first.
 * Once all this has been completed we can do the work that will not throw.
 */   
TreeNode::TreeNode(const TreeNode& node)
{
    // Do throwable work.
    std::auto_ptr<TreeNode>  nL(node.left  == null ? null : new TreeNode(*node.left));
    std::auto_ptr<TreeNode>  nR(node.right == null ? null : new TreeNode(*node.right));

    // All work that can throw has been completed.
    // So now set the current node with the correct values.
    data  = node.data;
    left  = nL.release();
    right = nR.release();
}

Annal

+1 Even if this might be a bit advanced for someone just learning the basics of managing pointers and implementing the big three operators, this is still a correct "industrial-strength" solution. – Intendant

@TheUndeadFish: It is only complex because there are two resources in the object to manage. If it was a single resource there would be basically zero code required (Which is why IMHO objects should only manage one resource at a time). – Annal

Thanks a lot, Martin.. I will try to compile it at my end.. I'm using MinGW.... I didn't use auto_ptr and release() before.. I think the reason why I need two objects is that I need to have left node and right node .... – Adventitia

@Michael Sync: Simplified the copy constructor a bit. – Annal

Answer 4

Is this the correct way to implement the default constructor?

No, calling delete on something that has not been allocated using new invokes Undefined Behavior (in most cases it results to crash of your application)

Set your pointers to NULL in your default constructor.

TreeNode::TreeNode(){
  data = "";   //not required since data being a std::string is default initialized.
  left = NULL;
  right = NULL;   
}

I don't see such problems with the rest of your code. Your assignment operator shallow copies the nodes whereas your copy constructor deep copies them.

Follow a suitable approach as per your requirement. :-)

EDIT:

Instead of assigning pointers in your default constructor use an initialization list

Mahmud

Thanks. What about other questions? – Adventitia

See the edits, I have tried to answer your questions briefly. :-) – Mahmud

Thanks .. Do I have to put "left = new TreeNode();" in copy constructor? Is it necessary? Otherwise, I will remove it... – Adventitia

@Michael : Depends on whether you want to perform deep copy or shallow copy – Mahmud

AFAIK, using copy constructor is for deep-copy, right? so, I would say that I want deep-copy.. – Adventitia

one more thing. Do I need to add the logic for comparing the object in operatior=? – Adventitia

@Michael : You would have to add code to check self assignment. – Mahmud

Answer 5

May I also suggest boost::shared_ptr from the library boost (if you can used it), instead of simple pointers? It'll solve a lot of problems you might have with invalid pointers, deep copies e.t.c.

Jenny

indeed, you'll run into trouble with the code as it is when you assign one tree node from another and then both are deleted: the children will be deleted twice but were only allocated once. So I can only support this suggestion to use smart pointers. – Teece