Copy constructor question Lippman

I was trying to solve a copy ctro qs given in lipman n not sure If i got it right. Since the class has pointers to itself it confused me a bit. Here is the code

#include <iostream>
#include <string>

using namespace std;

class BinStrTreeNode{

      public:
  开发者_Python百科       BinStrTreeNode(const string& val):_val(val){ 
              _leftchild = new BinStrTreeNode("nup");
              _rightchild = new BinStrTreeNode("rup");
              cout << "ctor" << endl;
         };
         BinStrTreeNode(const BinStrTreeNode&);
     private:
         string _val;
         BinStrTreeNode *_leftchild;
         BinStrTreeNode *_rightchild;
};

BinStrTreeNode::BinStrTreeNode(const BinStrTreeNode& rhs):_val(rhs._val){
    cout << "copy ctor" << endl;
    _leftchild = new BinStrTreeNode(*(rhs._leftchild));
    _rightchild = new BinStrTreeNode(*(rhs._rightchild));
}

And it gives segementation fault. I know i need to define a dtor too but first I need to get this right. How should i define a copy ctor, assignment operator for a class like this?

Thanks

you got it basically correct.
You just forgot to check for NULL pointers.

BinStrTreeNode::BinStrTreeNode(const BinStrTreeNode& rhs)
    :_val(rhs._val)
    ,_leftchild(NULL)
    ,_rightchild(NULL)
{
    cout << "copy ctor" << endl;
    if (rhs._leftchild  != NULL) {_leftchild  = new BinStrTreeNode(*(rhs._leftchild));}
    if (rhs._rightchild != NULL) {_rightchild = new BinStrTreeNode(*(rhs._rightchild));}
}

Note trees will not point to a node higher (or self) in the tree (as that would no longer be a tree it would be a graph). If your code is a graph then you need to re-write this so that you do a graph copy which is a lot more complex as you need to track which nodes have been copied in a map.

Though personally I would take it a step further and do everything in the initializer list:
Though I would just say that this is a personal preference.

BinStrTreeNode::BinStrTreeNode(const BinStrTreeNode& rhs)
    :_val(rhs._val)
    ,_leftchild ((rhs._leftchild  == NULL)?NULL:new BinStrTreeNode(*(rhs._leftchild)))
    ,_rightchild((rhs._rightchild == NULL)?NULL:new BinStrTreeNode(*(rhs._rightchild)))
{
    cout << "copy ctor" << endl;
}

Cycle trees (AKA Graphs)

Lets start from scratch here:
In this situation we need to track each node we create. Then when a pointer points back a node that has already been copied we use the copied node rather than creating a new one (otherwise we end up in a recursive nightmare following the loop round and around and around).

typedef std::map<BinStrTreeNode*,BinStrTreeNode*>   CopyMap;
BinStrTreeNode::BinStrTreeNode(const BinStrTreeNode& rhs)
    :_val(rhs._val)
{
    CopyMap    copyMap;
    copyMap[&rhs] = this;

    left  = copyGraph(left,copyMap);
    right = copyGraph(right,copyMap) 
}

private:
BinStrTreeNode* BinStrTreeNode::copyGraph(BinStrTreeNode* node,CopyMap& copyMap)
{
    if (node == NULL)
    {    return NULL;
    }

    if (copyMap[node] != NULL)
    {    return copyMap[ndoe];
    }

    return new BinStrTreeNode(*node, copyMap);
}
BinStrTreeNode::BinStrTreeNode(const BinStrTreeNode& rhs, CopyMap& copyMap)
    :_val(rhs._val)
{
    copyMap[&rhs] = this;
    left  = copyGraph(left,copyMap);
    right = copyGraph(right,copyMap) 
}

Your copy constructor is recursive. You might have exhausted memory or had new throw an out of memory exception or, most likely, dereferenced a null pointer in one of the copy constructor invocations.

Your main problem is that both the constructors infinitely recurse:

• Your constructor will recurse until you get a stack overflow, or until new throws a std::bad_alloc.
• Your copy constructor will recurse until you get a stack overflow, or until it encounters an invalid leftchild or right child, when it will segfault.

Your underlying problem is that your recursive functions don't have a terminating condition. All functions, including constructors, need a code path that doesn't recurse.