Что требуется для использования структуры в качестве ключа unordered_map

1️⃣ Как кратко ответить

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

2️⃣ Подробное объяснение темы

std::unordered_map — это контейнер, который хранит пары ключ-значение и обеспечивает быстрый доступ к значениям по ключу. В отличие от std::map, который использует бинарное дерево, std::unordered_map использует хеш-таблицу для хранения данных. Это позволяет выполнять операции поиска, вставки и удаления за амортизированное постоянное время.

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

Пример

Рассмотрим пример, где мы хотим использовать структуру Point в качестве ключа в std::unordered_map.

#include <iostream>
#include <unordered_map>
​
// Определяем структуру Point
struct Point {
    int x;
    int y;
​
    // Перегружаем оператор == для сравнения двух объектов Point
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};
​
// Определяем хеш-функцию для структуры Point
struct PointHash {
    std::size_t operator()(const Point& p) const {
        // Используем простую хеш-функцию, комбинируя хеши x и y
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};
​
int main() {
    // Создаем unordered_map с ключами типа Point
    std::unordered_map<Point, std::string, PointHash> pointMap;
​
    // Добавляем элементы в map
    pointMap[{1, 2}] = "Point A";
    pointMap[{3, 4}] = "Point B";
​
    // Доступ к элементам
    std::cout << "Point (1, 2): " << pointMap[{1, 2}] << std::endl;
    std::cout << "Point (3, 4): " << pointMap[{3, 4}] << std::endl;
​
    return 0;
}

Объяснение кода

1. Структура Point:

   • Содержит два целочисленных поля x и y.
   • Перегружен оператор ==, который сравнивает два объекта Point по их координатам. Это необходимо для того, чтобы std::unordered_map мог корректно определять, равны ли два ключа.

2. Хеш-функция PointHash:

   • Определяет оператор (), который принимает объект Point и возвращает std::size_t — хеш-код для этого объекта.
   • Использует стандартные хеш-функции для целых чисел std::hash<int>() и комбинирует хеши x и y с помощью операции XOR и сдвига. Это простая, но эффективная техника для создания уникального хеша.

3. Использование std::unordered_map:

   • Объявляется unordered_map с ключами типа Point и значениями типа std::string.
   • Указывается PointHash как третий параметр шаблона, чтобы unordered_map использовал нашу пользовательскую хеш-функцию.
   • Добавляются элементы в map и осуществляется доступ к ним по ключу.

Таким образом, для использования структуры в качестве ключа в std::unordered_map необходимо определить, как сравнивать и хешировать объекты этой структуры. Это позволяет контейнеру эффективно управлять элементами и обеспечивать быстрый доступ к данным.