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

Boost.Variant has a handy utility explicitly for this purpose – boost::recusive_wrapper<>. The following should work:

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

The only notable drawback is that Boost.Variant has not yet been updated to support C++11 move semantics. Update: added in Boost 1.56.

Answer 2

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 3

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.

Answer 4

I think you can just forward declare struct A; prior to its definition and the compiler should be happy.

EDIT: So after being downvoted several times, I wrote the following to see what I was missing:

#include <boost/unordered_map.hpp>                                                                                      
#include <string>
#include <iostream>

struct A;

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

int main(void)
{
    A b;
    b.whatever = 2.5;
    b.mapToMoreA["abc"] = b;
    std::cerr << b.mapToMoreA["abc"].whatever << std::endl;
    return 0;
}

This compiles fine using g++ 4.2.1 on my mac, and prints out "2.5" when it's run (as expected).

Sorry that I don't have unordered_map without boost. Is that the issue? (i.e., does std::unordered_map somehow place more constraints on the compiler than boost does?) Otherwise, I'm not sure what I'm missing here about the question. Those downvoting this, please enlighten me with comments. Thanks!

Answer 5

Or use a pointer to the map. The pointer must be of type void* in this case (can be hidden behind a set of functions). Maybe there are alternatives to std::unordered_map that can cope with incomplete value types.

Answer 6

In C++ you usually use pointers, which have predefined constant size, for incomplete types:

This of course changes how you use the map: you'll have to dereference with the * or -> operators to access members and have to delete the pointers at some point.

struct A
{
    double bla;
    std::map<std::string, A*> mapToMoreA;
};

Member functions of A should be split into a prototype inside the struct block and implemented later, otherwise A and its members are not yet completely defined:

struct A
{
    double bla;
    std::map<std::string, A*> mapToMoreA;
    void doStuff(const std::string& str);
};

void A::doStuff(const std::string& str)
{
    mapToMoreA[str] = new A();
}

Answer 7

If having the map hold pointers isn't acceptable, perhaps this will work for you:

struct A {
  struct hidden;
  std::unique_ptr<hidden> pimpl;
};

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