From Jason Turner

[numeric.ops]

C++14 → C++17 43.4 KB 857 lines
Current Draft | LaTeX Source
Archived: C++14 | C++17
Markdown: C++14 | C++17
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmp557i6bfc/{from.md → to.md} +800 -52
tmp/tmp557i6bfc/{from.md → to.md} RENAMED
@@ -2,77 +2,350 @@
2
 
3
  ### Header `<numeric>` synopsis <a id="numeric.ops.overview">[[numeric.ops.overview]]</a>
4
 
5
  ``` cpp
6
  namespace std {
 
7
  template <class InputIterator, class T>
8
  T accumulate(InputIterator first, InputIterator last, T init);
9
  template <class InputIterator, class T, class BinaryOperation>
10
  T accumulate(InputIterator first, InputIterator last, T init,
11
  BinaryOperation binary_op);
12
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
13
  template <class InputIterator1, class InputIterator2, class T>
14
  T inner_product(InputIterator1 first1, InputIterator1 last1,
15
  InputIterator2 first2, T init);
16
  template <class InputIterator1, class InputIterator2, class T,
17
  class BinaryOperation1, class BinaryOperation2>
18
  T inner_product(InputIterator1 first1, InputIterator1 last1,
19
  InputIterator2 first2, T init,
20
  BinaryOperation1 binary_op1,
21
  BinaryOperation2 binary_op2);
22
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
23
  template <class InputIterator, class OutputIterator>
24
  OutputIterator partial_sum(InputIterator first,
25
  InputIterator last,
26
  OutputIterator result);
27
- template <class InputIterator, class OutputIterator,
28
- class BinaryOperation>
29
  OutputIterator partial_sum(InputIterator first,
30
  InputIterator last,
31
  OutputIterator result,
32
  BinaryOperation binary_op);
33
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
34
  template <class InputIterator, class OutputIterator>
35
  OutputIterator adjacent_difference(InputIterator first,
36
  InputIterator last,
37
  OutputIterator result);
38
- template <class InputIterator, class OutputIterator,
39
- class BinaryOperation>
40
  OutputIterator adjacent_difference(InputIterator first,
41
  InputIterator last,
42
  OutputIterator result,
43
  BinaryOperation binary_op);
 
 
 
 
 
 
 
 
 
 
 
 
44
 
 
45
  template <class ForwardIterator, class T>
46
  void iota(ForwardIterator first, ForwardIterator last, T value);
 
 
 
 
 
 
 
 
47
  }
48
  ```
49
 
50
  The requirements on the types of algorithms’ arguments that are
51
  described in the introduction to Clause  [[algorithms]] also apply to
52
  the following algorithms.
53
 
 
 
 
 
 
 
 
 
54
  ### Accumulate <a id="accumulate">[[accumulate]]</a>
55
 
56
  ``` cpp
57
  template <class InputIterator, class T>
58
  T accumulate(InputIterator first, InputIterator last, T init);
59
  template <class InputIterator, class T, class BinaryOperation>
60
  T accumulate(InputIterator first, InputIterator last, T init,
61
  BinaryOperation binary_op);
62
  ```
63
 
 
 
 
 
 
 
64
  *Effects:* Computes its result by initializing the accumulator `acc`
65
  with the initial value `init` and then modifies it with `acc = acc + *i`
66
  or `acc = binary_op(acc, *i)` for every iterator `i` in the range
67
- \[`first`, `last`) in order.[^15]
68
 
69
- *Requires:* `T` shall meet the requirements of `CopyConstructible`
70
- (Table  [[copyconstructible]]) and `CopyAssignable`
71
- (Table  [[copyassignable]]) types. In the range \[`first`, `last`\],
72
- `binary_op` shall neither modify elements nor invalidate iterators or
73
- subranges.[^16]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
74
 
75
  ### Inner product <a id="inner.product">[[inner.product]]</a>
76
 
77
  ``` cpp
78
  template <class InputIterator1, class InputIterator2, class T>
@@ -84,98 +357,532 @@ template <class InputIterator1, class InputIterator2, class T,
84
  InputIterator2 first2, T init,
85
  BinaryOperation1 binary_op1,
86
  BinaryOperation2 binary_op2);
87
  ```
88
 
 
 
 
 
 
 
 
89
  *Effects:* Computes its result by initializing the accumulator `acc`
90
  with the initial value `init` and then modifying it with
91
  `acc = acc + (*i1) * (*i2)` or
92
  `acc = binary_op1(acc, binary_op2(*i1, *i2))` for every iterator `i1` in
93
  the range \[`first1`, `last1`) and iterator `i2` in the range
94
  \[`first2`, `first2 + (last1 - first1)`) in order.
95
 
96
- *Requires:* `T` shall meet the requirements of `CopyConstructible`
97
- (Table  [[copyconstructible]]) and `CopyAssignable`
98
- (Table  [[copyassignable]]) types. In the ranges \[`first1`, `last1`\]
99
- and \[`first2`, `first2 + (last1 - first1)`\] `binary_op1` and
100
- `binary_op2` shall neither modify elements nor invalidate iterators or
101
- subranges.[^17]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
102
 
103
  ### Partial sum <a id="partial.sum">[[partial.sum]]</a>
104
 
105
  ``` cpp
106
  template <class InputIterator, class OutputIterator>
107
  OutputIterator partial_sum(
108
  InputIterator first, InputIterator last,
109
  OutputIterator result);
110
- template
111
- <class InputIterator, class OutputIterator, class BinaryOperation>
112
  OutputIterator partial_sum(
113
  InputIterator first, InputIterator last,
114
  OutputIterator result, BinaryOperation binary_op);
115
  ```
116
 
117
- *Effects:* For a non-empty range, the function creates an accumulator
118
- `acc` whose type is `InputIterator`’s value type, initializes it with
119
- `*first`, and assigns the result to `*result`. For every iterator `i` in
120
- \[`first + 1`, `last`) in order, `acc` is then modified by
121
- `acc = acc + *i` or `acc = binary_op(acc, *i)` and the result is
122
- assigned to `*(result + (i - first))`.
123
-
124
- *Returns:* `result + (last - first)`.
125
-
126
- *Complexity:* Exactly `(last - first) - 1` applications of the binary
127
- operation.
128
-
129
  *Requires:* `InputIterator`’s value type shall be constructible from the
130
  type of `*first`. The result of the expression `acc + *i` or
131
  `binary_op(acc, *i)` shall be implicitly convertible to
132
- `InputIterator`’s value type. `acc` shall be writable to the `result`
133
- output iterator. In the ranges \[`first`, `last`\] and
134
- {\[}\texttt{result}, \texttt{result + (last - first)}{\]} `binary_op`
135
- shall neither modify elements nor invalidate iterators or
136
- subranges.[^18]
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
137
 
