Есть ли хэш-функция по умолчанию для unordered_set пользовательского класса?

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

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

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

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

ошибка C2440: «приведение типа»: невозможно преобразовать из «const MyClass» в «size_t»

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


person user974967    schedule 21.11.2012    source источник
comment
Как вы ожидаете, будет ли хэш по умолчанию пользовательского типа?   -  person David Brown    schedule 21.11.2012
comment
Возможный дубликат Вставка в unordered_set с пользовательской хеш-функцией   -  person Ciro Santilli 新疆再教育营六四事件ۍ    schedule 07.01.2017


Ответы (2)


Если вы не укажете свой собственный хеш-функтор в качестве аргумента шаблона, по умолчанию он будет равен 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;
}
person jogojapan    schedule 21.11.2012
comment
Вместо создания специализации std::hash для MyClass кажется проще просто добавить функцию-член преобразования size_t, которая использует hash_combine для своих членов. Мой класс состоит из 7-8 примитивных типов, и я вызываю hash_combine для всех из них, а затем возвращаю начальное значение. - person user974967; 21.11.2012
comment
@user974967 user974967 Это работает для вас? Я был бы удивлен, если бы простого добавления оператора преобразования было достаточно, чтобы заставить работать неупорядоченный набор. В конце концов, он все равно попытается создать экземпляр std::hash<MyClass>. - person jogojapan; 21.11.2012
comment
@ user974967 Хорошо. Это сработает, если вы объявите набор как std::unordered_set<MyClass,std::hash<std::size_t>>. Я полагаю, что это возможное решение, но оно требует определения operator std::size_t(), что может означать нежелательные неявные преобразования в целое число в других частях кода. Я не рекомендую этого делать. - person jogojapan; 21.11.2012
comment
Я думаю, что я просто собираюсь пойти со своим собственным классом функторов. На самом деле это не так уж и сложно и намного чище, чем предоставление специализации для std::hash. Кажется, нет никакой выгоды в предоставлении специализации std::hash, кроме того, что вы можете создавать unordered_lists без необходимости указывать указатель на функтор/функцию. Я знаю, что вы просто отвечали на мой вопрос, потому что я спросил, могу ли я полагаться на значение по умолчанию, но в этом случае это просто много хлопот напрасно. Спасибо за информацию о hash_combine, вы меня реально спасли! - person user974967; 21.11.2012
comment
Конечно, определение собственного класса функторов — это, безусловно, нормально. (Хотя я не согласен с тем, что в создании специализации std::hash есть что-то нечистое.) Но я думаю, что вы правы, единственная выгода в специализации std::hash заключается в том, что тогда вы можете использовать аргумент шаблона по умолчанию. - person jogojapan; 21.11.2012
comment
Какая «проблема» со специализацией std::hash<>? Пользовательский хэш-функтор будет выглядеть на 90% одинаково... - person ildjarn; 25.11.2012
comment
Вам также необходимо перегрузить equal_to (или оператор ==) - person CashCow; 17.02.2014

Я хотел бы расширить ответ, данный jogojapan. Как упоминалось в комментарии пользователя 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

person honk    schedule 15.02.2019