Using a class as template parameter in its own decleration

Question

(I know it is not a conventional implementation, but I wanted to try the idea.)

struct TrieNode {
    std::unordered_map<char, TrieNode> next;
};

This class is very well compiled and worked as expected under visual studio 2017. However, it does not compile with gcc (c++14) (as I'd expect).

In file included from /usr/include/c++/8/bits/stl_algobase.h:64,
                 from /usr/include/c++/8/bits/char_traits.h:39,
                 from /usr/include/c++/8/ios:40,
                 from /usr/include/c++/8/ostream:38,
                 from /usr/include/c++/8/iostream:39,
                 from prog.cpp:1:
    /usr/include/c++/8/bits/stl_pair.h: In instantiation of ‘struct std::pair<const char, TrieNode>’:
    /usr/include/c++/8/bits/stl_vector.h:1610:27:   required from ‘struct __gnu_cxx::__aligned_buffer<std::pair<const char, TrieNode> >’
    /usr/include/c++/8/bits/hashtable_policy.h:234:43:   required from ‘struct std::__detail::_Hash_node_value_base<std::pair<const char, TrieNode> >’
    /usr/include/c++/8/bits/hashtable_policy.h:280:12:   required from ‘struct std::__detail::_Hash_node<std::pair<const char, TrieNode>, false>’
    /usr/include/c++/8/bits/hashtable_policy.h:2027:49:   required from ‘struct std::__detail::_Hashtable_alloc<std::allocator<std::__detail::_Hash_node<std::pair<const char, TrieNode>, false> > >’
    /usr/include/c++/8/bits/hashtable.h:173:11:   required from ‘class std::_Hashtable<char, std::pair<const char, TrieNode>, std::allocator<std::pair<const char, TrieNode> >, std::__detail::_Select1st, std::equal_to<char>, std::hash<char>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >’
    /usr/include/c++/8/bits/unordered_map.h:105:18:   required from ‘class std::unordered_map<char, TrieNode>’
    prog.cpp:9:37:   required from here
    /usr/include/c++/8/bits/stl_pair.h:215:11: error: ‘std::pair<_T1, _T2>::second’ has incomplete type
           _T2 second;                /// @c second is a copy of the second object
               ^~~~~~
    prog.cpp:7:8: note: forward declaration of ‘struct TrieNode’
     struct TrieNode {
            ^~~~~~~~ 

I wonder how visual c++ implementation did not have any problem with that? What do standards say for such cases ?

Answer 1

I can't tell you why it worked in MSVS2017 but per the standard it is undefined behavior to use an incomplete type with std::unordered_map. The complete-class context of a class is defined by [class.mem]/6 as

A complete-class context of a class is a

• function body ([dcl.fct.def.general]),

• default argument,

• noexcept-specifier ([except.spec]), or

• default member initializer

It is only in those places that the class name denotes a complete type. Since we are not in any of those places the name names an incomplete type. If we check whether or not we can use that with std::unordered_map we check [res.on.functions]/2 and we have

In particular, the effects are undefined in the following cases: [...]

• If an incomplete type ([basic.types]) is used as a template argument when instantiating a template component or evaluating a concept, unless specifically allowed for that component.

So in general this is not allowed. We need to check [container.requirements] and [unord.map] but nothing in there says an incomplete type is allowed. That means we fall back to the general rule and it is not allowed.