std::map<std::variant，std::variant>与从KeyType到ValueType的映射

Question

我正在尝试通过从std::map到MappedType的映射来创建一个变体到变量的映射。

这可以用于大约100个左右的关键类型：https://coliru.stacked-crooked.com/a/3959534e4fa38caa。当我尝试用200个键类型编译时，GCC想了一会儿，然后放弃了错误：

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

我认为这可能是一个问题，因为参数包太大。是否有更可伸缩的解决方案？

以下是解决方案的主要部分：

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

如果实际上对所有MappedTypeForKey类型实例化了insert或get，并且它们都是不同的，则需要二次实例化多个Key，因为每次查找在映射成对的数量中都需要平均线性时间。最终GCC将耗尽内存来存储这些实例化和崩溃。

相反，您可以通过对基类的引用使用模板参数演绎规则来获得类型之间的映射。这总共只需要线性的编译时间内存，如果编译器适当地实现了基类查找，每次查找最多需要对数时间，这样整个程序就有希望在映射对的数量上具有次二次编译时间和内存复杂度：

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{}));
};

这就要求所有的键都是不同的。否则，您将收到错误，抱怨不明确的调用或重复的基类。