What is Fold Operations in C++?

Reduce a range to a single value using std::accumulate, std::reduce, std::transform_reduce, and the C++23 ranges::fold family.

Which C++ standard introduced Fold Operations?

Fold Operations was introduced in C++98.

What is the difficulty level of Fold Operations?

Fold Operations is considered Intermediate-level C++ material.

Fold Operations

Fold Operationssince C++98

A fold reduces a sequence of elements to a single accumulated value by repeatedly applying a binary operation, starting from an explicit initial value and consuming elements left-to-right (or right-to-left for right folds).

Overview

The C++ standard library provides a layered progression of fold algorithms, each adding capabilities introduced across standards:

Algorithm	Header	Since	Notes
`std::accumulate`	`<numeric>`	C++98	Sequential left fold
`std::inner_product`	`<numeric>`	C++98	Two-range fold
`std::partial_sum`	`<numeric>`	C++98	Prefix fold (scan)
`std::reduce`	`<numeric>`	C++17	Parallelisable; order unspecified
`std::transform_reduce`	`<numeric>`	C++17	Map then reduce
`std::inclusive_scan`	`<numeric>`	C++17	Parallelisable prefix fold
`std::exclusive_scan`	`<numeric>`	C++17	Prefix fold excluding current element
`std::ranges::fold_left`	`<algorithm>`	C++23	Range-based left fold
`std::ranges::fold_right`	`<algorithm>`	C++23	Range-based right fold
`std::ranges::fold_left_first`	`<algorithm>`	C++23	Left fold; first element as init

Syntax

cpp

Godbolt

// C++98 — sequential left fold
T accumulate(InputIt first, InputIt last, T init);
T accumulate(InputIt first, InputIt last, T init, BinaryOp op);

// C++17 — order-unspecified fold, supports execution policies
T reduce(InputIt first, InputIt last);
T reduce(InputIt first, InputIt last, T init);
T reduce(ExecPolicy&& policy, ForwardIt first, ForwardIt last, T init, BinaryOp op);

// C++17 — transform each element then fold
T transform_reduce(InputIt first, InputIt last, T init, BinaryReduceOp r, UnaryTransformOp t);
T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init); // dot product

// C++23 — range-based folds
auto ranges::fold_left(R&& r, T init, F op) -> T;
auto ranges::fold_right(R&& r, T init, F op) -> T;
auto ranges::fold_left_first(R&& r, F op) -> optional<T>;  // init = first element

Examples

Basic accumulation and the init-type trap

std::accumulate deduces its return type from init, not from the range element type. Passing integer 0 for a range of double silently truncates.

cpp

Godbolt

#include <numeric>
#include <vector>

std::vector<double> prices{1.5, 2.3, 0.8, 4.1};

// BAD: init is int — result is int (truncated to 8)
int wrong = std::accumulate(prices.begin(), prices.end(), 0);

// CORRECT: init matches the value type
double total = std::accumulate(prices.begin(), prices.end(), 0.0); // 8.7

Custom binary operation

cpp

Godbolt

#include <numeric>
#include <vector>
#include <string>

std::vector<std::string> words{"fold", "is", "powerful"};

// Right-fold simulation via reverse iterators
std::string sentence = std::accumulate(
    words.rbegin(), words.rend(), std::string{},
    [](const std::string& acc, const std::string& w) {
        return acc.empty() ? w : acc + " " + w;
    }
); // "powerful is fold"

std::reduce for parallel workloads (C++17)

std::reduce allows the runtime to reorder and group operations, enabling vectorisation and thread-level parallelism. The binary operation must be associative and commutative for results to be deterministic.

cpp

Godbolt

#include <numeric>
#include <execution>  // C++17
#include <vector>

std::vector<double> samples(10'000'000);
// ... fill samples ...

// Sequential — identical to accumulate
double seq_sum = std::reduce(samples.begin(), samples.end(), 0.0);

// Parallel — may use all available cores
double par_sum = std::reduce(
    std::execution::par_unseq,   // C++17 execution policy
    samples.begin(), samples.end(), 0.0
);

Subtraction and division are not commutative; using them with std::reduce produces undefined behaviour when an execution policy is active.

std::transform_reduce for map-reduce (C++17)

The canonical use case is a dot product or any weighted sum:

cpp

Godbolt

#include <numeric>
#include <execution>
#include <vector>

std::vector<double> weights{0.2, 0.5, 0.3};
std::vector<double> values{10.0, 20.0, 30.0};

