std::exclusive_scan() algorithm
- od C++20
- od C++17
// (1)
template< class InputIt, class OutputIt >
constexpr OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first );
// (2)
template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first, BinaryOperation binary_op );
// (3)
template< class InputIt, class OutputIt, class BinaryOperation, class T >
constexpr OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first, BinaryOperation binary_op, T init );
// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardtIt2 exclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first );
// (5)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOperation >
ForwardIt2 exclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
BinaryOperation binary_op );
// (6)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOperation, class T >
ForwardIt2 exclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
BinaryOperation binary_op, T init );
// (1)
template< class InputIt, class OutputIt >
OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first );
// (2)
template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first, BinaryOperation binary_op );
// (3)
template< class InputIt, class OutputIt, class BinaryOperation, class T >
OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first, BinaryOperation binary_op, T init );
// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardtIt2 exclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first );
// (5)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOperation >
ForwardIt2 exclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
BinaryOperation binary_op );
// (6)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOperation, class T >
ForwardIt2 exclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
BinaryOperation binary_op, T init );
Computes an exclusive prefix sum operation using binary_op
(or std::plus<>()
for overloads (1, 4)) for the range [first
; last
), using init
as the initial value (if provided), 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:
- (1, 2, 4, 5) The generalized noncommutative sum of
*j
... for everyj
in [first
;first + (i - d_first + 1) )
overbinary_op
- (3, 6) The generalized noncommutative sum of
init
,*j
... for everyj
in [first
;first + (i - d_first + 1))
overbinary_op
where generalized noncommutative sum GNSUM(op, a1, ..., aN)
is defined as follows:
-
If
N = 1
,a1
-
If
N > 1
,op(GNSUM(op, a1, ..., aK)
,GNSUM(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)
binary_op
shall not invalidate iterators (including the end iterators) or subranges, nor modify elements in the ranges [first
, last
) or [d_first
, d_first + (last - first)
).
Otherwise, the behavior is undefined
.Parameters
first last | The range of elements to sum. |
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. |
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 |
OutputIt | LegacyOutputIterator |
ForwardIt1 ForwardIt2 | LegacyForwardIterator |
T
(ifinit
is provided) must meet the requirements ofMoveConstructible
. The following expressions must be convertible toT
:binary_op(init, *first)
binary_op(init, init)
binary_op(*first, *first)
Return value
Iterator to the element past the last element written.
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
#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
int main()
{
std::vector data {3, 1, 4, 1, 5, 9, 2, 6};
std::cout << "Exclusive sum: ";
std::exclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
0);
std::cout << "\nInclusive sum: ";
std::inclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n\nExclusive product: ";
std::exclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
1, std::multiplies<>{});
std::cout << "\nInclusive product: ";
std::inclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
std::multiplies<>{});
}
Exclusive sum: 0 3 4 8 9 14 23 25
Inclusive sum: 3 4 8 9 14 23 25 31
Exclusive product: 1 3 3 12 12 60 540 1080
Inclusive product: 3 3 12 12 60 540 1080 6480
Hover to see the original license.