std::transform_exclusive_scan() algorithm
- od C++20
- od C++17
// (1)
template< class InputIt, class OutputIt, class T, class BinaryOperation, class UnaryOperation >
constexpr OutputIt transform_exclusive_scan( InputIt first, InputIt last, OutputIt d_first, T init,
BinaryOperation binary_op, UnaryOperation unary_op );
// (2)
template<
class ExecutionPolicy,
class ForwardIt1,
class ForwardIt2,
class T,
class BinaryOperation,
class UnaryOperation
>
ForwardIt2 transform_exclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
T init, BinaryOperation binary_op, UnaryOperation unary_op );
// (1)
template< class InputIt, class OutputIt, class T, class BinaryOperation, class UnaryOperation >
OutputIt transform_exclusive_scan( InputIt first, InputIt last, OutputIt d_first, T init,
BinaryOperation binary_op, UnaryOperation unary_op );
// (2)
template<
class ExecutionPolicy,
class ForwardIt1,
class ForwardIt2,
class T,
class BinaryOperation,
class UnaryOperation
>
ForwardIt2 transform_exclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
T init, BinaryOperation binary_op, UnaryOperation unary_op );
Transforms each element in the range [first
; last
) with unary_op
, then computes an exclusive prefix sum operation
using binary_op
over the resulting range, with init
as the initial value, and writes the results to the range
beginning at d_first
.
"exclusive" means that the i-th input element is not included in the i-th sum.
The summation operations may be performed in arbitrary order, and the behavior is nondeterministic if binary_op
is not associative.
Formally, assigns through each iterator i
in [d_first
; d_first + (last - first
)) the value of the generalized
noncommutative sum of init
, unary_op(*j)
... for every j
in [first
; first + (i - d_first
)) over binary_op
,
The generalized sum GSUM(op, a1, ..., aN)
is defined as follows:
-
If
N = 1
,a1
-
If
N > 1
,op(GSUM(op, a1, ..., aK), GSUM(op, aM, ..., aN))
for anyK
where1 < K + 1 = M ≤ N
-
(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 undefined
ifunary_op
and binary_op
invalidate iterators (including the end iterators) or subranges, or modify elements in the ranges [first
; last
)
or [d_first
; d_first + (last - first
)).Parameters
first last | The range of elements to apply the algorithm to. |
d_first | The beginning of the destination range, may be equal to |
init | The initial value of the generalized sum. |
policy | The execution policy to use. See execution policy for details. |
exclusive_scan | Unary FunctionObject that will be applied to each element of the
input range. The return type must be acceptable as input to |
transform | Binary FunctionObject that will be applied in to the result of |
Type requirements
InputIt | LegacyInputIterator |
OutputIt | LegacyOutputIterator |
ForwardIt1 ForwardIt2 | LegacyForwardIterator |
T | MoveConstructible |
The following expressions have to be convertible to T
:
binary_op(init, unary_op(*first))
binary_op(init, init)
binary_op(unary_op(*first), unary_op(*first))
Return value
Iterator to the element past the last element written.
Complexity
O(last - first) applications of each of binary_op
and unary_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.
Notes
unary_op
is not applied to init.
Examples
#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
int main()
{
std::vector data {3, 1, 4, 1, 5, 9, 2, 6};
auto times_10 = [](int x) { return x * 10; };
std::cout << "10 times exclusive sum: ";
std::transform_exclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
0, std::plus<int>{}, times_10);
std::cout << "\n10 times inclusive sum: ";
std::transform_inclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
std::plus<int>{}, times_10);
}
10 times exclusive sum: 0 30 40 80 90 140 230 250
10 times inclusive sum: 30 40 80 90 140 230 250 310
Hover to see the original license.