Каким требованиям должен удовлетворять оператор "меньше" для использования в std::sort?

Требования к оператору "меньше" для std::sort

Оператор сравнения "меньше" (<) для использования в std::sort должен удовлетворять нескольким строгим математическим требованиям, обеспечивающим корректность алгоритма сортировки.

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

1. Строгая слабая упорядоченность (Strict Weak Ordering)

Оператор < должен задавать отношение строгой слабой упорядоченности, что подразумевает четыре условия:

• Иррефлексивность: !(a < a) — элемент не может быть меньше сам себя
• Асимметричность: если a < b, то !(b < a)
• Транзитивность: если a < b и b < c, то a < c
• Транзитивность эквивалентности: если !(a < b) && !(b < a) и !(b < c) && !(c < a), то !(a < d) && !(d < a)

Последнее условие означает, что если элементы эквивалентны, то все элементы, эквивалентные одному из них, эквивалентны и второму.

2. Последовательность

Результат сравнения двух элементов не должен зависеть от контекста или других элементов массива. Сравнение a < b должно всегда давать одинаковый результат.

3. Отсутствие побочных эффектов

Оператор сравнения не должен модифицировать сравниваемые объекты или изменять состояние программы.

Пример правильной реализации

struct Person {
    int age;
    std::string name;
};

bool operator<(const Person& a, const Person& b) {

    if (a.age != b.age) {
        return a.age < b.age;
    }
    return a.name < b.name;
}

std::vector<Person> people = {{25, Bob}, {30, Alice}, {25, Alice}}; std::sort(people.begin(), people.end());

Типичные ошибки

❌ Неправильно: нарушает иррефлексивность bool operator<(const Person& a, const Person& b) {

    return a.age <= b.age;
}

❌ Неправильно: нарушает транзитивность bool operator<(const Person& a, const Person& b) {

    return std::abs(a.age - b.age) < 5;
}

Последствия нарушения требований

Если компаратор нарушает требования строгой слабой упорядоченности, std::sort может произвести неправильный порядок элементов, войти в бесконечный цикл, вызвать undefined behavior или привести к непредсказуемым результатам. Поэтому важно тщательно проверять логику компаратора перед использованием в алгоритмах сортировки.