Компараторы и лямбды

Сортировка по умолчанию идёт по возрастанию. Всё остальное — по убыванию, по второму полю, по модулю, по частоте — задаётся компаратором.

Лямбда за минуту

Лямбда — функция, записанная прямо на месте использования.

sort(a.begin(), a.end(), [](int x, int y) { return x > y; });

Разбор по частям: [] — что захватить из окружения, (int x, int y) — аргументы, { ... } — тело. Тип возвращаемого значения выводится сам; если нужно указать явно, пишут -> bool перед телом.

Отдельную функцию писать не запрещено, просто длиннее:

bool byDescending(int x, int y) { return x > y; }
sort(a.begin(), a.end(), byDescending);

Захват

В квадратных скобках указывается, что лямбда видит снаружи.

запись	смысл
[]	ничего — только аргументы
[&]	всё по ссылке
[=]	всё по значению (копия)
[&a]	только a, по ссылке
[a]	только a, копией

Типичный случай — сортировка индексов по значениям чужого массива:

vector<int> order(n);
iota(order.begin(), order.end(), 0);        // 0, 1, 2, ...
sort(order.begin(), order.end(),
     [&](int i, int j) { return a[i] < a[j]; });

Получили порядок индексов, при котором a возрастает, не трогая сам a. Приём нужен, когда исходный порядок ещё пригодится.

В олимпиадном коде обычно пишут [&] и не думают. В большом проекте так делать не стоит: захват по ссылке живёт, пока живы переменные, и лямбда, пережившая их, обращается к освобождённой памяти.

Рекурсивная лямбда

Лямбда не знает своего имени, поэтому обычная рекурсия в ней не работает. Обходной путь до C++23 — передавать себя аргументом:

auto dfs = [&](auto&& self, int v, int parent) -> void {
    for (int to : graph[v])
        if (to != parent) self(self, to, v);
};
dfs(dfs, 0, -1);

Тип возвращаемого значения тут указывать обязательно — сам он не выведется. С C++23 появился this auto&& self, и передавать вручную больше не нужно.

Зачем вообще: лямбда видит все локальные переменные через [&], и не приходится тащить массивы в глобальную область или передавать их параметрами.

Строгий порядок — не рекомендация

Компаратор обязан задавать строгий порядок. На практике это значит: comp(x, x) всегда ложно, и если comp(x, y) истинно, то comp(y, x) ложно.

Нарушение выглядит невинно:

sort(a.begin(), a.end(), [](int x, int y) { return x <= y; });   // так нельзя

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

Проверено на GCC: vector<int> a(100000, 7) плюс такой компаратор — segmentation fault. Собранная с -D_GLIBCXX_DEBUG та же программа сообщает внятно:

Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).

Ещё один флаг в пользу того, чтобы держать санитайзеры под рукой.

Сравнение по нескольким полям надёжнее всего писать через tie:

sort(v.begin(), v.end(), [](const Person& a, const Person& b) {
    return tie(a.grade, a.name) < tie(b.grade, b.name);
});

Кортежи сравниваются лексикографически и строго — нарушить порядок здесь невозможно.

Частая задача «по одному полю возрастая, по другому убывая» решается минусом или перестановкой сторон:

return tie(a.grade, b.score) < tie(b.grade, a.score);   // grade вверх, score вниз

Готовые компараторы

Для убывания лямбда не нужна:

sort(a.begin(), a.end(), greater<int>());   // или greater<>() с C++14
sort(a.rbegin(), a.rend());                 // то же самое через обратные итераторы

Второй вариант короче, но обратные итераторы легко перепутать. Третий путь — отсортировать обычно и вызвать reverse: стоит линию поверх $n \log n$, то есть практически ничего.

Компаратор для контейнера

У sort компаратор — аргумент, у set, map и priority_queue — часть типа:

set<int, greater<int>> descending;                       // множество по убыванию
priority_queue<int, vector<int>, greater<int>> minHeap;   // куча минимума

Запись priority_queue неудобна и запоминается плохо, но нужна постоянно: по умолчанию куча выдаёт максимум, а в алгоритме Дейкстры и почти везде ещё нужен минимум.

Свой компаратор для контейнера — структура с operator():

struct ByLength {
    bool operator()(const string& a, const string& b) const {
        if (a.size() != b.size()) return a.size() < b.size();
        return a < b;
    }
};
set<string, ByLength> words;

Сравнение по длине, а при равной длине — лексикографически. Вторая строка обязательна: без неё две строки одинаковой длины считались бы равными, и set оставил бы только одну.

Через tie это записать не выйдет: tie принимает ссылки, а a.size() — временное значение, и код не скомпилируется. Здесь нужен либо явный if, либо make_tuple с копированием.

Это же и есть ответ на вопрос, зачем структуре operator(): объект с ним ведёт себя как функция, и его можно передать туда, где ждут функцию, — но, в отличие от функции, он может хранить состояние.