Алгоритмы STL и ranges: урок по C++ к собеседованию

Хороший C++-разработчик не пишет циклы там, где есть алгоритм: название алгоритма сразу говорит, что делает код, а реализация в библиотеке отлажена и быстра. На собесе часто просят переписать цикл через STL или объяснить, чем отличаются похожие алгоритмы.

Сортировка и порядок

std::sort: O(n log n) гарантированно (с C++11). В libstdc++ это introsort: быстрая сортировка, которая при слишком глубокой рекурсии переключается на пирамидальную, а маленькие куски досортировывает вставками. Не стабильна.
std::stable_sort: сохраняет порядок равных, O(n log n) при наличии доп. памяти (сортировка слиянием), иначе O(n log² n).
std::partial_sort(first, middle, last): упорядочивает только первые k, O(n log k).
std::nth_element(first, nth, last): ставит на позицию nth тот элемент, что стоял бы там после сортировки, слева не больше, справа не меньше. В среднем O(n): медиана, k-я статистика.

Компаратор обязан задавать строгий слабый порядок: comp(a, a) ложно, транзитивность. Компаратор с <= нарушает это требование, и std::sort может выйти за границы массива: это UB.

Поиск в отсортированном

lower_bound(x): первый элемент ≥ x; upper_bound(x): первый > x; equal_range оба сразу.
binary_search возвращает только bool.
Всё это partition_point с разными предикатами, требование одно: диапазон разбит предикатом (на практике отсортирован).

Модифицирующие и «удаляющие»

std::remove и std::remove_if ничего не удаляют: они сдвигают оставляемые элементы к началу и возвращают новый логический конец. Размер контейнера тот же, хвост в неуказанном состоянии. Идиома erase-remove:

v.erase(std::remove_if(v.begin(), v.end(), is_bad), v.end());
std::erase_if(v, is_bad);   // C++20, то же одной строкой

Так же устроен std::unique: убирает соседние дубликаты, поэтому сначала сортируют.

Другие полезные: partition и stable_partition (разделить по предикату), rotate (циклический сдвиг, основа «перетаскивания» элементов), reverse, next_permutation, transform, copy_if, fill, iota.

Числовые

<numeric>: accumulate, reduce (C++17, может переставлять операции и работать параллельно), partial_sum, inner_product, iota, gcd, lcm. Ловушка accumulate: тип результата определяется начальным значением. std::accumulate(v.begin(), v.end(), 0) для vector<double> считает в int и отбрасывает дробные части на каждом шаге.

Множества на отсортированных

set_union, set_intersection, set_difference, set_symmetric_difference, includes, merge работают за линейное время на отсортированных диапазонах и пишут результат через выходной итератор (std::back_inserter(out)).

Ranges (C++20)

std::ranges::sort(people, {}, &Person::age);           // проекция: сортировка по полю
auto adults = people | std::views::filter([](const Person& p) { return p.age >= 18; })
                     | std::views::transform(&Person::name);

Алгоритмы из std::ranges принимают весь контейнер и поддерживают проекции.
Представления (views) ленивы: ничего не вычисляется, пока по ним не итерируются, и они не владеют данными, поэтому не должны переживать контейнер.
Концепты дают понятные ошибки: попытка ranges::sort для std::list сразу скажет, что нужен random access.

Частые ошибки

Ждать стабильности от std::sort.
std::remove без erase.
std::unique на неотсортированных данных.
Компаратор <=.
std::sort для std::list (не компилируется, у списка свой sort).
accumulate с начальным значением неподходящего типа.

Что спросят на собесе

Как устроен std::sort, его сложность и стабильность.
nth_element против partial_sort против sort для top-k и медианы.
Почему remove не меняет размер.
Требования к компаратору.
Что дают ranges: проекции, представления, ленивость.

Алгоритмы STL и ranges