Общий хэш для кортежей в unordered_map / unordered_set
Почему не std::unordered_map<tuple<int, int>, string> просто работать из коробки? Утомительно определять хэш-функцию для tuple<int, int>например,
template<> struct do_hash<tuple<int, int>>
{ size_t operator()(std::tuple<int, int> const& tt) const {...} };
Построение неупорядоченной карты с кортежами в качестве ключей (Matthieu M.) показывает, как автоматизировать это для boost::tuple, Есть ли способ сделать это для кортежей C++0x без использования шаблонов с переменными числами?
Наверняка это должно быть в стандарте:(
5 ответов
Это работает на gcc 4.5, позволяя всем кортежам C++0x, содержащим стандартные типы hashable, быть членамиunordered_map а также unordered_set без дальнейших церемоний.
(Я помещаю код в заголовочный файл и просто включаю его.)
Функция должна жить в пространстве имен std, чтобы ее можно было найти с помощью поиска по аргументам (ADL).
Есть ли более простое решение?
#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:
// http://stackru.com/questions/4948780
template <class T>
inline void hash_combine(std::size_t& seed, T const& v)
{
seed ^= std::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, std::get<Index>(tuple));
}
};
template <class Tuple>
struct HashValueImpl<Tuple,0>
{
static void apply(size_t& seed, Tuple const& tuple)
{
hash_combine(seed, std::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;
}
};
}
Стандартный код соответствия
Якк указывает, что специализация вещей в пространстве имен std на самом деле неопределенное поведение. Если вы хотите иметь решение, соответствующее стандартам, то вам нужно переместить весь этот код в собственное пространство имен и отказаться от любой идеи о том, что ADL найдет правильную реализацию хеш-функции. Вместо:
unordered_set<tuple<double, int> > test_set;
Тебе нужно:
unordered_set<tuple<double, int>, hash_tuple::hash<tuple<double, int>>> test2;
где hash_tuple это ваше собственное пространство имен, а не std::,
Для этого сначала нужно объявить реализацию хеша внутри hash_tuple Пространство имен. Это перенаправит все типы не кортежей в std::hash:
namespace hash_tuple{
template <typename TT>
struct hash
{
size_t
operator()(TT const& tt) const
{
return std::hash<TT>()(tt);
}
};
}
Удостоверься что hash_combine звонки hash_tuple::hash и не std::hash
namespace hash_tuple{
namespace
{
template <class T>
inline void hash_combine(std::size_t& seed, T const& v)
{
seed ^= hash_tuple::hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
}
Затем включите весь предыдущий код, но поместите его внутрь namespace hash_tuple и не std::
namespace hash_tuple{
namespace
{
// 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, std::get<Index>(tuple));
}
};
template <class Tuple>
struct HashValueImpl<Tuple,0>
{
static void apply(size_t& seed, Tuple const& tuple)
{
hash_combine(seed, std::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;
}
};
}
#include <boost/functional/hash.hpp>
#include <tuple>
namespace std
{
template<typename... T>
struct hash<tuple<T...>>
{
size_t operator()(tuple<T...> const& arg) const noexcept
{
return boost::hash_value(arg);
}
};
}
В C++20 можно использовать складные выражения и общие лямбда-выражения для вычисления хеша кортежа без рекурсии. Я предпочитаю полагаться на std::hash<uintmax_t> вместо ручного объединения хэшей:
#include <cinttypes>
#include <cstddef>
#include <functional>
#include <tuple>
class hash_tuple {
template<class T>
struct component {
const T& value;
component(const T& value) : value(value) {}
uintmax_t operator,(uintmax_t n) const {
n ^= std::hash<T>()(value);
n ^= n << (sizeof(uintmax_t) * 4 - 1);
return n ^ std::hash<uintmax_t>()(n);
}
};
public:
template<class Tuple>
size_t operator()(const Tuple& tuple) const {
return std::hash<uintmax_t>()(
std::apply([](const auto& ... xs) { return (component(xs), ..., 0); }, tuple));
}
};
- 1 в sizeof(uintmax_t) * 4 - 1 является необязательным, но, похоже, немного улучшает распределение хэшей. Этот класс может использоваться как с std::tuple а также std::pair,
В моем проекте C++0x, 20.8.15 говорит, что хеш специализирован для встроенных типов (включая указатели, но, похоже, не подразумевает их разыменование). Это также, кажется, специализируется на error_code, bitset<N>, unique_ptr<T, D>, shared_ptr<T>, typeindex, string, u16string, u32string, wstring, vector<bool, Allocator>, а также thread::id, (Список лиц!)
Я не использовал C++0x variadics, поэтому мое форматирование, вероятно, далеко, но что-то в этом роде может работать для всех кортежей.
size_t hash_combiner(size_t left, size_t right) //replacable
{ return left + 0x9e3779b9 + (right<<6) + (right>>2);}
template<int index, class...types>
struct hash_impl {
size_t operator()(size_t a, const std::tuple<types...>& t) const {
typedef typename std::tuple_element<index, std::tuple<types...>>::type nexttype;
hash_impl<index-1, types...> next;
size_t b = std::hash<nexttype>()(std::get<index>(t));
return next(hash_combiner(a, b), t);
}
};
template<class...types>
struct hash_impl<0, types...> {
size_t operator()(size_t a, const std::tuple<types...>& t) const {
typedef typename std::tuple_element<0, std::tuple<types...>>::type nexttype;
size_t b = std::hash<nexttype>()(std::get<0>(t));
return hash_combiner(a, b);
}
};
template<class...types>
struct tuple_hash<std::tuple<types...>> {
size_t operator()(const std::tuple<types...>& t) {
const size_t begin = std::tuple_size<std::tuple<types...>>::value-1;
return hash_impl<begin, types...>()(0, t);
}
}
Эта версия на самом деле компилируется и запускается
Якк заметил, что специализация std::hash напрямую это технически не разрешено, поскольку мы специализируем стандартный шаблон библиотеки с объявлением, которое не зависит от определяемого пользователем типа.
Если вы хотите сделать это простым способом. Просто делать
std::unordered_map<std::tuple<int, int>, std::string, boost::hash<std::tuple<int, int>>> mp;