Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Algorithms

The std::reduce and std::transform_reduce algorithms

Reference for C++17 std::reduce and transform_reduce: fold with an associative operation in any order, dot products, execution policies and how they differ from accumulate.

std::reduce (C++17, <numeric>) is like std::accumulate, but the standard allows it to combine the elements in any order and grouping. In exchange it can be vectorized or run in parallel. For that to give a well-defined result, the operation must be associative and commutative.

std::transform_reduce fuses a transformation with a reduction: it maps each element (or each pair of elements from two ranges) and then reduces the mapped values. Its two-range form with default operations is the dot product.

C++
int total = std::reduce(v.begin(), v.end());                     // init defaults to T{}
int dot = std::transform_reduce(a.begin(), a.end(), b.begin(), 0);

Try it

C++ reduce and the dot 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.

C++ Why the operation must be associative

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.

Syntax

C++
template<class InIt> auto reduce(InIt first, InIt last);
template<class InIt, class T> T reduce(InIt first, InIt last, T init);
template<class InIt, class T, class BinOp> T reduce(InIt first, InIt last, T init, BinOp op);

template<class It1, class It2, class T>
T transform_reduce(It1 first1, It1 last1, It2 first2, T init);
template<class It1, class It2, class T, class Reduce, class Transform>
T transform_reduce(It1 first1, It1 last1, It2 first2, T init, Reduce reduce, Transform transform);
template<class It, class T, class Reduce, class Unary>
T transform_reduce(It first, It last, T init, Reduce reduce, Unary transform);
Name Description
first, last The range to reduce.
first2 Start of the second range for the pairwise forms.
init Starting value and result type. Defaults to a value-initialized element type in the shortest reduce.
op / reduce Associative and commutative binary operation. Default std::plus<>.
transform Unary function (one range) or binary function (two ranges) applied before reducing. Default for two ranges is std::multiplies<>.

Each function also has an overload taking an execution policy as its first argument.

Returns: the reduced value; init for an empty range.

Errors / undefined behavior: if the operation is not associative and commutative the result is nondeterministic. The operations must not modify their arguments. Signed overflow is undefined.

Usage notes

  • Associative AND commutative. Addition, multiplication, max, min, bitwise operators and logical and/or qualify. Subtraction, division and string concatenation do not.
  • Floating point sums may differ slightly from accumulate because the grouping differs. Fine for statistics, not for exact reproducibility.
  • Execution policies: std::reduce(std::execution::par, ...) needs <execution>. With GCC the parallel algorithms are backed by Intel TBB and usually need to be linked with -ltbb; our online runner does not link TBB, so the examples here use the sequential overloads. See execution policies.
  • Small ranges gain nothing from parallelism; the overhead is larger than the work.
  • Not a drop-in for accumulate: accumulate is strictly left to right; use it when order matters or the operation is not associative.
  • Dot product: transform_reduce(a, a_end, b, 0) multiplies elements pairwise and sums. It replaces the older std::inner_product.
  • Wide init: pass 0LL or 0.0 for large or fractional sums, as with accumulate.
  • Complexity: O(n) applications of the operations.