std::map<std::variant, std::variant> with mapping from KeyType to ValueType

Question

I'm trying to create a std::map of variant to variant with a mapping from the KeyType to the MappedType.

This works for up to around 100 key types or so: https://coliru.stacked-crooked.com/a/3959534e4fa38caa. When I attempt to compile with 200 key types, GCC thinks hard for a while and then gives up with the error:

g++: internal compiler error: Killed (program cc1plus)

I believe it may be a problem with the parameter pack being too large. Is there a more scalable solution?

I include below the salient parts of the solution:

template<typename Key, typename T>
struct TypeMap {
    using KeyType = Key;
    using MappedType = T;
};

template<typename>
constexpr bool false_v = false;

// End case
template<typename Key, typename...>
struct MappedTypeForKey {
    static_assert(false_v<Key>, "Container mapping for key type not found");
};

// Recursive case
template<typename Key, typename MapKey, typename T, typename... TypeMaps>
struct MappedTypeForKey<Key, TypeMap<MapKey, T>, TypeMaps...> : MappedTypeForKey<Key, TypeMaps...> {
};

// Match case
template<typename Key, typename T, typename... TypeMaps>
struct MappedTypeForKey<Key, TypeMap<Key, T>, TypeMaps...> {
    using Type = T;
};

template<typename... TypeMaps>
struct VariantTypeMapImpl {
    using KeyType = std::variant<typename TypeMaps::KeyType...>;
    using MappedType = std::variant<typename TypeMaps::MappedType...>;
    template<typename Key>
    using TypeForKey = typename MappedTypeForKey<Key, TypeMaps...>::Type;
};

// This is the key part of the code, allowing a developer to extend the map variants
// at the same time as defining the type mappings:
using VariantTypeMap = VariantTypeMapImpl<
    TypeMap<FrogKey, Frog>,
    TypeMap<CatKey, Cat>
>;

class VariantMap {
  public:
    size_t size() const { return map_.size(); }

    template<typename Key>
    void insert(Key key, VariantTypeMap::TypeForKey<Key> value)
    {
        map_.emplace(std::move(key), std::move(value));
    }

    template<typename Key>
    const VariantTypeMap::TypeForKey<Key>& get(const Key& key) const
    {
        return std::get<VariantTypeMap::TypeForKey<Key>>(map_.at(key));
    }

  private:
    std::map<VariantTypeMap::KeyType, VariantTypeMap::MappedType> map_;
};

Answer 1

You are requiring quadratically many instantiations of MappedTypeForKey if insert or get are actually instantiated for all Key types and they are all distinct, because each lookup will take on average linear time in the number of mapped pairs. Eventually GCC will run out of memory to store these instantiations and crash.

Instead you can get a mapping between types by making use of template argument deduction rules for references to base classes. This does only require linear amount of compile time memory in total and if the compiler has implemented the base class lookup decently, this will take at most logarithmic time per lookup, so that the whole program will hopefully have sub-quadratic compile-time time and memory complexity in the number of mapped pairs:

template<typename... TypeMaps>
struct VariantTypeMapImpl {
    using KeyType = std::variant<typename TypeMaps::KeyType...>;
    using MappedType = std::variant<typename TypeMaps::MappedType...>;

    struct map : TypeMaps... {
        template<typename Key, typename Mapped>
        static auto lookup(const TypeMap<Key, Mapped>&) -> Mapped;
    };

    template<typename Key>
    using TypeForKey = decltype(map::template lookup<Key>(map{}));
};

This requires all keys to be distinct. Otherwise you will get errors complaining about ambiguous calls or repeated base classes.