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.

Answer 3

In your example n1 and n2 would point to the same instances of the Node(s). If one of them goes out of scope and deletes the Node(s) the other one would point to the freed memory.

If you use raw pointers in Nodes and Transitions, you must also provide assignment operators and destructors in addition to copy constructors for Network and Node classes.

Use smart pointers instead. In your case, if the “copy the pointer to object” is a copy semantic, using shared_ptr would save you from writing copy constructor, etc., manually - the default implementation would do the job. If the copy semantic is "copy object itself":

• If performance is not an issue – store object in containers, use default copy c-tor etc

• If performance important – write your own copy c-tor etc for both classes (or consider using third part or writing your own copy_ptr/clone_ptr)