Can standard container templates be instantiated with incomplete types?

Question

Sometimes it's useful to instantiate a standard container with an incomplete type to obtain a recursive structure:

struct multi_tree_node { // Does work in most implementations
    std::vector< multi_tree_node > child;
};

struct trie_node { // Does not work in most implementations
    std::map< char, trie_node > next;
};

This tends to work because containers don't have members of type value_type or member functions that pass or return any value_type objects by value. The Standard doesn't seem to say very much about incomplete template arguments, but there is one bit under C++11 §17.6.4.8 [lib.res.on.functions], "requirements on other functions":

In particular, the effects are undefined in the following cases: … if an incomplete type (3.9) is used as a template argument when instantiating a template component, unless specifically allowed for that component.

Does this make the above constructs illegal, even though the instantiations are not in block scope? Does this fall under "operations on types used to instantiate standard library template components" (also 17.6.4.8)? Or is a library implementation forbidden to incur template instantiations that might fail for incomplete types when all specifically required instantiations succeed?

Edit: Since only functions may call and instantiate other functions, restricting "operations on types…" to those in block scope would seem to hold the contents of member functions to a stricter requirement than the contents of signatures and member class definitions. After all, it certainly doesn't make sense to do anything with a multi_tree_node until the type is complete. And this extends to the std::unique_ptr which explicitly supports an incomplete type argument, even when used in block scope.

Edit 2: Serves me right for not bothering to test the trie_node example — and I've even tried it before. It's the same as the example of breakage in the article that @Ise linked. However, while the article seems to take for granted that "nothing like that could work," the solution seems simple to me — std::map's internal tree_node class should be a non-member template, not a member non-template class.

Anyway, that article establishes design intent pretty well, so I guess my nitpick about being under the subheading of "requirements on functions" is only just that.

Answer 1

Here's my attempt at an interpretation:

The standard simply says you mustn't do this, even though any given concrete implementation may have no problem supporting such a construction. But imagine for example if someone wanted to write a "small vector" optimization by which a vector always contains space for, say, five elements. Immediately you'd be in trouble because you'd have a self-referential type. This would be a problem even if the vector employed some sort of static branching depending on the size of the value type.

Therefore, in order to not preclude implementations from including such constructions, the standard simply says that you must only use complete types. In other words, the fact that most containers only contain references or pointers to the value type is an implementation detail rather than a standard requirement.

_{Just to clarify this: if you define your own class template, it is perfectly possible to design it in such a way that it explicitly supports incomplete types. An example from the standard is std::unique_ptr, which is perfectly happy with the incomplete type parameter T[] (or even void).}

Answer 2

Personally, I feel the wording instantiating in 17.6.4.8/2 is a little ambiguous, but according to this article, the standard's intent seems not to allow recursive data type using standard containers.

On a related note, VC2005 issues an error for class C { std::deque< C > x; };, while it compiles class C { std::vector< C > x; };...
However, in my understanding, this restriction is just for expanding the freedom of the implementation of standard containers. So as Kerrek SB mentioned, there can be containers which allow recursive data structure, and Boost.Container seems to provide this facility.