如何在无序容器中为用户定义的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. 有没有一种便携式的方式来做到这一点?

您明确允许并鼓励将特化添加到名称空间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::lessstd::equal_tostd::swap 。)

*),只要涉及的types之一是用户定义的,我想。

我敢打赌,在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式 –

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

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

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

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