自定义类的 unordered_set 是否有默认哈希函数?

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

我第一次使用 std::unordered_set 并且有一个关于哈希函数的问题.据我了解,如果您不指定哈希函数,它将默认为 std::hash.

I'm using a std::unordered_set for the first time and have a question about the hash function. As far as I understand, if you don't specify a hash function it will default to std::hash<Key>.

我的一个班级中有一个 mySet 成员:

I have a mySet member in one of my classes:

typedef std::unordered_set<MyClass> USetType;
USetType mySet;

当我尝试构建时,出现以下错误:

When I try to build, I get the following error:

错误 C2440:类型转换":无法从const MyClass"转换为size_t"

error C2440: 'type cast' : cannot convert from 'const MyClass' to 'size_t'

如果要将unordered_set 与自定义类一起使用,是否需要定义转换函数(到size_t)?有什么办法可以避免编写自己的哈希函数而只使用默认值?

Is it necessary to define a conversion function (to size_t) if you want to use unordered_set with a custom class? Is there any way to avoid writing your own hash function and just using the default?

推荐答案

如果不指定自己的哈希函子作为模板参数,它将默认为 std::hash,除非你定义它,否则它不存在.

If you don't specify your own hash functor as template argument, it will default to std::hash<MyClass>, which does not exist unless you define it.

最好在名称空间 std 中定义自己的 std::hash 特化:

Best define your own specialization of std::hash inside namespace std:

namespace std {
  template <>
  struct hash<MyClass>
  {
    typedef MyClass      argument_type;
    typedef std::size_t  result_type;

    result_type operator()(const MyClass & t) const
    {
       /* ..calculate hash value for t */
    }
  };
}

并确保在声明散列之前包含此代码.通过这种方式,您可以简单地将哈希声明为 std::unordered_set<MyClass>,而无需进一步的模板参数.

And make sure you include this code before the declaration of your hash. This way you can declare the hash simply as std::unordered_set<MyClass> with no need for further template arguments.

您没有指定 MyClass 在里面是什么样子,但典型的情况是您的用户定义类型只是由几个简单类型成员组成,对于这些成员,存在默认的散列函数.在这种情况下,您可能希望将各个类型的散列值组合为整个组合的散列值.Boost 库为此提供了一个名为 hash_combine 的函数.当然,不能保证它在您的特定情况下能很好地工作(这取决于数据值的分布和冲突的可能性),但它提供了一个良好且易于使用的起点.

You didn't specify what MyClass looks like inside, but a typical situation is that your user-defined type simply consists of several simple-type members, for which a default hash function exists. In this case, you will probably want to combine the hash values for the individual types to a hash value for the entire combination. The Boost library provides a function called hash_combine for this purpose. Of course, there is no guarantee that it will work well in your particular case (it depends on the distribution of data values and the likelihood of collisions), but it provides a good and easy-to-use starting point.

这里是一个如何使用它的例子,假设 MyClass 由两个字符串成员组成:

Here is an example of how to use it, assuming MyClass consists of two string members:

#include <unordered_set>
#include <boost/functional/hash.hpp>

struct MyClass
{
  std::string _s1;
  std::string _s2;
};

namespace std {
  template <>
  struct hash<MyClass>
  {
    typedef MyClass      argument_type;
    typedef std::size_t  result_type;

    result_type operator()(const MyClass & t) const
    {
      std::size_t val { 0 };
      boost::hash_combine(val,t._s1);
      boost::hash_combine(val,t._s2);
      return val;
    }
  };
}

int main()
{
  std::unordered_set<MyClass> s;
  /* ... */
  return 0;
}

相关文章