хеш-функция unordered_set

Question

хеш-функция unordered_set

Я использую std::unordered_set впервые и возник вопрос по хеш-функции. Насколько я понимаю, если вы не укажете хеш-функцию, по умолчанию будет использоваться std :: hash.

У меня есть член mySet в одном из моих классов:

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

Когда я пытаюсь собрать, я получаю сообщение об ошибке:

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

Нужно ли определять функцию преобразования (в size_t), если вы хотите использовать unordered_set с пользовательским классом? Есть ли способ избежать написания вашей собственной хэш-функции и просто использовать по умолчанию?

7

c++unordered-set

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Если вы не укажете свой собственный хеш-функтор в качестве аргумента шаблона, по умолчанию он будет 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> без необходимости дополнительных аргументов шаблона.

Вы не указали, что MyClass выглядит как внутри, но типичная ситуация заключается в том, что ваш пользовательский тип просто состоит из нескольких членов простого типа, для которых существует хеш-функция по умолчанию. В этом случае вам, вероятно, понадобится объединить значения хеш-функции для отдельных типов в значение хеш-функции для всей комбинации. Библиотека Boost предоставляет функцию под названием hash_combine для этого. Конечно, нет гарантии, что он будет работать хорошо в вашем конкретном случае (это зависит от распределения значений данных и вероятности коллизий), но он обеспечивает хорошую и простую в использовании отправную точку.

Вот пример того, как его использовать, предполагая, MyClass состоит из двух строковых членов:

#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;
}

12