Алгоритмы STL в C++: sort, find, transform и друзья на примерах

Зачем учить алгоритмы

Стандартная библиотека C++ содержит около сотни готовых алгоритмов в <algorithm> и <numeric>. Каждый написанный вами ручной цикл — это потенциальная ошибка границ, лишний код для ревью и место, где коллега споткнётся. std::sort или std::find читаются мгновенно: «сортируем», «ищем» — без разбора цикла.

#include <algorithm>
#include <numeric>
#include <vector>

std::vector<int> v = {5, 2, 8, 1, 9};
std::sort(v.begin(), v.end());           // 1 2 5 8 9
auto it = std::find(v.begin(), v.end(), 8);  // итератор на 8

Поиск и сравнение

// линейный поиск значения
auto it = std::find(v.begin(), v.end(), 8);

// поиск по условию
auto pos = std::find_if(v.begin(), v.end(), [](int x) { return x > 5; });

// подсчёт
int cnt = std::count(v.begin(), v.end(), 5);
auto big = std::count_if(v.begin(), v.end(), [](int x) { return x > 4; });

// все/хотя бы один/никто
bool allPos = std::all_of(v.begin(), v.end(), [](int x){ return x > 0; });
bool hasBig = std::any_of(v.begin(), v.end(), [](int x){ return x > 8; });
bool noZero = std::none_of(v.begin(), v.end(), [](int x){ return x == 0; });

std::find возвращает итератор или end() — привычный паттерн проверки if (it != v.end()).

Сортировка и бинарный поиск

std::sort(v.begin(), v.end());                           // по возрастанию
std::sort(v.begin(), v.end(), std::greater<int>());      // по убыванию
std::sort(v.begin(), v.end(), [](int a, int b){ return std::abs(a) < std::abs(b); });  // свой критерий

// устойчивая сортировка — порядок равных элементов сохраняется
std::stable_sort(v.begin(), v.end());

// частичная: топ-N без полной сортировки
std::partial_sort(v.begin(), v.begin() + 3, v.end());    // первые 3 — минимальные, отсортированы

// Nth элемент: топ-N в любом порядке — быстрее полной сортировки
std::nth_element(v.begin(), v.begin() + 3, v.end());

После сортировки доступны бинарные операции за O(log n):

bool has = std::binary_search(v.begin(), v.end(), 5);
auto lb = std::lower_bound(v.begin(), v.end(), 5);   // первая позиция не меньше 5
auto eq = std::equal_range(v.begin(), v.end(), 5);   // диапазон всех равных 5

Модификация коллекций

std::vector<int> v = {1,2,3,4,5,6}, out;

// копия по условию — фильтрация
std::copy_if(v.begin(), v.end(), std::back_inserter(out), [](int x){ return x % 2 == 0; });

// трансформация: элемент -> другой элемент
std::transform(v.begin(), v.end(), out.begin(), [](int x){ return x * x; });

// удаление по значению или условию (идиома erase-remove)
v.erase(std::remove(v.begin(), v.end(), 3), v.end());
v.erase(std::remove_if(v.begin(), v.end(), [](int x){ return x < 0; }), v.end());

// C++20 — короче:
std::erase(v, 3);
std::erase_if(v, [](int x){ return x < 0; });

Важно: remove/remove_if сами по себе не уменьшают контейнер — они сдвигают «хорошие» элементы в начало и возвращают итератор на начало «хвоста». Реальное удаление делает erase. Без пары v.erase(std::remove...) получите мусор в хвосте.

Аккумуляция и численные алгоритмы

#include <numeric>

int sum  = std::accumulate(v.begin(), v.end(), 0);                    // сумма
int prod = std::accumulate(v.begin(), v.end(), 1, std::multiplies<>()); // произведение

// с вложенной логикой
std::string joined = std::accumulate(v.begin(), v.end(), std::string(),
    [](std::string s, int x){ return s.empty() ? std::to_string(x) : s + "," + std::to_string(x); });

// частичные суммы: [1,2,3] -> [1,3,6]
std::partial_sum(v.begin(), v.end(), out.begin());

// соседние разности
std::adjacent_difference(v.begin(), v.end(), out.begin());

std::accumulate принимает начальное значение — оно же определяет тип результата: accumulate(v.begin(), v.end(), 0.0) даст double, а не int.

Минимум, максимум, куча

auto [mn, mx] = std::minmax_element(v.begin(), v.end());   // пара итераторов за один проход

// куча: максимум всегда в front
std::make_heap(v.begin(), v.end());
v.push_back(10); std::push_heap(v.begin(), v.end());   // добавление
std::pop_heap(v.begin(), v.end()); v.pop_back();        // удаление максимума

Ranges (C++20): алгоритмы без .begin()/.end()

#include <ranges>

std::sort(v);                                   // без итераторов
auto evens = v | std::views::filter([](int x){ return x % 2 == 0; })
              | std::views::transform([](int x){ return x * 10; })
              | std::views::take(3);
for (int x : evens) std::cout << x << ' ';      // ленивый пайплайн

Views ленивы — элементы обрабатываются по мере обхода, промежуточных векторов не создаётся.

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

remove без erase — «удаление», которое не удаляет.
Бинарный поиск в несортированном — binary_search молча вернёт ложь.
Модификация контейнера внутри алгоритма — инвалидация итераторов в середине прохода.
Начальное значение accumulate не того типа — теряете дробную часть или переполнение.
Забыть, что count/find линейные — для частых поисков нужен set/unordered_set.

Итог

Пятёрка на каждый день: sort, find/find_if, count_if, copy_if/remove_if (с erase), accumulate. Дальше — minmax_element, nth_element для топ-N, lower_bound для диапазонов, ranges для читаемых пайплайнов. Каждый алгоритм — это строчка вместо цикла: меньше кода, меньше багов, больше смысла.

Сложные примеры из жизни

Уникальные элементы и дубликаты

std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());   // убрать дубли
// теперь v — отсортированные уникальные

Разделить на две группы по условию

auto it = std::partition(v.begin(), v.end(), [](int x){ return x % 2 == 0; });
// [begin..it) — чётные, [it..end) — нечётные; порядок внутри не гарантирован

Перемешать

std::random_device rd;
std::mt19937 g(rd());
std::shuffle(v.begin(), v.end(), g);

Найти пересечение двух отсортированных

std::vector<int> common;
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                      std::back_inserter(common));

Строки через алгоритмы

std::string — контейнер char, все алгоритмы работают:

std::transform(s.begin(), s.end(), s.begin(), ::tolower);   // в нижний регистр
s.erase(std::remove(s.begin(), s.end(), ' '), s.end());      // убрать пробелы
auto words = std::count(s.begin(), s.end(), ' ') + 1;        // слова

Мини-проект: обработка логов

Возьмите файл логов и напишите: фильтрацию строк с «ERROR» через copy_if, группировку по коду ошибки через unordered_map, топ-10 самых частых через partial_sort или nth_element + подсчёт. Один файл — и вы увидите, как алгоритмы складываются в рабочую тулу.

Производительность алгоритмов

Алгоритмы написаны эффективно и оптимизируются компилятором лучше ручных циклов. std::sort — introsort (быстрый+куча+вставками), std::find — векторизуемый линейный обход, std::binary_search — кэш-дружественный на массиве. Замена алгоритма ручным циклом почти никогда не выигрывает — а читаемость теряет всегда.