C++ Struct that contains a map of itself

Question

Simple question: How do I get this to work?

struct A {
    double whatever; 
    std::unordered_map<std::string, A> mapToMoreA; 
}

g++ error: std::pair<_T1, _T2>::second has incomplete type

As far as I understand, when instantiating the map, the compiler needs to know the size of A, but it doesn't know this because the map is declared in A's declaration, so is the only way to get around this to use pointers to A (don't feel like doing that)?

Answer 1

Most of the time it will depend on the container implementation details (more precisely, on what gets instantiated at the point of container declaration and what doesn't). Apparently, std::unordered_map implementation requires the types to be complete. At the same time GCC's implementation of std::map compiles perfectly fine with incomplete type.

To illustrate the source of such difference, consider the following example. Let's say we decided to make our own naive implementation of std::vector-like functionality and declared our vector class as follows

template <typename T> class my_vector {
  T *begin;
  T *end;
  ...
};

As long as our class definition contains only pointers to T, the type T is not required to be complete for the class definition itself. We can instantiate my_vector itself for an incomplete T without any problems

class X;
my_vector<X> v; // OK

The "completeness" of the type would be required later, when we begin to use (and therefore instantiate) the individual methods of my_vector.

However, if for some reason we decide to include a direct instance of T into our vector class, things will chahge

template <typename T>
class my_vector {
  T *begin;
  T *end;
  T dummy_element;
  ...
};

Now the completeness of T will be required very early, at the point of instantiation of my_vector itself

class X;
my_vector<X> v; // ERROR, incomplete type

Something like that must be happening in your case. The definition of unordered_map you are dealing with somehow contains a direct instance of A. Which is the reason why it is impossible to instantiate (obviously, you would end up with infinitely recursive type in that case).

A better thought through implementation of unordered_map would make sure not to include A into itself as a direct member. Such implementation would not require A to be complete. As you noted yourself, Boost's implementation of unordered_map is designed better in this regard.

Answer 2

I don't know of any STL containers other than smart pointers that work with incomplete types. You can use a wrapper struct however if you don't want to use pointers:

struct A {
    struct B { double whatever; }; 
    std::unordered_map<std::string, B> mapToB; 
};

Edit: Here is a pointer alternative if the above doesn't meet your use case.

struct A {
    double whatever;
    std::unordered_map<std::string, std::unique_ptr<A>> mapToMoreA; 
};

You can also just use boost::unordered_map which not only supports incomplete types but also has far greater debug performance in Visual Studio as Microsoft's implementation of std::unordered_map is incredibly inefficient due to excessive iterator debugging checks. I am unaware of any performance concerns on gcc for either container.