Recursive containers in C++? [duplicate]

Question

Possible Duplicate:
Are C++ recursive type definitions possible, in particular can I put a vector<T> within the definition of T ?

I was looking through some code recently and noticed a data structure similar to the following:

class TreeNode {
    std::vector<TreeNode> subNodes;
};

As you can see, the container is instantiated with TreeNode before TreeNode has been defined. The code compiles under both GCC and MSVC, but I remember seeing something saying that this is not guaranteed behaviour. Unfortunately I can't find anything in the standard discussing this at all.

How are such containers able to be implemented? Is this behaviour guaranteed by the standard? If this is not guaranteed by the standard, what alternatives do I have to this design?

Answer 1

This is fine because the std::vector<T> class doesn't contain any concrete instances of the type T in it: it's typically implemented using pointers. The template instantiation std::vector<TreeNode> does not require the full definition of TreeNode.

std::vector<T> is usually implemented as a triplet of pointers (though this is not required by the standard):

template <typename T>
class vector
{
  ...
  T* start;
  T* end;
  T* end_of_storage;
};

If std::vector<T> did contain concrete instances of T in it, then you would have a problem. The following is not legal C++, because it creates a circular "has a" definition:

template <typename T>
class container
{
  T x;
};

class TreeNode
{
  container<TreeNode> subNodes;
};