Recursive containers in C ++?

Question

Possible duplicate:
Are C ++ recursive type definitions possible? In particular, can the vector <T> be placed in the definition of T?

I recently looked at the code and noticed a data structure similar to the following:

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

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

How can such containers be implemented? Is this behavior a guaranteed standard? If this is not guaranteed by the standard, what alternatives do I need for this design?

Answer 1

This is great because the std::vector<T> class does not contain specific instances of type T in it: it is usually implemented using pointers. Creating an instance of the std::vector<TreeNode> does not require a full TreeNode definition.

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

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

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

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