How to have an unordered_map where the value type is the class it's in?

Question

This code:

class Foo {
    std::unordered_map<std::string, Foo> x;
};

gives me an error:

/usr/include/c++/4.7/bits/stl_pair.h:94:11:
  error: 'std::pair<_T1, _T2>::second' has incomplete type
foo.cpp:4:7: error: forward declaration of 'class Foo'

However, this code compiles just fine:

class Foo {
    std::vector<Foo> x;
};

Is this a library/compiler bug?

Answer 1

The C++ standard specifies for the various smart pointers that the template parameter is allowed to be an incomplete type.

The 2017 and later versions of the standard allow a container's value_type to be an incomplete type when instantiating the class template only for the container templates std::forward_list, std::list, and std::vector, and only if the allocator type satisfies the "allocator completeness requirements". The default allocator template std::allocator always satisfies the allocator completeness requirements. Instantiating any member of the container class template still requires the value_type to be complete.

For any other standard container type, this information is not given. In cases where it is unspecified, an implementation is allowed to accept an incomplete type for one container class template and not another, and still be conformant.

To make your code portable, avoid making containers of any type before the type is completed, except in the cases specifically permitted by the standard.

Formally, the general constraint is found in the following rule ([res.on.functions]) which applies to your code:

In certain cases (replacement functions, handler functions, operations on types used to instantiate standard library template components), the C++ standard library depends on components supplied by a C++ program. If these components do not meet their requirements, the Standard places no requirements on the implementation.

In particular, the effects are undefined in the following cases:

...

• if an incomplete type is used as a template argument when instantiating a template component, unless specifically allowed for that component.

The three statements specifically allowing an incomplete template argument for forward_list, list, and vector are found in sections [forwardlist.overview], [list.overview], and [vector.overview].