138
  *Remarks:* `result` may be equal to `first`.
139
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
140
  ### Adjacent difference <a id="adjacent.difference">[[adjacent.difference]]</a>
141
 
142
  ``` cpp
143
  template <class InputIterator, class OutputIterator>
144
- OutputIterator adjacent_difference(
145
- InputIterator first, InputIterator last,
146
  OutputIterator result);
 
 
 
 
 
 
147
  template <class InputIterator, class OutputIterator, class BinaryOperation>
148
- OutputIterator adjacent_difference(
149
- InputIterator first, InputIterator last,
150
  OutputIterator result,
151
  BinaryOperation binary_op);
 
 
 
 
 
 
 
152
  ```
153
 
154
- *Effects:* For a non-empty range, the function creates an accumulator
155
- `acc` whose type is `InputIterator`’s value type, initializes it with
156
- `*first`, and assigns the result to `*result`. For every iterator `i` in
157
- \[`first + 1`, `last`) in order, creates an object `val` whose type is
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
158
  `InputIterator`’s value type, initializes it with `*i`, computes
159
  `val - acc` or `binary_op(val, acc)`, assigns the result to
160
  `*(result + (i - first))`, and move assigns from `val` to `acc`.
161
 
162
- *Requires:* `InputIterator`’s value type shall be `MoveAssignable`
163
- (Table  [[moveassignable]]) and shall be constructible from the type of
164
- `*first`. `acc` shall be writable to the `result` output iterator. The
165
- result of the expression `val - acc` or `binary_op(val, acc)` shall be
166
- writable to the `result` output iterator. In the ranges \[`first`,
167
- `last`\] and \[`result`, `result + (last - first)`\], `binary_op` shall
168
- neither modify elements nor invalidate iterators or subranges.[^19]
169
-
170
- *Remarks:* `result` may be equal to `first`.
171
 
172
  *Returns:* `result + (last - first)`.
173
 
174
  *Complexity:* Exactly `(last - first) - 1` applications of the binary
175
  operation.
176
 
 
 
 
 
 
177
  ### Iota <a id="numeric.iota">[[numeric.iota]]</a>
178
 
179
  ``` cpp
180
  template <class ForwardIterator, class T>
181
  void iota(ForwardIterator first, ForwardIterator last, T value);
@@ -188,5 +895,46 @@ The expression `++val`, where `val` has type `T`, shall be well formed.
188
  \[`first`, `last`), assigns `*i = value` and increments `value` as if by
189
  `++value`.
190
 
191
  *Complexity:* Exactly `last - first` increments and assignments.
192
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2
 
3
  ### Header `<numeric>` synopsis <a id="numeric.ops.overview">[[numeric.ops.overview]]</a>
4
 
5
  ``` cpp
