Компаратор и strict weak ordering

1. Как читать comp(a, b) и почему это важно

Если вы только начинаете, кажется, что «сортировка — это просто: числа по возрастанию, строки по алфавиту, всё». Но как только у вас появляются структуры данных (например, пользователь с именем и возрастом), возникает вопрос: по какому полю сортировать? А если по двум полям? А если «по возрасту, а внутри возраста — по имени»? Именно в этот момент компаратор перестаёт быть «какой-то лямбдой» и становится контрактом, на котором держатся сортировка и быстрый поиск.

Представьте, что вы дали библиотеке STL компаратор, который иногда «передумывает». Это как попросить двух людей сортировать папки, но одному дать правило «по алфавиту», а второму «по длине названия», и периодически менять им инструкции. Они честно рассортируют… но вы потом ничего не найдёте.

В рамках курса мы будем развивать маленькое консольное приложение «Справочник контактов»: храним контакты, сортируем по разным ключам, а на следующей лекции будем искать в отсортированных данных бинарным поиском.

Что такое компаратор: «кто раньше в очереди?»

Компаратор в STL — это функция (или объект-функтор), которую можно вызвать как comp(a, b) и получить bool. Смысл строго такой: comp(a, b) == true означает, что элемент a должен идти раньше элемента b в выбранном порядке.

Очень важно: компаратор — это не «условие фильтрации» и не «равенство». Это именно правило порядка.

Вот минимальный пример: сортируем числа по убыванию (вместо стандартного «по возрастанию»):

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{5, 1, 4, 1, 3};

    std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });

    for (int x : v) std::cout << x << ' ';
    std::cout << '\n'; // 5 4 3 1 1
}

Здесь a > b читается как «a раньше, если он больше».

Почему компаратор должен быть строгим

Сейчас будет один из самых частых багов дня: студент думает «ну я хочу по возрастанию, значит a <= b». Логика человеческая, но для сортировки — опасная.

Строгость означает, что элемент не может быть «строго раньше самого себя». То есть для любого x обязано быть:

comp(x, x) == false

Если вы пишете <=, то для любого x получится comp(x, x) == true, а это ломает контракт порядка. А дальше начинается магия уровня «я не знаю, что делает std::sort, но он точно злится».

Мини‑пример плохого компаратора:

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v{3, 1, 2};

    auto bad = [](int a, int b) { return a <= b; }; // плохо
    std::sort(v.begin(), v.end(), bad);
}

Это тот случай, когда код может скомпилироваться, но вы сами подписали бумагу «разрешаю неопределённое поведение моей логики». Не обязательно UB языка, но результат — не надёжен.

Правильный вариант:

auto good = [](int a, int b) { return a < b; }; // хорошо

Эквивалентность через компаратор

Дальше тонкость, которая очень пригодится для бинарного поиска (и вообще для понимания сортировки по ключу).

В алгоритмах порядка есть идея: элементы могут быть эквивалентны по компаратору. Это не всегда то же самое, что a == b.

Два элемента считаются эквивалентными (в смысле выбранного порядка), если:

!comp(a, b) && !comp(b, a)

То есть ни один не должен идти раньше другого.

Например, если вы сортируете людей только по возрасту, то люди одного возраста будут эквивалентны по компаратору — даже если у них разные имена.

Это нормально, но из этого вытекает практический эффект: std::sort не обещает сохранять порядок внутри «эквивалентной группы», а std::stable_sort — обещает.

3. Strict weak ordering человеческим языком

Термин strict weak ordering звучит как заклинание, но по сути это просто набор требований к компаратору, чтобы алгоритмы сортировки и бинарного поиска работали корректно.

В стандарте C++ даже есть concept strict_weak_order (как формальное имя этой идеи).

Для нас важно понять требования на уровне здравого смысла. Компаратор должен вести себя так, будто он задаёт «нормальный порядок»:

Небольшая аналогия: это как очередь в столовой. Если Петя «раньше» Маши, Маша «раньше» Вани, но Петя вдруг «после» Вани — очередь превращается в хаос, и никто не понимает, кто за кем.

4. Пример: «Справочник контактов» и tie-breaker

Модель данных

Чтобы не зависнуть в абстракциях, введём модель данных. Контакт — это id, name, age. И мы хотим сортировать «по возрасту, а если возраст одинаковый — по имени». Это называется tie-breaker: вторичный ключ, который «разруливает ничью».

#include <string>

struct Contact {
    int id{};
    std::string name;
    int age{};
};

Компаратор по двум полям

Теперь компаратор:

