Отобразить "int Triplets" на int? - PullRequest
Новая
       28

Отобразить "int Triplets" на int?

2 голосов
/ 22 марта 2012

с помощью unordered_map в c ++ std. Я хочу отобразить целочисленный триплет на одно целое число, я обычно не использую хеш-таблицы (я не знал, что они такие классные), но я не знаю правильного подхода в этом случае.используя функцию хеширования по умолчанию, я должен сопоставить триплеты напрямую (что-то вроде <<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;

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

Ответы [ 3 ]

3 голосов
/ 22 марта 2012

Во-первых, вы бы использовали 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;
        }
    };
}
1 голос
/ 22 марта 2012

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

0 голосов
/ 22 марта 2012

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

...