6
  namespace std {
7
+ // [accumulate], accumulate
8
  template <class InputIterator, class T>
9
  T accumulate(InputIterator first, InputIterator last, T init);
10
  template <class InputIterator, class T, class BinaryOperation>
11
  T accumulate(InputIterator first, InputIterator last, T init,
12
  BinaryOperation binary_op);
13
 
14
+ // [reduce], reduce
15
+ template<class InputIterator>
16
+ typename iterator_traits<InputIterator>::value_type
17
+ reduce(InputIterator first, InputIterator last);
18
+ template<class InputIterator, class T>
19
+ T reduce(InputIterator first, InputIterator last, T init);
20
+ template<class InputIterator, class T, class BinaryOperation>
21
+ T reduce(InputIterator first, InputIterator last, T init,
22
+ BinaryOperation binary_op);
23
+ template<class ExecutionPolicy, class ForwardIterator>
24
+ typename iterator_traits<ForwardIterator>::value_type
25
+ reduce(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
26
+ ForwardIterator first, ForwardIterator last);
27
+ template<class ExecutionPolicy, class ForwardIterator, class T>
28
+ T reduce(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
29
+ ForwardIterator first, ForwardIterator last, T init);
30
+ template<class ExecutionPolicy, class ForwardIterator, class T, class BinaryOperation>
31
+ T reduce(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
32
+ ForwardIterator first, ForwardIterator last, T init,
33
+ BinaryOperation binary_op);
34
+
35
+ // [inner.product], inner product
36
  template <class InputIterator1, class InputIterator2, class T>
37
  T inner_product(InputIterator1 first1, InputIterator1 last1,
38
  InputIterator2 first2, T init);
39
  template <class InputIterator1, class InputIterator2, class T,
40
  class BinaryOperation1, class BinaryOperation2>
41
  T inner_product(InputIterator1 first1, InputIterator1 last1,
42
  InputIterator2 first2, T init,
43
  BinaryOperation1 binary_op1,
44
  BinaryOperation2 binary_op2);
45
 
46
+ // [transform.reduce], transform reduce
47
+ template<class InputIterator1, class InputIterator2, class T>
48
+ T transform_reduce(InputIterator1 first1, InputIterator1 last1,
49
+ InputIterator2 first2,
50
+ T init);
51
+ template<class InputIterator1, class InputIterator2, class T,
52
+ class BinaryOperation1, class BinaryOperation2>
53
+ T transform_reduce(InputIterator1 first1, InputIterator1 last1,
54
+ InputIterator2 first2,
55
+ T init,
56
+ BinaryOperation1 binary_op1,
57
+ BinaryOperation2 binary_op2);
58
+ template<class InputIterator, class T,
59
+ class BinaryOperation, class UnaryOperation>
60
+ T transform_reduce(InputIterator first, InputIterator last,
61
+ T init,
62
+ BinaryOperation binary_op, UnaryOperation unary_op);
63
+ template<class ExecutionPolicy,
64
+ class ForwardIterator1, class ForwardIterator2, class T>
65
+ T transform_reduce(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
66
+ ForwardIterator1 first1, ForwardIterator1 last1,
67
+ ForwardIterator2 first2,
68
+ T init);
69
+ template<class ExecutionPolicy,
70
+ class ForwardIterator1, class ForwardIterator2, class T,
71
+ class BinaryOperation1, class BinaryOperation2>
72
+ T transform_reduce(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
73
+ ForwardIterator1 first1, ForwardIterator1 last1,
74
+ ForwardIterator2 first2,
75
+ T init,
76
+ BinaryOperation1 binary_op1,
77
+ BinaryOperation2 binary_op2);
78
+ template<class ExecutionPolicy,
79
+ class ForwardIterator, class T,
80
+ class BinaryOperation, class UnaryOperation>
81
+ T transform_reduce(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
82
+ ForwardIterator first, ForwardIterator last,
83
+ T init,
84
+ BinaryOperation binary_op, UnaryOperation unary_op);
85
+
86
+ // [partial.sum], partial sum
87
  template <class InputIterator, class OutputIterator>
88
  OutputIterator partial_sum(InputIterator first,
89
  InputIterator last,
90
  OutputIterator result);
91
+ template <class InputIterator, class OutputIterator, class BinaryOperation>
 
92
  OutputIterator partial_sum(InputIterator first,
93
  InputIterator last,
94
  OutputIterator result,
95
  BinaryOperation binary_op);
96
 
97
+ // [exclusive.scan], exclusive scan
98
+ template<class InputIterator, class OutputIterator, class T>
99
+ OutputIterator exclusive_scan(InputIterator first, InputIterator last,
100
+ OutputIterator result,
101
+ T init);
102
+ template<class InputIterator, class OutputIterator, class T, class BinaryOperation>
103
+ OutputIterator exclusive_scan(InputIterator first, InputIterator last,
104
+ OutputIterator result,
105
+ T init, BinaryOperation binary_op);
106
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T>
107
+ ForwardIterator2 exclusive_scan(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
108
+ ForwardIterator1 first, ForwardIterator1 last,
109
+ ForwardIterator2 result,
110
+ T init);
111
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T,
112
+ class BinaryOperation>
113
+ ForwardIterator2 exclusive_scan(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
114
+ ForwardIterator1 first, ForwardIterator1 last,
115
+ ForwardIterator2 result,
116
+ T init, BinaryOperation binary_op);
117
+
118
+ // [inclusive.scan], inclusive scan
119
+ template<class InputIterator, class OutputIterator>
120
+ OutputIterator inclusive_scan(InputIterator first, InputIterator last,
121
+ OutputIterator result);
122
+ template<class InputIterator, class OutputIterator, class BinaryOperation>
123
+ OutputIterator inclusive_scan(InputIterator first, InputIterator last,
124
+ OutputIterator result,
125
+ BinaryOperation binary_op);
126
+ template<class InputIterator, class OutputIterator, class BinaryOperation, class T>
127
+ OutputIterator inclusive_scan(InputIterator first, InputIterator last,
128
+ OutputIterator result,
129
+ BinaryOperation binary_op, T init);
130
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
131
+ ForwardIterator2 inclusive_scan(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
132
+ ForwardIterator1 first, ForwardIterator1 last,
133
+ ForwardIterator2 result);
134
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
135
+ class BinaryOperation>
136
+ ForwardIterator2 inclusive_scan(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
137
+ ForwardIterator1 first, ForwardIterator1 last,
138
+ ForwardIterator2 result,
139
+ BinaryOperation binary_op);
140
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
141
+ class BinaryOperation, class T>
142
+ ForwardIterator2 inclusive_scan(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
143
+ ForwardIterator1 first, ForwardIterator1 last,
144
+ ForwardIterator2 result,
145
+ BinaryOperation binary_op, T init);
146
+
147
+ // [transform.exclusive.scan], transform exclusive scan
148
+ template<class InputIterator, class OutputIterator, class T,
149
+ class BinaryOperation, class UnaryOperation>
150
+ OutputIterator transform_exclusive_scan(InputIterator first, InputIterator last,
151
+ OutputIterator result,
152
+ T init,
153
+ BinaryOperation binary_op,
154
+ UnaryOperation unary_op);
155
+ template<class ExecutionPolicy,
156
+ class ForwardIterator1, class ForwardIterator2, class T,
157
+ class BinaryOperation, class UnaryOperation>
158
+ ForwardIterator2 transform_exclusive_scan(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
159
+ ForwardIterator1 first, ForwardIterator1 last,
160
+ ForwardIterator2 result,
161
+ T init,
162
+ BinaryOperation binary_op,
163
+ UnaryOperation unary_op);
164
+
165
+ // [transform.inclusive.scan], transform inclusive scan
166
+ template<class InputIterator, class OutputIterator,
167
+ class BinaryOperation, class UnaryOperation>
168
+ OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last,
169
+ OutputIterator result,
170
+ BinaryOperation binary_op,
171
+ UnaryOperation unary_op);
172
+ template<class InputIterator, class OutputIterator,
173
+ class BinaryOperation, class UnaryOperation, class T>
174
+ OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last,
175
+ OutputIterator result,
176
+ BinaryOperation binary_op,
177
+ UnaryOperation unary_op,
178
+ T init);
179
+ template<class ExecutionPolicy,
180
+ class ForwardIterator1, class ForwardIterator2,
181
+ class BinaryOperation, class UnaryOperation>
182
+ ForwardIterator2 transform_inclusive_scan(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
183
+ ForwardIterator1 first, ForwardIterator1 last,
184
+ ForwardIterator2 result,
185
+ BinaryOperation binary_op,
186
+ UnaryOperation unary_op);
187
+ template<class ExecutionPolicy,
188
+ class ForwardIterator1, class ForwardIterator2,
189
+ class BinaryOperation, class UnaryOperation, class T>
190
+ ForwardIterator2 transform_inclusive_scan(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
191
+ ForwardIterator1 first, ForwardIterator1 last,
192
+ ForwardIterator2 result,
193
+ BinaryOperation binary_op,
194
+ UnaryOperation unary_op,
195
+ T init);
196
+
197
+ // [adjacent.difference], adjacent difference
198
  template <class InputIterator, class OutputIterator>
199
  OutputIterator adjacent_difference(InputIterator first,
200
  InputIterator last,
201
  OutputIterator result);
202
+ template <class InputIterator, class OutputIterator, class BinaryOperation>
 
203
  OutputIterator adjacent_difference(InputIterator first,
204
  InputIterator last,
205
  OutputIterator result,
206
  BinaryOperation binary_op);
207
+ template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
208
+ ForwardIterator2 adjacent_difference(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
209
+ ForwardIterator1 first,
210
+ ForwardIterator1 last,
211
+ ForwardIterator2 result);
212
+ template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
213
+ class BinaryOperation>
214
+ ForwardIterator2 adjacent_difference(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
215
+ ForwardIterator1 first,
216
+ ForwardIterator1 last,
217
+ ForwardIterator2 result,
218
+ BinaryOperation binary_op);
219
 
220
+ // [numeric.iota], iota
221
  template <class ForwardIterator, class T>
222
  void iota(ForwardIterator first, ForwardIterator last, T value);
