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

2021-12-27 00:00:00 hash c++ c++11 unordered-map unordered-set

在std::unordered_set和std::unordered_map中支持用户定义的键类型必须提供 operator==(Key, Key) 和一个哈希函子:

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:

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，喜欢与编译器和库一起出现的类型.咨询后

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

  • C++ 标准 草案 N3242§20.8.12 [unord.hash] 和 §17.6.3.4 [hash.requirements]，
  • Boost.Unordered
  • g++ includec++4.7.0itsfunctional_hash.h
  • VC10 includexfunctional
  • Stack Overflow 中的各种相关问题
  • C++ Standard Draft N3242 §20.8.12 [unord.hash] and §17.6.3.4 [hash.requirements],
  • Boost.Unordered
  • g++ includec++4.7.0itsfunctional_hash.h
  • VC10 includexfunctional
  • various related questions 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---，这些是我的问题:

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

  1. 向命名空间 std 添加这样的特化是否合法?我对此有复杂的感觉.

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

哪个std::hash<X>::operator() 版本(如果有)符合 C++11 标准?

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

有没有便携的方法来做到这一点?

Is there a portable way to do it?

推荐答案

明确允许并鼓励您将 specializations 添加到命名空间 std*.添加哈希函数的正确(并且基本上是唯一的)方法是:

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

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

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

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

相关文章