115

为了支持用户定义的键类型，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> 仅使用type的默认哈希编写会更方便X，例如编译器和库附带的类型。咨询后

  • C++ 标准草案 N3242 §20.8.12 [unord.hash] 和 §17.6.3.4 [hash.requirements]，
  • Boost.Unordered
  • 克++include\c++\4.7.0\bits\functional_hash.h
  • VC10include\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. 有便携的方法吗？

4

3 回答 3

145

明确允许并鼓励您向命名空间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）

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

于 2011-11-16T20:07:56.610 回答
7

我的赌注是 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<X>()
    • 任何满足签名的绑定表达式 -
于 2011-11-16T20:36:29.343 回答
4

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

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

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

  • 哈希类型H是一个函数对象，至少有一个参数类型Key。
  • H是可复制构造的。
  • H是可破坏的。
  • ifh是Hor类型的表达式const H，并且k是可转换为 (可能const)的类型的表达式Key，thenh(k)是类型为 的有效表达式size_t。
  • ifh是Hor类型的表达式const H，并且u是 type 的左值Key， thenh(u)是类型size_t不修改的有效表达式u。
于 2011-11-16T20:24:50.677 回答