223
+
224
+ // [numeric.ops.gcd], greatest common divisor
225
+ template <class M, class N>
226
+ constexpr common_type_t<M,N> gcd(M m, N n);
227
+
228
+ // [numeric.ops.lcm], least common multiple
229
+ template <class M, class N>
230
+ constexpr common_type_t<M,N> lcm(M m, N n);
231
  }
232
  ```
233
 
234
  The requirements on the types of algorithms’ arguments that are
235
  described in the introduction to Clause  [[algorithms]] also apply to
236
  the following algorithms.
237
 
238
+ Throughout this subclause, the parameters `UnaryOperation`,
239
+ `BinaryOperation`, `BinaryOperation1`, and `BinaryOperation2` are used
240
+ whenever an algorithm expects a function object ([[function.objects]]).
241
+
242
+ [*Note 1*: The use of closed ranges as well as semi-open ranges to
243
+ specify requirements throughout this subclause is
244
+ intentional. — *end note*]
245
+
246
  ### Accumulate <a id="accumulate">[[accumulate]]</a>
247
 
248
  ``` cpp
249
  template <class InputIterator, class T>
250
  T accumulate(InputIterator first, InputIterator last, T init);
251
  template <class InputIterator, class T, class BinaryOperation>
252
  T accumulate(InputIterator first, InputIterator last, T init,
253
  BinaryOperation binary_op);
254
  ```
255
 
256
+ *Requires:* `T` shall meet the requirements of `CopyConstructible`
257
+ (Table  [[tab:copyconstructible]]) and `CopyAssignable`
258
+ (Table  [[tab:copyassignable]]) types. In the range \[`first`, `last`\],
259
+ `binary_op` shall neither modify elements nor invalidate iterators or
260
+ subranges.[^13]
261
+
262
  *Effects:* Computes its result by initializing the accumulator `acc`
263
  with the initial value `init` and then modifies it with `acc = acc + *i`
264
  or `acc = binary_op(acc, *i)` for every iterator `i` in the range
265
+ \[`first`, `last`) in order.[^14]
266
 
267
+ ### Reduce <a id="reduce">[[reduce]]</a>
268
+
269
+ ``` cpp
270
+ template<class InputIterator>
271
+ typename iterator_traits<InputIterator>::value_type
272
+ reduce(InputIterator first, InputIterator last);
273
+ ```
274
+
275
+ *Effects:* Equivalent to:
276
+
277
+ ``` cpp
278
+ return reduce(first, last,
279
+ typename iterator_traits<InputIterator>::value_type{});
280
+ ```
281
+
282
+ ``` cpp
283
+ template<class ExecutionPolicy, class ForwardIterator>
284
+ typename iterator_traits<ForwardIterator>::value_type
285
+ reduce(ExecutionPolicy&& exec,
286
+ ForwardIterator first, ForwardIterator last);
287
+ ```
288
+
289
+ *Effects:* Equivalent to:
290
+
291
+ ``` cpp
292
+ return reduce(std::forward<ExecutionPolicy>(exec), first, last,
293
+ typename iterator_traits<ForwardIterator>::value_type{});
294
+ ```
295
+
296
+ ``` cpp
297
+ template<class InputIterator, class T>
298
+ T reduce(InputIterator first, InputIterator last, T init);
299
+ ```
300
+
301
+ *Effects:* Equivalent to:
302
+
303
+ ``` cpp
304
+ return reduce(first, last, init, plus<>());
305
+ ```
306
+
307
+ ``` cpp
308
+ template<class ExecutionPolicy, class ForwardIterator, class T>
309
+ T reduce(ExecutionPolicy&& exec,
310
+ ForwardIterator first, ForwardIterator last, T init);
311
+ ```
312
+
313
+ *Effects:* Equivalent to:
314
+
315
+ ``` cpp
316
+ return reduce(std::forward<ExecutionPolicy>(exec), first, last, init, plus<>());
317
+ ```
318
+
319
+ ``` cpp
320
+ template<class InputIterator, class T, class BinaryOperation>
321
+ T reduce(InputIterator first, InputIterator last, T init,
322
+ BinaryOperation binary_op);
323
+ template<class ExecutionPolicy, class ForwardIterator, class T, class BinaryOperation>
324
+ T reduce(ExecutionPolicy&& exec,
325
+ ForwardIterator first, ForwardIterator last, T init,
326
+ BinaryOperation binary_op);
327
+ ```
328
+
329
+ *Requires:*
330
+
331
+ - `T` shall be `MoveConstructible` (Table  [[tab:moveconstructible]]).
332
+ - All of `binary_op(init, *first)`, `binary_op(*first, init)`,
333
+ `binary_op(init, init)`, and `binary_op(*first, *first)` shall be
334
+ convertible to `T`.
335
+ - `binary_op` shall neither invalidate iterators or subranges, nor
336
+ modify elements in the range \[`first`, `last`\].
337
+
338
+ *Returns:* *GENERALIZED_SUM*(binary_op, init, \*i, ...) for every `i` in
339
+ \[`first`, `last`).
340
+
341
+ *Complexity:* 𝑂(`last - first`) applications of `binary_op`.
342
+
343
+ [*Note 1*: The difference between `reduce` and `accumulate` is that
344
+ `reduce` applies `binary_op` in an unspecified order, which yields a
345
+ nondeterministic result for non-associative or non-commutative
346
+ `binary_op` such as floating-point addition. — *end note*]
347
 
348
  ### Inner product <a id="inner.product">[[inner.product]]</a>
349
 
350
  ``` cpp
351
  template <class InputIterator1, class InputIterator2, class T>
 
357
  InputIterator2 first2, T init,
358
  BinaryOperation1 binary_op1,
359
  BinaryOperation2 binary_op2);
