🥳 Алгоритмы диапазонов: Свёртки (fold)

В прошлый раз модифицировали диапазоны — теперь сворачиваем их в одно значение. В C++23 появилось семейство fold_*, которое наконец заменяет std::accumulate и аккуратно выводит типы.


🍰 ranges::fold_left — свёртка слева

std::vector<int> v = {1, 2, 3, 4, 5};
int sum     = std::ranges::fold_left(v, 0, std::plus{});       // 15
int product = std::ranges::fold_left(v, 1, std::multiplies{}); // 120

Левоассоциативная свёртка: аккумулятор — левый аргумент операции, элемент — правый. По шагам это (((( 0+1 )+2 )+3 )+4 )+5. Начальное значение задаёте сами.


🥨 ranges::fold_left_first — первый элемент как начало

std::vector<int> v = {3, 1, 4, 1, 5};
auto max_val = std::ranges::fold_left_first(v, [](int a, int b){
return std::max(a, b);
});
// max_val == std::optional<int>{5}

То же самое, но начальным значением берётся первый элемент диапазона — отдельный init не нужен. Удобно для max/min, где придумывать «нейтральный» элемент неловко (Для готовых max/min, конечно, есть ranges::max — fold_left_first интересен произвольной операцией).

❗️ Возвращает std::optional: у пустого диапазона нет первого элемента, поэтому на пустом входе придёт std::nullopt. Не забудьте проверить перед разыменованием.


🥖 ranges::fold_right — свёртка справа

std::vector<int> v = {1, 2, 3};
int r = std::ranges::fold_right(v, 0, std::minus{});
// 1 - (2 - (3 - 0)) == 2
int l = std::ranges::fold_left(v, 0, std::minus{});
// ((0 - 1) - 2) - 3 == -6

Идёт с правого конца: result = f(1, f(2, f(3, 0))). Для коммутативных операций (plus, multiplies) результат совпадёт с fold_left, а для некоммутативных — нет, как видно по вычитанию.

❗️ У fold_right порядок аргументов операции зеркальный: вызывается f(элемент, аккумулятор), то есть элемент идёт первым, а не вторым. Для своих лямбд это легко перепутать.


🥯 ranges::fold_right_last — последний элемент как начало

std::vector<int> v = {1, 2, 3};
auto res = std::ranges::fold_right_last(v, std::minus{});
// 1 - (2 - 3) == 2, внутри std::optional<int>{2}

Зеркало fold_left_first: начальным значением берётся последний элемент, результат — тоже std::optional с тем же поведением на пустом диапазоне.


🧇 ranges::fold_left_with_iter — результат и итератор

std::vector<int> v = {1, 2, 3, 4, 5};
auto [in, value] = std::ranges::fold_left_with_iter(v, 0, std::plus{});
// value == 15
// in == v.end()

Возвращает не просто значение, а структуру с полями in (итератор конца обработки) и value. Полезно, когда после свёртки нужно знать, где именно остановились — например, при работе с подсчётами в потоке.


❗️ Несколько подводных камней

• Главное отличие от accumulate — в том, как выводится тип накопления. У accumulate тип аккумулятора равен типу init, поэтому std::accumulate(vd.begin(), vd.end(), 0) на векторе double молча копит в int и теряет дробную часть. А fold_left выводит тип аккумулятора из РЕЗУЛЬТАТА операции (U = decay_t<invoke_result_t<F&, T, range_reference_t<R>>>), и здесь int-ный ноль на векторе double уже ничего не теряет: plus(int, double) даёт double, и всё копится в double.

std::vector<double> vd = {1.5, 2.5, 3.0};
auto s = std::ranges::fold_left(vd, 0, std::plus{});
// s == 7.0, а НЕ 6 — тип s выведен как double
// (то же самое через accumulate с init 0 дало бы int 6)

Это и есть причина, по которой fold_left лучше: он не обрезает молча.

• fold_left довольствуется однопроходным input-диапазоном (годится для istream_view и прочих потоков), а fold_right требует bidirectional-диапазона — ему нужно дойти до конца и пойти обратно. Поэтому «свернуть справа» поток на лету не выйдет.

• В отличие от remove, transform и copy_if из прошлого поста, свёртки НЕ принимают проекцию. «Свернуть по полю» одним аргументом не выйдет — нужна лямбда, которая сама достанет нужное:

std::vector<Task> tasks = { {"Код", 1}, {"Деплой", 2} };
int total = std::ranges::fold_left(tasks, 0,
[](int acc, const Task& t){ return acc + t.priority; });
// 3

📍Навигация: Вакансии • Задачи • Собесы • Канал в Max

Библиотека C/C++ разработчика

#константная_правильностьx