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

Question

支持 std::unordered_set 和 std::unordered_map 中用户定义的键类型 必须提供 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 的默认哈希， 就像编译器和库附带的类型一样。 查阅

• C++ 标准 Draft N3242 § 20.8.12 [unord.hash] 和 §17.6.3.4 [hash.requirements]，
• Boost.Unordered
• g++ include\c++\4.7。 0\bits\function_hash.h
• VC10 include\xfunction
• 各种Stack Overflow 中的相关问题

似乎可以专门化 std： :hash::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::operator() 版本（如果有）符合 C++11 标准？

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

Answer 1

明确允许并鼓励您将专业化添加到命名空间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。）

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

Answer 2

我的赌注是 unordered_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()
  • 任何满足签名的绑定表达式
    -

Answer 3

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

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

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

• 哈希类型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。