cppdraft_translate/cppdraft/inclusive/scan.md

[inclusive.scan]

# 26 Algorithms library [[algorithms]](./#algorithms)

## 26.10 Generalized numeric operations [[numeric.ops]](numeric.ops#inclusive.scan)

### 26.10.9 Inclusive scan [inclusive.scan]

[🔗](#lib:inclusive_scan)

`template<class InputIterator, class OutputIterator>
  constexpr OutputIterator
    inclusive_scan(InputIterator first, InputIterator last,
                   OutputIterator result);
`

[1](#1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12816)

*Effects*: Equivalent to:return inclusive_scan(first, last, result, plus<>());

[🔗](#lib:inclusive_scan_)

`template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
  ForwardIterator2
    inclusive_scan(ExecutionPolicy&& exec,
                   ForwardIterator1 first, ForwardIterator1 last,
                   ForwardIterator2 result);
`

[2](#2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12834)

*Effects*: Equivalent to:return inclusive_scan(std::forward<ExecutionPolicy>(exec), first, last, result, plus<>());

[🔗](#lib:inclusive_scan__)

`template<class InputIterator, class OutputIterator, class BinaryOperation>
  constexpr OutputIterator
    inclusive_scan(InputIterator first, InputIterator last,
                   OutputIterator result, BinaryOperation binary_op);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
         class BinaryOperation>
  ForwardIterator2
    inclusive_scan(ExecutionPolicy&& exec,
                   ForwardIterator1 first, ForwardIterator1 last,
                   ForwardIterator2 result, BinaryOperation binary_op);

template<class InputIterator, class OutputIterator, class BinaryOperation, class T>
  constexpr OutputIterator
    inclusive_scan(InputIterator first, InputIterator last,
                   OutputIterator result, BinaryOperation binary_op, T init);
template<class ExecutionPolicy,
         class ForwardIterator1, class ForwardIterator2, class BinaryOperation, class T>
  ForwardIterator2
    inclusive_scan(ExecutionPolicy&& exec,
                   ForwardIterator1 first, ForwardIterator1 last,
                   ForwardIterator2 result, BinaryOperation binary_op, T init);
`

[3](#3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12868)

Let U be the value type of decltype(first)[.](#3.sentence-1)

[4](#4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12871)

*Mandates*: If init is provided, all of

- [(4.1)](#4.1)

binary_op(init, init),

- [(4.2)](#4.2)

binary_op(init, *first), and

- [(4.3)](#4.3)

binary_op(*first, *first)

are convertible to T;
otherwise, binary_op(*first, *first) is convertible to U[.](#4.sentence-1)

[5](#5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12883)

*Preconditions*: 

- [(5.1)](#5.1)

  If init is provided, 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;
 otherwise, U meets the [*Cpp17MoveConstructible*](utility.arg.requirements#:Cpp17MoveConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements[.](#5.1.sentence-1)

- [(5.2)](#5.2)

  binary_op neither invalidates iterators or subranges,
 nor modifies elements in
 the ranges [first, last] or [result, result + (last - first)][.](#5.2.sentence-1)

[6](#6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12897)

*Effects*: For each integer K in [0, last - first)
assigns through result + K the value of

- [(6.1)](#6.1)

  *GENERALIZED_NONCOMMUTATIVE_SUM*(  
 binary_op,
 init, *(first + 0), *(first + 1), …, *(first + K))  
  if init is provided, or

- [(6.2)](#6.2)

  *GENERALIZED_NONCOMMUTATIVE_SUM*(  
 binary_op, *(first + 0), *(first + 1), …, *(first + K))  
  otherwise[.](#6.2.sentence-2)

[7](#7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12910)

*Returns*: The end of the resulting range beginning at result[.](#7.sentence-1)

[8](#8)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12914)

*Complexity*: O(last - first) applications of binary_op[.](#8.sentence-1)

[9](#9)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12918)

*Remarks*: result may be equal to first[.](#9.sentence-1)

[10](#10)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L12922)

[*Note [1](#note-1)*:

The difference between exclusive_scan and inclusive_scan is
that inclusive_scan includes the ith input element
in the ith sum[.](#10.sentence-1)

If binary_op is not mathematically associative,
the behavior of inclusive_scan can be nondeterministic[.](#10.sentence-2)

— *end note*]