Copy constructor and dynamic allocation

Question

I would like to ask you how to write a copy constructor (and operator = ) for the following classes.

Class Node stores coordinates x,y of each node and pointer to another node.

class Node
{
private:
double x, y;
Node *n;

public:
Node (double xx, double yy, Node *nn) : x(xx), y(yy), n(nn) {}
void setNode (Node *nn) : n(nn) {} 
...
};

Class NodesList (inherited from std:: vector) stores all dynamically allocated Nodes

class NodesList : public std::vector<Node *>
{}

The main program:

int main()
{
Node *n1 = new Node(5,10,NULL);
Node *n2 = new Node(10,10,NULL);
Node *n3 = new Node(20,10,NULL);
n1->setNode(n2);
n2->setNode(n3);
n3->setNode(n2);
NodesList nl1;
nl1.push_back(n1);
nl1.push_back(n2);
nl1.push_back(n3);
//Copy contructor is used, how to write
NodesList nl2(nl1);
//OPerator = is used, how to write?
NodesList nl3 = nl1;

}

I do not want to create a shallow copy of each node but a deep copy of each node. Could I ask you for a sample code with copy constructor?

Each node can be pointed more than once. Let us have such situation, when 3 nodes n[1], n[2], n[3] are stored in the NodesList nl1:

n[1] points to n[2]

n[2] points to n[3]

n[3] points to n[2]

A] Our copy constructor process the node n[1]. It creates a new object n[1]_new represented by the copy of the old object n[1]_old. The node n[2] pointed from n[1]_old still does not exist, so n[2]_new must be also created... The pointer from n1_new to n2_new is set.

B] Then second point n[2] is processed. It can not be created twice, n[2]_new was created in A]. But pointed node n[3] does not exist, so the new object n[3]_new as a copy of an old object n[3]_old is created. The pointer from n2_new to n3_new is set.

C] Node n[3]_new has already been created and n[2]_new. The pointer from n3_new to n2_new is set and no other object will be created...

So the copy constructor should check whether the object has been created in the past or has not...

Some reference counting could be helpful...

Answer 1

You should not inherit from standard library containers (because they lack virtual destructors). Instead, include them as member variables in your classes.

Since you want a deep copy, you need these: (rule of three)

Node(Node const& orig): x(orig.x), y(orig.y), n() {
    if (orig.n) n = new Node(*orig.n);
}
Node& operator=(Node const& orig) {
    // The copy-swap idiom
    Node tmp = orig;
    swap(tmp); // Implementing this member function left as an exercise
    return *this;
}
~Node() { delete n; }

A better idea might be to avoid using pointers entirely and just put your nodes in a suitable container.

Answer 2

Perform a shallow copy in NodeList::NodeList(const NodeList&) and you don't have to worry about cycles breaking the copy operation. Disclaimer: the following is untested, incomplete and may have bugs.

class NodeList {
private:
    typedef std::vector<Node*> Delegate;
    Delegate nodes;

public:
    NodeList(int capacity=16) : nodes() { nodes.reserve(capacity); }

    NodeList(const NodeList& from);
    virtual ~NodeList();

    NodeList& operator=(const NodeList& from);

    /* delegated stuff */
    typedef Delegate::size_type size_type;
    typedef Delegate::reference reference;
    typedef Delegate::const_reference const_reference;
    typedef Delegate::iterator iterator;
    typedef Delegate::const_iterator const_iterator;

    size_type size() const { return nodes.size(); }

    iterator begin() { return nodes.begin(); }
    const_iterator begin() const { return nodes.begin(); }
    iterator end() { return nodes.end(); }
    const_iterator end() const { return nodes.end(); }
    // ...
};

NodeList::NodeList(const NodeList& from)
    : nodes(from.size()), flags(NodeList::owner)
{
    std::map<Node*, Node*> replacement;
    Delegate::const_iterator pfrom;
    Delegate::iterator pto;
    // shallow copy nodes
    for (pfrom=from.begin(), pto=nodes.begin(); 
         pfrom != from.end(); 
         ++pfrom, ++pto) 
    {
        replacement[*pfrom] = *pto = new Node(**pfrom);
    }
    // then fix nodes' nodes
    for (pto = nodes.begin(); pto != nodes.end(); ++pto) {
        (*pto)->setNode(replacement[(*pto)->getNode()]);
    }
}

