станд :: Карта с отображением из KeyType в ValueType - PullRequest
Новая
       98

станд :: Карта с отображением из KeyType в ValueType

0 голосов
/ 18 марта 2020

Я пытаюсь создать std::map варианта к варианту с отображением от KeyType до MappedType.

. Это работает для примерно 100 типов ключей или около того: https://coliru.stacked-crooked.com/a/3959534e4fa38caa. Когда я пытаюсь скомпилировать с 200 типами ключей, G CC некоторое время задумывается, а затем сдается с ошибкой: 

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_;
};

1 Ответ

1 голос
/ 18 марта 2020

Требуется квадратично много экземпляров MappedTypeForKey, если insert или get фактически созданы для всех типов Key, и все они различны, потому что каждый поиск будет занимать в среднем линейное время в количестве отображенных пар. В конце концов G CC не хватит памяти для хранения этих экземпляров и cra sh.

Вместо этого вы можете получить отображение между типами, используя правила вывода аргументов шаблона для ссылок на базовые классы. Для этого требуется только линейный объем памяти времени компиляции, и если компилятор прилично реализовал поиск в базовом классе, это займет самое большее логарифмическое c время на поиск, так что вся программа, как мы надеемся, будет иметь субкадры c время компиляции и сложность памяти в количестве отображаемых пар: 

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

Это требует, чтобы все ключи были различны. В противном случае вы получите ошибки с жалобами на неоднозначные вызовы или повторные базовые классы.

...