sort, find, count, accumulate и лямбды

Подсчёт, сумма, поиск и сортировка нужны почти в каждой программе, и писать для них цикл каждый раз не обязательно. Заголовок (header) <algorithm> содержит готовые функции для таких задач. Они получают элементы как два итератора (iterators) — begin() и end():

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

int main() {
    std::vector<int> v{5, 3, 8, 3};
    std::cout << std::count(v.begin(), v.end(), 3) << ' '
              << std::accumulate(v.begin(), v.end(), 0) << '\n';  // 2 19
    std::sort(v.begin(), v.end());
    for (int x : v) {
        std::cout << x << ' ';  // 3 3 5 8
    }
}

std::count возвращает число элементов, равных третьему аргументу (argument). std::accumulate из заголовка <numeric> складывает элементы, начиная со значения 0.

std::sort переставляет элементы самого вектора по возрастанию и ничего не возвращает. Элементов остаётся столько же, обе тройки на месте. Сортировка работает за O(n log n), а count и accumulate — за O(n).

Поиск и предикаты

std::find возвращает итератор на первый элемент, равный значению, или end(), если такого нет. Поэтому результат сравнивают с end(), прежде чем читать элемент:

std::vector<int> v{5, 3, 8, 3};
auto it = std::find(v.begin(), v.end(), 8);
if (it != v.end()) {
    std::cout << *it << '\n';  // 8
}
auto big = std::count_if(v.begin(), v.end(), [](int x) { return x > 4; });
std::cout << big << '\n';  // 2

Предикат (predicate) — функция, которая получает элемент и возвращает bool. Его удобно записать лямбдой (lambda) прямо в вызове. std::count_if считает элементы, для которых предикат вернул true, а std::find_if находит первый такой элемент.

Свой порядок сортировки

Третий аргумент std::sort — компаратор (comparator): функция двух элементов, которая возвращает true, если a должен стоять раньше b. Без компаратора элементы сравниваются через <, а с компаратором [](int a, int b) { return a > b; } числа встанут по убыванию. Компаратор означает «строго раньше»: для равных элементов он возвращает false.

Равные элементы std::sort может переставить между собой. Стабильная сортировка (stable sort) std::stable_sort сохраняет их исходный порядок:

std::vector<std::string> words{"pear", "fig", "kiwi", "apple"};
auto shorter = [](const std::string& a, const std::string& b) {
    return a.size() < b.size();
};
std::stable_sort(words.begin(), words.end(), shorter);
for (const std::string& w : words) {
    std::cout << w << ' ';  // fig pear kiwi apple
}

Слова pear и kiwi одной длины, и pear стоит раньше, как в исходном векторе. После std::sort слово kiwi могло бы оказаться первым из двух.

Частая ошибка

В компараторе пишут <= вместо <:

std::vector<int> v{5, 3, 8, 3};
std::sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });  // ✗

Для двух равных троек такой компаратор отвечает, что каждая должна стоять раньше другой. std::sort требует строгого сравнения, поэтому вызов с <= — неопределённое поведение (undefined behavior), хотя код компилируется без предупреждений. В задачах курса такой компаратор может остановить программу. Пишите a < b, а для порядка по убыванию — a > b.