Циклы, которые не нужно писать
На предыдущей странице вы видели, что каждый контейнер выдаёт итераторы - лёгкие курсоры с begin() и end(). Именно ради этой абстракции и существуют стандартные алгоритмы. Вместо того чтобы каждый раз писать обычный цикл for, когда нужно найти, посчитать или преобразовать данные, вы вызываете именованную функцию из <algorithm> и передаёте ей диапазон.
Диапазон - это всего лишь два итератора: откуда начинать и на единицу дальше того, где остановиться. Поскольку каждый алгоритм говорит на одном и том же языке итераторов, один и тот же find работает с vector, string или обычным массивом.
Шаблон, который стоит усвоить: алгоритм поиска возвращает итератор end(), чтобы обозначить «ничего не найдено». Всегда сравнивайте результат с end() перед разыменованием - разыменование end() является неопределённым поведением.
Подсчёт и проверка с помощью предикатов
Многие алгоритмы принимают предикат - функцию (обычно лямбду), которая возвращает bool для каждого элемента. count_if считает совпадения; all_of, any_of и none_of отвечают на вопросы «да/нет» обо всём диапазоне.
std::count (без _if) - более простой родственник, который считает точное значение, а не условие. Переходите к версиям с предикатом, как только ваша проверка становится «всё, что подходит под правило», а не «именно это значение».
Преобразование и свёртка диапазона
Две рабочие лошадки покрывают большую часть обработки данных: std::transform отображает каждый элемент через функцию, а std::accumulate (из <numeric>, а не из <algorithm>) сворачивает диапазон до единственного значения.
transform записывает свои результаты через выходной итератор. Распространённая и опасная ошибка - направить вывод в пустой vector: алгоритм предполагает, что место уже есть, и пишет за концом. Либо заранее задайте размер приёмника, либо используйте back_inserter, чтобы каждый результат добавлялся через push_back.
accumulate начинает с начального значения и комбинирует элементы слева направо. Тип начального значения имеет значение: передайте 0 (это int), и сумма будет вычисляться в int, что может привести к переполнению или усечению.
Если бы вы написали accumulate(prices.begin(), prices.end(), 0) с затравкой int, каждое сложение происходило бы в int и копейки бы исчезли. Тип затравки незаметно определяет тип результата.
Идиома erase-remove
Вот подводный камень, который удивляет всех. std::remove не удаляет ничего из контейнера. У алгоритмов есть только итераторы, поэтому они не могут изменить размер контейнера - они даже не знают, что контейнер вообще существует. На самом деле remove перемещает все сохраняемые элементы к началу, оставляя хвост в неопределённом состоянии, и возвращает итератор на новый логический конец.
// один remove оставляет размер неизменным - вот в чём баг:
remove(v.begin(), v.end(), 0); // возвращает итератор, который вы проигнорировали
// v всё ещё имеет исходный размер; хвост - мусор
Чтобы по-настоящему удалить элементы, вы сочетаете remove с erase контейнера, поэтому это и называется идиомой erase-remove:
Используйте remove_if для предиката вместо точного значения. В C++20 можно полностью обойтись без этого танца с помощью свободных функций std::erase / std::erase_if, которые делают оба шага за вас: erase(v, 0);.
Итераторы переживают свою действительность на ваш страх и риск
Поскольку алгоритмы возвращают итераторы, эти итераторы подчиняются тем же правилам инвалидации, с которыми вы познакомились на предыдущей странице. Сохранение итератора, а затем изменение контейнера - push_back, вызывающий перевыделение памяти, или erase - может оставить сохранённый итератор повисшим, и его использование является неопределённым поведением.
auto it = find(v.begin(), v.end(), 16);
v.push_back(99); // может перевыделить хранилище v
cout << *it; // BUG: `it` теперь может указывать на освобождённую память
Безопасная привычка: используйте итератор, возвращённый алгоритмом, немедленно, до любой операции, которая может изменить размер или перевыделить контейнер. Если вам нужно изменить контейнер на основе результата, захватите вместо этого индекс (it - v.begin()), поскольку индексы переживают перевыделение.
Далее: сортировка
Теперь вы увидели поиск, подсчёт, преобразование и свёртку, но один алгоритм достаточно важен, чтобы заслужить отдельную страницу. std::sort переупорядочивает диапазон на месте, и как только данные отсортированы, открывается целое семейство более быстрых алгоритмов, работающих только на отсортированных данных (binary_search, lower_bound, equal_range). Дальше мы углубимся в сортировку: как задать собственный компаратор, в чём разница между sort и stable_sort, и каким правилам должна подчиняться ваша функция сравнения, чтобы избежать неопределённого поведения.
Часто задаваемые вопросы
Что такое заголовок <algorithm> в C++?
<algorithm> - это заголовок стандартной библиотеки, содержащий обобщённые функции, такие как std::find, std::sort, std::count_if и std::transform. Они работают над диапазонами, описанными парой итераторов (обычно begin() и end()), поэтому один и тот же алгоритм работает с vector, array, string или любым контейнером, предоставляющим итераторы.
Как проверить, существует ли значение в vector в C++?
Используйте std::find: auto it = find(v.begin(), v.end(), target);. Если it == v.end(), значения нет; иначе it указывает на первое совпадение. Чтобы проверить условие вместо точного значения, используйте std::any_of с предикатом.
Почему std::remove на самом деле не удаляет элементы из моего контейнера?
Алгоритмы видят только итераторы, а не контейнер, поэтому std::remove не может его уменьшить - он сдвигает сохраняемые элементы к началу и возвращает итератор на новый логический конец. Чтобы физически отбросить остаток, нужно дополнить его вызовом v.erase(...) (идиома erase-remove).
