Defined in header
template<classInputIt1,classInputIt2,classT>Ttransform_reduce(InputIt1first1,InputIt1last1,InputIt2first2,Tinit); (1) (since C++17)
(constexpr since C++20)template<classExecutionPolicy,classForwardIt1,classForwardIt2,classT>Ttransform_reduce(ExecutionPolicy&&policy,ForwardIt1first1,ForwardIt1last1,ForwardIt2first2,Tinit); (2) (since C++17)template<classInputIt1,classInputIt2,classT,classBinaryOp1,classBinaryOp2>Ttransform_reduce(InputIt1first1,InputIt1last1,InputIt2first2,Tinit,BinaryOp1reduce,BinaryOp2transform); (3) (since C++17)
(constexpr since C++20)template<classExecutionPolicy,classForwardIt1,classForwardIt2,classT,classBinaryOp1,classBinaryOp2>Ttransform_reduce(ExecutionPolicy&&policy,ForwardIt1first1,ForwardIt1last1,ForwardIt2first2,Tinit,BinaryOp1reduce,BinaryOp2transform); (4) (since C++17)template<classInputIt,classT,classBinaryOp,classUnaryOp>Ttransform_reduce(InputItfirst,InputItlast,Tinit,BinaryOpreduce,UnaryOptransform); (5) (since C++17)
(constexpr since C++20)template<classExecutionPolicy,classForwardIt,classT,classBinaryOp,classUnaryOp>Ttransform_reduce(ExecutionPolicy&&policy,ForwardItfirst,ForwardItlast,Tinit,BinaryOpreduce,UnaryOptransform); (6) (since C++17)1) Equivalent to
transform_reduce(first1,last1,first2,init,std::plus<>(),std::multiplies<>()), effectively parallelized version of the default
.
3) Applies transform to each pair of elements from the ranges [first1, last1) and the range of std::distance(first1,last1) elements starting from first2 and reduces the results (possibly permuted and aggregated in unspecified manner) along with the initial value init over reduce.
The result is non-deterministic if the reduce is not associative or not commutative (such as floating-point addition).
If any of the following values is not convertible to T, the program is ill-formed:
reduce(init,init)
reduce(init,transform(*first1,*first2))
reduce(transform(*first1,*first2),init)
reduce(transform(*first1,*first2),transform(*first1,*first2))
Given last2 as the std::distance(first1,last1)th next iterator of first2, if any of the following conditions is satisfied, the behavior is undefined:
T is not
.
transform or reduce modifies any element of [first1, last1) or [first2, last2).
transform or reduce invalidates any iterator or subrange of [first1, last1] or [first2, last2].
5) Applies transform to each element in the range [first, last) and reduces the results (possibly permuted and aggregated in unspecified manner) along with the initial value init over reduce.
The result is non-deterministic if the reduce is not associative or not commutative (such as floating-point addition).
If any of the following values is not convertible to T, the program is ill-formed:
reduce(init,init)
reduce(init,transform(*first))
reduce(transform(*first),init)
reduce(transform(*first),transform(*first))
If any of the following conditions is satisfied, the behavior is undefined:
T is not
.
transform or reduce modifies any element of [first, last).
transform or reduce invalidates any iterator or subrange of [first, last].
2,4,6) Same as (1,3,5), but executed according to policy.
These overloads participate in overload resolution only if the value of the following expression is true:
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
(until C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
(since C++20)Parameters
first1, last1 - the pair of iterators defining the
of elements to be taken as the left operand of transformfirst2 - the start of range of elements to be taken as the right operand of transformfirst, last - the pair of iterators defining the
of elements to be taken as the operand of transforminit - the initial value of the generalized sum policy - the
to use reduce - binary
that will be applied in unspecified order to the results of transform, the results of other reduce and init. transform - unary or binary
that will be applied to each element of the input range(s). The return type must be acceptable as input to reduce. Type requirements -InputIt1, InputIt2, InputIt must meet the requirements of
. -ForwardIt1, ForwardIt2, ForwardIt must meet the requirements of
. Return value
1,2) The generalized sum of init and values over std::plus<>(), where values are the values transformed by std::multiplies<>(), each value is transformed from a pair of elements from the two input ranges.
3,4) The generalized sum of init and values over reduce, where values are the values transformed by transform, each value is transformed from a pair of elements from the two input ranges.
5,6) The generalized sum of init and values over reduce, where values are the values transformed by transform, each value is transformed from an element from the input range.
The generalized sum of a group of elements over an binary operation binary_op is defined as follows:
If the group only has one element, the sum is the value of the element.
Otherwise, performs the following operations in order:
Takes any two elements elem1 and elem2 from the group.
Calculates binary_op(elem1,elem2) and puts the result back to the group.
Repeats steps 1 and 2 until there is only one element in the group.
Complexity
Given N as std::distance(first1,last1) (or std::distance(first,last) for overloads (5,6)):
1,2)O(N) applications of std::plus<>() and std::multiplies<>() respectively.
3-6)O(N) applications of reduce and transform respectively.
Exceptions
The overloads with a template parameter named ExecutionPolicy report errors as follows:
If execution of a function invoked as part of the algorithm throws an exception and ExecutionPolicy is one of the
,
is called. For any other ExecutionPolicy, the behavior is implementation-defined.
If the algorithm fails to allocate memory,
is thrown.
Notes
transform is never applied to init.
If first==last or first1==last1, init is returned, unmodified.
Example
transform_reduce can be used to parallelize
. Some systems may need additional support to get advantages of parallel execution. E.g., on GNU/Linux, the
be installed and -ltbb option be provided to gcc/clang compiler.
Run this code
#if PARALLEL#include<execution>#define PAR std::execution::par,#else#define PAR#endif#include<algorithm>#include<functional>#include<iostream>#include<iterator>#include<locale>#include<numeric>#include<vector>// to parallelize non-associate accumulative operation, you'd better choose// transform_reduce instead of reduce; e.g., a + b * b != b + a * avoidprint_sum_squared(longconstnum){std::cout.imbue(std::locale{"en_US.UTF8"});std::cout<<"num = "<<num<<'\n';// create an immutable vector filled with pattern: 1,2,3,4, 1,2,3,4 ...conststd::vector<long>v{[n=num*4]{std::vector<long>v;v.reserve(n);std::generate_n(std::back_inserter(v),n,[i=0]()mutable{return1+i++%4;});returnv;}()};autosquared_sum=[](autosum,autoval){returnsum+val*val;};autosum1=std::accumulate(v.cbegin(),v.cend(),0L,squared_sum);std::cout<<"accumulate(): "<<sum1<<'\n';autosum2=std::reduce(PARv.cbegin(),v.cend(),0L,squared_sum);std::cout<<"reduce(): "<<sum2<<'\n';autosum3=std::transform_reduce(PARv.cbegin(),v.cend(),0L,std::plus{},[](autoval){returnval*val;});std::cout<<"transform_reduce(): "<<sum3<<"\n\n";}intmain(){print_sum_squared(1);print_sum_squared(1'000);print_sum_squared(1'000'000);}Possible output:
num = 1 accumulate(): 30 reduce(): 30 transform_reduce(): 30 num = 1,000 accumulate(): 30,000 reduce(): -7,025,681,278,312,630,348 transform_reduce(): 30,000 num = 1,000,000 accumulate(): 30,000,000 reduce(): -5,314,886,882,370,003,032 transform_reduce(): 30,000,000 // Compile-options for parallel execution on POSIX: // g++ -O2 -std=c++17 -Wall -Wextra -pedantic -DPARALLEL ./example.cpp -ltbb -o tr; ./tr See also