Сопоставить триплеты int с int?

используя c++ std unordered_map, я хочу сопоставить тройку целых чисел с одним целым числом, я обычно не использую хеш-таблицы (не знал, что они такие крутые), но я не знаю правильный подход в этом случае, используя хэш-функция по умолчанию, если я сопоставляю триплеты напрямую (что-то вроде ‹ ‹ int,int>,int>->int)

std::unordered_map <std::make_pair <make_pair <int,int>,int>,int> hash;

или, может быть, использовать функцию для сопоставления триплета с одним значением и использовать это значение с функцией по умолчанию?

int mapping(int a, int b, int c){
}

std::unordered_map <int,int> hash;

оба подхода работают, но я хотел бы знать, какой из них наиболее эффективен. благодарю вас


c++ hash std unordered-map
person Alb3rt    schedule 22.03.2012    source источник
comment
У вас есть доступ к std::tuple?   -  person Jesse Good    schedule 22.03.2012
comment
(Пара — это особый вид кортежа: с двумя элементами.)   -  person    schedule 22.03.2012
comment
да, у меня есть доступ к std::tuple, я просто не привык к библиотекам c++, я проверю   -  person Alb3rt    schedule 22.03.2012

Ответы (3)


arrow_upward
3
arrow_downward

Во-первых, вы должны использовать std::tuple<int, int, int> в качестве типа ключа.

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

#include <tuple>
#include <utility>

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

template <class Tuple, std::size_t Index = std::tuple_size<Tuple>::value - 1>
struct tuple_hash_impl
{
    static inline void apply(std::size_t & seed, Tuple const & tuple)
    {
        tuple_hash_impl<Tuple, Index - 1>::apply(seed, tuple);
        hash_combine(seed, std::get<Index>(tuple));
    }
};

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

namespace std
{
    template<typename S, typename T> struct hash<pair<S, T>>
    {
        inline size_t operator()(const pair<S, T> & v) const
        {
            size_t seed = 0;
            ::hash_combine(seed, v.first);
            ::hash_combine(seed, v.second);
            return seed;
        }
    };

    template<typename ...Args> struct hash<tuple<Args...>>
    {
        inline size_t operator()(const tuple<Args...> & v) const
        {
            size_t seed = 0;
            tuple_hash_impl<tuple<Args...>>::apply(seed, v);
            return seed;
        }
    };
}
person Kerrek SB    schedule 22.03.2012

arrow_upward
1
arrow_downward

«Наиболее эффективный» кажется чем-то в зависимости от вашего компилятора, но я бы сказал, что решение make_pair выглядит как беспорядок. Лучше используйте свою собственную хеш-функцию... просто убедитесь, что вы составили достойную :)

person Johan Kotlinski    schedule 22.03.2012

arrow_upward
0
arrow_downward

Ваше решение с парой пар должно быть довольно эффективным. Будет сложно сопоставить три целых числа чему-то более простому с точки зрения хеширования.

person piokuc    schedule 22.03.2012