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

Подсчёт, сумма, поиск и сортировка нужны почти в каждой программе. Писать для них цикл каждый раз — всё равно что каждый вечер выстругивать новую ложку вместо того, чтобы взять готовую из ящика. Такой ящик в C++ — заголовок <algorithm> с готовыми функциями. Диапазон элементов они получают двумя итераторами — 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
    }
}

Разберём программу по строкам:

1. std::count возвращает число элементов, равных третьему аргументу: двух троек.
2. std::accumulate из заголовка <numeric> складывает элементы и прибавляет их к начальному значению — третьему аргументу 0. Получается 19.
3. 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

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

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

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

Равные элементы std::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 требует строгого сравнения, поэтому вызов с <= — неопределённое поведение, хотя код компилируется без предупреждений. В задачах курса такой компаратор может остановить программу. Пишите a < b, а для порядка по убыванию — a > b.

Главное

• Функции <algorithm> получают диапазон двумя итераторами: begin() и end().
• Результат std::find сравнивают с end(), прежде чем читать элемент.
• Компаратор отвечает true, только если a стоит строго раньше b: пишите <, а не <=.
• std::stable_sort сохраняет порядок равных элементов, а std::sort — нет.