How implement node references in a node class

Question

I am trying to write a little quadedge class in c++ (think of it as a some kind of graph). Every node should keep track of his neighbours. I have to keep track only of the outgoing arcs.

The first idea is to use pointers to do that:

struct Node {
         //....
         Node * n1,n2,... nk;
};

However, this approach is particullary painful when you have to implement a copy constructor^* (first copy all the nodes, then map every pointer to the old nodes to the relative pointer to the new nodes).

I think that using integer indices instead of pointers would be a better idea in this case.

 struct Node {
        //....
        int n1,n2,...nk;
 };

Is this approach common and correct? If it is, which is the proper container to map indices to nodes?

std::vector<Node> is probably the most efficient way, I can just use the index in the vector to refer to a Node, but unfortunatly it would be quite complicated to remove a node from the graph (would need to rebase every reference in the graph).

Using std::unordered_map<int,Node> would be a little better, but it will still need to keep track of the free names (if i insert the nodes 1,2,3 then remove 2, I need to keep track of the fact that the name 2 is available).

What I need is quite similar to the implementation of the heap. Think to a pool allocator which uses offset from its base as pointers type.

Is there any popular container like this (in Boost or in any other popular library)?

_{*Its usefulness is not limited to copy constructor, think about serialization for example}

Answer 1

Using int indexes into the container permanently is fragile, because you cannot delete or insert items in the middle of the container without reshuffling all your indexes. Using indexes temporarily during a copy or a serialization operation is a lot better: use pointers as you describe in your first approach for operations that do not rely on node identity, and create a temporary identity of a node (say, its index) only for the duration of the operation where it is required.

For example, before you start a copying operation in the copy constructor, create a vector<Node*>, and an unordered_map<Node*,int>. Perform copying in two passes: first, add a copy of the node without the references to the vector, and an address of the old node to the map. Then go through your nodes again, and resolve references by looking up the address of the new node in the vector using its index from the unordered map.