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

How to specialize std::hash<Key>::operator() for user-defined type in unordered containers?

提问by René Richter

To support user-defined key types in std::unordered_set<Key>and std::unordered_map<Key, Value>one has to provide operator==(Key, Key)and a hash functor:

为了支持用户定义的键类型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;

It would be more convenient to write just std::unordered_set<X>with a default hashfor type X, like for types coming along with the compiler and library. After consulting

仅std::unordered_set<X>使用type的默认散列来编写会更方便X，就像编译器和库附带的类型一样。咨询后

• C++ Standard Draft N3242§20.8.12 [unord.hash] and §17.6.3.4 [hash.requirements],
• Boost.Unordered
• g++ include\c++\4.7.0\bits\functional_hash.h
• VC10 include\xfunctional
• various related questions in Stack Overflow

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

it seems possible to specialize std::hash<X>::operator():

似乎可以专攻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 
}                                                                             

Given compiler support for C++11 is yet experimental---I did not try Clang---, these are my questions:

鉴于对 C++11 的编译器支持尚处于试验阶段——我没有尝试 Clang——，这些是我的问题：

1. Is it legal to add such a specialization to namespace std? I have mixed feelings about that.

2. Which of the std::hash<X>::operator()versions, if any, is compliant with C++11 standard?

3. Is there a portable way to do it?

1. 将这样的专业化添加到 namespace 是否合法std？我对此有复杂的感觉。

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

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

回答by Kerrek SB

You are expressly allowed and encouraged to add specializationsto namespace std*. The correct (and basically only) way to add a hash function is this:

明确允许并鼓励您向命名空间*添加专业化std。添加哈希函数的正确（并且基本上是唯一的）方法是：

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

(Other popular specializations that you might consider supporting are std::less, std::equal_toand std::swap.)

（您可能考虑支持的其他流行专业包括std::less、std::equal_to和std::swap。）

_{*) as long as one of the involved types is user-defined, I suppose.}

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

回答by sehe

My bet would be on the Hash template argument for the unordered_map/unorder_set/... classes:

我的赌注是 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
}

Of course

当然

• hashX could just as well be a global static function
• in the second case, you could pass that
  • the oldfashioned functor object (struct Xhasher { size_t operator(const X&) const; };)
  • std::hash<X>()
  • any bind expression satisfying the signature -

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

回答by aschepler

@Kerrek SB has covered 1) and 3).

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

2) Even though g++ and VC10 declare std::hash<T>::operator()with different signatures, both library implementations are Standard compliant.

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

The Standard does not specify the members of std::hash<T>. It just says that each such specialization must satisfy the same "Hash" requirements needed for the second template argument of std::unordered_setand so on. Namely:

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

• Hash type His a function object, with at least one argument type Key.
• His copy constructible.
• His destructible.
• If his an expression of type Hor const H, and kis an expression of a type convertible to (possibly const) Key, then h(k)is a valid expression with type size_t.
• If his an expression of type Hor const H, and uis an lvalue of type Key, then h(u)is a valid expression with type size_twhich does not modify u.

• 哈希类型H是一个函数对象，至少有一个参数类型Key。
• H是可复制构造的。
• H是可破坏的。
• 如果h是Hor类型的表达式const H，并且k是可转换为（可能const）类型的表达式Key，则h(k)是类型为 的有效表达式size_t。
• 如果h是Hor类型的表达式const H，并且u是类型的左值Key，则h(u)是类型size_t不修改的有效表达式u。