std::transform_reduce
<numeric>
T transform_reduce( InputIt1 first1, InputIt1 last1,
(constexpr since C++20)
class ForwardIt1, class ForwardIt2, class T >
T transform_reduce( ExecutionPolicy&& policy,
ForwardIt1 first1, ForwardIt1 last1,
class BinaryOp1, class BinaryOp2 >
T transform_reduce( InputIt1 first1, InputIt1 last1,
InputIt2 first2, T init,
(constexpr since C++20)
class ForwardIt1, class ForwardIt2, class T,
class BinaryOp1, class BinaryOp2 >
T transform_reduce( ExecutionPolicy&& policy,
ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, T init,
class BinaryOp, class UnaryOp >
T transform_reduce( InputIt first, InputIt last, T init,
(constexpr since C++20)
class ForwardIt, class T,
class BinaryOp, class UnaryOp >
T transform_reduce( ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last, T init,
std::plus <>(), std::multiplies <>()), effectively parallelized version of the default std::inner_product .
[
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.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))
-
T
is not MoveConstructible. - 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]
.
[
first,
last)
and reduces the results (possibly permuted and aggregated in unspecified manner) along with the initial value init over reduce.T
, the program is ill-formed:
- reduce(init, init)
- reduce(init, transform(*first))
- reduce(transform(*first), init)
- reduce(transform(*first), transform(*first))
-
T
is not MoveConstructible. - transform or reduce modifies any element of
[
first,
last)
. - transform or reduce invalidates any iterator or subrange of
[
first,
last]
.
std::is_execution_policy_v <std::decay_t <ExecutionPolicy>> is true.
(until C++20)std::is_execution_policy_v <std::remove_cvref_t <ExecutionPolicy>> is true.
(since C++20)[edit] Parameters
InputIt1, InputIt2, InputIt
must meet the requirements of LegacyInputIterator.
ForwardIt1, ForwardIt2, ForwardIt
must meet the requirements of LegacyForwardIterator.
[edit] Return value
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.
[edit] Complexity
Given \(\scriptsize N\)N as std::distance (first1, last1) (or std::distance (first, last) for overloads (5,6)):
[edit] 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 standard policies, std::terminate is called. For any otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory, std::bad_alloc is thrown.
[edit] Notes
transform is never applied to init.
If first == last or first1 == last1, init is returned, unmodified.
[edit] Example
transform_reduce
can be used to parallelize std::inner_product . Some systems may need additional support to get advantages of parallel execution. E.g., on GNU/Linux, the Intel TBB be installed and -ltbb option be provided to gcc/clang compiler.
#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 * a void print_sum_squared(long const num) { 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 ... const std::vector <long> v{[n = num * 4] { std::vector <long> v; v.reserve(n); std::generate_n (std::back_inserter (v), n, [i = 0]() mutable { return 1 + i++ % 4; }); return v; }()}; auto squared_sum = [](auto sum, auto val) { return sum + val * val; }; auto sum1 = std::accumulate (v.cbegin(), v.cend(), 0L, squared_sum); std::cout << "accumulate(): " << sum1 << '\n'; auto sum2 = std::reduce (PAR v.cbegin(), v.cend(), 0L, squared_sum); std::cout << "reduce(): " << sum2 << '\n'; auto sum3 = std::transform_reduce(PAR v.cbegin(), v.cend(), 0L, std::plus {}, [](auto val) { return val * val; }); std::cout << "transform_reduce(): " << sum3 << "\n\n"; } int main() { 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
[edit] See also
(function template) [edit]