Как сделать так, чтобы ключ карты был двух разных типов данных? - PullRequest
Новая
       17

Как сделать так, чтобы ключ карты был двух разных типов данных?

0 голосов
/ 12 октября 2018

У меня есть контейнер std::unordered_map, где Key может быть двух типов данных:

  • 64-битный беззнаковый int
  • кортеж, имеющий (8-битный беззнаковый int, 8-битное без знака int, 16-битное unsigned-int, 32-битное unsigned int)

Но значение - это тип объекта, который одинаков для обоих типов ключей.

Одна вещь, которую я попробовал, это сделать ключ std::variant, чтобы он мог хранить оба типа.Основываясь на некоторой проверке состояния, ключ устанавливается на один из типов: 

void A::a() {
    std::varaint<type1, type2> Id; //key

    if (condition) {
        Id = 64 bit unsigned value;
    }
    else {
        Id = tuple<.....>;
    }
}

unorderedmap[Id] = obj1;
// ^-- gives compile-time error
// (expecting Id specialized to either of the variant types)

Также, подобно этой функции, есть несколько функций, где мы выполняем find () для unordered_map. 

unorderedmap.find(Id);
// ^-- Here also, compiler is throwing similar error

Есть ли способ исправить вариант std ::, или я должен использовать другой подход?

1 Ответ

0 голосов
/ 12 октября 2018

Кажется, это работает просто отлично: 

#include <iostream>
#include <unordered_map>
#include <string>
#include <variant>

typedef std::variant<int, std::string> mytype;

std::unordered_map<mytype, int> m;

int main()
{
    m[5] = 20;
    std::cout << m[5];
    m["hey"] = 10;
    std::cout << m["hey"];
    mytype tmp = "hey";
    std::cout << m[tmp];
}

Таким образом, ответ в основном таков: убедитесь, что при попытке индексации карты с вариантом, индекс карты имеет тот же тип варианта.Если вы используете get или , то это , вы даже можете заставить его работать, когда map - это расширенный вариант варианта, который вы хотите использовать - тесно эмулируя динамические языки.

EDIT:

Если вы хотите поддержать std::tuple, у вас есть несколько вариантов.

Опция 1

Просто используйте std::map вместо std::unordered_map.Маловероятно, что вы когда-либо сможете увидеть logN, а из опыта std::map будет на самом деле быстрее (вас также не убьет перефразировка, которая занимает столетие, что происходит каждый раз, когда std::unordered_map должен расти).

Вариант 2

Продолжайте использовать std::unordered_map, но используйте хеширование.Например, здесь со следующим адаптированным кодом: 

#include <iostream>
#include <string>
#include <variant>
#include <unordered_map>
// #include "custom_tuple.h"

// CUSTOM_TUPLE.h
#include <tuple>

namespace std{
    namespace
    {

        // Code from boost
        // Reciprocal of the golden ratio helps spread entropy
        //     and handles duplicates.
        // See Mike Seymour in magic-numbers-in-boosthash-combine:
        //     https://stackoverflow.com/questions/4948780

        template <class T>
        inline void hash_combine(std::size_t& seed, T const& v)
        {
            seed ^= hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }

        // Recursive template code derived from Matthieu M.
        template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
        struct HashValueImpl
        {
          static void apply(size_t& seed, Tuple const& tuple)
          {
            HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
            hash_combine(seed, get<Index>(tuple));
          }
        };

        template <class Tuple>
        struct HashValueImpl<Tuple,0>
        {
          static void apply(size_t& seed, Tuple const& tuple)
          {
            hash_combine(seed, get<0>(tuple));
          }
        };
    }

    template <typename ... TT>
    struct hash<std::tuple<TT...>> 
    {
        size_t
        operator()(std::tuple<TT...> const& tt) const
        {                                              
            size_t seed = 0;                             
            HashValueImpl<std::tuple<TT...> >::apply(seed, tt);    
            return seed;                                 
        }                                              

    };
}
// END CUSTOM_TUPLE.h

typedef std::variant<std::string, std::tuple<int, bool>> mytype;

std::unordered_map<mytype, int> m;

int main()
{
    m[std::tuple{5, false}] = 20;
    std::cout << m[std::tuple{5, false}];
    m["hey"] = 10;
    std::cout << m["hey"];
    mytype tmp = "hey";
    std::cout << m[tmp];
}

Вы можете поместить все внутри части namespace std{} внутри заголовка, а затем просто включать этот заголовок, где бы вы ни находилисьхочу (я не включил охранников, так что добавьте, как обычно).Если стандарт когда-либо догоняет и реализует хэширование кортежей, просто удалите файл заголовка.

...