360
  ```
361
 
362
+ *Requires:* `T` shall meet the requirements of `CopyConstructible`
363
+ (Table  [[tab:copyconstructible]]) and `CopyAssignable`
364
+ (Table  [[tab:copyassignable]]) types. In the ranges \[`first1`,
365
+ `last1`\] and \[`first2`, `first2 + (last1 - first1)`\] `binary_op1` and
366
+ `binary_op2` shall neither modify elements nor invalidate iterators or
367
+ subranges.[^15]
368
+
369
  *Effects:* Computes its result by initializing the accumulator `acc`
370
  with the initial value `init` and then modifying it with
371
  `acc = acc + (*i1) * (*i2)` or
372
  `acc = binary_op1(acc, binary_op2(*i1, *i2))` for every iterator `i1` in
373
  the range \[`first1`, `last1`) and iterator `i2` in the range
374
  \[`first2`, `first2 + (last1 - first1)`) in order.
375
 
376
+ ### Transform reduce <a id="transform.reduce">[[transform.reduce]]</a>
377
+
378
+ ``` cpp
379
+ template <class InputIterator1, class InputIterator2, class T>
380
+ T transform_reduce(InputIterator1 first1, InputIterator1 last1,
381
+ InputIterator2 first2,
382
+ T init);
383
+ template <class ExecutionPolicy,
384
+ class ForwardIterator1, class ForwardIterator2, class T>
385
+ T transform_reduce(ExecutionPolicy&& exec,
386
+ ForwardIterator1 first1, ForwardIterator1 last1,
387
+ ForwardIterator2 first2,
388
+ T init);
389
+ ```
390
+
391
+ *Effects:* Equivalent to:
392
+
393
+ ``` cpp
394
+ return transform_reduce(first1, last1, first2, init, plus<>(), multiplies<>());
395
+ ```
396
+
397
+ ``` cpp
398
+ template <class InputIterator1, class InputIterator2, class T,
399
+ class BinaryOperation1, class BinaryOperation2>
400
+ T transform_reduce(InputIterator1 first1, InputIterator1 last1,
401
+ InputIterator2 first2,
402
+ T init,
403
+ BinaryOperation1 binary_op1,
404
+ BinaryOperation2 binary_op2);
405
+ template <class ExecutionPolicy,
406
+ class ForwardIterator1, class ForwardIterator2, class T,
407
+ class BinaryOperation1, class BinaryOperation2>
408
+ T transform_reduce(ExecutionPolicy&& exec,
409
+ ForwardIterator1 first1, ForwardIterator1 last1,
410
+ ForwardIterator2 first2,
411
+ T init,
412
+ BinaryOperation1 binary_op1,
413
+ BinaryOperation2 binary_op2);
414
+ ```
415
+
416
+ *Requires:*
417
+
418
+ - `T` shall be `MoveConstructible` (Table  [[tab:moveconstructible]]).
419
+ - All of
420
+ - `binary_op1(init, init)`,
421
+ - `binary_op1(init, binary_op2(*first1, *first2))`,
422
+ - `binary_op1(binary_op2(*first1, *first2), init)`, and
423
+ - `binary_op1(binary_op2(*first1, *first2), binary_op2(*first1, *first2))`
424
+
425
+ shall be convertible to `T`.
426
+ - Neither `binary_op1` nor `binary_op2` shall invalidate subranges, or
427
+ modify elements in the ranges \[`first1`, `last1`\] and \[`first2`,
428
+ `first2 + (last1 - first1)`\].
429
+
430
+ *Returns:*
431
+
432
+ ``` cpp
433
+ GENERALIZED_SUM(binary_op1, init, binary_op2(*i, *(first2 + (i - first1))), ...)
434
+ ```
435
+
436
+ for every iterator `i` in \[`first1`, `last1`).
437
+
438
+ *Complexity:* 𝑂(`last1 - first1`) applications each of `binary_op1` and
439
+ `binary_op2`.
440
+
441
+ ``` cpp
442
+ template<class InputIterator, class T,
443
+ class BinaryOperation, class UnaryOperation>
444
+ T transform_reduce(InputIterator first, InputIterator last, T init,
445
+ BinaryOperation binary_op, UnaryOperation unary_op);
446
+ template<class ExecutionPolicy,
447
+ class ForwardIterator, class T,
448
+ class BinaryOperation, class UnaryOperation>
449
+ T transform_reduce(ExecutionPolicy&& exec,
450
+ ForwardIterator first, ForwardIterator last,
451
+ T init, BinaryOperation binary_op, UnaryOperation unary_op);
452
+ ```
453
+
454
+ *Requires:*
455
+
456
+ - `T` shall be `MoveConstructible` (Table  [[tab:moveconstructible]]).
457
+ - All of
458
+ - `binary_op(init, init)`,
459
+ - `binary_op(init, unary_op(*first))`,
460
+ - `binary_op(unary_op(*first), init)`, and
461
+ - `binary_op(unary_op(*first), unary_op(*first))`
462
+
463
+ shall be convertible to `T`.
464
+ - Neither `unary_op` nor `binary_op` shall invalidate subranges, or
465
+ modify elements in the range \[`first`, `last`\].
466
+
467
+ *Returns:*
468
+
469
+ ``` cpp
470
+ GENERALIZED_SUM(binary_op, init, unary_op(*i), ...)
471
+ ```
472
+
473
+ for every iterator `i` in \[`first`, `last`).
474
+
475
+ *Complexity:* 𝑂(`last - first`) applications each of `unary_op` and
476
+ `binary_op`.
477
+
478
+ [*Note 1*: `transform_reduce` does not apply `unary_op` to
479
+ `init`. — *end note*]
480
 
481
  ### Partial sum <a id="partial.sum">[[partial.sum]]</a>
482
 
483
  ``` cpp
484
  template <class InputIterator, class OutputIterator>
485
  OutputIterator partial_sum(
486
  InputIterator first, InputIterator last,
487
  OutputIterator result);
488
+ template <class InputIterator, class OutputIterator, class BinaryOperation>
 
489
  OutputIterator partial_sum(
490
  InputIterator first, InputIterator last,
491
  OutputIterator result, BinaryOperation binary_op);
