Unordered_map с пользовательским классом в качестве ключа [дубликат]

Чтобы иметь возможность использовать std::unordered_map (или один из других неупорядоченных ассоциативных контейнеров) с пользовательским ключом, вам необходимо определить две вещи:

1. Хеш-функция ; это должен быть класс, который переопределяет operator() и вычисляет хэш-значение, заданное объектом типа ключа. Один особенно прямой способ сделать это - специализировать шаблон std::hash для вашего ключевого типа.
2. Функция сравнения для равенства; это необходимо, потому что хеш не может полагаться на то, что хеш-функция всегда будет предоставлять уникальное значение хэша для каждого отдельного ключа (т. е. он должен иметь возможность иметь дело с коллизиями), поэтому ему нужен способ сравнения двух заданных ключей для точного соответствия. Вы можете реализовать это либо как класс, который переопределяет operator(), либо как специализацию std::equal, или & ndash; самый легкий из всех & ndash; перегружая operator==() для вашего типа ключа (как вы уже сделали).

Трудность с хеш-функцией заключается в том, что если ваш тип ключа состоит из нескольких членов, вы обычно будете иметь хэш функция вычисляет значения хэша для отдельных членов, а затем каким-то образом объединяет их в одно значение хэша для всего объекта. Для хорошей производительности (т. Е. Нескольких столкновений) вы должны тщательно подумать о том, как объединить отдельные хэш-значения, чтобы вы не слишком часто получали одинаковый вывод для разных объектов.

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

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

Вот простая хеш-функция (адаптированная из той, которая используется в примере cppreference для пользовательских хеш-функций ):

namespace std {

  template <>
  struct hash<Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::size_t;
      using std::hash;
      using std::string;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
    }
  };

}

При этом вы можете создать экземпляр std::unordered_map для ключевого типа:

int main()
{
  std::unordered_map<Key,std::string> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}

Он будет автоматически использовать std::hash<Key>, как определено выше для вычислений значений хэш-функции и operator==, определенных как функция-член Key для проверок равенства.

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

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
    using std::size_t;
    using std::hash;
    using std::string;

    return ((hash<string>()(k.first)
             ^ (hash<string>()(k.second) << 1)) >> 1)
             ^ (hash<int>()(k.third) << 1);
  }
};

int main()
{
  std::unordered_map<Key,std::string,KeyHasher> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}

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

может быть трудным; метод XOR / бит-сдвига выше, вероятно, не плохой старт. Для немного лучшего начала вы можете использовать шаблон функции hash_value и hash_combine в библиотеке Boost. Первый действует аналогично std::hash для стандартных типов (в последнее время также включает кортежи и другие полезные стандартные типы); последний помогает вам объединить отдельные хэш-значения в один. Ниже приведена перепись хэш-функции, использующей вспомогательные функции Boost:

#include <boost/functional/hash.hpp>

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
      using boost::hash_value;
      using boost::hash_combine;

      // Start with a hash value of 0    .
      std::size_t seed = 0;

      // Modify 'seed' by XORing and bit-shifting in
      // one member of 'Key' after the other:
      hash_combine(seed,hash_value(k.first));
      hash_combine(seed,hash_value(k.second));
      hash_combine(seed,hash_value(k.third));

      // Return the result.
      return seed;
  }
};

И вот переписывание, которое не использует boost, но использует хороший метод объединения хэшей:

namespace std
{
    template <>
    struct hash<Key>
    {
        size_t operator()( const Key& k ) const
        {
            // Compute individual hash values for first, second and third
            // http://stackoverflow.com/a/1646913/126995
            size_t res = 17;
            res = res * 31 + hash<string>()( k.first );
            res = res * 31 + hash<string>()( k.second );
            res = res * 31 + hash<int>()( k.third );
            return res;
        }
    };
}