Skip to content
Tutorials Center
My learning

Topics

Lesson 109 of 171 ยท The Standard Library (STL)

Numeric Algorithms

Learn the C++ numeric algorithms - accumulate and its init-type trap, fold_left, reduce, inner_product, transform_reduce, partial_sum, scans, iota, gcd and lcm.

The header <numeric> is small but extremely useful. It holds the algorithms that combine elements into a result: totals and products (accumulate, reduce), dot products and "map then combine" operations (inner_product, transform_reduce), running totals and differences (partial_sum, inclusive_scan, exclusive_scan, adjacent_difference), sequence generation (iota), and a few number-theory helpers (gcd, lcm, midpoint). C++23 adds the std::ranges::fold_left family in <algorithm>, the modern, range-friendly version of accumulate.

These algorithms aren't only for math. "Combine everything into one value" also describes joining strings, merging statistics, finding the longest line, or building a checksum. In this lesson you'll learn what each algorithm computes, the famous initial-value type trap of accumulate, when reduce may reorder your operations and why that matters for floating point, how prefix sums turn range queries into O(1) subtractions, and how to avoid overflow. You should be comfortable with lambdas and function objects like std::plus<> and std::multiplies<>.

accumulate: folding a range into one value

std::accumulate(first, last, init) starts with init and adds each element in order: ((init + a) + b) + c. With a fourth argument you choose the operation, so std::accumulate(first, last, 1, std::multiplies<>{}) computes a product.

There's one trap you must know: the result has the type of init, not the type of the elements. The running total is stored in a variable of that type, and every intermediate result is converted to it.

