Алгоритмы стандартной библиотеки

Почти всё, что вы собираетесь написать циклом, уже написано. Подключается одним #include <algorithm>, часть — из <numeric>. С bits/stdc++.h не нужно и этого.

Все функции работают с полуинтервалом: первый итератор включается, последний — нет. a.begin(), a.end() — весь контейнер, a.begin() + 2, a.begin() + 5 — элементы с индексами 2, 3, 4.

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

int smallest = *min_element(a.begin(), a.end());
int position = min_element(a.begin(), a.end()) - a.begin();
auto [lo, hi] = minmax_element(a.begin(), a.end());   // за один проход

Возвращается итератор, а не значение: чтобы получить число, разыменуйте, чтобы получить индекс — вычтите begin(). При равных элементах min_element даёт первый из них, max_element — тоже первый.

Не путайте с min(a, b) и max(a, b) — те сравнивают два значения, а не ищут по диапазону. min({a, b, c}) со списком в фигурных скобках работает для любого количества.

unique

Функция с самым обманчивым названием. Она не удаляет повторы — она переставляет элементы так, что уникальные оказываются в начале, и возвращает итератор на первый «мусорный».

Работает только на отсортированном диапазоне: она сравнивает лишь соседей.

Канонический приём — сжатие массива до различных значений:

sort(a.begin(), a.end());
a.resize(unique(a.begin(), a.end()) - a.begin());

Для {5, 2, 8, 2, 5, 1, 8, 8} получится {1, 2, 5, 8} — четыре элемента. Что осталось в хвосте до resize, знать не нужно: там может оказаться что угодно, в том числе лишние копии.

Это основа сжатия координат: значения до $10^9$ заменяются на их номера в отсортированном списке различных, после чего под них можно завести массив.

vector<int> sorted = a;
sort(sorted.begin(), sorted.end());
sorted.resize(unique(sorted.begin(), sorted.end()) - sorted.begin());
for (int& value : a)
    value = lower_bound(sorted.begin(), sorted.end(), value) - sorted.begin();

iota

Заполняет диапазон подряд идущими числами. Живёт в <numeric>.

vector<int> order(n);
iota(order.begin(), order.end(), 0);   // 0, 1, 2, ..., n-1

Шаг всегда единица, изменить нельзя. Главное применение — массив индексов, который потом сортируется своим компаратором, и инициализация системы непересекающихся множеств.

accumulate

Свёртка диапазона в одно значение. Тоже <numeric>.

long long sum = accumulate(a.begin(), a.end(), 0LL);
long long product = accumulate(a.begin(), a.end(), 1LL, multiplies<long long>());

Третий аргумент задаёт тип результата. Написать 0 вместо 0LL при сумме больших чисел — классическое переполнение: аккумулятор будет int, даже если сам вектор из long long.

Четвёртым аргументом можно передать любую функцию двух аргументов, в том числе лямбду.

partial_sum

Префиксные суммы одной строкой:

vector<long long> prefix(a.size());
partial_sum(a.begin(), a.end(), prefix.begin());

Для {2, 4, 1, 3} получится {2, 6, 7, 10}. Приёмник должен быть достаточного размера — функция не расширяет его сама, а молча пишет столько, сколько влезло.

Обратная операция — adjacent_difference, разности соседних.

На практике префиксные суммы часто заводят со сдвигом на единицу (prefix[0] = 0), чтобы сумма на отрезке считалась как prefix[r + 1] - prefix[l] без особых случаев. Тогда пишут цикл вручную — так яснее.

Перестановки, повороты, переворот

reverse(a.begin(), a.end());                    // перевернуть
rotate(a.begin(), a.begin() + k, a.end());      // циклический сдвиг влево на k
sort(a.begin(), a.end());
do { /* обработать */ } while (next_permutation(a.begin(), a.end()));

У rotate средний аргумент — элемент, который станет первым. Для сдвига вправо на $k$ передайте a.end() - k.

next_permutation перебирает перестановки в лексикографическом порядке и возвращает false, вернувшись к началу. Поэтому массив нужно предварительно отсортировать, иначе часть перестановок не переберётся. Для трёх элементов цикл даёт ровно шесть итераций — удобная проверка, что всё написано верно.

Это основной инструмент для медленного решения в стресс-тестировании.

Поиск и подсчёт

int howMany = count(a.begin(), a.end(), x);
int matching = count_if(a.begin(), a.end(), [](int v) { return v % 2 == 0; });
bool present = find(a.begin(), a.end(), x) != a.end();
bool any = any_of(a.begin(), a.end(), [](int v) { return v < 0; });
bool all = all_of(a.begin(), a.end(), [](int v) { return v > 0; });

Все — за линию. Для отсортированного массива вместо count и find берите lower_bound и upper_bound: логарифм вместо линии.

Перемешивание

#include <random>
mt19937 rng(12345);
shuffle(a.begin(), a.end(), rng);

Старый random_shuffle удалён из стандарта — он использовал rand() и давал неравномерное распределение. Используйте shuffle с mt19937.

Сид стоит задавать явно: с фиксированным сидом падение воспроизводится, а это половина отладки. Когда нужна непредсказуемость (например, чтобы защитить быструю сортировку от подобранного теста), берут chrono::steady_clock::now().time_since_epoch().count().

Модификация

fill(a.begin(), a.end(), 0);
replace(a.begin(), a.end(), 5, 7);        // все пятёрки на семёрки
a.erase(remove(a.begin(), a.end(), 0), a.end());   // удалить все нули

Последняя строка — идиома «remove-erase». remove работает как unique: сдвигает нужное в начало и возвращает границу, а физически укорачивает контейнер уже erase. С C++20 то же самое пишется как erase(a, 0).

Стоит ли это учить

Почти всё перечисленное пишется циклом за три строки. Смысл не в экономии символов, а в том, что в цикле можно ошибиться, а в вызове accumulate — нет.

Исключения, которые руками писать не стоит вообще: sort, stable_sort, nth_element, lower_bound. Они не просто короче — они устроены сложнее, чем кажется, и своя версия почти наверняка окажется медленнее.