std::reduce() algorithm
- od C++20
- od C++17
// (1)
template< class InputIt >
constexpr typename std::iterator_traits<InputIt>::value_type
reduce( InputIt first, InputIt last );
// (2)
template< class InputIt, class T >
constexpr T reduce( InputIt first, InputIt last, T init );
// (3)
template< class InputIt, class T, class BinaryOp >
constexpr T reduce( InputIt first, InputIt last, T init, BinaryOp binary_op );
// (4)
template< class ExecutionPolicy, class ForwardIt >
typename std::iterator_traits<ForwardIt>::value_type
reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );
// (5)
template< class ExecutionPolicy, class ForwardIt, class T >
T reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init );
// (6)
template< class ExecutionPolicy, class ForwardIt, class T, class BinaryOp >
T reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init, BinaryOp binary_op );
// (1)
template< class InputIt >
typename std::iterator_traits<InputIt>::value_type
reduce( InputIt first, InputIt last );
// (2)
template< class InputIt, class T >
T reduce( InputIt first, InputIt last, T init );
// (3)
template< class InputIt, class T, class BinaryOp >
T reduce( InputIt first, InputIt last, T init, BinaryOp binary_op );
// (4)
template< class ExecutionPolicy, class ForwardIt >
typename std::iterator_traits<ForwardIt>::value_type
reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );
// (5)
template< class ExecutionPolicy, class ForwardIt, class T >
T reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init );
// (6)
template< class ExecutionPolicy, class ForwardIt, class T, class BinaryOp >
T reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init, BinaryOp binary_op );
-
(1) Same as
reduce(first, last, typename std::iterator_traits<InputIt>::value_type{})
-
(2) Same as
reduce(first, last, init, std::plus<>())
-
(3) Reduces the range [
first
;last
), possibly permuted and aggregated in unspecified manner, along with the initial value init overbinary_op
. -
(4 - 6) Same as (1 - 3), but executed according to policy.
Overload ResolutionThese overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
istrue
. (do C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
istrue
. (od C++20)
The behavior is non-deterministic if binary_op
is not associative or not commutative.
The behavior is undefined
ifbinary_op
modifies any element or invalidates any iterator in [first
, last
), including the end iterator.Parameters
first last | The range of elements to apply the algorithm to. |
init | The initial value of the generalized sum. |
policy | The execution policy to use. See execution policy for details. |
binary_op | Binary FunctionObject that will be applied in unspecified order to the result of dereferencing the input iterators, the results of other |
Type requirements
InputIt | LegacyInputIterator |
ForwardIt | LegacyForwardIterator |
T | MoveAssignable MoveConstructible |
- The following expressions must be convertible to
T
:binary_op(init, *first)
binary_op(*first, init)
binary_op(init, init)
binary_op(*first, *first)
Return value
Generalized sum of init
and *first
, *(first + 1)
, ... *(last - 1)
over binary_op
,
Behaves like std::reduce
except the elements of the range may be grouped and rearranged in arbitrary order.
Formallly, the generalized sum GSUM(op, a1, ..., aN)
is defined as follows:
- If
N = 1
,a1
- If
N > 1
,op(GSUM(op, b 1, ..., b K), GSUM(op, b M, ..., b N))
whereb1
, ...,bN
may be any permutation ofa1
, ...,aN
- and
1 < K + 1 = M ≤ N
If the range is empty, init
is returned, unmodified
Complexity
O(last - first) applications of binary_op
.
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.
Examples
#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 <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::reduce (double)",
std::reduce(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::reduce (long)",
std::reduce(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())}; } );
}
}
// POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3; ./a.out
std::reduce (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::reduce (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::reduce (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::reduce (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
Hover to see the original license.