STL Set of pointers. Copy constructor issue

Question

I am developing a project in C++ under Ubuntu 11.10 using the latest version of NetBeans. I'll only post minimal parts of the code relevant to the problem. Let's say I have the following code for a graph kind of problem:

typedef map<Node*, double, DereferenceCompare> Transitions;

class Node {
    int _nodeNumber;
    Transitions _transitions;
}

Each Node object holds a map of pointers to other Node objects. Now we have:

typedef set<Node*, DereferenceCompare> Nodes;

class Network {
    Nodes _network;
}

The problem: I am at a loss about writing a copy constructor for the class Network. What I am trying to achieve is to be able to do the following:

Network n1;
Network n2(n1);
//Have both n1 and n2 identical in structure but distinct in memory (deep copy).

Am I right in the following assumption: if I write a copy constructor for the Node class it would need to also copy the Transitions container. The Transitions container at that moment would hold pointers to the old nodes as the new ones do not exist yet.

This is my first post here. I hope I provided clear and sufficient information. I can further clarify if I was not coherent enough with my problem. Any help would be greatly appreciated.

Answer 1

I've done this exact same thing before. It's tricky:

Network::Network(const Network& b) {
    //old to new mapping
    std::unordered_map<Node*, Node*> mapper(b._network.size()); 
    // duplicate all nodes without links
    for(auto iter = b.begin(); iter != b.end(); ++iter) {
        Node* new_node = new Node();
        try {
            _network.insert(new_node);
        } catch (std::bad_alloc& e) {
            delete new_node;
            throw;
        }
        mapper[iter->first] = _network; //and map the old Nodes to new ones
        new_node->_nodeNumber = iter->_node_number;
    }
    // THEN map the links
    for(auto iter = b.begin(); iter != b.end(); ++iter) {
        Node* new_node = mapper[iter->first];
        //for each link in the old one
        for(auto iter2 = iter->_transitions.begin(); 
                 iter2 != iter->_transitions.end();
                 ++iter2)
        {
            //link to the corresponding new node
            Node* connection = mapper[iter2->first];
            new_node->_transitions[connection ] = iter2->second;
        }
    }
}

[EDIT] Now exception safe
Also note I haven't attempted to validate the code in any way other than to compile. I just remember this is what I did years ago when I ran into the same problem.

Answer 2

Given that you are using raw pointers for your key element, you can't use the default copy constructor but it is pretty simple to do yourself if your Node structure is a tree structure (ie. no cycles to worry about)

Network(const Network& other)
{
    if (this != &other)
    {
        for (auto it = other._network.begin(); it != other._network.end(); ++it)
        {
            _network.insert(new Node(*it));
        }
    }
}

Node(const Node& other)
{
    if (this != &other)
    {
        _nodeNumber = other._nodeNumber;
        for (auto it = other._transitions.begin(); it != other._transitions.end(); ++it)
        {
            _transitions[new Node(*it->first)] = it->second;
        }
    }
}

A much easier solution would be to store Node elements themselves so that the containers can manage the memory automatically, or use a smart pointer that represents the semantics you want.

If you are allowing cycles in the Node structure, that is really beyond the realm of copy constructors. You will want to write a seperate "copy" function that begins at some point and scans the entire structure, reproducing it along the way.