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 astd::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.
精彩评论