Какие требования к компаратору (предикату) для std::map?

Ключи в std::map<K, V, Compare> должны быть сравнимы с помощью функционального объекта Compare. Этот компаратор должен обеспечивать строгое слабое упорядочение (strict weak ordering).

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

1. Для любых ключей a и b должно выполняться ровно одно из: comp(a, b) == true, comp(b, a) == true или a и b эквивалентны (ни одно условие не истинно).
2. Отношение должно быть транзитивным: если comp(a, b) == true и comp(b, c) == true, то comp(a, c) == true.
3. Эквивалентность (отсутствие порядка) также должна быть транзитивной.

Стандартный компаратор std::less<Key> использует operator<. Для пользовательских типов нужно обеспечить такое сравнение.

Примеры реализации:

#include <map>
#include <tuple>
#include <string>

// Способ 1: Перегрузка operator< для типа ключа (наиболее частый)
struct Person {
    std::string name;
    int id;
    // Определяем порядок: сначала по name, затем по id
    bool operator<(const Person& other) const {
        return std::tie(name, id) < std::tie(other.name, other.id);
    }
};
// Теперь можно использовать std::map<Person, Value> без явного указания компаратора.

// Способ 2: Пользовательский функтор-компаратор
struct CaseInsensitiveCompare {
    bool operator()(const std::string& a, const std::string& b) const {
        // Сравнение строк без учета регистра
        return std::lexicographical_compare(
            a.begin(), a.end(),
            b.begin(), b.end(),
            [](char c1, char c2) { return std::tolower(c1) < std::tolower(c2); }
        );
    }
};
// Использование с явным указанием компаратора
std::map<std::string, int, CaseInsensitiveCompare> case_insensitive_map;

// Способ 3: Лямбда-функция (начиная с C++20 для конструктора map)
auto cmp = [](int a, int b) { return a > b; }; // Порядок по убыванию
std::map<int, std::string, decltype(cmp)> descending_map(cmp);

Важно: Несоблюдение строгого слабого упорядочения (например, использование operator<=) ведет к неопределенному поведению.