C++ unordered_map / unordered_set 中元组的通用哈希
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7110301/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Generic hash for tuples in unordered_map / unordered_set
提问by Leo Goodstadt
Why doesn't std::unordered_map<tuple<int, int>, string>just
work out of the box?
It is tedious to have to define a hash function for tuple<int, int>, e.g.
为什么不能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 {...} };
Building an unordered map with tuples as keys(Matthieu M.) shows how to
automate this for boost::tuple. Is there anyway of doing this for c++0x tuples without using variadic templates?
构建一个以元组为键的无序映射(Matthieu M.) 展示了如何为boost::tuple. 无论如何，是否可以在不使用可变参数模板的情况下对 c++0x 元组执行此操作？
Surely this should be in the standard :(
当然，这应该在标准中:(
采纳答案by Leo Goodstadt
This works on gcc 4.5 allowing all c++0x tuples containing standard hashable types to be members of
unordered_mapand unordered_setwithout further ado.
(I put the code in a header file and just include it.)
上的gcc 4.5这个作品允许所有的C ++ 0x元组包含标准可哈希类型是成员
unordered_map和unordered_set不用再费周折。（我将代码放在一个头文件中并只包含它。）
The function has to live in the std namespace so that it is picked up by argument-dependent name lookup (ADL).
该函数必须存在于 std 命名空间中，以便通过参数相关名称查找 (ADL) 来获取它。
Is there a simpler solution?
有没有更简单的解决方案？
#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://stackoverflow.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;
}
};
}
Standard Conformant code
标准合规代码
Yakk points out that specialising things in the std namespace is actually undefined behaviour. If you wish to have a standards conforming solution, then you need to move all of this code into your own namespace and give up any idea of ADL finding the right hash implementation automatically. Instead of :
Yakk 指出，在 std 命名空间中专门化事物实际上是未定义的行为。如果您希望有一个符合标准的解决方案，那么您需要将所有这些代码移动到您自己的命名空间中，并放弃 ADL 自动查找正确哈希实现的任何想法。代替 ：
unordered_set<tuple<double, int> > test_set;
You need:
你需要：
unordered_set<tuple<double, int>, hash_tuple::hash<tuple<double, int>>> test2;
where hash_tupleis your own namespace rather than std::.
哪里hash_tuple是你自己的命名空间而不是std::.
To do this, you first have to declare a hash implementation inside the hash_tuplenamespace. This will forward all non tuple types to the std::hash:
为此，您首先必须在hash_tuple命名空间内声明一个哈希实现。这会将所有非元组类型转发到std::hash：
namespace hash_tuple{
template <typename TT>
struct hash
{
size_t
operator()(TT const& tt) const
{
return std::hash<TT>()(tt);
}
};
}
Make sure that hash_combinecalls hash_tuple::hashand not std::hash
确保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);
}
}
Then include all the other previous code but put it inside namespace hash_tupleand not std::
然后包含所有其他先前的代码，但将其放入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;
}
};
}
回答by Вова
#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);
}
};
}
回答by Mooing Duck
In my C++0x draft, 20.8.15says hash is specialized for built-in types (including pointers, but doesn't seem to imply dereferencing them). It also appears to be specialized for error_code, bitset<N>, unique_ptr<T, D>, shared_ptr<T>, typeindex, string, u16string, u32string, wstring, vector<bool, Allocator>, and thread::id. (facinating list!)
在我的 C++0x 草案中，20.8.15说 hash 专门用于内置类型（包括指针，但似乎并不意味着取消引用它们）。这似乎也可以专门用于error_code，bitset<N>，unique_ptr<T, D>，shared_ptr<T>，typeindex，string，u16string，u32string，wstring，vector<bool, Allocator>，和thread::id。（迷人的清单！）
I've not used C++0x variadics, so my formatting is probably way off, but something along these lines might work for all tuples.
我没有使用过 C++0x 可变参数，所以我的格式可能有点偏离，但这些方面的东西可能适用于所有元组。
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);
}
}
This version actually compiles and runs
Yakk has observed that specializing std::hashdirectly is technicallynot allowed, since we're specializing a standard library template with a declaration that does notdepend on a user-defined type.
Yakk 观察到std::hash直接特化在技术上是不允许的，因为我们特化了一个标准库模板，其声明不依赖于用户定义的类型。
回答by Vladimir Reshetnikov
With C++20, it is possible to use fold expressionsand generic lambdasto compute hash of a tuple without recursion. I prefer to rely on std::hash<uintmax_t>instead of manually combining hashes:
使用 C++20，可以使用折叠表达式和泛型 lambda来计算元组的哈希值而无需递归。我更喜欢依赖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));
}
};
- 1in sizeof(uintmax_t) * 4 - 1is optional, but appears to slightly improve hash distribution. This class can be used both with std::tupleand std::pair.
- 1insizeof(uintmax_t) * 4 - 1是可选的，但似乎稍微改善了哈希分布。此类可以与std::tuple和一起使用std::pair。