#include <string>

bool byAgeThenName(const Contact& a, const Contact& b) {
    if (a.age != b.age) return a.age < b.age;
    return a.name < b.name;
}

Обратите внимание: мы не пишем <= нигде. Мы задаём правило «строго раньше».

И теперь сортировка:

#include <algorithm>
#include <vector>

void sortContacts(std::vector<Contact>& contacts) {
    std::sort(contacts.begin(), contacts.end(), byAgeThenName);
}

Такой компаратор обычно «дружит» и с сортировкой, и с бинарным поиском, потому что он действительно задаёт порядок.

Почему «сравнение через вычитание» — плохая привычка

Иногда можно увидеть такой стиль:

return (a.age - b.age) < 0;

На маленьких числах кажется, что всё нормально, но в общем случае это риск переполнения (особенно если типы шире/уже, или если вы сортируете по long long, или если ключ может быть около границ диапазона).

Правильнее и безопаснее:

return a.age < b.age;

Это не «медленнее» в практическом смысле, зато гораздо надёжнее и читаемее.

Компаратор не должен «передумывать»

Ещё один класс ошибок — компаратор зависит от внешней переменной, которая меняется во время работы алгоритма, или (что ещё веселее) внутри компаратора.

Сама по себе идея «компаратор зависит от режима сортировки» нормальная, если режим фиксирован на момент сортировки. Но если вы сделали так, что режим поменялся между сортировкой и поиском — вы сломали главный принцип лекции.

Пример: мы хотим уметь сортировать либо по имени, либо по возрасту:

enum class SortMode { ByName, ByAgeThenName };

Компаратор, который «читает режим»:

#include <string>

struct ContactLess {
    SortMode mode{SortMode::ByAgeThenName};

    bool operator()(const Contact& a, const Contact& b) const {
        if (mode == SortMode::ByName) return a.name < b.name;
        if (a.age != b.age) return a.age < b.age;
        return a.name < b.name;
    }
};

Здесь ключевое: mode должен оставаться одним и тем же, пока вы работаете с уже отсортированными данными.

Когда tie-breaker «спасает голову»

Если вы сортируете только по age, то все контакты одного возраста эквивалентны. Это не ошибка. Но иногда вам хочется, чтобы порядок был «полным» и предсказуемым: например, чтобы одинаковый возраст дальше сортировался по имени, а если имена совпали — по id.

Это не обязаловка для корректности std::sort, но часто полезно для ясности: меньше сюрпризов при выводе, проще тестировать, проще объяснять себе через неделю, что происходит.

Выглядит так:

auto comp = [](const Contact& a, const Contact& b) {
    if (a.age != b.age) return a.age < b.age;
    if (a.name != b.name) return a.name < b.name;
    return a.id < b.id;
};

Так вы уменьшаете «большие классы эквивалентности» и делаете порядок более детерминированным.

5. Один порядок для sort и для бинарного поиска

Главная идея: порядок обязан совпадать

Самая «дорогая» мысль дня: если вы отсортировали vector одним правилом, а искать в нём пытаетесь другим, вы получаете логически некорректную операцию.

Сортировка создаёт структуру данных: «вектор отсортирован по правилу X». Бинарный поиск (и lower_bound) — это алгоритмы, которые работают только если структура соответствует их ожиданиям: «диапазон отсортирован по тому же правилу X».

Если это не так, поиск может порой «находить не то», порой «не находить то, что есть», порой возвращать странные позиции вставки.

И самое неприятное: он может иногда работать «на ваших тестах», а потом ломаться на данных пользователя. То есть классическая проблема: «ну у меня же запускалось».

Мини‑демонстрация рассинхронизации

Давайте сделаем пример, который визуально объясняет проблему. У нас есть контакты:

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<Contact> v{{1, "Bob", 25}, {2, "Ann", 30}, {3, "Eve", 30}};

    auto byName = [](const Contact& a, const Contact& b) {
        return a.name < b.name;
    };

    std::sort(v.begin(), v.end(), byName);
    // Теперь v отсортирован ПО ИМЕНИ: Ann(30), Bob(25), Eve(30)

    for (const auto& c : v) std::cout << c.name << "(" << c.age << ") ";
    std::cout << '\n'; // Ann(30) Bob(25) Eve(30)
}

Если на следующем шаге вы попробуете делать бинарный поиск по возрасту (как будто вектор отсортирован по возрасту), вы используете алгоритм не по назначению. Он рассчитан на «возрастной порядок», а вы дали ему «алфавитный». Это примерно как искать книгу по автору в библиотеке, расставленной по цвету обложки.

