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

Question

Я использую 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 с пользовательским классом? Есть ли способ избежать написания вашей собственной хэш-функции и просто использовать по умолчанию?

Answer 1

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

Answer 2

Я хотел бы подробнее остановиться на ответе Джогоджапана. Как упомянуто в комментарии CashCow к этому ответу, вы также должны перегрузить оператор сравнения равенства (operator==) за MyClass или определить отдельную функцию сравнения и предоставить ее unordered_set, В противном случае вы получите другое сообщение об ошибке. Например, VS 2013 выбрасывает:

ошибка C2678: двоичный файл "==": не найден оператор, который принимает левый операнд типа "const MyClass" (или нет приемлемого преобразования)

Более того, вы можете использовать лямбда-выражения вместо определения хеш-функций и функций сравнения. Если вы не хотите использовать Boost, вы также можете создать хеш-функцию. Я понимаю, что вы хотите использовать некоторую функцию по умолчанию, но компилятор не знает, как вычислить значимый хэш для пользовательского класса. Тем не менее, вы можете использовать std::hash для членов вашего класса. Если вы соберете все воедино, то ваш код может быть написан следующим образом:

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

Код на Ideone