CODEWITHSUNDEEP
c++treecopy-constructor
Peter Stewart
Peter Stewart

Reputation: 3017

What's wrong with this copy constructor?

I've been trying to come up with a copy constructor for a tree. I've found quite a few suggestions.

This one interested me. 

class TreeNode
{
    int ascii;
    TreeNode* left;
    TreeNode* right;

public:
    TreeNode() { ascii = 0; left = right = 0; }
    TreeNode* clone();
    // ...
};

 TreeNode* TreeNode::clone()
    {
        if (TreeNode* tmp = new TreeNode)
        {
            tmp->ascii = ascii;
            if (left) tmp->left = left->clone();
            if (right) tmp->right = right->clone();
            return tmp;
        }
        return 0;
    }

What does "if (TreeNode* tmp = new TreeNode) mean?

Other than that it looks alright. It just doesn't work very well.

Any idea what's wrong with it?

The example above came from this site.

Upvotes: 4

Views: 452

Answers (4)

Manfred
Manfred

Reputation: 5666

I wouldn't call the method clone() a copy constructor. For example it is not a constructor in the first place just a method.

Implement a copy constructor in C++ like this (I left out all other members to keep it short):

class TreeNode {
    public:
       TreeNode(const TreeNode& source) {
          // copy members here, e.g.
          left = source.left;
          ...
       }
};

Edit: The example given implements/suggests a shallow copy. This is what the compiler creates for you if you didn't implement a copy constructor. So if you are happy with a shallow copy then you may as well leave out the copy constructor.

Of you prefer a deep copy this constructor may look as follows:

class TreeNode {
   public:
      TreeNode(const TreeNode& source) {
         left = source.left != NULL ? new TreeNode(*source.left) : NULL;
         ...
      }

By implementing the copy constructor you can also mix between deep-copy and shallow-copy if required.

Upvotes: 3

jpalecek
jpalecek

Reputation: 47762

What does if (TreeNode* tmp = new TreeNode) mean?

This is supposed to check the outcome of the allocation, ie. that it hasn't failed. However, this is a bad way of doing it, because:

  1. as others pointed out, new TreeNode will throw an exception in new C++ compilers
  2. Even if it hadn't thrown an exception, it is bad: when only some of the nodes fail to allocate, the caller of clone() won't have noticed anything, but will silently get only a part of the tree.
  3. when considering standard behaviour, this method is exception-unsafe.

Upvotes: 0

Timo Geusch
Timo Geusch

Reputation: 24351

Well, for starters it's not a copy constructor - the copy constructors have a very well defined syntax in C++, so a proper copy constructor would have the prototype TreeNode(TreeNode const &). Just to get the terminology right (and the compiler will still generate a copy constructor as it has no idea what the clone() function is supposed to do).

The expression in the if statement will both allocate a new TreeNode object and purports to check that the allocation succeeded (by checking that the resulting pointer isn't 0). Unfortunately that's pre-standard C++ and modern C++ implementations that are standard conforming will throw a std::bad_alloc exception instead, so the test will mainly give the user a warm fuzzy feeling that something is being done about memory allocation failure, even if it isn't.

In order to make the code work as expected on a standard-compliant compiler, you'll have to use nothrow new. From memory the line would read something like this:

if (TreeNode* tmp = new(std::nothrow) TreeNode)

All that said, unless TreeNode is part of an object hierarchy that relies on the presence of the clone() function I would do away with it and implement a proper C++ constructor instead. That way, the compiler and you are on the same page when it comes to duplicating objects, plus other programmers will find it a little easier to follow your code.

Upvotes: 10

dvallejo
dvallejo

Reputation: 1053

It's been a while but the if ( ) is checking if the the allocation is non-null. IE the "new" succeeded.

Upvotes: 0

Related Questions