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

Question

我正在尝试使用从 KeyType 到 MappedType 的映射创建一个 std::map 变体到变体。

这适用于大约 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

如果 insert 或 get 实际上为所有 Key 类型实例化并且它们都是不同的，那么您需要 MappedTypeForKey 的二次实例化，因为每次查找都会在映射对的数量上采用平均线性时间。最终 GCC 将运行内存不足来存储这些实例并崩溃。

相反，您可以通过对基 classes 的引用使用模板参数推导规则来获得类型之间的映射。这总共只需要线性数量的编译时间内存，如果编译器已经很好地实现了基础 class 查找，那么每次查找最多需要对数时间，因此整个程序有望进行次二次编译-time 映射对数量的时间和内存复杂度：

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

这要求所有键都不同。否则你会收到错误，抱怨不明确的调用或重复的 base classes.

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

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

c++

c++17

variadic-templates

type-safety