如何在无序容器中为用户定义的types专门化std :: hash <Key> :: operator（）？

为了支持std::unordered_set<Key>和std::unordered_map<Key, Value>用户定义的键types，必须提供operator==(Key, Key)和一个哈希仿函数：

 struct X { int id; /* ... */ }; bool operator==(X a, X b) { return a.id == b.id; } struct MyHash { size_t operator()(const X& x) const { return std::hash<int>()(x.id); } }; std::unordered_set<X, MyHash> s; 

用std::unordered_set<X>写一个types为X的默认散列会更方便，就像编译器和库一样。 经过咨询

• C ++标准草案N3242§20.8.12 [unord.hash]和§17.6.3.4[hash.requirements]，
• Boost.Unordered
• g ++ include\c++\4.7.0\bits\functional_hash.h
• VC10 include\xfunctional
• 堆栈溢出中的各种相关问题

似乎有可能专门化std::hash<X>::operator() ：

 namespace std { // argh! template <> inline size_t hash<X>::operator()(const X& x) const { return hash<int>()(x.id); } // works for MS VC10, but not for g++ // or // hash<X>::operator()(X x) const { return hash<int>()(x.id); } // works for g++ 4.7, but not for VC10 } 

鉴于编译器支持C + + 11是尚未实验—我没有尝试铿锵—，这些是我的问题：

1. 将这样的专业化添加到名称空间std是合法的吗？ 关于这一点，我感觉好奇。

2. 哪一个std::hash<X>::operator()版本（如果有的话）符合C ++ 11标准？

3. 有没有一种便携式的方式来做到这一点？

Answer 1

您明确允许并鼓励将特化添加到名称空间std *。 添加哈希函数的正确（并且基本上是唯一的）方法是这样的：

 namespace std { template <> struct hash<Foo> { size_t operator()(const Foo & x) const { /* your code here, eg "return hash<int>()(x.value);" */ } }; } 

（其他stream行的专业，你可能会考虑支持std::less ， std::equal_to和std::swap 。）

_{*），只要涉及的types之一是用户定义的，我想。}

Answer 2

我敢打赌，在unordered_map / unorder_set / …类的哈希模板参数：

 #include <unordered_set> #include <functional> struct X { int x, y; std::size_t gethash() const { return (x*39)^y; } }; typedef std::unordered_set<X, std::size_t(*)(const X&)> Xunset; typedef std::unordered_set<X, std::function<std::size_t(const X&)> > Xunset2; int main() { auto hashX = [](const X&x) { return x.gethash(); }; Xunset my_set (0, hashX); Xunset2 my_set2(0, hashX); // if you prefer a more flexible set typedef } 

当然

• hashX也可以是一个全局静态函数
• 在第二种情况下，你可以通过这个
  • struct Xhasher { size_t operator(const X&) const; }; functor对象（ struct Xhasher { size_t operator(const X&) const; }; ）
  • std::hash<X>()
  • 任何满足签名的绑定expression式 –

Answer 3

@Kerrek SB已经涵盖了1）和3）。

2）尽pipeg ++和VC10用不同的签名来声明std::hash<T>::operator() ，但两个库实现都符合标准。

标准没有指定std::hash<T>的成员。 它只是说每个这样的特殊化必须满足std::unordered_set的第二个模板参数所需的相同的“哈希”要求等等。 即：

• 哈希typesH是一个函数对象，至less有一个参数types为Key 。
• H是可复制的。
• H是可破坏的。
• 如果h是typesH或const H的expression式，并且k是可转换为（可能是const ） Key的types的expression式，则h(k)是types为size_t的有效expression式。
• 如果h是H型或const H型的expression式，并且u是Keytypes的左值，那么h(u)是typessize_t的有效expression式，不会修改u 。