How to refer to recursive structs through pointers using vectors

Question

I have structs, let's call them sn, that look like:

struct sn {
    string name;
    vector<sn*> connected_to;
};

Now, suppose I have the connected_to vector already declared from 0 - 9; and I'm connecting sn A, to sn B:

A.connected_to[0] = &B; 

I have a feeling that I'm going about this the wrong way. Essentially what I'm trying to do is avoid copying the struct when I'm connecting the structs... i.e:

struct sn {
    string name;
    vector<sn> connected_to;
};

// ... 

A.connected_to[0] = B; 

Does this copy anything? The more fundamental problem is of course I don't understand how vectors, pointers, and referencing really works deeply.

Answer 1

Your second approach is probably illegal. However, in some implementations of the standard library it might work. In those cases, the objects you add would get copied (including all their children - when a standard container is copied, all the elements it contains are copied too). Thus, such a data-structure would only be suitable for representing a tree.

Your first approach, on the other hand, is fine, because a pointer to an incomplete type is itself a valid type (§3.9.2/3 - [basic.compound])^✝. Since you only store a pointer, the object will not get copied. You have to take care though when you start deleting this graph. Depending on what type of graph you are modeling, there are three scenarios when implementing them:

^{✝_{There are some restrictions. Note that in your case the type is only incomplete inside the definition (of sn) - at the point you actually use it, sn is complete, hence you can also delete it then.}}

Trees

In case of a tree, every child has exactly one parent. Thus, when deleting the structure, you would start from the the root, and each node would just have to delete all of its children. This would work recursively to the leaves, which have no children.

To implement this efficiently, you could store the children in a boost::ptr_vector<sn>. Thus, you will not have to write a destructor yourself - the ptr_vector will delete all its elements.

Directed Acyclic Graphs (DAG)

In a DAG a node can have multiple parents, thus you have to take care not to delete the same node twice (this would happen if each node just deletes all its children - for this reason, a ptr_vector will not work here). One way to handle this is to use reference-counting - each nodes counts how many other nodes point to it, and only when the reference-count reaches zero, the node is actually deleted. You can automate this by storing the nodes in a std::vector<std::shared_ptr<sn> > (or boost::shared_ptr if you use a pre-C++11 compiler). The shared_ptr manages the reference-counting internally, and will only delete the object it points to when there are no more shared_ptr-instances pointing to that object (when the reference-count is zero).

Cyclic Graphs

In a cyclic graph, a node can also be its own parent (either directly, if it contains loops, or indirectly, through a cycle). Thus, if each node deletes all its children, that would result in an infinite loop of destructor-calls. A shared_ptr could also fail here, because when you have a cycle of shared_ptr referencing each other, their reference-count will never reach zero. Now it is time to think about the difference between owning an object and referencing it. Each node should have exactly one parent that owns it, but can have several that reference it. The owner, and only the owner, is responsible for deleting that node. As explained in the excellent answer I linked above, this can be implemented using a combination of shared_ptr and weak_ptr.