NodeList::operator=(const NodeList&) can use the copy-swap idiom, the same as Tronic's Node::operator=(const Node&).

This design has a potential memory leak in that a copied NodeList is (initally) the only place that references its nodes. If a temporary NodeList goes out of scope, a poor implementation will leak the Nodes the list contained.

One solution is to proclaim that NodeLists own Nodes. As long as you don't add a Node to more than one NodeList (via NodeList::push_back, NodeList::operator[] &c), NodeList's methods can delete nodes when necessary (e.g. in NodeList::~NodeList, NodeList::pop_back).

NodeList::~NodeList() {
    Delegate::iterator pnode;
    for (pnode = nodes.begin(); pnode != nodes.end(); ++pnode) {
        delete *pnode;
    }
}

void NodeList::pop_back() {
    delete nodes.back();
    nodes.pop_back();
}

Another solution is to use smart pointers, rather than Node*. NodeList should store shared pointers. Node::n should be a weak pointer to prevent ownership cycles.

Answer 3

Apparently each Node is only allowed to point to another Node in the same list? Otherwise the "deep copy" of a list needs more definition. Should it not be connected to the original NodeList? Should it not be connected to any original Node? Are copies of Nodes not in the list being copied added to some other list or free-floating?

If all the Node-to-Node pointers are constrained within the NodeList, then perhaps you should store indexes instead of pointers, then no special handling is required.

Answer 4

There is my solution of the problem. A new data member n_ref storing a new verion of the node n was added:

class Node
{
private:
double x, y;
Node *n, *n_ref;

public:
Node (double xx, double yy, Node *nn) : x(xx), y(yy), n(nn) {n_ref = NULL;}
Node * getNode() {return n;}
Node * getRefNode () {return n_ref;}
void setNode (Node *nn) {this->n = nn;} 
void setRefNode (Node *nn) {this->n_ref = nn;}

The copy constructor creates a shallow copy of the node:

Node (const Node *node) 
{
    x = node->x;
    y = node->y;
    n = node->n;
    n_ref = node->n_ref;
}

The copy constructor for NodesList

    NodesList::NodesList(const NodesList& source)
    {
        const_iterator e = source.end();
        for (const_iterator i = source.begin(); i != e; ++i) {

            //Node* n = new Node(**i);

            //Node n still has not been added to the list
            if ((*i)->getRefNode() == NULL)
            {
                //Create node
                Node *node = new Node(*i);

                //Add node to the list
                push_back(node);

                //Set this note as processed
                (*i)->setRefNode(node);

                //Pointed node still has not been added to the list
                if ((*i)->getNode()->getRefNode() == NULL)
                {
                    //Create new pointed node
                    Node *node_pointed = new Node ((*i)->getNode());

                    //Add node to the list
                    push_back(node_pointed);

                    //Set pointer to n
                    node->setNode(node_pointed);

                    //Set node as processed
                    ((*i)->getNode())->setRefNode(node_pointed);
                }

                //Pointed node has already been added to the list
                else
                {
                    //Set pointer to node n
                    node->setNode((*i)->getRefNode());
                }
            }

            //Node n has already been added to the list
            else
            {
                //Get node
                Node * node = (*i)->getRefNode();

                //Pointed node still has not been added
                if ((*i)->getNode()->getRefNode() == NULL)
                {
                    //Create new node
                    Node *node_pointed = new Node ((*i)->getNode());

                    //Add node to the list
                    push_back(node_pointed);

                    //Set pointer to n
                    node->setNode(node_pointed);

                    //Set node as processed
                    ((*i)->getNode())->setRefNode(node_pointed);
                }

                //Pointed node has already been added to the list
                else
                {
                    //Set pointer to n
                    node->setNode((*i)->getNode()->getRefNode());
                }
            }
        }
    }