templated recursive data types

Question

I have a recursive data type like this:

template<typename T>
struct SomeType {
    std::map<T, SomeType<T>> mapping;
};

SomeType<int> foo;

This works fine, but replacing std::map with std::unordered_map results in a compile error due to an incomplete type. Am I (or gcc) making an error somewhere? or is this just part of the standard?

I would also like to have the internal container determined by a template parameter (like std::stack and std::queue), but I can't figure out a way to do it since that would require SomeType to already be defined.

Incomplete example:

template<typename T, typename C = std::map<T, SomeType<[???]>>>
struct SomeType {
    C mapping;
};

SomeType<int, [???]> foo;

I know this can be done with runtime indirection, but that's not what I'm looking for.

Answer 1

Your class is incomplete anywhere before the final } of its definition. So the mapping member is using incomplete type SomeType in its type's template arguments.

The standard does not allow this, and it is pure luck that it works with some STL containers.

Your second questions falls under the same answer -- it is illegal to do that in the first place.

Answer 2

You cannot define a template with recursive default parameters for obvious reasons. You also cannot instantiate standard library container templates on incomplete types, because the standard says so (otherwise it's undefined behaviour). The usual PIMPL idiom may help, though:

#include <map>
#include <memory>
template <typename T> class SomeType
{
    typedef std::map<T, SomeType<T>> map_type;
    typedef std::unique_ptr<map_type> map_ptr;
    map_ptr pimpl;
public:
    SomeType() : pimpl(new map_type) { }
};

Answer 3

While you cannot use incomplete types with containers, you can do it with smart pointers. And while you cannot create template types with undefined types parameters, you can use some tricks here:

template<typename T, template <typename U, typename V, typename... Args> class Container = std::unordered_map >
struct SomeType {
    Container<T, std::unique_ptr<SomeType> > mapping;
};