Practically safe to assume sizeof(std::unordered_map<std::string, T>) is the same for all T?

Question

I'm in a situation where I have a circular dependency loop between the definitions of two classes, where (as far as I can tell) both classes need the other type to be a complete type in order to define them properly.

In simplified terms, what I need simplified version of what is going on:

struct Map;

struct Node {
    // some interface...
private:
    // this cannot be done because Map is an incomplete type
    char buffer[sizeof(Map)];
    // plus other stuff...
    void* dummy;
};

struct Map {
    // some interface...
private:
    // this is Map's only member
    std::unordered_map<std::string, Node> map_;
};

The situation is actually more complicated than the above, since Node is actually going to be a variant type (similar to boost::variant) that uses placement new to explicitly construct one of multiple types of objects in an preallocated (and with proper alignment, which I'm ignoring in this simplification) buffer: the buffer is therefore not exactly sizeof(Map) but rather some calculated constant that is dependent on sizeof(Map).

The problem, obviously, is that sizeof(Map) is not available when Map is only forward declared. Furthermore, if I change the order of the declarations to forward declare Node first, then compilation of Map fails, as std::unordered_map<std::string, Node> cannot be instantiated when Node is an incomplete type, at least with my GCC 4.8.2 on Ubuntu. (I know it depends on the libstdc++ version more than the GCC version, but I don't know easily how to find that...)

As an alternative, I'm considering the following workaround:

struct Node {
    // some interface...
private:
    // doing this instead of depending on sizeof(Map)
    char buffer[sizeof(std::unordered_map<std::string, void*>)];
    // other stuff...
    void* dummy;
};

struct Map {
    // some interface...
private:
    // this is Map's only member
    std::unordered_map<std::string, Node> map_;
};

// and asserting this after the fact to make sure buffer is large enough
static_assert (sizeof(Map) <= sizeof(std::unordered_map<std::string, void*>),
    "Map is unexpectedly too large");

This basically relies on the assumption that std::unordered_map<std::string, T> is the same size for all T, which seems to hold true from my testing using GCC.

My question is thus threefold:

• Is there anything in the C++ standard that requires that this assumption to hold true? (I'm assuming no, but if there is I would be pleasantly surprised...)

• If not, is it practically safe to assume it holds true for all reasonable implementations anyway, and that the static assertion in my revised version will never fire?

• Finally, is there a better workaround to this issue that I haven't thought of? I'm sure it's possible there's something obvious I can do instead that I haven't thought of, but unfortunately I can't think of anything...

Answer 1

1) No

2) STL containers cannot be instantiated with an incomplete type. However, apparently some compilers do allow this. Not allowing this wasn't a trivial decision and in many cases your assumption will indeed hold true. This article might interest you. Given the fact that according to the standard this problem is not solvable without adding a layer of indirection and you don't want to do that. I just have to give a heads up you are indeed not doing things according to the standard.

Having said that, I think that your solution is the best one using stl containers. And the static assert will indeed warn when the size does indeed exceed the expected size.

3) Yes with adding another layer of indirection, my solution would be the following:

The problem you have is that the size of an object, depends on the size of its arrays. Say you have an object A and and object B:

struct A
{
   char sizeof[B]
}

struct B
{
    char sizeof[A]
}

Object A will grow, in order to house chars for the size of B. But then in turn object B will have to grow. I guess you can see where this is going. I know this is your exact problem, but I think the underlying principles are pretty similar.

In this particular case I would solve it by changing the

char buffer[sizeof(Map)];

Line to be just a pointer:

char* buffer

And dynamically allocate memory after initialization. Sow your cpp file would look something like this:

//node.cpp
//untested code
node::node()
{
    buffer = malloc(sizeof(map));
}

node::~node()
{
    free buffer;
}

Answer 2

Just go ahead and assume. Then static_assert at construction that you are right.

There are fancier solutions, like figuring out how boost recursive data structures work and applying the technique here (which might require writing your own map), or just using a boost:: container that supports incomplete data structures.