128 lines
4.0 KiB
Markdown
128 lines
4.0 KiB
Markdown
[exclusive.scan]
|
||
|
||
# 26 Algorithms library [[algorithms]](./#algorithms)
|
||
|
||
## 26.10 Generalized numeric operations [[numeric.ops]](numeric.ops#exclusive.scan)
|
||
|
||
### 26.10.8 Exclusive scan [exclusive.scan]
|
||
|
||
[ð](#lib:exclusive_scan)
|
||
|
||
`template<class InputIterator, class OutputIterator, class T>
|
||
constexpr OutputIterator
|
||
exclusive_scan(InputIterator first, InputIterator last,
|
||
OutputIterator result, T init);
|
||
`
|
||
|
||
[1](#1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12710)
|
||
|
||
*Effects*: Equivalent to:return exclusive_scan(first, last, result, init, plus<>());
|
||
|
||
[ð](#lib:exclusive_scan_)
|
||
|
||
`template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T>
|
||
ForwardIterator2
|
||
exclusive_scan(ExecutionPolicy&& exec,
|
||
ForwardIterator1 first, ForwardIterator1 last,
|
||
ForwardIterator2 result, T init);
|
||
`
|
||
|
||
[2](#2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12728)
|
||
|
||
*Effects*: Equivalent to:return exclusive_scan(std::forward<ExecutionPolicy>(exec),
|
||
first, last, result, init, plus<>());
|
||
|
||
[ð](#lib:exclusive_scan__)
|
||
|
||
`template<class InputIterator, class OutputIterator, class T, class BinaryOperation>
|
||
constexpr OutputIterator
|
||
exclusive_scan(InputIterator first, InputIterator last,
|
||
OutputIterator result, T init, BinaryOperation binary_op);
|
||
template<class ExecutionPolicy,
|
||
class ForwardIterator1, class ForwardIterator2, class T, class BinaryOperation>
|
||
ForwardIterator2
|
||
exclusive_scan(ExecutionPolicy&& exec,
|
||
ForwardIterator1 first, ForwardIterator1 last,
|
||
ForwardIterator2 result, T init, BinaryOperation binary_op);
|
||
`
|
||
|
||
[3](#3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12752)
|
||
|
||
*Mandates*: All of
|
||
|
||
- [(3.1)](#3.1)
|
||
|
||
binary_op(init, init),
|
||
|
||
- [(3.2)](#3.2)
|
||
|
||
binary_op(init, *first), and
|
||
|
||
- [(3.3)](#3.3)
|
||
|
||
binary_op(*first, *first)
|
||
|
||
are convertible to T[.](#3.sentence-1)
|
||
|
||
[4](#4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12763)
|
||
|
||
*Preconditions*:
|
||
|
||
- [(4.1)](#4.1)
|
||
|
||
T meets the [*Cpp17MoveConstructible*](utility.arg.requirements#:Cpp17MoveConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [31](utility.arg.requirements#tab:cpp17.moveconstructible "Table 31: Cpp17MoveConstructible requirements")) requirements[.](#4.1.sentence-1)
|
||
|
||
- [(4.2)](#4.2)
|
||
|
||
binary_op neither invalidates iterators or subranges,
|
||
nor modifies elements in
|
||
the ranges [first, last] or [result, result + (last - first)][.](#4.2.sentence-1)
|
||
|
||
[5](#5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12774)
|
||
|
||
*Effects*: For each integer K in [0, last - first)
|
||
assigns through result + K the value of:*GENERALIZED_NONCOMMUTATIVE_SUM*( binary_op, init, *(first + 0), *(first + 1), …, *(first + K - 1))
|
||
|
||
[6](#6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12783)
|
||
|
||
*Returns*: The end of the resulting range beginning at result[.](#6.sentence-1)
|
||
|
||
[7](#7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12787)
|
||
|
||
*Complexity*: O(last - first) applications of binary_op[.](#7.sentence-1)
|
||
|
||
[8](#8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12791)
|
||
|
||
*Remarks*: result may be equal to first[.](#8.sentence-1)
|
||
|
||
[9](#9)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12795)
|
||
|
||
[*Note [1](#note-1)*:
|
||
|
||
The difference between exclusive_scan and inclusive_scan is
|
||
that exclusive_scan excludes the ith input element
|
||
from the ith sum[.](#9.sentence-1)
|
||
|
||
If binary_op is not mathematically associative,
|
||
the behavior of exclusive_scan can be nondeterministic[.](#9.sentence-2)
|
||
|
||
â *end note*]
|