1. Агрегации диапазона: идея и контекст
Если вы писали хотя бы пару программ, вы точно делали вещи вроде «посчитать сумму», «найти минимальное», «найти максимальное». Обычно это начинается с невинного for, а заканчивается тем, что в одном месте вы забыли обработать пустой список, в другом перепутали типы, а в третьем — случайно сделали переполнение int. Агрегации STL — это набор алгоритмов, которые решают эти задачи в стандартизированном виде: коротко, читаемо и с едиными правилами.
Агрегация — это сведение «многих элементов» к «одному результату». Результат бывает разный: иногда это число (сумма, количество, общая длительность), иногда итератор (где лежит минимум), иногда пара итераторов (минимум и максимум). В этой лекции разберём три инструмента: std::accumulate для свёртки в значение и std::min_element / std::max_element / std::minmax_element для поиска экстремумов.
Чтобы примеры не висели в воздухе, продолжим наше учебное консольное приложение TaskBoard (список задач в std::vector). Пусть у задачи есть оценка времени и приоритет — как раз то, что приятно агрегировать.
Подготовка модели: задача в TaskBoard
Перед тем как «крутить алгоритмы», полезно договориться о данных. Даже если у вас в проекте модель уже богаче, нам достаточно минимума: название, приоритет и оценка времени. А ещё — флаг «выполнено», потому что статистика по выполненным/невыполненным часто нужна в реальных приложениях. И да: писать std:: — это не прихоть преподавателя, а нормальная дисциплина работы со стандартной библиотекой.
#include <string>
struct Task {
std::string title;
int priority = 0; // чем больше — тем важнее
int estimateMinutes = 0; // оценка времени в минутах
bool done = false;
};
Обратите внимание на две вещи. Во‑первых, поля инициализируются значениями по умолчанию: это снижает шанс «мусора» в данных. Во‑вторых, estimateMinutes — int: так проще в учебных примерах, но именно это решение позже заставит нас быть аккуратнее в accumulate, чтобы не переполниться на больших суммах.
2. std::accumulate: сворачиваем диапазон в одно значение
Когда вы впервые видите std::accumulate, он может показаться слегка странным: «почему сумма начинается не с нуля сама? почему я должен передавать init?». Но в этом как раз сила: вы контролируете начальное значение и тем самым контролируете тип результата. А ещё accumulate умеет не только суммировать, если дать ему свою операцию.
Форма самая базовая:
// std::accumulate(first, last, init)
Алгоритм идёт слева направо и делает примерно такую мысленную работу:
acc = init
acc = acc + x0
acc = acc + x1
...
Простая сумма чисел
Начнём с максимально простого примера: есть std::vector<int>, хотим сумму.
#include <numeric>
#include <vector>
int main() {
std::vector<int> v{1, 2, 3};
int sum = std::accumulate(v.begin(), v.end(), 0);
// sum == 6
}
Работает? Работает. Но этот пример слишком «идеальный» — он скрывает самую частую ловушку: тип 0 — это int, значит и sum будет копиться как int.
Сумма оценок времени по задачам и роль 0LL
Теперь то же самое по нашему TaskBoard: хотим общую оценку времени всех задач.
#include <numeric>
#include <vector>
long long totalEstimateMinutes(const std::vector<Task>& tasks) {
return std::accumulate(tasks.begin(), tasks.end(), 0LL,
[](long long acc, const Task& t) {
return acc + t.estimateMinutes;
}
);
}
Здесь важно сразу несколько моментов, и они все практические.
Начальное значение 0LL делает аккумулятор типа long long, а значит суммирование идёт в 64‑битном типе. Даже если у вас тысяча задач по миллиону минут (что звучит как план на бессмертие), шанс переполнения становится значительно ниже, чем у int. Лямбда принимает long long acc, и вы видите это в сигнатуре — тип не «угадывается», он читается.
Как init влияет на тип результата
Чтобы закрепить, вот маленькая таблица, которую полезно мысленно держать рядом с accumulate:
| Что передали как init | Какой будет тип аккумулятора | Типичная задача |
|---|---|---|
|
|
маленькие суммы, учебные примеры |
|
|
суммы минут/денег/счётчиков, где возможны большие значения |
|
|
средние значения, расчёты с дробями |
|
|
суммарные длины строк, размеры, индексы |
Да, std::size_t{0} выглядит чуть более «церемониально», но зато вы честно говорите: «я считаю размеры, хочу беззнаковый тип размера».
accumulate со своей операцией: считаем только невыполненные задачи
Часто нужно агрегировать не всё подряд, а по условию. Можно фильтровать отдельным алгоритмом (вы это будете делать в других местах), но иногда проще прямо в операции сложения.
#include <numeric>
#include <vector>
int remainingMinutes(const std::vector<Task>& tasks) {
return std::accumulate(tasks.begin(), tasks.end(), 0,
[](int acc, const Task& t) {
return acc + (t.done ? 0 : t.estimateMinutes);
}
);
}
Этот код не самый «строгий» по типам (аккумулятор int), зато идеально показывает идею: accumulate — это «свертка», а не обязательно «сумма всех элементов как есть». В реальном проекте вы бы легко заменили 0 на 0LL, чтобы сделать его более стойким к большим данным.
3. std::min_element и std::max_element: поиск экстремума
После сумм самое приятное — найти минимум или максимум. Тут STL делает важный ход: min_element и max_element возвращают итератор, а не значение. И это логично: итератор — это «указатель на элемент», значит вы можете не только прочитать значение, но и понять, где оно в контейнере, а при желании — изменить (если итератор не const).
Форма такая:
auto it = std::min_element(first, last);
И главный закон безопасности:
Если диапазон пустой, min_element возвращает last.
То есть разыменовывать результат можно только после проверки it != end().
Минимальная оценка времени среди задач
Сделаем функцию: найти задачу с минимальной estimateMinutes.
#include <algorithm>
#include <vector>
const Task* findCheapestTask(const std::vector<Task>& tasks) {
auto it = std::min_element(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) {
return a.estimateMinutes < b.estimateMinutes;
}
);
if (it == tasks.end()) return nullptr;
return &(*it);
}
Здесь мы возвращаем const Task*, потому что для пустого списка нужно вернуть «ничего». Мы могли бы вернуть std::optional, но это отдельная уже знакомая вам стратегия, а сегодня держим фокус на алгоритмах.
Обратите внимание на чтение компаратора: он отвечает на вопрос «a меньше b?». Это тот же стиль мышления, что и в сортировке, только применяется не для перестановки, а для выбора лучшего кандидата.
Максимальный приоритет среди невыполненных задач
Теперь сделаем max_element, но с чуть более «жизненной» логикой: максимум среди невыполненных. Тут есть тонкость: max_element не умеет «пропускать» элементы сам по себе, он просто сравнивает всё подряд. Поэтому либо вы заранее отфильтровали, либо вы делаете «трюк» в компараторе. Для новичка проще сначала отфильтровать в голове и написать аккуратный компаратор, который считает выполненные «хуже».
#include <algorithm>
#include <vector>
const Task* findTopPendingTask(const std::vector<Task>& tasks) {
auto it = std::max_element(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) {
int pa = a.done ? -1 : a.priority;
int pb = b.done ? -1 : b.priority;
return pa < pb;
}
);
if (it == tasks.end() || it->done) return nullptr;
return &(*it);
}
Смысл: выполненные задачи получают «виртуальный приоритет» -1, поэтому они не победят у реальных задач с приоритетом 0..N. А финальная проверка it->done нужна на случай, если все задачи выполнены: тогда максимум тоже будет выполненной, и мы честно вернём nullptr.
4. std::minmax_element: минимум и максимум за один проход
Очень типичная ситуация: вам нужны и минимум, и максимум. Наивный путь — вызвать min_element, затем max_element. Это нормально, но это два прохода по данным. Стандартная библиотека даёт minmax_element, который делает это за один проход и возвращает пару итераторов: {minIt, maxIt}.
Это удобно и по производительности, и по читабельности: вы явно показываете, что эти два значения логически связаны («границы диапазона»).
Минимум и максимум по оценке времени
#include <algorithm>
#include <utility>
#include <vector>
std::pair<const Task*, const Task*> minMaxByEstimate(const std::vector<Task>& tasks) {
auto [itMin, itMax] = std::minmax_element(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) {
return a.estimateMinutes < b.estimateMinutes;
}
);
if (itMin == tasks.end()) return {nullptr, nullptr};
return {&(*itMin), &(*itMax)};
}
Если контейнер пуст, оба итератора будут равны end(). Поэтому проверка itMin == end() — это сразу проверка «есть ли вообще данные».
Схема безопасной работы с итератором
Иногда полезно представить это как маленькую блок-схему — особенно если вы ловите себя на том, что разыменовываете итераторы «на автомате».
flowchart TD
A[Получили итератор it из min/max/minmax_element] --> B{"it == end()?"}
B -- да --> C[Диапазон пуст: ничего не разыменовываем]
B -- нет --> D[Безопасно используем *it или it->field]
Да, это выглядит банально. Но половина «странных падений» в учебных проектах происходит ровно из-за пропущенной проверки пустоты.
5. Агрегации в TaskBoard: команда stats
Очень хочется, чтобы алгоритмы были не «отдельной математикой», а частью приложения. Поэтому давайте представим, что в нашем TaskBoard есть команда stats, которая печатает краткую статистику: сколько задач, сколько минут всего, сколько минут осталось, а также минимум/максимум по оценке.
Мы не делаем большой рефакторинг, а добавим одну функцию печати. Заметьте: это не «полная архитектура», а связанный пример того, как алгоритмы превращаются в полезную фичу.
#include <iostream>
#include <vector>
void printStats(const std::vector<Task>& tasks) {
std::cout << "Tasks: " << tasks.size() << "\n"; // Tasks: 3
std::cout << "Total minutes: " << totalEstimateMinutes(tasks) << "\n";
std::cout << "Remaining minutes: " << remainingMinutes(tasks) << "\n";
auto [mn, mx] = minMaxByEstimate(tasks);
if (mn && mx) {
std::cout << "Min estimate: " << mn->estimateMinutes << "\n";
std::cout << "Max estimate: " << mx->estimateMinutes << "\n";
}
}
Здесь красиво видно разделение ответственности. printStats ничего не знает о том, как именно считается сумма или как находится минимум. Он просто вызывает функции, а те внутри используют правильные алгоритмы STL. Если вы потом захотите поменять модель задачи или условия подсчёта, у вас будет меньше мест для правок и меньше шансов «сломать всё сразу».
6. Типичные ошибки при агрегациях и поиске экстремумов
Ошибка №1: использовать std::accumulate(..., 0) и случайно суммировать в int.
Такое выглядит безобидно, пока данные маленькие. Потом появляется много задач, большие оценки времени, или вы считаете деньги в копейках, и внезапно получается отрицательная сумма (переполнение), хотя вы точно «всё сложили правильно». Лечится это выбором правильного init: 0LL для long long, 0.0 для double, std::size_t{0} для размеров. Важно запомнить: init — это не «просто начальное значение», это ещё и способ задать тип результата.
Ошибка №2: разыменовать итератор из min_element/max_element без проверки на пустоту.
Если контейнер пуст, алгоритм возвращает end(). Разыменование *end() — это уже не «логическая ошибка», а прямой билет в неопределённое поведение: программа может упасть, может «работать», может начать вести себя как кот, который притворяется, что вас не знает. Правило простое: сначала if (it != end()), потом *it.
Ошибка №3: путать смысл компаратора в min_element/max_element.
Компаратор читается как «a меньше b». Если вы по привычке пишете что-то вроде return a > b и ожидаете минимум, вы получите максимум (или наоборот) — и будете час смотреть на код, уверяя себя, что «всё же логично». Спасает простой ритуал: проговорите вслух — «я сейчас определяю, что считается меньшим».
Ошибка №4: забыть, что minmax_element тоже может вернуть end() и что проверка нужна даже если вы «почти уверены».
«Почти уверен» — это состояние, в котором баги размножаются почкованием. Если у вас есть хоть один сценарий, где задач может быть ноль (а в реальном приложении он всегда есть: новый пользователь, очищенный список, ошибка загрузки), то проверка должна быть частью кода, а не частью вашей веры в лучшее.
Ошибка №5: пытаться агрегировать «сложные вещи» через accumulate, не думая о стоимости операций.
accumulate с конкатенацией строк может оказаться неожиданно дорогим, потому что строки могут перевыделять память много раз. Это не значит, что accumulate плохой — это значит, что операция внутри должна быть разумной. На учебном уровне достаточно помнить принцип: если операция внутри агрегации делает «много работы», итог может быть медленным даже при одном проходе.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