title: Can standard container templates be instantiated with incomplete types?
body: <p>Sometimes it's useful to instantiate a standard container with an incomplete type to obtain a recursive structure:</p>
  
  <pre><code>struct multi_tree_node { // Does work in most implementations
      std::vector&lt; multi_tree_node &gt; child;
  };
  
  struct trie_node { // Does not work in most implementations
      std::map&lt; char, trie_node &gt; next;
  };
  </code></pre>
  
  <p>This tends to work because containers don't have members of type <code>value_type</code> or member functions that pass or return any <code>value_type</code> 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":</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>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?</p>
  
  <p><strong>Edit:</strong> 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 <em>do anything</em> with a <code>multi_tree_node</code> until the type is complete. And this extends to the <code>std::unique_ptr</code> which explicitly supports an incomplete type argument, <em>even when used in block scope</em>.</p>
  
  <p><strong>Edit 2:</strong> Serves me right for not bothering to test the <code>trie_node</code> example — and I've even tried it before. It's the same as the example of breakage in <a href="http://drdobbs.com/184403814" rel="noreferrer">the article</a> that @Ise linked. However, while the article seems to take for granted that "nothing like that could work," the solution seems simple to me — <code>std::map</code>'s internal <code>tree_node</code> class should be a non-member template, not a member non-template class.</p>
  
  <p>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.</p>