// Dot product: sum(weights[i] * values[i])
double weighted = std::transform_reduce(
    std::execution::par,   // C++17
    weights.begin(), weights.end(),
    values.begin(),
    0.0  // init
);  // 0.2*10 + 0.5*20 + 0.3*30 = 21.0

// Unary form: sum of squares
std::vector<int> v{1, 2, 3, 4, 5};
int sum_sq = std::transform_reduce(
    v.begin(), v.end(), 0,
    std::plus<>{},
    [](int x){ return x * x; }
);  // 55

C++23 ranges::fold_left and fold_right

The C++23 ranges fold algorithms work directly on range objects and return the accumulated value without requiring explicit iterator pairs. fold_left_first uses the first element as the initial value, returning std::optional to handle empty ranges safely.

cpp

Godbolt

#include <algorithm>  // C++23
#include <ranges>
#include <vector>
#include <optional>

std::vector<int> nums{1, 2, 3, 4, 5};

// Left fold: ((((1+2)+3)+4)+5) = 15
int sum = std::ranges::fold_left(nums, 0, std::plus<>{}); // C++23

// Right fold: (1+(2+(3+(4+5)))) = 15
int rsum = std::ranges::fold_right(nums, 0, std::plus<>{}); // C++23

// fold_left_first: no explicit init; uses nums[0] as starting value
std::optional<int> maybe = std::ranges::fold_left_first(nums, std::plus<>{}); // C++23
int result = maybe.value(); // 15; safe — nums is non-empty

// Composes naturally with views
auto evens_sum = std::ranges::fold_left(
    nums | std::views::filter([](int x){ return x % 2 == 0; }), // C++20
    0, std::plus<>{}
); // 6

fold_left_with_iter and fold_left_first_with_iter (C++23)

The two _with_iter variants perform the same fold as fold_left and fold_left_first but return a struct containing both the computed value and the iterator that was reached at the end of the range. The return type is a specialisation of ranges::in_value_result<I, T>, so structured bindings work directly.

This matters when the range being folded has a sentinel-based end (such as a views::take_while view). Calling fold_left throws away the final iterator position; if you later need to know where the range stopped, you would have to scan the underlying container a second time. fold_left_with_iter avoids that extra pass.

cpp

Godbolt

#include <algorithm>  // C++23
#include <ranges>
#include <vector>

struct Cat { int age; };
int feed_half(Cat& c, int food) {
    int share = food / 2;
    c.age += share;          // not realistic, just demonstration
    return food - share;
}

std::vector<Cat> cats{{2}, {4}, {8}, {12}};

// Take only young cats (age < 7); the sentinel is a predicate, not an iterator.
auto young = cats | std::views::take_while([](const Cat& c){ return c.age < 7; });

// fold_left discards the end position — we cannot cheaply know where young ends in cats.
// fold_left_with_iter returns {.in = iterator into cats, .value = leftover food}.
auto [first_old, leftover] = std::ranges::fold_left_with_iter(
    young, 100, feed_half
);
// first_old now points to the first cat with age >= 7 in the original vector.
// No second scan needed.

// fold_left_first_with_iter: uses the first element as init, returns optional value.
std::vector<int> nums{3, 1, 4, 1, 5};
auto [end_it, maybe_max] = std::ranges::fold_left_first_with_iter(
    nums,
    [](int a, int b){ return a > b ? a : b; }
);
int maximum = maybe_max.value(); // 5; end_it == nums.end()

The table below summarises the complete C++23 fold family, including the _with_iter variants:

Function	Init source	Returns
`ranges::fold_left`	explicit `init`	`U` (value only)
`ranges::fold_left_first`	first element	`std::optional<U>`
`ranges::fold_right`	explicit `init`	`U`
`ranges::fold_right_last`	last element	`std::optional<U>`
`ranges::fold_left_with_iter`	explicit `init`	`in_value_result<I, U>` (`{.in, .value}`)
`ranges::fold_left_first_with_iter`	first element	`in_value_result<I, std::optional<U>>`

The _with_iter pair adds no extra algorithmic cost — the final iterator is computed as a side-effect of the fold itself.

Example: Building Delimited Strings

Joining a sequence of strings with a separator is a classic use case for std::accumulate, but the naive formulation causes O(n²) allocations because each intermediate concatenation creates a new std::string object that is then discarded.

cpp

Godbolt

#include <numeric>
#include <vector>
#include <string>
#include <numeric>   // for std::transform_reduce (C++17)

std::vector<std::string> tokens{"alpha", "beta", "gamma", "delta"};
const std::string sep{", "};

