Какими свойствами должен обладать объект, чтобы его можно было использовать в качестве ключа в ассоциативных контейнерах?

В стандартной библиотеке C++ для использования типа в качестве ключа в std::map или std::unordered_map он должен обладать следующими свойствами:

Для std::map (на основе красно-черного дерева):

• Сравнимость: Тип должен поддерживать слабое строгое упорядочивание (weak strict ordering), обычно реализуемое оператором <. Этот оператор < должен быть:
  • Иррефлексивным: x < x всегда ложно.
  • Транзитивным: Если f(x, y) и f(y, z) истинны, то f(x, z) тоже истинно (где f - отношение, например, <).
  • Асимметричным: Если x < y истинно, то y < x ложно.
  • Альтернативно, можно предоставить компаратор (например, лямбда-функцию или класс-функтор) при создании контейнера.

Для std::unordered_map (на основе хеш-таблицы):

• Хешируемость: Для типа должна быть определена хеш-функция, которая вычисляет значение типа std::size_t на основе объекта данного типа. Обычно это реализуется:
  • Наличием специализации шаблонного класса std::hash для данного типа.
  • Использованием встроенных хеш-функций для примитивных типов и указателей.
  • Для пользовательских типов часто требуется явно определить специализацию std::hash или предоставить хеш-функтор при создании контейнера.
• Сравнимость на равенство: Тип должен поддерживать определение равенства, обычно реализуемое оператором ==. Этот оператор должен быть:
  • Рефлексивным: x == x всегда истинно.
  • Симметричным: Если x == y истинно, то y == x тоже истинно.
  • Транзитивным: Если x == y и y == z истинны, то x == z тоже истинно.
  • Альтернативно, можно предоставить функцию сравнения на равенство (например, лямбда-функцию или класс-функтор) при создании контейнера.

Пример специализации std::hash:

#include <functional> // Для std::hash

struct Point {
    int x, y;

    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// Специализация std::hash для того, чтобы Point был хешируем
namespace std {
    template <>
    struct hash<Point> {
        size_t operator()(const Point& p) const {
            // Простая комбинированная хеш-функция
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}

Пример компаратора для std::map:

#include <map>

struct Point {
    int x, y;
};

struct PointCompare {
    bool operator()(const Point& a, const Point& b) const {
        if (a.x != b.x) {
            return a.x < b.x;
        }
        return a.y < b.y;
    }
};

// Создание map с пользовательским компаратором
// std::map<Point, int, PointCompare> my_map;