492
  ```
493
 
 
 
 
 
 
 
 
 
 
 
 
 
494
  *Requires:* `InputIterator`’s value type shall be constructible from the
495
  type of `*first`. The result of the expression `acc + *i` or
496
  `binary_op(acc, *i)` shall be implicitly convertible to
497
+ `InputIterator`’s value type. `acc` shall be
498
+ writable ([[iterator.requirements.general]]) to the `result` output
499
+ iterator. In the ranges \[`first`, `last`\] and \[`result`,
500
+ `result + (last - first)`\] `binary_op` shall neither modify elements
501
+ nor invalidate iterators or subranges.[^16]
502
+
503
+ *Effects:* For a non-empty range, the function creates an accumulator
504
+ `acc` whose type is `InputIterator`’s value type, initializes it with
505
+ `*first`, and assigns the result to `*result`. For every iterator `i` in
506
+ \[`first + 1`, `last`) in order, `acc` is then modified by
507
+ `acc = acc + *i` or `acc = binary_op(acc, *i)` and the result is
508
+ assigned to `*(result + (i - first))`.
509
+
510
+ *Returns:* `result + (last - first)`.
511
+
512
+ *Complexity:* Exactly `(last - first) - 1` applications of the binary
513
+ operation.
514
+
515
+ *Remarks:* `result` may be equal to `first`.
516
+
517
+ ### Exclusive scan <a id="exclusive.scan">[[exclusive.scan]]</a>
518
+
519
+ ``` cpp
520
+ template<class InputIterator, class OutputIterator, class T>
521
+ OutputIterator exclusive_scan(InputIterator first, InputIterator last,
522
+ OutputIterator result,
523
+ T init);
524
+ ```
525
+
526
+ *Effects:* Equivalent to:
527
+
528
+ ``` cpp
529
+ return exclusive_scan(first, last, result, init, plus<>());
530
+ ```
531
+
532
+ ``` cpp
533
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T>
534
+ ForwardIterator2 exclusive_scan(ExecutionPolicy&& exec,
535
+ ForwardIterator1 first, ForwardIterator1 last,
536
+ ForwardIterator2 result,
537
+ T init);
538
+ ```
539
+
540
+ *Effects:* Equivalent to:
541
+
542
+ ``` cpp
543
+ return exclusive_scan(std::forward<ExecutionPolicy>(exec),
544
+ first, last, result, init, plus<>());
545
+ ```
546
+
547
+ ``` cpp
548
+ template<class InputIterator, class OutputIterator, class T, class BinaryOperation>
549
+ OutputIterator exclusive_scan(InputIterator first, InputIterator last,
550
+ OutputIterator result,
551
+ T init, BinaryOperation binary_op);
552
+ template<class ExecutionPolicy,
553
+ class ForwardIterator1, class ForwardIterator2, class T, class BinaryOperation>
554
+ ForwardIterator2 exclusive_scan(ExecutionPolicy&& exec,
555
+ ForwardIterator1 first, ForwardIterator1 last,
556
+ ForwardIterator2 result,
557
+ T init, BinaryOperation binary_op);
558
+ ```
559
+
560
+ *Requires:*
561
+
562
+ - `T` shall be `MoveConstructible` (Table  [[tab:moveconstructible]]).
563
+ - All of `binary_op(init, init)`, `binary_op(init, *first)`, and
564
+ `binary_op(*first, *first)` shall be convertible to `T`.
565
+ - `binary_op` shall neither invalidate iterators or subranges, nor
566
+ modify elements in the ranges \[`first`, `last`\] or \[`result`,
567
+ `result + (last - first)`\].
568
+
569
+ *Effects:* For each integer `K` in \[`0`, `last - first`) assigns
570
+ through `result + K` the value of:
571
+
572
+ ``` cpp
573
+ GENERALIZED_NONCOMMUTATIVE_SUM(
574
+ binary_op, init, *(first + 0), *(first + 1), ..., *(first + K - 1))
575
+ ```
576
+
577
+ *Returns:* The end of the resulting range beginning at `result`.
578
+
579
+ *Complexity:* 𝑂(`last - first`) applications of `binary_op`.
580
+
581
+ *Remarks:* `result` may be equal to `first`.
582
+
583
+ [*Note 1*: The difference between `exclusive_scan` and `inclusive_scan`
584
+ is that `exclusive_scan` excludes the `i`th input element from the `i`th
585
+ sum. If `binary_op` is not mathematically associative, the behavior of
586
+ `exclusive_scan` may be nondeterministic. — *end note*]
587
+
588
+ ### Inclusive scan <a id="inclusive.scan">[[inclusive.scan]]</a>
589
+
590
+ ``` cpp
591
+ template<class InputIterator, class OutputIterator>
592
+ OutputIterator inclusive_scan(InputIterator first, InputIterator last,
593
+ OutputIterator result);
594
+ ```
595
+
596
+ *Effects:* Equivalent to:
597
+
598
+ ``` cpp
599
+ return inclusive_scan(first, last, result, plus<>());
600
+ ```
601
+
602
+ ``` cpp
603
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
604
+ ForwardIterator2 inclusive_scan(ExecutionPolicy&& exec,
605
+ ForwardIterator1 first, ForwardIterator1 last,
606
+ ForwardIterator2 result);
607
+ ```
608
+
609
+ *Effects:* Equivalent to:
610
+
611
+ ``` cpp
612
+ return inclusive_scan(std::forward<ExecutionPolicy>(exec), first, last, result, plus<>());
613
+ ```
614
+
615
+ ``` cpp
616
+ template<class InputIterator, class OutputIterator, class BinaryOperation>
617
+ OutputIterator inclusive_scan(InputIterator first, InputIterator last,
618
+ OutputIterator result,
619
+ BinaryOperation binary_op);
620
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
621
+ class BinaryOperation>
622
+ ForwardIterator2 inclusive_scan(ExecutionPolicy&& exec,
623
+ ForwardIterator1 first, ForwardIterator1 last,
624
+ ForwardIterator2 result,
625
+ BinaryOperation binary_op);
626
+
627
+ template<class InputIterator, class OutputIterator, class BinaryOperation, class T>
628
+ OutputIterator inclusive_scan(InputIterator first, InputIterator last,
629
+ OutputIterator result,
630
+ BinaryOperation binary_op, T init);
631
+ template<class ExecutionPolicy,
632
+ class ForwardIterator1, class ForwardIterator2, class BinaryOperation, class T>
633
+ ForwardIterator2 inclusive_scan(ExecutionPolicy&& exec,
634
+ ForwardIterator1 first, ForwardIterator1 last,
635
+ ForwardIterator2 result,
636
+ BinaryOperation binary_op, T init);
637
+ ```
638
+
639
+ *Requires:*
640
+
641
+ - If `init` is provided, `T` shall be `MoveConstructible`
642
+ (Table  [[tab:moveconstructible]]); otherwise, `ForwardIterator1`’s
643
+ value type shall be `MoveConstructible`.
644
+ - If `init` is provided, all of `binary_op(init, init)`,
645
+ `binary_op(init, *first)`, and `binary_op(*first, *first)` shall be
646
+ convertible to `T`; otherwise, `binary_op(*first, *first)` shall be
647
+ convertible to `ForwardIterator1`’s value type.
648
+ - `binary_op` shall neither invalidate iterators or subranges, nor
649
+ modify elements in the ranges \[`first`, `last`\] or \[`result`,
650
+ `result + (last - first)`\].
651
+
652
+ *Effects:* For each integer `K` in \[`0`, `last - first`) assigns
653
+ through `result + K` the value of
654
+
655
+ - *GENERALIZED_NONCOMMUTATIVE_SUM*(
656
+     binary_op, init, \*(first + 0), \*(first + 1), ..., \*(first +
657
+ K))
658
+ if `init` is provided, or
659
+ - *GENERALIZED_NONCOMMUTATIVE_SUM*(
660
+     binary_op, \*(first + 0), \*(first + 1), ..., \*(first + K))
661
+ otherwise.
662
+
663
+ *Returns:* The end of the resulting range beginning at `result`.
664
+
665
+ *Complexity:* 𝑂(`last - first`) applications of `binary_op`.
666
 
667
  *Remarks:* `result` may be equal to `first`.
668
 
669
+ [*Note 1*: The difference between `exclusive_scan` and `inclusive_scan`
670
+ is that `inclusive_scan` includes the `i`th input element in the `i`th
671
+ sum. If `binary_op` is not mathematically associative, the behavior of
672
+ `inclusive_scan` may be nondeterministic. — *end note*]
673
+
674
+ ### Transform exclusive scan <a id="transform.exclusive.scan">[[transform.exclusive.scan]]</a>
675
+
676
+ ``` cpp
677
+ template<class InputIterator, class OutputIterator, class T,
678
+ class BinaryOperation, class UnaryOperation>
679
+ OutputIterator transform_exclusive_scan(InputIterator first, InputIterator last,
680
+ OutputIterator result,
681
+ T init,
682
+ BinaryOperation binary_op,
683
+ UnaryOperation unary_op);
684
+ template<class ExecutionPolicy,
685
+ class ForwardIterator1, class ForwardIterator2, class T,
686
+ class BinaryOperation, class UnaryOperation>
687
+ ForwardIterator2 transform_exclusive_scan(ExecutionPolicy&& exec,
688
+ ForwardIterator1 first, ForwardIterator1 last,
689
+ ForwardIterator2 result,
690
+ T init,
691
+ BinaryOperation binary_op,
692
+ UnaryOperation unary_op);
693
+ ```
694
+
695
+ *Requires:*
696
+
697
+ - `T` shall be `MoveConstructible` (Table  [[tab:moveconstructible]]).
698
+ - All of
699
+ - `binary_op(init, init)`,
700
+ - `binary_op(init, unary_op(*first))`, and
701
+ - `binary_op(unary_op(*first), unary_op(*first))`
702
+
703
+ shall be convertible to `T`.
704
+ - Neither `unary_op` nor `binary_op` shall invalidate iterators or
705
+ subranges, or modify elements in the ranges \[`first`, `last`\] or
706
+ \[`result`, `result + (last - first)`\].
707
+
708
+ *Effects:* For each integer `K` in \[`0`, `last - first`) assigns
709
+ through `result + K` the value of:
710
+
711
+ ``` cpp
712
+ GENERALIZED_NONCOMMUTATIVE_SUM(
713
+ binary_op, init,
714
+ unary_op(*(first + 0)), unary_op(*(first + 1)), ..., unary_op(*(first + K - 1)))
715
+ ```
716
+
717
+ *Returns:* The end of the resulting range beginning at `result`.
718
+
719
+ *Complexity:* 𝑂(`last - first`) applications each of `unary_op` and
720
+ `binary_op`.
721
+
722
+ *Remarks:* `result` may be equal to `first`.
723
+
724
+ [*Note 1*: The difference between `transform_exclusive_scan` and
725
+ `transform_inclusive_scan` is that `transform_exclusive_scan` excludes
726
+ the iᵗʰ input element from the iᵗʰ sum. If `binary_op` is not
727
+ mathematically associative, the behavior of `transform_exclusive_scan`
728
+ may be nondeterministic. `transform_exclusive_scan` does not apply
729
+ `unary_op` to `init`. — *end note*]
730
+
731
+ ### Transform inclusive scan <a id="transform.inclusive.scan">[[transform.inclusive.scan]]</a>
732
+
733
+ ``` cpp
734
+ template<class InputIterator, class OutputIterator,
735
+ class BinaryOperation, class UnaryOperation>
736
+ OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last,
737
+ OutputIterator result,
738
+ BinaryOperation binary_op,
739
+ UnaryOperation unary_op);
740
+ template<class ExecutionPolicy,
741
+ class ForwardIterator1, class ForwardIterator2,
742
+ class BinaryOperation, class UnaryOperation>
743
+ ForwardIterator2 transform_inclusive_scan(ExecutionPolicy&& exec,
744
+ ForwardIterator1 first, ForwardIterator1 last,
745
+ ForwardIterator2 result,
746
+ BinaryOperation binary_op,
747
+ UnaryOperation unary_op);
748
+ template<class InputIterator, class OutputIterator,
749
+ class BinaryOperation, class UnaryOperation, class T>
750
+ OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last,
751
+ OutputIterator result,
752
+ BinaryOperation binary_op,
753
+ UnaryOperation unary_op,
754
+ T init);
755
+ template<class ExecutionPolicy,
756
+ class ForwardIterator1, class ForwardIterator2,
757
+ class BinaryOperation, class UnaryOperation, class T>
758
+ ForwardIterator2 transform_inclusive_scan(ExecutionPolicy&& exec,
759
+ ForwardIterator1 first, ForwardIterator1 last,
760
+ ForwardIterator2 result,
761
+ BinaryOperation binary_op,
762
+ UnaryOperation unary_op,
763
+ T init);
764
+ ```
765
+
766
+ *Requires:*
767
+
768
+ - If `init` is provided, `T` shall be `MoveConstructible`
769
+ (Table  [[tab:moveconstructible]]); otherwise, `ForwardIterator1`’s
770
+ value type shall be `MoveConstructible`.
771
+ - If `init` is provided, all of
772
+ - `binary_op(init, init)`,
773
+ - `binary_op(init, unary_op(*first))`, and
774
+ - `binary_op(unary_op(*first), unary_op(*first))`
775
+
776
+ shall be convertible to `T`; otherwise,
777
+ `binary_op(unary_op(*first), unary_op(*first))` shall be convertible
778
+ to `ForwardIterator1`’s value type.
779
+ - Neither `unary_op` nor `binary_op` shall invalidate iterators or
780
+ subranges, nor modify elements in the ranges \[`first`, `last`\] or
781
+ \[`result`, `result + (last - first)`\].
782
+
783
+ *Effects:* For each integer `K` in \[`0`, `last - first`) assigns
784
+ through `result + K` the value of
785
+
786
+ - *GENERALIZED_NONCOMMUTATIVE_SUM*(
787
+     binary_op, init,
788
+     unary_op(\*(first + 0)), unary_op(\*(first + 1)), ...,
789
+ unary_op(\*(first + K)))
790
+ if `init` is provided, or
791
+ - *GENERALIZED_NONCOMMUTATIVE_SUM*(
792
+     binary_op,
793
+     unary_op(\*(first + 0)), unary_op(\*(first + 1)), ...,
794
+ unary_op(\*(first + K)))
795
+ otherwise.
796
+
797
+ *Returns:* The end of the resulting range beginning at `result`.
798
+
799
+ *Complexity:* 𝑂(`last - first`) applications each of `unary_op` and
800
+ `binary_op`.
801
+
802
+ *Remarks:* `result` may be equal to `first`.
803
+
804
+ [*Note 1*: The difference between `transform_exclusive_scan` and
805
+ `transform_inclusive_scan` is that `transform_inclusive_scan` includes
806
+ the iᵗʰ input element in the iᵗʰ sum. If `binary_op` is not
807
+ mathematically associative, the behavior of `transform_inclusive_scan`
808
+ may be nondeterministic. `transform_inclusive_scan` does not apply
809
+ `unary_op` to `init`. — *end note*]
810
+
811
  ### Adjacent difference <a id="adjacent.difference">[[adjacent.difference]]</a>
812
 
813
  ``` cpp
