Кастомные компараторы и predicate-функции в алгоритмах STL

Введение

Алгоритмы STL — sort, find_if, unique, lower_bound, контейнеры map/set — по умолчанию используют operator< или operator== для сравнения элементов. Но реальные задачи часто требуют сортировки по нестандартному критерию, поиска по сложному условию или упорядочивания структур, у которых нет естественного «меньше». Для этого STL предоставляет механизм кастомных компараторов и predicate-функций.

Концепция

Компаратор — бинарная функция (или функтор/лямбда), принимающая два элемента и возвращающая bool: «первый должен идти раньше второго?». Используется в sort, stable_sort, priority_queue, map, set.
Predicate — унарная (обычно) функция, возвращающая bool для одного элемента: «элемент удовлетворяет условию?». Используется в find_if, count_if, remove_if, partition, all_of/any_of/none_of.

Компаратор должен задавать строгий слабый порядок (strict weak ordering): он не должен говорить, что элемент меньше самого себя, и должен быть транзитивным. Нарушение этого требования — частая причина крашей или некорректной сортировки.

Пример кода

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

struct Task {
    std::string title;
    int priority;   // 1 - высший приоритет
    bool done;
};

int main() {
    std::vector<Task> tasks = {
        {"Fix crash", 1, false},
        {"Write docs", 3, false},
        {"Refactor module", 2, true},
        {"Update deps", 2, false},
        {"Review PR", 1, true}
    };

    // Кастомный компаратор: сортировка по приоритету, затем по статусу (незавершённые выше)
    std::sort(tasks.begin(), tasks.end(), [](const Task& a, const Task& b) {
        if (a.priority != b.priority) return a.priority < b.priority;
        return a.done < b.done; // false (0) < true (1) -> незавершённые раньше
    });

    std::cout << "Sorted tasks:n";
    for (const auto& t : tasks) {
        std::cout << "  [" << t.priority << "] " << t.title
                  << (t.done ? " (done)" : "") << "n";
    }

    // Predicate: найти первую незавершённую задачу с высоким приоритетом
    auto urgent = std::find_if(tasks.begin(), tasks.end(), [](const Task& t) {
        return !t.done && t.priority == 1;
    });
    if (urgent != tasks.end()) {
        std::cout << "Most urgent: " << urgent->title << "n";
    }

    // count_if: сколько задач ещё не выполнено
    auto pending = std::count_if(tasks.begin(), tasks.end(),
                                  [](const Task& t) { return !t.done; });
    std::cout << "Pending tasks: " << pending << "n";

    // Кастомный компаратор как тип для std::set (а не лямбда напрямую)
    struct ByPriority {
        bool operator()(const Task& a, const Task& b) const {
            return a.priority < b.priority;
        }
    };
    // multiset, т.к. компаратор не учитывает title -> возможны "равные" по порядку элементы
    std::multiset<Task, ByPriority> byPriority(tasks.begin(), tasks.end());
    std::cout << "By priority (multiset): ";
    for (const auto& t : byPriority) std::cout << t.title << "(" << t.priority << ") ";
    std::cout << "n";

    return 0;
}

Пояснения к коду

Лямбда-компаратор в std::sort реализует составной критерий: сначала по приоритету, затем (если приоритеты равны) — по статусу выполнения. Такой «тай-брейк» — стандартный паттерн многоуровневой сортировки, без необходимости писать operator< для самой структуры Task.

find_if и count_if принимают predicate — унарную функцию, которая для каждого элемента решает, подходит он или нет. Это избавляет от написания циклов for с ручной проверкой условия и явно документирует намерение через название алгоритма.

Пример с std::multiset<Task, ByPriority> показывает использование функтора (класса с operator()) как компаратора-типа, а не лямбды — это необходимо, когда компаратор нужно указать как шаблонный параметр контейнера (а не передать аргументом в вызов функции, как для sort). Контейнер выбран multiset, а не set, потому что компаратор ByPriority не различает задачи с одинаковым приоритетом — с точки зрения такого компаратора это «эквивалентные» элементы, и std::set отбросил бы дубликаты.

Подводные камни и советы

1. Компаратор обязан задавать строгий слабый порядок: для любого a, comp(a, a) должно быть false. Если в компараторе использовать <= вместо <, можно получить undefined behavior при сортировке (вплоть до краша в некоторых реализациях). 2. Не путайте предикат «равенства» с компаратором «меньше» — std::set/std::map определяют эквивалентность через компаратор (!comp(a,b) && !comp(b,a)), а не через operator==. Если нужна и сортировка, и явная проверка равенства — будьте внимательны, чтобы критерии совпадали по смыслу. 3. Лямбда vs функтор vs указатель на функцию: для алгоритмов (передаются как аргумент) удобны лямбды; для типов контейнеров (std::set<T, Comp>) нужен именованный тип компаратора — класс с operator() или decltype от лямбды (C++20 допускает использование лямбд как типа шаблонного параметра через decltype). 4. Помните о std::greater, std::less и других готовых функторах из <functional> — для простой обратной сортировки не нужно писать лямбду: std::sort(v.begin(), v.end(), std::greater<int>{}). 5. Делайте компараторы const-корректными и помечайте operator() как const, иначе компаратор не будет работать с константными контейнерами или в некоторых контекстах шаблонной магии STL.

================================================================================