cppdraft_translate/cppdraft/numeric/ops.md

[numeric.ops]

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

## 26.10 Generalized numeric operations [numeric.ops]

### [26.10.1](#general) General [[numeric.ops.general]](numeric.ops.general)

[1](#general-1)

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

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

The use of closed ranges as well as semi-open ranges
to specify requirements throughout [numeric.ops] is intentional[.](#general-1.sentence-1)

— *end note*]

### [26.10.2](#numerics.defns) Definitions [[numerics.defns]](numerics.defns)

[1](#numerics.defns-1)

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

Define *GENERALIZED_NONCOMMUTATIVE_SUM*(op, a1, …, aN) as follows:

- [(1.1)](#numerics.defns-1.1)

a1 when N is 1, otherwise

- [(1.2)](#numerics.defns-1.2)

op(*GENERALIZED_NONCOMMUTATIVE_SUM*(op, a1, …, aK),   
  op(*GENERALIZED_NONCOMMUTATIVE_SUM*(op, aM, …, aN)) for any K where 1<K+1=M≤N[.](#numerics.defns-1.2.sentence-2)

[2](#numerics.defns-2)

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

Define *GENERALIZED_SUM*(op, a1, …, aN) as*GENERALIZED_NONCOMMUTATIVE_SUM*(op, b1, …, bN),  
whereb1, …, bN may be any permutation of a1, …, aN[.](#numerics.defns-2.sentence-1)

### [26.10.3](#accumulate) Accumulate [[accumulate]](accumulate)

[🔗](#lib:accumulate)

`template<class InputIterator, class T>
  constexpr T accumulate(InputIterator first, InputIterator last, T init);
template<class InputIterator, class T, class BinaryOperation>
  constexpr T accumulate(InputIterator first, InputIterator last, T init,
                         BinaryOperation binary_op);
`

[1](#accumulate-1)

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

*Preconditions*: T meets
the [*Cpp17CopyConstructible*](utility.arg.requirements#:Cpp17CopyConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [32](utility.arg.requirements#tab:cpp17.copyconstructible "Table 32: Cpp17CopyConstructible requirements (in addition to Cpp17MoveConstructible)"))
and [*Cpp17CopyAssignable*](utility.arg.requirements#:Cpp17CopyAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [34](utility.arg.requirements#tab:cpp17.copyassignable "Table 34: Cpp17CopyAssignable requirements (in addition to Cpp17MoveAssignable)")) requirements[.](#accumulate-1.sentence-1)

In the range [first, last],binary_op neither modifies elements
nor invalidates iterators or subranges[.](#accumulate-1.sentence-2)[205](#footnote-205 "The use of fully closed ranges is intentional.")

[2](#accumulate-2)

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

*Effects*: Computes its result by
initializing the accumulator acc with the initial value init and then modifies it withacc = std​::​move(acc) + *i oracc = binary_op(std​::​move(acc), *i) for every iterator i in the range [first, last) in order[.](#accumulate-2.sentence-1)[206](#footnote-206 "accumulate is similar to the APL reduction operator and Common Lisp reduce function, but it avoids the difficulty of defining the result of reduction on an empty sequence by always requiring an initial value.")

[205)](#footnote-205)[205)](#footnoteref-205)

The use of fully closed ranges is intentional[.](#footnote-205.sentence-1)

[206)](#footnote-206)[206)](#footnoteref-206)

accumulate is similar
to the APL reduction operator and Common Lisp reduce function,
but it avoids the difficulty of defining the result of reduction
on an empty sequence by always requiring an initial value[.](#footnote-206.sentence-1)

### [26.10.4](#reduce) Reduce [[reduce]](reduce)

[🔗](#lib:reduce)

`template<class InputIterator>
  constexpr typename iterator_traits<InputIterator>::value_type
    reduce(InputIterator first, InputIterator last);
`

[1](#reduce-1)

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

*Effects*: Equivalent to:return reduce(first, last, typename iterator_traits<InputIterator>::value_type{});

[🔗](#lib:reduce_)

`template<class ExecutionPolicy, class ForwardIterator>
  typename iterator_traits<ForwardIterator>::value_type
    reduce(ExecutionPolicy&& exec,
           ForwardIterator first, ForwardIterator last);
`

[2](#reduce-2)

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

*Effects*: Equivalent to:return reduce(std::forward<ExecutionPolicy>(exec), first, last, typename iterator_traits<ForwardIterator>::value_type{});

[🔗](#lib:reduce__)

`template<class InputIterator, class T>
  constexpr T reduce(InputIterator first, InputIterator last, T init);
`

[3](#reduce-3)

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

*Effects*: Equivalent to:return reduce(first, last, init, plus<>());

[🔗](#lib:reduce___)

`template<class ExecutionPolicy, class ForwardIterator, class T>
  T reduce(ExecutionPolicy&& exec,
           ForwardIterator first, ForwardIterator last, T init);
`

[4](#reduce-4)

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

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

[🔗](#lib:reduce____)

`template<class InputIterator, class T, class BinaryOperation>
  constexpr T reduce(InputIterator first, InputIterator last, T init,
                     BinaryOperation binary_op);
template<class ExecutionPolicy, class ForwardIterator, class T, class BinaryOperation>
  T reduce(ExecutionPolicy&& exec,
           ForwardIterator first, ForwardIterator last, T init,
           BinaryOperation binary_op);
`

[5](#reduce-5)

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

*Mandates*: All of

- [(5.1)](#reduce-5.1)

binary_op(init, *first),

- [(5.2)](#reduce-5.2)

binary_op(*first, init),

- [(5.3)](#reduce-5.3)

binary_op(init, init), and

- [(5.4)](#reduce-5.4)

binary_op(*first, *first)

are convertible to T[.](#reduce-5.sentence-1)

[6](#reduce-6)

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

*Preconditions*: 

- [(6.1)](#reduce-6.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[.](#reduce-6.1.sentence-1)

- [(6.2)](#reduce-6.2)

  binary_op neither invalidates iterators or subranges,
 nor modifies elements in the range [first, last][.](#reduce-6.2.sentence-1)

[7](#reduce-7)

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

*Returns*: *GENERALIZED_SUM*(binary_op, init, *i, …) for every i in [first, last)[.](#reduce-7.sentence-1)

[8](#reduce-8)

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

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

[9](#reduce-9)

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

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

The difference between reduce and accumulate is thatreduce applies binary_op in an unspecified order,
which yields a nondeterministic result
for non-associative or non-commutative binary_op such as floating-point addition[.](#reduce-9.sentence-1)

— *end note*]

### [26.10.5](#inner.product) Inner product [[inner.product]](inner.product)

[🔗](#lib:inner_product)

`template<class InputIterator1, class InputIterator2, class T>
  constexpr T inner_product(InputIterator1 first1, InputIterator1 last1,
                            InputIterator2 first2, T init);
template<class InputIterator1, class InputIterator2, class T,
         class BinaryOperation1, class BinaryOperation2>
  constexpr T inner_product(InputIterator1 first1, InputIterator1 last1,
                            InputIterator2 first2, T init,
                            BinaryOperation1 binary_op1,
                            BinaryOperation2 binary_op2);
`

[1](#inner.product-1)

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

*Preconditions*: T meets
the [*Cpp17CopyConstructible*](utility.arg.requirements#:Cpp17CopyConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [32](utility.arg.requirements#tab:cpp17.copyconstructible "Table 32: Cpp17CopyConstructible requirements (in addition to Cpp17MoveConstructible)"))
and [*Cpp17CopyAssignable*](utility.arg.requirements#:Cpp17CopyAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [34](utility.arg.requirements#tab:cpp17.copyassignable "Table 34: Cpp17CopyAssignable requirements (in addition to Cpp17MoveAssignable)")) requirements[.](#inner.product-1.sentence-1)

In the ranges [first1, last1] and
[first2, first2 + (last1 - first1)]binary_op1 and binary_op2 neither modifies elements nor invalidates iterators or subranges[.](#inner.product-1.sentence-2)[207](#footnote-207 "The use of fully closed ranges is intentional.")

[2](#inner.product-2)

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

*Effects*: Computes its result by
initializing the accumulator acc with the initial value init and then modifying it withacc = std​::​move(acc) + (*i1) * (*i2) oracc = binary_op1(std​::​move(acc), binary_op2(*i1, *i2)) for every iterator i1 in the range [first1, last1)
and iterator i2 in the range [first2, first2 + (last1 - first1))
in order[.](#inner.product-2.sentence-1)

[207)](#footnote-207)[207)](#footnoteref-207)

The use of fully closed ranges is intentional[.](#footnote-207.sentence-1)

### [26.10.6](#transform.reduce) Transform reduce [[transform.reduce]](transform.reduce)

[🔗](#lib:transform_reduce)

`template<class InputIterator1, class InputIterator2, class T>
  constexpr T transform_reduce(InputIterator1 first1, InputIterator1 last1,
                               InputIterator2 first2,
                               T init);
`

[1](#transform.reduce-1)

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

*Effects*: Equivalent to:return transform_reduce(first1, last1, first2, init, plus<>(), multiplies<>());

[🔗](#lib:transform_reduce_)

`template<class ExecutionPolicy,
         class ForwardIterator1, class ForwardIterator2, class T>
  T transform_reduce(ExecutionPolicy&& exec,
                     ForwardIterator1 first1, ForwardIterator1 last1,
                     ForwardIterator2 first2,
                     T init);
`

[2](#transform.reduce-2)

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

*Effects*: Equivalent to:return transform_reduce(std::forward<ExecutionPolicy>(exec),
 first1, last1, first2, init, plus<>(), multiplies<>());

[🔗](#lib:transform_reduce__)

`template<class InputIterator1, class InputIterator2, class T,
         class BinaryOperation1, class BinaryOperation2>
  constexpr T transform_reduce(InputIterator1 first1, InputIterator1 last1,
                               InputIterator2 first2,
                               T init,
                               BinaryOperation1 binary_op1,
                               BinaryOperation2 binary_op2);
template<class ExecutionPolicy,
         class ForwardIterator1, class ForwardIterator2, class T,
         class BinaryOperation1, class BinaryOperation2>
  T transform_reduce(ExecutionPolicy&& exec,
                     ForwardIterator1 first1, ForwardIterator1 last1,
                     ForwardIterator2 first2,
                     T init,
                     BinaryOperation1 binary_op1,
                     BinaryOperation2 binary_op2);
`

[3](#transform.reduce-3)

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

*Mandates*: All of 

- [(3.1)](#transform.reduce-3.1)

binary_op1(init, init),

- [(3.2)](#transform.reduce-3.2)

binary_op1(init, binary_op2(*first1, *first2)),

- [(3.3)](#transform.reduce-3.3)

binary_op1(binary_op2(*first1, *first2), init), and

- [(3.4)](#transform.reduce-3.4)

binary_op1(binary_op2(*first1, *first2), binary_op2(*first1, *first2))

are convertible to T[.](#transform.reduce-3.sentence-1)

[4](#transform.reduce-4)

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

*Preconditions*: 

- [(4.1)](#transform.reduce-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[.](#transform.reduce-4.1.sentence-1)

- [(4.2)](#transform.reduce-4.2)

  Neither binary_op1 nor binary_op2 invalidates subranges, nor modifies elements in the ranges
 [first1, last1] and [first2, first2 + (last1 - first1)][.](#transform.reduce-4.2.sentence-1)

[5](#transform.reduce-5)

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

*Returns*: *GENERALIZED_SUM*(binary_op1, init, binary_op2(*i, *(first2 + (i - first1))), …) for every iterator i in [first1, last1)[.](#transform.reduce-5.sentence-1)

[6](#transform.reduce-6)

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

*Complexity*: O(last1 - first1) applications each
of binary_op1 and binary_op2[.](#transform.reduce-6.sentence-1)

[🔗](#lib:transform_reduce___)

`template<class InputIterator, class T,
         class BinaryOperation, class UnaryOperation>
  constexpr T transform_reduce(InputIterator first, InputIterator last, T init,
                               BinaryOperation binary_op, UnaryOperation unary_op);
template<class ExecutionPolicy,
         class ForwardIterator, class T,
         class BinaryOperation, class UnaryOperation>
  T transform_reduce(ExecutionPolicy&& exec,
                     ForwardIterator first, ForwardIterator last,
                     T init, BinaryOperation binary_op, UnaryOperation unary_op);
`

[7](#transform.reduce-7)

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

*Mandates*: All of 

- [(7.1)](#transform.reduce-7.1)

binary_op(init, init),

- [(7.2)](#transform.reduce-7.2)

binary_op(init, unary_op(*first)),

- [(7.3)](#transform.reduce-7.3)

binary_op(unary_op(*first), init), and

- [(7.4)](#transform.reduce-7.4)

binary_op(unary_op(*first), unary_op(*first))

are convertible to T[.](#transform.reduce-7.sentence-1)

[8](#transform.reduce-8)

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

*Preconditions*: 

- [(8.1)](#transform.reduce-8.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[.](#transform.reduce-8.1.sentence-1)

- [(8.2)](#transform.reduce-8.2)

  Neither unary_op nor binary_op invalidates subranges,
 nor modifies elements in the range [first, last][.](#transform.reduce-8.2.sentence-1)

[9](#transform.reduce-9)

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

*Returns*: *GENERALIZED_SUM*(binary_op, init, unary_op(*i), …) for every iterator i in [first, last)[.](#transform.reduce-9.sentence-1)

[10](#transform.reduce-10)

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

*Complexity*: O(last - first) applications each of unary_op andbinary_op[.](#transform.reduce-10.sentence-1)

[11](#transform.reduce-11)

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

[*Note [1](#transform.reduce-note-1)*:

transform_reduce does not apply unary_op to init[.](#transform.reduce-11.sentence-1)

— *end note*]

### [26.10.7](#partial.sum) Partial sum [[partial.sum]](partial.sum)

[🔗](#lib:partial_sum)

`template<class InputIterator, class OutputIterator>
  constexpr OutputIterator
    partial_sum(InputIterator first, InputIterator last,
                OutputIterator result);
template<class InputIterator, class OutputIterator, class BinaryOperation>
  constexpr OutputIterator
    partial_sum(InputIterator first, InputIterator last,
                OutputIterator result, BinaryOperation binary_op);
`

[1](#partial.sum-1)

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

*Mandates*: InputIterator's value type is constructible from *first[.](#partial.sum-1.sentence-1)

The result of the
expression std​::​move(acc) + *i or binary_op(std​::​move(acc), *i) is implicitly convertible to InputIterator's value type[.](#partial.sum-1.sentence-2)

acc is writable ([[iterator.requirements.general]](iterator.requirements.general "24.3.1 General")) to result[.](#partial.sum-1.sentence-3)

[2](#partial.sum-2)

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

*Preconditions*: In the ranges [first, last] and [result, result + (last - first)]binary_op neither modifies elements
nor invalidates iterators or subranges[.](#partial.sum-2.sentence-1)[208](#footnote-208 "The use of fully closed ranges is intentional.")

[3](#partial.sum-3)

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

*Effects*: For a non-empty range,
the function creates an accumulator acc whose type is InputIterator's value type,
initializes it with *first,
and assigns the result to *result[.](#partial.sum-3.sentence-1)

For every iterator i in [first + 1, last) in order,acc is then modified byacc = std​::​move(acc) + *i or acc = binary_op(std​::​move(acc), *i) and the result is assigned to *(result + (i - first))[.](#partial.sum-3.sentence-2)

[4](#partial.sum-4)

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

*Returns*: result + (last - first)[.](#partial.sum-4.sentence-1)

[5](#partial.sum-5)

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

*Complexity*: Exactly (last - first) - 1 applications of the binary operation[.](#partial.sum-5.sentence-1)

[6](#partial.sum-6)

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

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

[208)](#footnote-208)[208)](#footnoteref-208)

The use of fully closed ranges is intentional[.](#footnote-208.sentence-1)

### [26.10.8](#exclusive.scan) Exclusive scan [[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](#exclusive.scan-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](#exclusive.scan-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](#exclusive.scan-3)

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

*Mandates*: All of 

- [(3.1)](#exclusive.scan-3.1)

binary_op(init, init),

- [(3.2)](#exclusive.scan-3.2)

binary_op(init, *first), and

- [(3.3)](#exclusive.scan-3.3)

binary_op(*first, *first)

are convertible to T[.](#exclusive.scan-3.sentence-1)

[4](#exclusive.scan-4)

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

*Preconditions*: 

- [(4.1)](#exclusive.scan-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[.](#exclusive.scan-4.1.sentence-1)

- [(4.2)](#exclusive.scan-4.2)

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

[5](#exclusive.scan-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](#exclusive.scan-6)

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

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

[7](#exclusive.scan-7)

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

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

[8](#exclusive.scan-8)

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

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

[9](#exclusive.scan-9)

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

[*Note [1](#exclusive.scan-note-1)*:

The difference between exclusive_scan and inclusive_scan is
that exclusive_scan excludes the ith input element
from the ith sum[.](#exclusive.scan-9.sentence-1)

If binary_op is not mathematically associative,
the behavior of exclusive_scan can be nondeterministic[.](#exclusive.scan-9.sentence-2)

— *end note*]

### [26.10.9](#inclusive.scan) Inclusive scan [[inclusive.scan]](inclusive.scan)

[🔗](#lib:inclusive_scan)

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

[1](#inclusive.scan-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](#inclusive.scan-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](#inclusive.scan-3)

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

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

[4](#inclusive.scan-4)

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

*Mandates*: If init is provided, all of

- [(4.1)](#inclusive.scan-4.1)

binary_op(init, init),

- [(4.2)](#inclusive.scan-4.2)

binary_op(init, *first), and

- [(4.3)](#inclusive.scan-4.3)

binary_op(*first, *first)

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

[5](#inclusive.scan-5)

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

*Preconditions*: 

- [(5.1)](#inclusive.scan-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[.](#inclusive.scan-5.1.sentence-1)

- [(5.2)](#inclusive.scan-5.2)

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

[6](#inclusive.scan-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)](#inclusive.scan-6.1)

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

- [(6.2)](#inclusive.scan-6.2)

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

[7](#inclusive.scan-7)

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

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

[8](#inclusive.scan-8)

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

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

[9](#inclusive.scan-9)

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

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

[10](#inclusive.scan-10)

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

[*Note [1](#inclusive.scan-note-1)*:

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

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

— *end note*]

### [26.10.10](#transform.exclusive.scan) Transform exclusive scan [[transform.exclusive.scan]](transform.exclusive.scan)

[🔗](#lib:transform_exclusive_scan)

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

[1](#transform.exclusive.scan-1)

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

*Mandates*: All of 

- [(1.1)](#transform.exclusive.scan-1.1)

binary_op(init, init),

- [(1.2)](#transform.exclusive.scan-1.2)

binary_op(init, unary_op(*first)), and

- [(1.3)](#transform.exclusive.scan-1.3)

binary_op(unary_op(*first), unary_op(*first))

are convertible to T[.](#transform.exclusive.scan-1.sentence-1)

[2](#transform.exclusive.scan-2)

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

*Preconditions*: 

- [(2.1)](#transform.exclusive.scan-2.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[.](#transform.exclusive.scan-2.1.sentence-1)

- [(2.2)](#transform.exclusive.scan-2.2)

  Neither unary_op nor binary_op invalidates iterators or subranges, nor modifies elements in
 the ranges [first, last] or [result, result + (last - first)][.](#transform.exclusive.scan-2.2.sentence-1)

[3](#transform.exclusive.scan-3)

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

*Effects*: For each integer K in [0, last - first)
assigns through result + K the value of:*GENERALIZED_NONCOMMUTATIVE_SUM*( binary_op, init,
 unary_op(*(first + 0)), unary_op(*(first + 1)), …, unary_op(*(first + K - 1)))

[4](#transform.exclusive.scan-4)

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

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

[5](#transform.exclusive.scan-5)

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

*Complexity*: O(last - first) applications each
of unary_op and binary_op[.](#transform.exclusive.scan-5.sentence-1)

[6](#transform.exclusive.scan-6)

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

*Remarks*: result may be equal to first[.](#transform.exclusive.scan-6.sentence-1)

[7](#transform.exclusive.scan-7)

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

[*Note [1](#transform.exclusive.scan-note-1)*:

The difference between transform_exclusive_scan andtransform_inclusive_scan is that transform_exclusive_scan excludes the ith input element from the ith sum[.](#transform.exclusive.scan-7.sentence-1)

If binary_op is not mathematically associative,
the behavior of transform_exclusive_scan can be nondeterministic[.](#transform.exclusive.scan-7.sentence-2)

transform_exclusive_scan does not apply unary_op to init[.](#transform.exclusive.scan-7.sentence-3)

— *end note*]

### [26.10.11](#transform.inclusive.scan) Transform inclusive scan [[transform.inclusive.scan]](transform.inclusive.scan)

[🔗](#lib:transform_inclusive_scan)

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

[1](#transform.inclusive.scan-1)

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

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

[2](#transform.inclusive.scan-2)

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

*Mandates*: If init is provided, all of

- [(2.1)](#transform.inclusive.scan-2.1)

binary_op(init, init),

- [(2.2)](#transform.inclusive.scan-2.2)

binary_op(init, unary_op(*first)), and

- [(2.3)](#transform.inclusive.scan-2.3)

binary_op(unary_op(*first), unary_op(*first))

are convertible to T;
otherwise, binary_op(unary_op(*first), unary_op(*first)) is convertible to U[.](#transform.inclusive.scan-2.sentence-1)

[3](#transform.inclusive.scan-3)

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

*Preconditions*: 

- [(3.1)](#transform.inclusive.scan-3.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[.](#transform.inclusive.scan-3.1.sentence-1)

- [(3.2)](#transform.inclusive.scan-3.2)

  Neither unary_op nor binary_op invalidates
 iterators or subranges, nor modifies elements in
 the ranges [first, last] or [result, result + (last - first)][.](#transform.inclusive.scan-3.2.sentence-1)

[4](#transform.inclusive.scan-4)

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

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

- [(4.1)](#transform.inclusive.scan-4.1)

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

- [(4.2)](#transform.inclusive.scan-4.2)

  *GENERALIZED_NONCOMMUTATIVE_SUM*(  
 binary_op,  
 unary_op(*(first + 0)), unary_op(*(first + 1)), …, unary_op(*(first + K)))  
   otherwise[.](#transform.inclusive.scan-4.2.sentence-2)

[5](#transform.inclusive.scan-5)

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

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

[6](#transform.inclusive.scan-6)

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

*Complexity*: O(last - first) applications each
of unary_op and binary_op[.](#transform.inclusive.scan-6.sentence-1)

[7](#transform.inclusive.scan-7)

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

*Remarks*: result may be equal to first[.](#transform.inclusive.scan-7.sentence-1)

[8](#transform.inclusive.scan-8)

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

[*Note [1](#transform.inclusive.scan-note-1)*:

The difference between transform_exclusive_scan andtransform_inclusive_scan is that transform_inclusive_scan includes the ith input element in the ith sum[.](#transform.inclusive.scan-8.sentence-1)

If binary_op is not mathematically associative,
the behavior of transform_inclusive_scan can be nondeterministic[.](#transform.inclusive.scan-8.sentence-2)

transform_inclusive_scan does not
apply unary_op to init[.](#transform.inclusive.scan-8.sentence-3)

— *end note*]

### [26.10.12](#adjacent.difference) Adjacent difference [[adjacent.difference]](adjacent.difference)

[🔗](#lib:adjacent_difference)

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

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

[1](#adjacent.difference-1)

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

Let T be the value type of decltype(first)[.](#adjacent.difference-1.sentence-1)

For the overloads that do not take an argument binary_op,
let binary_op be an lvalue
that denotes an object of type minus<>[.](#adjacent.difference-1.sentence-2)

[2](#adjacent.difference-2)

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

*Mandates*: 

- [(2.1)](#adjacent.difference-2.1)

  For the overloads with no ExecutionPolicy, T is constructible from *first[.](#adjacent.difference-2.1.sentence-1)
  acc (defined below) is
 writable ([[iterator.requirements.general]](iterator.requirements.general "24.3.1 General"))
 to the result output iterator[.](#adjacent.difference-2.1.sentence-2)
  The result of the expression binary_op(val, std​::​move(acc)) is writable to result[.](#adjacent.difference-2.1.sentence-3)

- [(2.2)](#adjacent.difference-2.2)

  For the overloads with an ExecutionPolicy,
 the result of the expressions binary_op(*first, *first) and *first are writable to result[.](#adjacent.difference-2.2.sentence-1)

[3](#adjacent.difference-3)

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

*Preconditions*: 

- [(3.1)](#adjacent.difference-3.1)

  For the overloads with no ExecutionPolicy, T meets the [*Cpp17MoveAssignable*](utility.arg.requirements#:Cpp17MoveAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [33](utility.arg.requirements#tab:cpp17.moveassignable "Table 33: Cpp17MoveAssignable requirements"))
 requirements[.](#adjacent.difference-3.1.sentence-1)

- [(3.2)](#adjacent.difference-3.2)

  For all overloads, in the ranges [first, last]
 and [result, result + (last - first)], binary_op neither modifies elements
 nor invalidates iterators or subranges[.](#adjacent.difference-3.2.sentence-1)[209](#footnote-209 "The use of fully closed ranges is intentional.")

[4](#adjacent.difference-4)

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

*Effects*: For the overloads with no ExecutionPolicy and a non-empty range,
the function creates an accumulator acc of type T,
initializes it with *first,
and assigns the result to *result[.](#adjacent.difference-4.sentence-1)

For every iterator i in [first + 1, last) in order,
creates an object val whose type is T,
initializes it with *i,
computes binary_op(val, std​::​move(acc)),
assigns the result to *(result + (i - first)), and
move assigns from val to acc[.](#adjacent.difference-4.sentence-2)

[5](#adjacent.difference-5)

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

For the overloads with an ExecutionPolicy and a non-empty range,
performs *result = *first[.](#adjacent.difference-5.sentence-1)

Then, for every d in [1, last - first - 1],
performs *(result + d) = binary_op(*(first + d), *(first + (d - 1)))[.](#adjacent.difference-5.sentence-2)

[6](#adjacent.difference-6)

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

*Returns*: result + (last - first)[.](#adjacent.difference-6.sentence-1)

[7](#adjacent.difference-7)

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

*Complexity*: Exactly (last - first) - 1 applications of the binary operation[.](#adjacent.difference-7.sentence-1)

[8](#adjacent.difference-8)

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

*Remarks*: For the overloads with no ExecutionPolicy,result may be equal to first[.](#adjacent.difference-8.sentence-1)

For the overloads with an ExecutionPolicy,
the ranges [first, last) and [result, result + (last - first))
shall not overlap[.](#adjacent.difference-8.sentence-2)

[209)](#footnote-209)[209)](#footnoteref-209)

The use of fully closed ranges is intentional[.](#footnote-209.sentence-1)

### [26.10.13](#numeric.iota) Iota [[numeric.iota]](numeric.iota)

[🔗](#lib:iota)

`template<class ForwardIterator, class T>
  constexpr void iota(ForwardIterator first, ForwardIterator last, T value);
`

[1](#numeric.iota-1)

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

*Mandates*: T is convertible to ForwardIterator's value type[.](#numeric.iota-1.sentence-1)

The expression ++val, where val has type T,
is well-formed[.](#numeric.iota-1.sentence-2)

[2](#numeric.iota-2)

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

*Effects*: For each element referred to by the iterator i in the range [first, last),
assigns *i = value and increments value as if by ++value[.](#numeric.iota-2.sentence-1)

[3](#numeric.iota-3)

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

*Complexity*: Exactly last - first increments and assignments[.](#numeric.iota-3.sentence-1)

[🔗](#lib:iota_)

`template<[input_or_output_iterator](iterator.concept.iterator#concept:input_or_output_iterator "24.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]") O, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<O> S, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") T>
  requires [indirectly_writable](iterator.concept.writable#concept:indirectly_writable "24.3.4.3 Concept indirectly_­writable [iterator.concept.writable]")<O, const T&>
  constexpr ranges::iota_result<O, T> ranges::iota(O first, S last, T value);
template<[weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]") T, [output_range](range.refinements#concept:output_range "25.4.6 Other range refinements [range.refinements]")<const T&> R>
  constexpr ranges::iota_result<borrowed_iterator_t<R>, T> ranges::iota(R&& r, T value);
`

[4](#numeric.iota-4)

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

*Effects*: Equivalent to:while (first != last) {*first = as_const(value); ++first; ++value;}return {std::move(first), std::move(value)};

### [26.10.14](#gcd) Greatest common divisor [[numeric.ops.gcd]](numeric.ops.gcd)

[🔗](#lib:gcd)

`template<class M, class N>
  constexpr common_type_t<M, N> gcd(M m, N n);
`

[1](#gcd-1)

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

*Mandates*: M and N both are integer types other thancv bool[.](#gcd-1.sentence-1)

[2](#gcd-2)

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

*Preconditions*: |m| and |n| are representable as a value of common_type_t<M, N>[.](#gcd-2.sentence-1)

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

These requirements ensure, for example,
that gcd(m, m)=|m| is representable as a value of type M[.](#gcd-2.sentence-2)

— *end note*]

[3](#gcd-3)

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

*Returns*: Zero when m and n are both zero[.](#gcd-3.sentence-1)

Otherwise,
returns the greatest common divisor of |m| and |n|[.](#gcd-3.sentence-2)

[4](#gcd-4)

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

*Throws*: Nothing[.](#gcd-4.sentence-1)

### [26.10.15](#lcm) Least common multiple [[numeric.ops.lcm]](numeric.ops.lcm)

[🔗](#lib:lcm)

`template<class M, class N>
  constexpr common_type_t<M, N> lcm(M m, N n);
`

[1](#lcm-1)

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

*Mandates*: M and N both are integer types other thancv bool[.](#lcm-1.sentence-1)

[2](#lcm-2)

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

*Preconditions*: |m| and |n| are representable as a value of common_type_t<M, N>[.](#lcm-2.sentence-1)

The least common multiple of |m| and |n| is representable as a value of type common_type_t<M, N>[.](#lcm-2.sentence-2)

[3](#lcm-3)

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

*Returns*: Zero when either m or n is zero[.](#lcm-3.sentence-1)

Otherwise, returns the least common multiple of |m| and |n|[.](#lcm-3.sentence-2)

[4](#lcm-4)

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

*Throws*: Nothing[.](#lcm-4.sentence-1)

### [26.10.16](#midpoint) Midpoint [[numeric.ops.midpoint]](numeric.ops.midpoint)

[🔗](#lib:midpoint)

`template<class T>
  constexpr T midpoint(T a, T b) noexcept;
`

[1](#midpoint-1)

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

*Constraints*: T is an arithmetic type other than bool[.](#midpoint-1.sentence-1)

[2](#midpoint-2)

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

*Returns*: Half the sum of a and b[.](#midpoint-2.sentence-1)

If T is an integer type and the sum is odd,
the result is rounded towards a[.](#midpoint-2.sentence-2)

[3](#midpoint-3)

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

*Remarks*: No overflow occurs[.](#midpoint-3.sentence-1)

If T is a floating-point type, at most one inexact operation occurs[.](#midpoint-3.sentence-2)

[🔗](#lib:midpoint_)

`template<class T>
  constexpr T* midpoint(T* a, T* b);
`

[4](#midpoint-4)

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

*Constraints*: T is an object type[.](#midpoint-4.sentence-1)

[5](#midpoint-5)

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

*Mandates*: T is a complete type[.](#midpoint-5.sentence-1)

[6](#midpoint-6)

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

*Preconditions*: a and b point to, respectively,
elements i and j of the same array object x[.](#midpoint-6.sentence-1)

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

As specified in [[basic.compound]](basic.compound "6.9.4 Compound types"),
an object that is not an array element
is considered to belong to a single-element array for this purpose and
a pointer past the last element of an array of n elements
is considered to be equivalent to a pointer
to a hypothetical array element n for this purpose[.](#midpoint-6.sentence-2)

— *end note*]

[7](#midpoint-7)

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

*Returns*: A pointer to array element i+j−i2 of x,
where the result of the division is truncated towards zero[.](#midpoint-7.sentence-1)

### [26.10.17](#numeric.sat) Saturation arithmetic [[numeric.sat]](numeric.sat)

#### [26.10.17.1](#numeric.sat.func) Arithmetic functions [[numeric.sat.func]](numeric.sat.func)

[1](#numeric.sat.func-1)

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

In the following descriptions, an arithmetic operation
is performed as a mathematical operation with infinite range and then
it is determined whether the mathematical result fits into the result type[.](#numeric.sat.func-1.sentence-1)

[🔗](#lib:add_sat)

`template<class T>
  constexpr T add_sat(T x, T y) noexcept;
`

[2](#numeric.sat.func-2)

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

*Constraints*: T is a signed or unsigned integer type ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#numeric.sat.func-2.sentence-1)

[3](#numeric.sat.func-3)

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

*Returns*: If x+y is representable as a value of type T, x+y;
otherwise, either the largest or smallest representable value of type T,
whichever is closer to the value of x+y[.](#numeric.sat.func-3.sentence-1)

[🔗](#lib:sub_sat)

`template<class T>
  constexpr T sub_sat(T x, T y) noexcept;
`

[4](#numeric.sat.func-4)

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

*Constraints*: T is a signed or unsigned integer type ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#numeric.sat.func-4.sentence-1)

[5](#numeric.sat.func-5)

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

*Returns*: If x−y is representable as a value of type T, x−y;
otherwise, either the largest or smallest representable value of type T,
whichever is closer to the value of x−y[.](#numeric.sat.func-5.sentence-1)

[🔗](#lib:mul_sat)

`template<class T>
  constexpr T mul_sat(T x, T y) noexcept;
`

[6](#numeric.sat.func-6)

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

*Constraints*: T is a signed or unsigned integer type ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#numeric.sat.func-6.sentence-1)

[7](#numeric.sat.func-7)

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

*Returns*: If x ×y is representable as a value of type T, x ×y;
otherwise, either the largest or smallest representable value of type T,
whichever is closer to the value of x ×y[.](#numeric.sat.func-7.sentence-1)

[🔗](#lib:div_sat)

`template<class T>
  constexpr T div_sat(T x, T y) noexcept;
`

[8](#numeric.sat.func-8)

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

*Constraints*: T is a signed or unsigned integer type ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#numeric.sat.func-8.sentence-1)

[9](#numeric.sat.func-9)

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

*Preconditions*: y != 0 is true[.](#numeric.sat.func-9.sentence-1)

[10](#numeric.sat.func-10)

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

*Returns*: If T is a signed integer type
and x == numeric_limits<T>​::​min() && y == -1 is true,numeric_limits<T>​::​max(), otherwise, x / y[.](#numeric.sat.func-10.sentence-1)

[11](#numeric.sat.func-11)

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

*Remarks*: A function call expression
that violates the precondition in the *Preconditions* element
is not a core constant expression ([[expr.const]](expr.const "7.7 Constant expressions"))[.](#numeric.sat.func-11.sentence-1)

#### [26.10.17.2](#numeric.sat.cast) Casting [[numeric.sat.cast]](numeric.sat.cast)

[🔗](#lib:saturate_cast)

`template<class R, class T>
  constexpr R saturate_cast(T x) noexcept;
`

[1](#numeric.sat.cast-1)

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

*Constraints*: R and T are signed or unsigned integer types ([[basic.fundamental]](basic.fundamental "6.9.2 Fundamental types"))[.](#numeric.sat.cast-1.sentence-1)

[2](#numeric.sat.cast-2)

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

*Returns*: If x is representable as a value of type R, x;
otherwise, either the largest or smallest representable value of type R,
whichever is closer to the value of x[.](#numeric.sat.cast-2.sentence-1)