814
  template <class InputIterator, class OutputIterator>
815
+ OutputIterator
816
+ adjacent_difference(InputIterator first, InputIterator last,
817
  OutputIterator result);
818
+ template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
819
+ ForwardIterator2
820
+ adjacent_difference(ExecutionPolicy&& exec,
821
+ ForwardIterator1 first, ForwardIterator1 last,
822
+ ForwardIterator2 result);
823
+
824
  template <class InputIterator, class OutputIterator, class BinaryOperation>
825
+ OutputIterator
826
+ adjacent_difference(InputIterator first, InputIterator last,
827
  OutputIterator result,
828
  BinaryOperation binary_op);
829
+ template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
830
+ class BinaryOperation>
831
+ ForwardIterator2
832
+ adjacent_difference(ExecutionPolicy&& exec,
833
+ ForwardIterator1 first, ForwardIterator1 last,
834
+ ForwardIterator2 result,
835
+ BinaryOperation binary_op);
836
  ```
837
 
838
+ *Requires:*
839
+
840
+ - For the overloads with no `ExecutionPolicy`, `InputIterator`’s value
841
+ type shall be `MoveAssignable` (Table  [[tab:moveassignable]]) and
842
+ shall be constructible from the type of `*first`. `acc` (defined
843
+ below) shall be writable ([[iterator.requirements.general]]) to the
844
+ `result` output iterator. The result of the expression `val - acc` or
845
+ `binary_op(val, acc)` shall be writable to the `result` output
846
+ iterator.
847
+ - For the overloads with an `ExecutionPolicy`, the value type of
848
+ `ForwardIterator1` shall be `CopyConstructible`
849
+ (Table  [[tab:copyconstructible]]), constructible from the expression
850
+ `*first - *first` or `binary_op(*first, *first)`, and assignable to
851
+ the value type of `ForwardIterator2`.
852
+ - For all overloads, in the ranges \[`first`, `last`\] and \[`result`,
853
+ `result + (last - first)`\], `binary_op` shall neither modify elements
854
+ nor invalidate iterators or subranges.[^17]
855
+
856
+ *Effects:* For the overloads with no `ExecutionPolicy` and a non-empty
857
+ range, the function creates an accumulator `acc` whose type is
858
+ `InputIterator`’s value type, initializes it with `*first`, and assigns
859
+ the result to `*result`. For every iterator `i` in \[`first + 1`,
860
+ `last`) in order, creates an object `val` whose type is
861
  `InputIterator`’s value type, initializes it with `*i`, computes
862
  `val - acc` or `binary_op(val, acc)`, assigns the result to
863
  `*(result + (i - first))`, and move assigns from `val` to `acc`.
864
 
865
+ For the overloads with an `ExecutionPolicy` and a non-empty range, first
866
+ the function creates an object whose type is `ForwardIterator1`’s value
867
+ type, initializes it with `*first`, and assigns the result to `*result`.
868
+ Then for every `d` in \[`1`, `last - first - 1`\], creates an object
869
+ `val` whose type is `ForwardIterator1`’s value type, initializes it with
870
+ `*(first + d) - *(first + d - 1)` or
871
+ `binary_op(*(first + d), *(first + d - 1))`, and assigns the result to
872
+ `*(result + d)`.
 
873
 
874
  *Returns:* `result + (last - first)`.
875
 
876
  *Complexity:* Exactly `(last - first) - 1` applications of the binary
877
  operation.
878
 
879
+ *Remarks:* For the overloads with no `ExecutionPolicy`, `result` may be
880
+ equal to `first`. For the overloads with an `ExecutionPolicy`, the
881
+ ranges \[`first`, `last`) and \[`result`, `result + (last - first)`)
882
+ shall not overlap.
883
+
884
  ### Iota <a id="numeric.iota">[[numeric.iota]]</a>
885
 
886
  ``` cpp
