9

我std::unordered_set第一次使用 a 并且对哈希函数有疑问。据我了解，如果您不指定哈希函数，它将默认为std::hash<Key>.

我的mySet一个班级中有一名成员：

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

当我尝试构建时，我收到以下错误：

错误 C2440：“类型转换”：无法从“const MyClass”转换为“size_t”

size_t如果要unordered_set与自定义类一起使用，是否需要定义转换函数 (to )？有没有办法避免编写自己的哈希函数而只使用默认值？

4

2 回答 2

14

如果您不指定自己的哈希函子作为模板参数，它将默认为std::hash<MyClass>，除非您定义它，否则它不存在。

最好定义您自己的std::hash内部命名空间专业化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>而无需进一步的模板参数。

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.

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;
}
于 2012-11-21T04:06:07.587 回答
3

I'd like to expand on the answer given by jogojapan. As mentioned in a comment by CashCow on that answer, you also have to either overload the equality comparison operator (operator==) for MyClass or define a separate comparison function and provide it to the unordered_set. Otherwise, you will get another error message. For example, VS 2013 throws:

error C2678: binary '==' : no operator found which takes a left-hand operand of type 'const MyClass' (or there is no acceptable conversion)

Moreover, you can use lambda expressions instead of defining the hash and comparison functions. If you don't want to use Boost, then you can also handcraft a hash function. I understand, that you want to use some default function, but a compiler doesn't know how to calculate a meaningful hash for a custom class. However, you can use std::hash for the members of your class. If you put everything together, then your code could be written as follows:

class MyClass {
public:
    int i;
    double d;
    std::string s;
};

int main() {
    auto hash = [](const MyClass& mc){
        return (std::hash<int>()(mc.i) * 31 + std::hash<double>()(mc.d)) * 31 + std::hash<std::string>()(mc.s);
    };
    auto equal = [](const MyClass& mc1, const MyClass& mc2){
        return mc1.i == mc2.i && mc1.d == mc2.d && mc1.s == mc2.s;
    };
    std::unordered_set<MyClass, decltype(hash), decltype(equal)> mySet(8, hash, equal);

    return 0;
}

Code on Ideone

于 2019-02-15T15:20:44.413 回答