如何为无序容器中的用户定义类型专门化 std: : hash < Key > : : Operator() ？

支持 std::unordered_set<Key>和 std::unordered_map<Key, Value>中用户定义的键类型 必须提供 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>会更方便 X型的 默认哈希, 类似于随编译器和库而来的类型。 在咨询之后

  • C++ Standard 草案 N3242 §20.8.12 [unord.hash] and §17.6.3.4 [hash.requirements],
  • 推进，无序
  • g++ include\c++\4.7.0\bits\functional_hash.h
  • VC10 include\xfunctional
  • various 相关问题s in Stack Overflow

似乎可以将 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的编译器支持还处于试验阶段——-我没有尝试 Clang ——-，这是我的问题:

  1. 在名称空间 std中添加这样的专门化是合法的吗。

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

  3. 有便携式的方法吗？

59003 次浏览
小开
最佳答案

明确允许并鼓励您将 专业化添加到名称空间 std * 。添加哈希函数的正确(基本上也是唯一)方法是:

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

(您可能考虑支持的其他流行专门化是 std::less、 std::equal_to和 std::swap。)

*) ，只要其中一个涉及的类型是用户定义的，我想。

小开

@ Kerrek SB 已覆盖1)及3)。

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

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

  • 散列类型 H是一个函数对象，至少有一个参数类型 Key。
  • H是可复制构造的。
  • H是可摧毁的。
  • 如果 h是 H或 const H类型的表达，而 k是可转换为(可能是 const) Key的类型的表达，则 h(k)是 size_t类型的有效表达。
  • 如果 h是 H或 const H类型的表达式，而 u是 Key类型的左值，那么 h(u)是 size_t类型的有效表达式，它不修改 u。
小开

我打赌是 unorder _ map/unorder _ set/... 类的 Hash 模板参数:

#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; };)
    • std::hash<X>()
    • 满足签名的任何绑定表达式 -

提交答案