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

Требования к классам для использования в качестве ключа

Когда вы хотите использовать объект пользовательского класса как ключ в контейнерах типа std::map, std::unordered_map или в std::set, класс должен отвечать определённым требованиям.

Основные требования

Все контейнеры-ассоциативные массивы требуют возможности сравнивать ключи:

Для std::map и std::set (упорядоченные)

1. Оператор сравнения operator< — должен быть определён или указан компаратор

   • Класс должен реализовать bool operator<(const YourClass& other) const
   • Или предоставить пользовательский компаратор как шаблонный параметр
   • Оператор должен определять строгий слабый порядок (strict weak ordering)

2. Стабильность — результат сравнения не должен меняться во время жизни объекта

Для std::unordered_map и std::unordered_set (хеш-таблица)

1. Оператор хеширования — специализация std::hash<YourClass>

   • Реализуется как функтор или функция
   • Должна возвращать size_t
   • Инвариант: равные объекты должны давать одинаковый хеш

2. Оператор равенства operator==

   • Должен быть определён в классе
   • Должен быть логически согласован с хешем

Практический пример

struct Point {
    int x, y;
    
    // Для std::map/std::set
    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
    
    // Для std::unordered_map/std::unordered_set
    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<Point, std::string> orderedMap;  // Требует operator<
std::unordered_map<Point, std::string> hashMap;  // Требует operator== и std::hash

Критические свойства

Строгий слабый порядок (для упорядоченных контейнеров):

• Иррефлексивность: !(a < a)
• Асимметричность: если a < b, то !(b < a)
• Транзитивность: если a < b и b < c, то a < c
• Несравнимость транзитивна

Согласованность хеша и равенства:

• Если a == b, то hash(a) == hash(b)
• Обратное не требуется: разные объекты могут иметь одинаковый хеш (коллизия)

Рекомендации

1. Используйте значимые типы — ключи должны быть const-qualified или недорогими для копирования
2. Избегайте изменения ключей после вставки в контейнер
3. Для сложных типов — реализуйте хеш функцию с хорошим распределением
4. Документируйте семантику сравнения и хеширования

С++ 20 и позже

Можно использовать operator<=> (three-way comparison) для автоматической генерации всех операторов сравнения:

struct Point {
    int x, y;
    
    auto operator<=>(const Point&) const = default;
};

Это обеспечивает полную согласованность всех операций сравнения.