Что нужно сделать, чтобы хранить свою структуру в unordered_map?

Чтобы хранить структуру в std::unordered_map в качестве ключа, необходимо предоставить:

1. Функцию хеширования (hash function): Находит хеш-значение для экземпляра структуры.
2. Оператор сравнения на равенство (operator==): Сравнивает два экземпляра структуры на равенство.

Существует несколько способов предоставить эти элементы:

• Перегрузить operator== внутри структуры и специализировать std::hash для вашей структуры. Это наиболее распространенный и рекомендуемый подход.

  #include <unordered_map>
  #include <string>
  #include <functional>
  
  struct MyStruct {
      int id;
      std::string name;
  
      bool operator==(const MyStruct& other) const {
          return id == other.id && name == other.name;
      }
  };
  
  // Специализация std::hash для MyStruct
  namespace std {
      template <>
      struct hash<MyStruct> {
          size_t operator()(const MyStruct& obj) const {
              // Комбинируем хеши полей
              size_t h1 = hash<int>()(obj.id);
              size_t h2 = hash<string>()(obj.name);
              // Простой способ объединить хеши.
              // Более продвинутые методы используют битовые операции.
              return h1 ^ (h2 << 1);
          }
      };
  }
  
  // Пример использования в main
  int main() {
      std::unordered_map<MyStruct, int> my_map;
      MyStruct key1 = {1, "Alice"};
      MyStruct key2 = {2, "Bob"};
      MyStruct key3 = {1, "Alice"}; // Эквивалентен key1
  
      my_map[key1] = 10;
      my_map[key2] = 20;
  
      // Доступ по эквивалентному ключу
      if (my_map.count(key3)) {
          // my_map[key3] даст 10
      }
  
      return 0;
  }
  
  

• Предоставить функции хеширования и сравнения как отдельные параметры шаблона при объявлении unordered_map. Менее удобно, если вы часто используете структуру как ключ, так как нужно указывать типы компаратора и хешера при каждом объявлении контейнера.

  #include <unordered_map>
  #include <string>
  #include <functional>
  
  struct MyStruct {
      int id;
      std::string name;
  };
  
  // Отдельная функция хеширования
  struct MyStructHash {
      size_t operator()(const MyStruct& obj) const {
          size_t h1 = std::hash<int>()(obj.id);
          size_t h2 = std::hash<std::string>()(obj.name);
          return h1 ^ (h2 << 1);
      }
  };
  
  // Отдельная функция сравнения (или функтор)
  struct MyStructEqual {
      bool operator()(const MyStruct& lhs, const MyStruct& rhs) const {
          return lhs.id == rhs.id && lhs.name == rhs.name;
      }
  };
  
  // Пример использования в main
  int main() {
      std::unordered_map<MyStruct, int, MyStructHash, MyStructEqual> my_map;
      MyStruct key1 = {1, "Alice"};
      MyStruct key2 = {2, "Bob"};
  
      my_map[key1] = 10;
      my_map[key2] = 20;
  
      return 0;
  }
  
  

Важные моменты:

• Корректность хеш-функции: Для любых двух ключей a и b, если a == b, то hash(a) должно быть равно hash(b). Обратное не требуется (разные ключи могут иметь одинаковый хеш – коллизии).
• Качество хеш-функции: Хорошая хеш-функция равномерно распределяет хеш-значения для различных ключей, минимизируя коллизии и повышая производительность (O(1) в среднем).
• Константность: Операторы сравнения и хеш-функция должны быть const, так как они не должны изменять объект ключа.