Implementing a Graph / Tree with Incomplete Types

Question

The problem has been discussed many times. What to do if necessary:

struct Node { ::std::vector<Node> nodes_; }; 

From here it seems that (smart) pointers to Node* can be a canonical solution. This implies some additional indirection and a corresponding performance hit. From here we see that libstdc++ supports ::std::vector<T> instances where T is an incomplete type but not libc++ . This is hardly tolerated. But one solution could be the portable container ::std::vector , which supports incomplete types. Finally, we can do:

 template <::std::size_t I = 0> struct Node { ::std::vector<Node<I + 1> > nodes_; }; template <> struct Node<20> { }; 

Which imposes restrictions on our graph / tree. Are there additional workarounds due to the fact that a Node contains Node s, but is an incomplete type at the declaration point ::std::vector<Node> nodes_; ?

Answer 1

Boost containers handle partial types and are portable.

Thus, your Node can become:

 #include <boost/container/vector.hpp> struct Node { boost::container::vector<Node> nodes_; };