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

Question

支持在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++标准草案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
• 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. 有一种便携式的方法可以做到吗？

- René Richter

---

使用gcc 4.7.2，我必须提供一个全局的operator==(const Key, const Key)。 - Victor Lyuboslavsky

请注意，std::hash的特化（与std命名空间中的其他内容不同）受到Google样式指南的反对；请谨慎使用。 - Franklin Yu

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。)

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

- Kerrek SB

---

虽然这是可能的，但您一般会推荐以这种方式进行吗？我更喜欢实例化unorder_map<eltype, hash, equality>，以避免因有趣的ADL问题而破坏某人的一天。（编辑Pete Becker在此主题上的建议） - sehe

如果你手头上有一个哈希函数对象，它是可以默认构造的，或许可以这么做。但为什么要这样做呢？（相等比较更容易，因为你只需要实现成员运算符 operator==。）我的一般哲学是，如果这个功能是自然的且基本上是唯一的“正确”方法（比如词典序对比），那么我会将其添加到 std 中。如果它是某种奇特的功能（比如无序对比），那么我就将其特化为某个容器类型。 - Kerrek SB

我不反对，但是在标准中哪里允许并鼓励我们向 std 添加专业化呢？ - razeh

@Kerrek，我同意你的观点，但我希望能够在标准中找到相关章节和课文的引用。我发现17.6.4.2.1中允许注入代码，但前提是“除非另有规定”，但我没能在4000多页的规范中找到相应的“另有规定”的内容。 - razeh

根据此处提供的链接，如果程序依赖于用户定义的类型并且特化符合原始模板的标准库要求且未被明确禁止，则程序可以将任何标准库模板的特化添加到 std 命名空间中。因此，这个解决方案是可行的。 - Marek R

Answer 2

我猜测unordered_map/unordered_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>()
  • 任何满足签名的绑定表达式-

- sehe

---

我很欣赏你能够编写一些没有默认构造函数的代码，但我总是觉得要求每个映射构造都记住额外的参数有点繁琐——对我来说负担有点太重了。不过，如果使用显式模板参数，我还是可以接受的，虽然专门化std::hash仍然是最好的解决方法 :-) - Kerrek SB

用户自定义类型来拯救 :-) 更严肃地说，我希望我们在他们的类包含 char* 的阶段就已经警告过他们了！ - Kerrek SB

嗯...你有hash特化如何通过ADL干扰的例子吗？我的意思是，这完全是可能的，但我很难想出一个问题案例。 - Kerrek SB

让我们在聊天室中继续这个讨论。 - sehe

玩笑归玩笑，但当你需要一个 std::unordered_map<Whatever, Xunset> 时，如果你的 Xunset 哈希类型不可默认构造，则会出现问题。 - Rag

Answer 3

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

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

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

• 哈希类型H是一个函数对象，至少有一个参数类型Key。
• H可以复制构造。
• H是可销毁的。
• 如果h是类型H或const H的表达式，而k是可转换为（可能是const）Key的类型的表达式，则h(k)是具有类型size_t的有效表达式。
• 如果h是类型H或const H的表达式，而u是类型Key的lvalue，则h(u)是具有类型size_t的有效表达式，不修改u。

- aschepler

---

不，两种实现都不符合标准，因为它们试图专门化 std::hash<X>::operator() 而不是整个 std::hash<X>，而且 std::hash<T>::operator() 的签名是由实现定义的。 - ildjarn

@ildjarn：澄清一下 - 我所说的是库实现，而不是尝试的特化。不确定OP确切想问什么。 - aschepler