Pointers or Indexes?

Question

I have a network-like data structure, composed by nodes linked together. The nodes, whose number will change, will be stored in a std::vector<Node> in no particular order, where Node is an appropriate class.

I want to keep track of the links between nodes. Again, the number of these links will change, and I was thinking about using again a std::vector<Link>. The Link class has to contain the information about the two nodes it's connecting, as well as other link features.

Should Link contain

1. two pointers to the two nodes?
2. two integers, to be used as an indexes for the std::vector<Node>?
3. or should I adopt a different system (why?)

the first approach, although probably better, is problematic as the pointers will have to be regenerated every time I add or remove nodes from the network, but on the other hand that will free me from e.g. storing nodes in a random-access container.

Answer 1

This is difficult to answer in general. There are various performance and ease-of-use trade-offs.

Using pointers can provide a more convenient usage for some operations. For example

link.first->value

vs.

nodes[link.first].value

Using pointers may provide better or worse performance than indices. This depends on various factors. You would need to measure to determine which is better in your case.

Using indices can save space if you can guarantee that there are only a certain number of nodes. You can then use a smaller data type for the indices, whereas with pointers you always need to use the full pointer size no matter how many nodes you have. Using a smaller data type can have a performance benefit by allowing more links to fit within a single cache line.

Copying the network data structure will be easier with indices, since you don't have to recreate the link pointers.

Having pointers to elements of a std::vector can be error-prone, since the vector may move the elements to another place in memory after an insert.

Using indices will allow you to do bounds checking, which may make it easier to find some bugs.

Using indices makes serialization more straightforward.

All that being said, I often find indices to be the best choice overall. Many of the syntactical inconveniences of indices can be overcome by using convenience methods, and you can switch the indices to pointers during certain operations where pointers have better performance.