Recursive copy constructor?

I'm attempt开发者_高级运维ing to write a copy constructor that takes a node of a quad tree, and copies that node, along with all its children, and its children, and so on. Here's what I have:

 Node(const Node & n) {

    nChild=new Node(*(n.nwChild));
    neChild=new Node(*(n.nChild));
    eChild=new Node(*(n.seChild));
    wChild=new Node(*(n.sChild));   
}

I feel like the last 4 lines are a little funky. Does what I'm doing make sense?

Your constructor isn't exception-safe - suppose the second new throws bad_alloc, then how is the first one going to be cleaned up?

You could probably make your own life easier by changing the Child fields to your favourite smart pointer. If you don't have a favourite smart pointer, introduce yourself to some ;-)

[Edit: just noticed that you didn't provide the data member definitions, I just assumed they were raw pointers. Apologies if they're already smart pointers.]

The early-out looks a bit weird - how come if all four children on the rhs are NULL, then the x/y/height/width aren't copied? Normally those members would be handled by an initialization list. And should you do something special if any of the children is NULL, rather than all of them? Currently you don't handle nodes with children in one direction but not all 4. If it's a property of your tree that every node has either 4 children or none, then you don't need to check all 4, but you do need to initialize the various fields when you copy a leaf node. If it's possible for a node to have exactly 1 child, then you don't copy that node correctly.

Other than that, the basic logic seems OK to me, in the sense that provided nothing goes wrong, it will recursively copy.

Makes sense to me. This is a recursive deep copy, should work fine. But don't forget to free all this memory in the destructor. And beware of temporary copies of Quadtree when coding, they may be brutal if the tree is large.

The only real issue with this code is that it's miles away from being exception safe. For one, it should be written using an initializer list, this way:

Quadtree::QuadtreeNode::QuadtreeNode(const QuadtreeNode & n) 
 : x(n.x), y(n.y), height(n.height), width(n.width),
   nwChild(new QuadtreeNode(*(n.nwChild)), // ...

The constructor body can remain empty unless you want to do more than initialize the members. After doing this, you might want to consider swapping bare pointers for some kind of smart pointer. This will be a good foundation towards making the class exception-safe.

In addition to the good answers here (I upvoted Jon's), I'd like to introduce a cool new way to gain the exception safety in C++0x. Your compiler probably doesn't implement it yet. But I have high hopes a year from now that will not be the case.

I'm starting with Jon's copy constructor:

Quadtree::QuadtreeNode::QuadtreeNode(const QuadtreeNode & n) 
 : x(n.x), y(n.y), height(n.height), width(n.width),
   nwChild(new QuadtreeNode(*(n.nwChild)), // ...

And now assume you have a default constructor as you described in one of your comments:

Quadtree::QuadtreeNode::QuadtreeNode() 
 : x(0), y(0), height(0), width(0),
   nwChild(nullptr), // ...

Now you can transform Jon's copy constructor into an exception safe one by calling the default constructor first! :-) And it ironically comes out looking much like your original code:

Quadtree::QuadtreeNode::QuadtreeNode(const QuadtreeNode & n)
     : QuadtreeNode()
{
    if(!(n.nwChild==NULL && n.neChild==NULL && n.seChild==NULL && n.swChild==NULL))
    {
        x=n.x;
        y=n.y;
        height=n.height;
        width=n.width;
        nwChild=new QuadtreeNode(*(n.nwChild));
        neChild=new QuadtreeNode(*(n.neChild));
        seChild=new QuadtreeNode(*(n.seChild));
        swChild=new QuadtreeNode(*(n.swChild)); 
    }
}

Explanation: This is called delegating constructors. And is a new feature of C++0x. You can literally call one constructor from another. And when any constructor completes, the object is considered constructed. From that point on, any exception that gets thrown, will activate the destructor to clean up. So the default constructor is often a convenient way to construct the object in a noexcept manner. Then you can build up your object in a natural way knowing that the destructor will be called if an exception is thrown.

How are the nodes assigned? I see a problem where if this case

 1   3
   5 
 7   9

if I am trying to copy 5, and 1 has a se pointer to 5, it would remake 5, which in turn remakes 1 and so on.

First, I'm having some difficulty understanding the reponses, because they refer to a conditional test which I don't see in your original code. However...

IIUC, you want to do a deep copy. There are two issues which have to be considered: what to do if one (or more) of the pointers is null, and how to make the code exception safe. The most obvious solution to both of these is to use a smart pointer for each of the pointers, which does the deep copy and makes all the necessary checks. Designing a good generic copy_ptr isn't trivial, since it should handle polymorphic pointers as well. But for any one case, or given convention, it's pretty simple; if Node isn't polymorphic, then the copy ctor for shared_ptr can be as simple as:

copy_ptr( T const& other )
    : m_ptr( other.m_ptr == NULL ? NULL : new T( *other.m_ptr ) )
{
}
~copy_ptr()
{
    delete m_ptr;
}

(Use the swap idiom for asignment, and provide the other usual smart pointer functions.)

Do this, and you can put the initializers directly in the initialization list:

Node( Node const& other )
    : nChild( other.nChild )
    , neChild( other.neChild )
    //  ...

(Without the smart pointers, or at least a separate class type encapsulating each pointer, you'll have to initialize the pointers to null in the initialization list, then assign the newed pointers to them in a try-catch block in order to delete the already newed objects in case of an exception.)