// NAIVE — O(n^2) copies: each iteration allocates a fresh string.
std::string naive = std::accumulate(
    std::next(tokens.begin()), tokens.end(),
    tokens.front(),
    [&sep](std::string acc, const std::string& s) {
        return acc + sep + s;   // acc is a value copy, then re-allocated
    }
); // "alpha, beta, gamma, delta"

// BETTER — pre-reserve to avoid repeated reallocations.
// Compute the total character count first, then accumulate in place.
std::size_t total = std::accumulate(
    tokens.begin(), tokens.end(), std::size_t{0},
    [&sep](std::size_t n, const std::string& s) {
        return n + s.size() + sep.size();
    }
);
// subtract one trailing separator
if (total >= sep.size()) total -= sep.size();

std::string result;
result.reserve(total);   // single allocation
result = std::accumulate(
    std::next(tokens.begin()), tokens.end(),
    tokens.front(),
    [&sep](std::string acc, const std::string& s) {
        acc += sep;   // appends in place — no temporary string
        acc += s;
        return acc;   // NRVO or move elision eliminates the extra copy
    }
); // "alpha, beta, gamma, delta"

The key difference is using += (in-place append) inside the lambda rather than + (which builds a fresh std::string on each call). With reserve, the underlying buffer is allocated exactly once regardless of the number of tokens.

For C++23 code this pattern is cleaner with ranges::fold_left, which avoids the std::next/tokens.front() dance required to skip the first element:

cpp

Godbolt

#include <algorithm>  // C++23
#include <ranges>
#include <vector>
#include <string>

std::vector<std::string> tokens{"alpha", "beta", "gamma", "delta"};
const std::string sep{", "};

// C++23: fold_left_first uses the first token as init — no manual skip.
std::string joined = std::ranges::fold_left_first(
    tokens,
    [&sep](std::string acc, const std::string& s) {
        acc += sep;
        acc += s;
        return acc;
    }
).value_or("");

std::inner_product vs std::transform_reduce

Both algorithms perform a two-range map-reduce (transform each pair of elements, then reduce the results), but they differ in ordering guarantees and parallelism support:

Property	`std::inner_product` (C++98)	`std::transform_reduce` (C++17)
Standard	C++98	C++17
Header	`<numeric>`	`<numeric>`
Execution order	Strictly left-to-right, in-order	Unspecified (may be reordered)
Execution policy	None	Supports `par`, `par_unseq`
One-range form	No	Yes (unary transform overload)
Op requirements	None (non-commutative ops are safe)	`reduce` op must be associative and commutative for deterministic results
Default ops	`+` and `*`	`+` and `*` (same defaults)

std::inner_product is the safe, predictable choice when the reduce operation is not commutative or associative (for example, custom saturating arithmetic or ordered string building). Because it always applies operations in the order given, results are deterministic regardless of the operator.

std::transform_reduce trades that guarantee for the ability to parallelise. The standard permits the implementation to apply the reduce operation in any order and with any grouping, which enables vectorisation (SIMD) and thread distribution. If the reduce operation is not commutative and associative (such as floating-point subtraction), results can differ between runs or implementations.

cpp

Godbolt

#include <numeric>
#include <execution>   // C++17
#include <vector>

std::vector<double> a{1.0, 2.0, 3.0};
std::vector<double> b{4.0, 5.0, 6.0};

// inner_product: always (0 + 1*4 + 2*5 + 3*6) = 32, strictly ordered.
double ip = std::inner_product(a.begin(), a.end(), b.begin(), 0.0);

// transform_reduce default (two-range): semantically equivalent to inner_product
// but the reduce (+) is allowed to be reordered — safe here because + is commutative.
double tr = std::transform_reduce(a.begin(), a.end(), b.begin(), 0.0);

// transform_reduce with parallel policy — not available for inner_product.
double par_tr = std::transform_reduce(
    std::execution::par_unseq,
    a.begin(), a.end(),
    b.begin(),
    0.0   // dot product
);

// One-range form (no equivalent in inner_product): sum of squares.
std::vector<int> v{1, 2, 3, 4, 5};
int sum_sq = std::transform_reduce(
    v.begin(), v.end(), 0,
    std::plus<>{},
    [](int x){ return x * x; }
);  // 55

When to prefer inner_product: the reduce operation is non-commutative, or you need guaranteed left-to-right application for numerical stability or reproducibility.

When to prefer transform_reduce: the operations are commutative and associative, you want to pass a parallel execution policy, or you need the single-range unary-transform overload.

