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

В стандартной библиотеке 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:

cpp

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

cpp