std::reduce
<numeric>
typename std::iterator_traits <InputIt>::value_type
(constexpr since C++20)
typename std::iterator_traits <ForwardIt>::value_type
reduce( ExecutionPolicy&& policy,
T reduce( InputIt first, InputIt last, T init );
(constexpr since C++20)
T reduce( ExecutionPolicy&& policy,
T reduce( InputIt first, InputIt last, T init, BinaryOp op );
(constexpr since C++20)
class ForwardIt, class T, class BinaryOp >
T reduce( ExecutionPolicy&& policy,
[
first,
last)
, possibly permuted and aggregated in unspecified manner, along with the initial value init over op.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)Given binary_op as the actual binary operation:
- The result is non-deterministic if the binary_op 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:
- binary_op(init, *first)
- binary_op(*first, init)
- binary_op(init, init)
- binary_op(*first, *first)
- If any of the following conditions is satisfied, the behavior is undefined:
-
T
is not MoveConstructible. - binary_op modifies any element of
[
first,
last)
. - binary_op invalidates any iterator or subrange of
[
first,
last]
.
-
[edit] Parameters
InputIt
must meet the requirements of LegacyInputIterator.
ForwardIt
must meet the requirements of LegacyForwardIterator.
[edit] Return value
[
first,
last)
over op.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 (first, last):
[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
std::reduce
behaves like std::accumulate except the elements of the range may be grouped and rearranged in arbitrary order.
[edit] Example
Side-by-side comparison between std::reduce
and std::accumulate :
#if PARALLEL #include <execution> #define SEQ std::execution::seq, #define PAR std::execution::par, #else #define SEQ #define PAR #endif #include <chrono> #include <iomanip> #include <iostream> #include <locale> #include <numeric> #include <utility> #include <vector> int main() { std::cout.imbue(std::locale ("en_US.UTF-8")); std::cout << std::fixed << std::setprecision (1); auto eval = [](auto fun) { const auto t1 = std::chrono::high_resolution_clock::now (); const auto [name, result] = fun(); const auto t2 = std::chrono::high_resolution_clock::now (); const std::chrono::duration <double, std::milli > ms = t2 - t1; std::cout << std::setw (28) << std::left << name << "sum: " << result << '\t' << "time: " << ms.count() << " ms\n"; }; { const std::vector <double> v(100'000'007, 0.1); eval([&v]{ return std::pair {"std::accumulate (double)", std::accumulate (v.cbegin(), v.cend(), 0.0)}; }); eval([&v]{ return std::pair {"std::reduce (seq, double)", std::reduce(SEQ v.cbegin(), v.cend())}; }); eval([&v]{ return std::pair {"std::reduce (par, double)", std::reduce(PAR v.cbegin(), v.cend())}; }); } { const std::vector <long> v(100'000'007, 1); eval([&v]{ return std::pair {"std::accumulate (long)", std::accumulate (v.cbegin(), v.cend(), 0l)}; }); eval([&v]{ return std::pair {"std::reduce (seq, long)", std::reduce(SEQ v.cbegin(), v.cend())}; }); eval([&v]{ return std::pair {"std::reduce (par, long)", std::reduce(PAR v.cbegin(), v.cend())}; }); } }
Possible output:
// POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3; ./a.out std::accumulate (double) sum: 10,000,000.7 time: 356.9 ms std::reduce (seq, double) sum: 10,000,000.7 time: 140.1 ms std::reduce (par, double) sum: 10,000,000.7 time: 140.1 ms std::accumulate (long) sum: 100,000,007 time: 46.0 ms std::reduce (seq, long) sum: 100,000,007 time: 67.3 ms std::reduce (par, long) sum: 100,000,007 time: 63.3 ms // POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3 -DPARALLEL; ./a.out std::accumulate (double) sum: 10,000,000.7 time: 353.4 ms std::reduce (seq, double) sum: 10,000,000.7 time: 140.7 ms std::reduce (par, double) sum: 10,000,000.7 time: 24.7 ms std::accumulate (long) sum: 100,000,007 time: 42.4 ms std::reduce (seq, long) sum: 100,000,007 time: 52.0 ms std::reduce (par, long) sum: 100,000,007 time: 23.1 ms
[edit] See also
(function template) [edit]