Best Practices

Prefer std::reduce over std::accumulate for arithmetic on large ranges. With std::execution::par_unseq, the compiler can auto-vectorise and distribute across threads. Reserve std::accumulate for non-commutative operations (e.g., string concatenation, matrix multiplication) or when exact left-to-right order is required.

Prefer std::ranges::fold_left in new C++23 code. It accepts ranges directly, composes with views pipelines, and expresses intent more clearly than iterator pairs. fold_left_first eliminates the need to manually extract front() as an initial value.

Match the init type explicitly. Template deduction derives the return type from init. For any fold over floating-point elements, always write 0.0, 0.0f, or T{} — never a bare integer literal.

Use std::transform_reduce instead of separate transform + accumulate. A single pass is cache-friendlier and enables the parallelism optimisations to span both phases simultaneously.

Common Pitfalls

Mutation in the binary operation. Both std::accumulate and std::reduce pass the accumulator by value. Capturing and mutating state outside the lambda is a data race when a parallel execution policy is active.

Non-commutative ops with std::reduce. Passing std::execution::par to std::reduce with subtraction or non-commutative user ops produces implementation-defined results. The standard allows arbitrary grouping of operations.

Empty range with fold_left_first. When the range is empty, std::ranges::fold_left_first returns std::nullopt. Always check the optional before using the value.

Overflow in the accumulator. If the element type is int and the sum exceeds INT_MAX, the accumulator overflows. Use a wider init type: std::accumulate(v.begin(), v.end(), 0LL) promotes the accumulator to long long.

std::fold_left and std::fold_right (C++23 Named Algorithms)

C++23 gives folds their own named algorithms. std::ranges::fold_left and std::ranges::fold_right are not merely convenience wrappers — they carry well-defined ordering contracts that std::reduce deliberately omits, making them the right choice whenever operation order affects correctness or reproducibility.

fold_left applies the binary operation as op(op(op(init, e0), e1), e2) — strictly left-to-right, matching the mental model of iterative accumulation. fold_right applies it as op(e0, op(e1, op(e2, init))) — right-to-left from the last element toward the first. For commutative operations the two produce the same numeric result, but for non-commutative operations (string building, matrix products, function composition) the difference is observable.

cpp

Godbolt

// C++23
#include <algorithm>
#include <ranges>
#include <vector>
#include <string>
#include <functional>

std::vector<std::string> words{"C", "plus", "plus"};

// fold_left:  (("" + "C") + "plus") + "plus" → "Cplusplus"
std::string lft = std::ranges::fold_left(
    words, std::string{},
    [](std::string acc, const std::string& w){ return acc + w; }
);

// fold_right: "C" + ("plus" + ("plus" + "")) → "Cplusplus"
// Note: fold_right passes (element, accumulator), i.e. op(elem, acc)
std::string rgt = std::ranges::fold_right(
    words, std::string{},
    [](const std::string& w, std::string acc){ return w + acc; }
);

// With numeric types fold_left == fold_right for +, but not for -
std::vector<int> nums{10, 3, 2};
int l = std::ranges::fold_left (nums, 0, std::minus<>{}); // ((0-10)-3)-2 = -15
int r = std::ranges::fold_right(nums, 0, std::minus<>{}); // 10-(3-(2-0)) =  9

Unlike std::reduce, neither algorithm accepts an execution policy — sequential, ordered processing is the explicit contract. Prefer them over std::accumulate in C++23 code because they accept range objects directly, compose with views, and do not require spelling out begin()/end().

std::fold_left_first and std::fold_right_last (C++23)

When the first or last element is a natural identity, the explicit init value is redundant. std::ranges::fold_left_first uses the first element of the range as the initial accumulator, then folds left over the remaining elements. std::ranges::fold_right_last does the symmetric thing from the right. Both return std::optional<T> to safely handle the empty-range case, where no initial value can be drawn from the sequence.

cpp

Godbolt

// C++23
#include <algorithm>
#include <ranges>
#include <vector>
#include <optional>
#include <string>

std::vector<int> scores{88, 92, 71, 95, 60};

// Maximum score — first element seeds the accumulator.
std::optional<int> best = std::ranges::fold_left_first(
    scores,
    [](int a, int b){ return a > b ? a : b; }
);
int max_score = best.value_or(0); // 95

// Minimum score using fold_right_last — last element seeds from the right.
std::optional<int> worst = std::ranges::fold_right_last(
    scores,
    [](int a, int b){ return a < b ? a : b; }
);
int min_score = worst.value_or(0); // 60

