Карта "int Triplets" to int?

using C++ std's unordered_map Я хочу сопоставить целочисленный триплет с одним целым числом, я обычно не использую хеш-таблицы (не знал, что они были такими классными), но я не знаю правильного подхода в этом случае, с помощью функции хэширования по умолчанию я должен отображать тройни непосредственно (что-то вроде < < междунара, Int> Int> -> Int)Карта "int Triplets" to 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;

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

источник

2012-03-22 Alb3rt

У вас есть доступ к [станд :: кортеж] (http://en.cppreference.com/w/cpp/utility/tuple)? –

(«Пара» - это просто особый тип «кортежа»: это с двумя элементами.) –

да, я делаю hace acces для std :: tuple, я просто не тот, что используется для библиотек C++, я проверю его – Alb3rt

Прежде всего, вы бы использовали 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; 
     } 
    }; 
}

источник

2012-03-22 01:21:01

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

источник

2012-03-22 01:14:10 piokuc

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

источник

2012-03-22 01:17:34

Карта "int Triplets" to int?

ответ

Смежные вопросы