🔒 Locked

Binary Node (Copy Constructor)

Started by Recruit0 Apr 10, 2009 at 8:58 PM 1 reply 1.4k views

Original Post

Apr 10, 2009 at 8:58 PM

I'm trying to understand why this copy constructor doesn't work, and how to get it to work if possible.

BinaryNode::BinaryNode( const BinaryNode& argNode )
{
  if ( this != 0 && &argNode != 0 ) // How to stop recursion?
  {
    leftNode = 0, rightNode = 0;
    // Only way is to put this in a if statement?
    leftNode = new(nothrow) BinaryNode( *argNode.leftNode );
    data = argNode.data;
    // Only way is to put this in a if statement?
    rightNode = new(nothrow) BinaryNode( *argNode.rightNode );
  }
}

I read somewhere that "new" never returns null. Is this true? I'm wondering if it's possible to use recursion and use some form of the if statement above to stop it (recursing). Hopefully you get the idea of what I'm trying to do with this code. The reason I hoped this would work is because C++ delete operator can do this:

public:
  ~BinaryNode()
    {
      delete leftNode; // recursively deletes each child node
      delete rightNode;
    }

I have a working copy constructor but I'm trying to understand why the code above doesn't work.

Zipster

511

Zipster

Apr 10, 2009 at 9:25 PM

BinaryNode::BinaryNode( const BinaryNode& argNode ) : leftNode(0), rightNode(0){  // Copy left sub-tree  if(argNode.leftNode)    leftNode = new(nothrow) BinaryNode( *argNode.leftNode );  // Copy right sub-tree  if(argNode.rightNode)    rightNode = new(nothrow) BinaryNode( *argNode.rightNode );  // Copy data for this node  data = argNode.data;}

You need to check each sub-tree individually. Plus, it's bad practice to check for this == 0 because a) an invalid instance doesn't necessarily have an address of 0, and b) you shouldn't silently ignore a bug where you're assigning to bad memory.

Zahlman

257

Zahlman

Apr 11, 2009 at 1:23 AM

0) You are on the right track. You want to do this recursively.
1) Checking for 'this' being NULL is not only "bad practice", it's completely useless.

In any circumstance where 'this' could possibly evaluate as NULL, the program has already invoked undefined behaviour somewhere else. The same is true for checking the address of the reference: there is no such thing as a "null reference" in C++.

It's also useless to set a variable to 0 immediately before re-setting it to something else. :)

2) 'new' never returns NULL - unless you tell it to. This is a good thing. You want it not to return NULL, unless you have very specific extenuating circumstances. You want it to throw an exception instead, which is what it does.

Except when you use (nothrow). This instructs the compiler, "if the memory can't be allocated, return NULL instead of throwing an exception". You don't want that. By throwing the exception, if there's a problem with copying anywhere in the tree, you can find out about it, instead of getting stuck with a partly-who-knows-how-much-copied tree.

3) Yes, you must use an if statement to check the pointers before you dereference them to make the recursive calls. That is what stops the recursion. :)

4) Because you are allocating more than once in the same place, you need to be careful. If copying the right subtree fails, you must deallocate the left subtree, since otherwise it will be leaked. To do this, we catch the exception, clean up (with 'delete', which will recursively call destructors) and re-throw. (If copying the left subtree fails, there is no problem, because objects that throw an exception in the constructor officially never existed.) This is part of what we call "exception safety".

5) Once you have a working, exception-safe copy constructor as described above, implementing a working, exception-safe assignment operator is trivial; see below.

// I'm assuming your node contains some kind of data, which I will assume is// represented by a single member named 'data'.BinaryNode::BinaryNode(const BinaryNode& argNode): data(data) {  if (argNode.leftNode) { leftNode = new BinaryNode(*argNode.leftNode); }  if (argNode.rightNode) {    try {      rightNode = new BinaryNode(*argNode.rightNode);    } catch (...) {      delete leftNode;      throw;    }  }}void BinaryNode::swap(const BinaryNode& other) {  std::swap(data, other.data);  std::swap(leftNode, other.leftNode);  std::swap(rightNode, other.rightNode);}BinaryNode& BinaryNode::operator=(BinaryNode copy_of_rhs) {  swap(copy_of_rhs);  return *this;}

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.