Правильный паттерн: один comp переиспользуется везде

Чтобы не ошибаться, в реальном коде удобно делать так: вы создали компаратор (лямбду или функтор), положили его в переменную comp и используете везде, где нужен тот же порядок.

Это дисциплина, а не «красивый стиль».

#include <algorithm>
#include <vector>

int main() {
    std::vector<Contact> v{{1, "Bob", 25}, {2, "Ann", 30}, {3, "Eve", 30}};

    auto comp = [](const Contact& a, const Contact& b) {
        if (a.age != b.age) return a.age < b.age;
        return a.name < b.name;
    };

    std::sort(v.begin(), v.end(), comp);

    // В следующей лекции этим же comp мы будем вызывать lower_bound / binary_search.
}

Небольшая схема: почему несогласованность ломает поиск

flowchart TD
    A[Данные в vector<Contact>] --> B[sort по компаратору COMP]
    B --> C[vector отсортирован по COMP]
    C --> D[lower_bound / binary_search с компаратором ???]
    D -->|если ??? == COMP| E[Корректный результат]
    D -->|если ??? != COMP| F[Некорректный результат: может найти не то / не найти то, что есть]

Суть не в том, что «алгоритм плохой». Он хороший. Просто вы нарушили предусловие: «диапазон должен быть отсортирован по тому же правилу».

6. Мини‑проверки компаратора

Полную проверку strict weak ordering написать непросто (и алгоритмически дорого), но несколько «санитарных» проверок помогают поймать самые распространённые ошибки: <=, случайность, «оба раньше друг друга».

Например, проверим на маленьком наборе, что comp(x, x) всегда false:

#include <iostream>
#include <vector>

template <typename T, typename Comp>
void checkIrreflexive(const std::vector<T>& v, Comp comp) {
    for (const T& x : v) {
        if (comp(x, x)) std::cout << "BUG: comp(x,x) == true\n";
    }
}

И проверка «если a раньше b, то b не раньше a»:

#include <iostream>
#include <vector>

template <typename T, typename Comp>
void checkNoTwoWayOrder(const std::vector<T>& v, Comp comp) {
    for (const T& a : v) {
        for (const T& b : v) {
            if (comp(a, b) && comp(b, a)) {
                std::cout << "BUG: a<b and b<a simultaneously\n";
            }
        }
    }
}

Да, это квадратично и «не для продакшна», но как учебный диагностический приём — отлично. Иногда полезнее 20 минут такой проверки, чем 2 часа смотреть на «странную сортировку».

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

Ошибка №1: использовать <= или >= в компараторе.
Это выглядит логично, но ломает «строгость»: получается comp(x, x) == true. Сортировка перестаёт работать на корректном контракте, а вы получаете поведение из серии «иногда нормально, иногда странно». Если вам хочется «нестрого», почти всегда вы на самом деле хотите «строго, но с равенством отдельно», то есть a < b и отдельная логика при равенстве ключей.

Ошибка №2: сравнивать числа через вычитание (a.key - b.key).
На маленьких примерах это работает, а на реальных данных может дать переполнение и некорректный знак. В итоге компаратор становится нетранзитивным «на краях диапазона», и вы ловите баг, который редко воспроизводится. Лучше писать явное сравнение a.key < b.key: короче, понятнее, безопаснее.

Ошибка №3: компаратор зависит от меняющегося внешнего состояния.
Если компаратор «читает режим сортировки», это нормально только при условии, что режим фиксирован. Как только вы отсортировали одним режимом, а потом переключили режим и начали искать — вы нарушили согласованность порядка. В результате бинарный поиск может не находить существующие элементы.

Ошибка №4: сортировать одним компаратором, а искать другим.
Это главный риск дня. Даже если оба компаратора «кажутся разумными», они задают разные порядки. Бинарный поиск не угадывает ваши намерения, он работает по математическому контракту: «данные отсортированы по этому же правилу». Спасает простая дисциплина: один comp, переиспользуемый и в sort, и в lower_bound/binary_search.

Ошибка №5: забывать про эквивалентность по компаратору и не делать tie-breaker там, где он нужен по смыслу.
Если вы сортируете людей по возрасту и печатаете список, то внутри одного возраста порядок может быть «как получится» (для std::sort). Иногда это нормально, иногда пользователи начинают думать, что программа «прыгает». Если порядок внутри группы важен, либо используйте std::stable_sort, либо добавьте вторичный ключ (tie-breaker) в компаратор.