887
  template <class ForwardIterator, class T>
888
  void iota(ForwardIterator first, ForwardIterator last, T value);
 
895
  \[`first`, `last`), assigns `*i = value` and increments `value` as if by
896
  `++value`.
897
 
898
  *Complexity:* Exactly `last - first` increments and assignments.
899
 
900
+ ### Greatest common divisor <a id="numeric.ops.gcd">[[numeric.ops.gcd]]</a>
901
+
902
+ ``` cpp
903
+ template <class M, class N>
904
+ constexpr common_type_t<M,N> gcd(M m, N n);
905
+ ```
906
+
907
+ *Requires:* `|m|` and `|n|` shall be representable as a value of
908
+ `common_type_t<M, N>`.
909
+
910
+ [*Note 1*: These requirements ensure, for example, that
911
+ `gcd(m, m) = |m|` is representable as a value of type
912
+ `M`. — *end note*]
913
+
914
+ *Remarks:* If either `M` or `N` is not an integer type, or if either is
915
+ cv `bool`, the program is ill-formed.
916
+
917
+ *Returns:* Zero when `m` and `n` are both zero. Otherwise, returns the
918
+ greatest common divisor of `|m|` and `|n|`.
919
+
920
+ *Throws:* Nothing.
921
+
922
+ ### Least common multiple <a id="numeric.ops.lcm">[[numeric.ops.lcm]]</a>
923
+
924
+ ``` cpp
925
+ template <class M, class N>
926
+ constexpr common_type_t<M,N> lcm(M m, N n);
927
+ ```
928
+
929
+ *Requires:* `|m|` and `|n|` shall be representable as a value of
930
+ `common_type_t<M, N>`. The least common multiple of `|m|` and `|n|`
931
+ shall be representable as a value of type `common_type_t<M,N>`.
932
+
933
+ *Remarks:* If either `M` or `N` is not an integer type, or if either is
934
+ cv `bool` the program is ill-formed.
935
+
936
+ *Returns:* Zero when either `m` or `n` is zero. Otherwise, returns the
937
+ least common multiple of `|m|` and `|n|`.
938
+
939
+ *Throws:* Nothing.
940
+