// String join without a sentinel: the first word becomes the initial value.
std::vector<std::string> parts{"one", "two", "three"};
std::string joined = std::ranges::fold_left_first(
    parts,
    [](std::string acc, const std::string& s){ return acc + "-" + s; }
).value_or(""); // "one-two-three"

// Empty-range safety: always check the optional.
std::vector<int> empty{};
auto result = std::ranges::fold_left_first(empty, std::plus<>{});
static_assert(std::is_same_v<decltype(result), std::optional<int>>);
bool has_value = result.has_value(); // false — safe, no UB

fold_left_first is particularly useful for reductions where a neutral identity element does not exist (such as max, min, or gcd) or where inventing a dummy init value would require domain knowledge the algorithm should not encode.

Parallel std::reduce vs Sequential std::accumulate

Parallelism comes at the cost of operation-ordering freedom. std::reduce with std::execution::par or std::execution::par_unseq allows the runtime to partition the input into sub-ranges, fold each chunk independently, and then combine the chunk results in an unspecified tree structure. This is only safe when the binary operation is both associative (op(op(a,b),c) == op(a,op(b,c))) and commutative (op(a,b) == op(b,a)).

Floating-point addition satisfies neither property exactly. IEEE 754 arithmetic is not associative due to rounding, so std::reduce with std::execution::par on float or double data may produce slightly different values across runs, compilers, or hardware. For reproducible floating-point sums, use std::accumulate (or ranges::fold_left in C++23), which fixes the summation order.

cpp

Godbolt

// C++17
#include <numeric>
#include <execution>
#include <vector>
#include <iostream>

std::vector<double> data(1'000'000, 1e-7);

// Sequential: deterministic result, left-to-right.
double seq = std::accumulate(data.begin(), data.end(), 0.0);

// Parallel: faster, but floating-point result may differ from seq.
double par = std::reduce(
    std::execution::par_unseq,
    data.begin(), data.end(), 0.0
);

// For integer addition (truly associative + commutative), results are identical.
std::vector<int> ints(1'000'000, 1);
int seq_i = std::accumulate(ints.begin(), ints.end(), 0);
int par_i = std::reduce(std::execution::par_unseq, ints.begin(), ints.end(), 0);
// seq_i == par_i == 1'000'000, guaranteed.

// WRONG: subtraction is non-commutative — undefined behaviour with par policy.
// double bad = std::reduce(std::execution::par, data.begin(), data.end(),
//                          0.0, std::minus<>{});  // DO NOT DO THIS

A practical rule: use std::reduce with a parallel policy for integer arithmetic, bitwise operations (|, &, ^), and commutative user-defined monoids. Fall back to std::accumulate (or ranges::fold_left) whenever order or bit-exact reproducibility matters.

Fold with Projections using std::ranges::fold_left

Projections let you fold on a derived attribute without modifying the range or writing a wrapper lambda. std::ranges::fold_left accepts an optional projection argument (as do most std::ranges algorithms) that is applied to each element before the binary operation sees it. The projection does not affect the type of the accumulator — only the element values passed as the second argument to op are transformed.

cpp

Godbolt

// C++23
#include <algorithm>
#include <ranges>
#include <vector>
#include <string>

struct Employee {
    std::string name;
    double salary;
    int    tenure_years;
};

std::vector<Employee> team{
    {"Alice", 95'000, 5},
    {"Bob",   82'000, 3},
    {"Carol", 110'000, 8},
};

// Sum of salaries using a projection — no intermediate range needed.
double total_payroll = std::ranges::fold_left(
    team, 0.0,
    std::plus<>{},
    &Employee::salary       // projection: extract salary before adding
);  // 287'000.0

// Total tenure, also via projection.
int total_tenure = std::ranges::fold_left(
    team, 0,
    std::plus<>{},
    &Employee::tenure_years // pointer-to-member as projection
);  // 16

// Projection can be a lambda for computed attributes.
double total_years_of_salary = std::ranges::fold_left(
    team, 0.0,
    std::plus<double>{},
    [](const Employee& e){ return e.salary * e.tenure_years; }
);  // 95000*5 + 82000*3 + 110000*8 = 1'607'000.0

The projection is applied to every element exactly once, in the same order as the fold itself, so it carries no additional cost over embedding the projection logic inside the binary operation. Pointer-to-member syntax (&Employee::salary) keeps call sites concise and avoids a spelling-out a lambda.