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.
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
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.
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
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
accumulatebecause 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:accumulateis 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 olderstd::inner_product. - Wide init: pass
0LLor0.0for large or fractional sums, as withaccumulate. - Complexity: O(n) applications of the operations.