Как происходит сравнение в std::unordered_map, если ключ является объектом

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

В std::unordered_map сравнение ключей осуществляется с помощью функции хеширования и функции сравнения на равенство. Если ключ является объектом, необходимо предоставить специализацию std::hash для вычисления хеш-кода и перегрузить оператор == или предоставить функцию сравнения для проверки равенства объектов.

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

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

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

1. Функция хеширования:

   • По умолчанию std::unordered_map использует std::hash для вычисления хеш-кода ключа. Если ключ является пользовательским объектом, необходимо предоставить специализацию std::hash для этого типа.
   • Специализация std::hash должна быть определена в пространстве имен std и должна содержать оператор (), который принимает объект ключа и возвращает std::size_t — хеш-код.

2. Функция сравнения на равенство:

   • По умолчанию std::unordered_map использует оператор == для проверки равенства ключей. Если ключ является пользовательским объектом, необходимо перегрузить оператор == для этого типа.
   • Альтернативно, можно передать пользовательскую функцию сравнения в качестве третьего шаблонного параметра std::unordered_map.

Пример:

#include <iostream>
#include <unordered_map>
#include <string>
​
// Пользовательский класс
class Person {
public:
    std::string name;
    int age;
​
    Person(const std::string& name, int age) : name(name), age(age) {}
​
    // Перегрузка оператора == для сравнения объектов Person
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};
​
// Специализация std::hash для класса Person
namespace std {
    template <>
    struct hash<Person> {
        std::size_t operator()(const Person& p) const {
            // Простая хеш-функция, комбинирующая хеши имени и возраста
            return std::hash<std::string>()(p.name) ^ (std::hash<int>()(p.age) << 1);
        }
    };
}
​
int main() {
    // Создание unordered_map с ключами типа Person
    std::unordered_map<Person, std::string> people;
​
    // Вставка элементов
    people[Person("Alice", 30)] = "Engineer";
    people[Person("Bob", 25)] = "Designer";
​
    // Поиск элемента
    Person searchPerson("Alice", 30);
    if (people.find(searchPerson) != people.end()) {
        std::cout << "Found: " << people[searchPerson] << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
​
    return 0;
}

В этом примере:

• Класс Person используется в качестве ключа в std::unordered_map.
• Перегружен оператор == для сравнения объектов Person.
• Определена специализация std::hash для класса Person, которая вычисляет хеш-код на основе имени и возраста.
• std::unordered_map использует эти определения для управления объектами Person в хеш-таблице.