Как использовать unordered_set с пользовательскими типами?

Ответ 1

Стандартная библиотека содержит специализации std::hash<T> для основных типов, для указателей и для std::string (или, вернее, для всех специализаций std::basic_string).

К сожалению, библиотека не содержит следующую важную новую комбинацию из старой, которая является частью Boost и которую вы должны скопировать в свой код:

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

С помощью этой функции вы можете использовать пары хэша, кортежи, массивы и любой диапазон элементов, которые сами хешируются. Просмотрите источники Boost для многих примеров и полезных реализаций. И, очевидно, вы можете использовать эту функцию для создания хеш-функции для ваших собственных типов. Например, здесь хеширование пары:

template<typename S, typename T> struct pair_hash<std::pair<S, T>>
{
    inline std::size_t operator()(const std::pair<S, T> & v) const
    {
         std::size_t seed = 0;
         hash_combine(seed, v.first);
         hash_combine(seed, v.second);
         return seed;
    }
};

Помните, однако, что хэш-комбинирование не дает хороших хеш-значений. Результаты имеют очень плохие статистические качества (например, очень легко создавать хеш-коллизии). Хорошее хеширование должно быть в состоянии видеть все исходные биты ввода и не может быть учтено посредством частичных хэшей. (Вот почему в текущей стандартной библиотеке нет лучшего решения, никто не смог найти удовлетворительный дизайн.)

Ответ 2

Да, вам нужно написать собственную хэш-функцию. Это не так плохо, как кажется: если у вашего класса есть хешируемый член, который, как вы знаете, будет достаточно уникальным, вы можете просто вернуть хэш этого члена.

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