C++ accumulate and the init type trap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The first line prints with 0: 27 instead of 29.23. With an int initial value, each step computes int + double, then stores the result back into an int, cutting off the fraction: 0 + 19.99 becomes 19, 19 + 5.49 becomes 24, and 24 + 3.75 becomes 27. No warning, no error. The fix is to make init the type you want the result in: 0.0 for doubles, 0LL for large integer sums, std::string{} for strings. (Passing "" for strings is a related trap: the accumulator would be a const char*, and the code wouldn't compile.)

The string example moves the accumulator into each step (std::move(acc) + ...). Since C++20, accumulate itself moves the running value into the operation, so this avoids copying the growing string on every step.

accumulate is in <numeric>, not <algorithm>. Forgetting the include is one of the most common compile errors with it.

fold_left and friends (C++23)

std::accumulate predates ranges: it takes iterators, has no projections, and you must name the result type through init. C++23 adds range-based folds in <algorithm>:

  • std::ranges::fold_left(r, init, op) is accumulate for ranges, and its result type is what op returns, so mixing int and double doesn't silently truncate.
  • std::ranges::fold_left_first(r, op) uses the first element as the initial value and returns a std::optional, empty for an empty range. That's ideal when there's no natural "zero", such as for a maximum.
  • std::ranges::fold_right(r, init, op) combines from the right: a op (b op (c op init)).
C++ fold_left, fold_left_first and fold_right

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

fold_left prints 29.23 even though init was the int 0: the result type follows std::plus<>{}(int, double), which is double. When your compiler supports C++23, prefer the folds for new code.

reduce: accumulate that may reorder

std::reduce(first, last, init, op) (C++17) looks like accumulate, but it's allowed to combine elements in any order and grouping: (a + b) + (c + d) instead of ((a + b) + c) + d. That freedom lets it run in parallel with an execution policy and lets compilers vectorize the sequential version.

The price: op must be associative and commutative, or the result is unspecified. Addition and multiplication of integers qualify; subtraction and string concatenation don't. Floating-point addition is commutative but only almost associative, so a parallel reduce of doubles may differ from accumulate in the last digits.

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

double parallel_total(const std::vector<double>& values) {
    // Splits the work across threads. With GCC this needs Intel TBB at link time (-ltbb).
    return std::reduce(std::execution::par, values.begin(), values.end(), 0.0);
}

The execution policies (std::execution::seq, par, par_unseq, unseq) also work with transform_reduce, sort and most other algorithms. Our online compiler doesn't link TBB, so parallel examples here are read-only; the sequential calls below run normally.

transform_reduce and inner_product

Very often you want to transform each element, then combine: sum of squares, total price of items, number of mismatches between two ranges. std::transform_reduce does both in one pass, without a temporary container:

  • One range: transform_reduce(first, last, init, reduce_op, transform_op) computes init โŠ• f(a) โŠ• f(b) โŠ• ....
  • Two ranges: transform_reduce(first1, last1, first2, init) is a dot product (a1*b1 + a2*b2 + ...); you can pass your own reduce and combine operations too.

std::inner_product is the older, strictly left-to-right two-range version. Like accumulate, it takes its result type from init.

C++ reduce, transform_reduce and inner_product

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

In the Hamming distance, std::not_equal_to<>{} turns each pair of characters into true or false, and std::plus<>{} adds them up as 1s and 0s. Like all two-range numeric algorithms, transform_reduce reads exactly as many elements from the second range as the first range has, so the second must be at least as long.

Running totals: partial_sum and scans

A prefix sum turns [a, b, c, d] into [a, a+b, a+b+c, a+b+c+d]. The standard offers:

  • partial_sum(first, last, out, op = plus): the classic, strictly left to right.
  • inclusive_scan (C++17): the same result, but may reorder like reduce and accepts execution policies.
  • exclusive_scan(first, last, out, init) (C++17): element i is the sum of everything before i, starting at init: [init, init+a, init+a+b, ...].
  • adjacent_difference(first, last, out): the inverse of partial_sum: [a, b-a, c-b, ...].

Prefix sums have a famous use: after one O(n) pass, the sum of any subrange [i, j) is prefix[j] - prefix[i], an O(1) subtraction instead of a new loop.

C++ partial_sum, scans and adjacent_difference

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Look at the inclusive_scan call: it writes to prefix.begin() + 1, leaving prefix[0] = 0, and passes 0LL as the initial value so the sums are computed in long long. That one-element offset is what makes prefix[to] - prefix[from] work for every range, including ranges that start at day 0.

adjacent_difference copies the first element unchanged, which is why daily change starts with 4200. Feed its output back into partial_sum and you get the original data back.

iota: consecutive values

std::iota(first, last, start) fills a range with start, start + 1, start + 2, โ€ฆ (using ++). The name comes from the Greek letter ฮน used for the same operation in the APL language. It's perfect for creating index arrays, which you can then sort by some key to get a ranking without moving the original data. C++23 adds std::ranges::iota(r, start), and std::views::iota produces such sequences lazily without any container (see Ranges and Views).

C++ iota and sorting indexes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The projection [&times](std::size_t i) { return times[i]; } sorts the indexes by the times they point to. names and times stay untouched and in sync, which is exactly what you want when several parallel arrays describe the same records.

gcd, lcm and midpoint

Three small helpers in <numeric> handle classic number problems correctly:

  • std::gcd(a, b) (C++17): greatest common divisor, for example to reduce a fraction.
  • std::lcm(a, b) (C++17): least common multiple, for example to find when two repeating events coincide.
  • std::midpoint(a, b) (C++20): the middle of two numbers (or pointers) without overflow. The naive (a + b) / 2 overflows when a + b exceeds the type's range, a real bug that once lurked in many binary search implementations.
C++ gcd, lcm and midpoint

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The folds start from neutral values: gcd(0, x) == x and lcm(1, x) == x. The last line shows a subtle detail of std::midpoint for integers: when the exact middle is a fraction, it rounds toward the first argument, so midpoint(1, 4) is 2 but midpoint(4, 1) is 3. The naive (lo + hi) / 2 would overflow for the values above, which is undefined behavior for signed integers. More math helpers are covered in Math Functions.

Choosing a numeric algorithm

Goal Use
Sum or combine in strict order std::accumulate (watch the init type), or C++23 std::ranges::fold_left
Combine with no natural start value std::ranges::fold_left_first
Sum that may be parallel or vectorized std::reduce (operation must be associative and commutative)
Transform each element, then combine std::transform_reduce
Dot product std::transform_reduce or std::inner_product
Running totals, range-sum queries std::partial_sum, std::inclusive_scan
Offsets / "sum of everything before" std::exclusive_scan
Differences between neighbors std::adjacent_difference
0, 1, 2, โ€ฆ std::iota, std::ranges::iota, std::views::iota
Fractions, cycles, safe averages std::gcd, std::lcm, std::midpoint

Watch overflow in every summing algorithm. The type that holds the running value decides the limit, so choose long long (or double) for the accumulator when totals can grow large.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. std::vector<double> v{0.5, 0.5, 0.5}; What does std::accumulate(v.begin(), v.end(), 0) return?

    The init value 0 is an int, so each partial sum is truncated back to int. 0 + 0.5 becomes 0 three times, giving 0.
  2. 2. Why is std::reduce(v.begin(), v.end(), 0, std::minus<>{}) a bad idea?

    reduce is allowed to compute in any order. Only use it with operations like + and * on integers, where order doesn't change the result.
  3. 3. What does std::exclusive_scan write for the input [3, 1, 4] with init 0?

    Each output element is the sum of all elements before it. That gives 0, then 0+3, then 0+3+1; the current element is excluded.
  4. 4. prefix holds prefix sums with a leading 0 for data = [5, 2, 7, 1], so prefix is [0, 5, 7, 14, 15]. What is the sum of data[1] through data[3] inclusive?

    The range [1, 4) is prefix[4] - prefix[1] = 15 - 5 = 10, which is 2 + 7 + 1.
  5. 5. What does std::ranges::fold_left_first(std::vector<int>{}, std::plus<>{}) return?

    fold_left_first has no initial value, so for an empty range it returns an empty optional instead of inventing a result.

Summary

  • <numeric> holds accumulate, reduce, inner_product, transform_reduce, partial_sum, the scans, adjacent_difference, iota, gcd, lcm and midpoint.
  • std::accumulate folds strictly left to right, and its result type is the type of init: use 0.0, 0LL or std::string{} as needed.
  • C++23's std::ranges::fold_left, fold_left_first and fold_right are range-friendly folds whose result type follows the operation.
  • std::reduce and std::inclusive_scan may reorder work for parallelism, so their operations must be associative and commutative.
  • std::transform_reduce maps and combines in one pass: sums of squares, totals, dot products, Hamming distances.
  • Prefix sums from partial_sum/inclusive_scan answer any range-sum query with one subtraction; exclusive_scan gives offsets, and adjacent_difference undoes a prefix sum.
  • std::iota creates index sequences, and std::gcd, std::lcm and std::midpoint solve classic number problems without overflow traps.

Next: Ranges and Views, where algorithms take whole containers and views build lazy pipelines with the | operator.