From Jason Turner

[alg.nonmodifying]

C++14 → C++17 22.3 KB 291 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/tmp36n44waj/{from.md → to.md} +249 -28
tmp/tmp36n44waj/{from.md → to.md} RENAMED
@@ -3,10 +3,13 @@
3
  ### All of <a id="alg.all_of">[[alg.all_of]]</a>
4
 
5
  ``` cpp
6
  template <class InputIterator, class Predicate>
7
  bool all_of(InputIterator first, InputIterator last, Predicate pred);
 
 
 
8
  ```
9
 
10
  *Returns:* `true` if \[`first`, `last`) is empty or if `pred(*i)` is
11
  `true` for every iterator `i` in the range \[`first`, `last`), and
12
  `false` otherwise.
@@ -16,10 +19,13 @@ template <class InputIterator, class Predicate>
16
  ### Any of <a id="alg.any_of">[[alg.any_of]]</a>
17
 
18
  ``` cpp
19
  template <class InputIterator, class Predicate>
20
  bool any_of(InputIterator first, InputIterator last, Predicate pred);
 
 
 
21
  ```
22
 
23
  *Returns:* `false` if \[`first`, `last`) is empty or if there is no
24
  iterator `i` in the range \[`first`, `last`) such that `pred(*i)` is
25
  `true`, and `true` otherwise.
@@ -29,10 +35,13 @@ iterator `i` in the range \[`first`, `last`) such that `pred(*i)` is
29
  ### None of <a id="alg.none_of">[[alg.none_of]]</a>
30
 
31
  ``` cpp
32
  template <class InputIterator, class Predicate>
33
  bool none_of(InputIterator first, InputIterator last, Predicate pred);
 
 
 
34
  ```
35
 
36
  *Returns:* `true` if \[`first`, `last`) is empty or if `pred(*i)` is
37
  `false` for every iterator `i` in the range \[`first`, `last`), and
38
  `false` otherwise.
@@ -45,39 +54,129 @@ template <class InputIterator, class Predicate>
45
  template<class InputIterator, class Function>
46
  Function for_each(InputIterator first, InputIterator last, Function f);
47
  ```
48
 
49
  *Requires:* `Function` shall meet the requirements of
50
- `MoveConstructible` (Table  [[moveconstructible]]). `Function` need not
51
- meet the requirements of `CopyConstructible`
52
- (Table  [[copyconstructible]]).
 
53
 
54
  *Effects:* Applies `f` to the result of dereferencing every iterator in
55
  the range \[`first`, `last`), starting from `first` and proceeding to
56
- `last - 1`. If the type of `first` satisfies the requirements of a
57
- mutable iterator, `f` may apply nonconstant functions through the
58
- dereferenced iterator.
59
 
60
- *Returns:* `std::move(f)`.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
61
 
62
  *Complexity:* Applies `f` exactly `last - first` times.
63
 
64
  *Remarks:* If `f` returns a result, the result is ignored.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
65
 
66
  ### Find <a id="alg.find">[[alg.find]]</a>
67
 
68
  ``` cpp
69
  template<class InputIterator, class T>
70
  InputIterator find(InputIterator first, InputIterator last,
71
  const T& value);
 
 
 
72
 
73
  template<class InputIterator, class Predicate>
74
  InputIterator find_if(InputIterator first, InputIterator last,
75
  Predicate pred);
 
 
 
 
76
  template<class InputIterator, class Predicate>
77
  InputIterator find_if_not(InputIterator first, InputIterator last,
78
  Predicate pred);
 
 
 
79
  ```
80
 
81
  *Returns:* The first iterator `i` in the range \[`first`, `last`) for
82
  which the following corresponding conditions hold: `*i == value`,
83
  `pred(*i) != false`, `pred(*i) == false`. Returns `last` if no such
@@ -91,17 +190,29 @@ predicate.
91
  ``` cpp
92
  template<class ForwardIterator1, class ForwardIterator2>
93
  ForwardIterator1
94
  find_end(ForwardIterator1 first1, ForwardIterator1 last1,
95
  ForwardIterator2 first2, ForwardIterator2 last2);
 
 
 
 
 
96
 
97
  template<class ForwardIterator1, class ForwardIterator2,
98
  class BinaryPredicate>
99
  ForwardIterator1
100
  find_end(ForwardIterator1 first1, ForwardIterator1 last1,
101
  ForwardIterator2 first2, ForwardIterator2 last2,
102
  BinaryPredicate pred);
 
 
 
 
 
 
 
103
  ```
104
 
105
  *Effects:* Finds a subsequence of equal values in a sequence.
106
 
107
  *Returns:* The last iterator `i` in the range \[`first1`,
@@ -120,17 +231,29 @@ applications of the corresponding predicate.
120
  ``` cpp
121
  template<class InputIterator, class ForwardIterator>
122
  InputIterator
123
  find_first_of(InputIterator first1, InputIterator last1,
124
  ForwardIterator first2, ForwardIterator last2);
 
 
 
 
 
125
 
126
  template<class InputIterator, class ForwardIterator,
127
  class BinaryPredicate>
128
  InputIterator
129
  find_first_of(InputIterator first1, InputIterator last1,
130
  ForwardIterator first2, ForwardIterator last2,
131
  BinaryPredicate pred);
 
 
 
 
 
 
 
132
  ```
133
 
134
  *Effects:* Finds an element that matches one of a set of values.
135
 
136
  *Returns:* The first iterator `i` in the range \[`first1`, `last1`) such
@@ -145,35 +268,50 @@ the corresponding predicate.
145
  ### Adjacent find <a id="alg.adjacent.find">[[alg.adjacent.find]]</a>
146
 
147
  ``` cpp
148
  template<class ForwardIterator>
149
  ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
 
 
 
150
 
151
  template<class ForwardIterator, class BinaryPredicate>
152
  ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,
153
  BinaryPredicate pred);
 
 
 
 
154
  ```
155
 
156
  *Returns:* The first iterator `i` such that both `i` and `i + 1` are in
157
  the range \[`first`, `last`) for which the following corresponding
158
  conditions hold: `*i == *(i + 1), pred(*i, *(i + 1)) != false`. Returns
159
  `last` if no such iterator is found.
160
 
161
- *Complexity:* For a nonempty range, exactly
162
  `min((i - first) + 1, (last - first) - 1)` applications of the
163
  corresponding predicate, where `i` is `adjacent_find`’s return value.
 
 
164
 
165
  ### Count <a id="alg.count">[[alg.count]]</a>
166
 
167
  ``` cpp
168
  template<class InputIterator, class T>
169
  typename iterator_traits<InputIterator>::difference_type
170
  count(InputIterator first, InputIterator last, const T& value);
 
 
 
171
 
172
  template<class InputIterator, class Predicate>
173
  typename iterator_traits<InputIterator>::difference_type
174
  count_if(InputIterator first, InputIterator last, Predicate pred);
 
 
 
175
  ```
176
 
177
  *Effects:* Returns the number of iterators `i` in the range \[`first`,
178
  `last`) for which the following corresponding conditions hold:
179
  `*i == value, pred(*i) != false`.
@@ -186,70 +324,107 @@ predicate.
186
  ``` cpp
187
  template<class InputIterator1, class InputIterator2>
188
  pair<InputIterator1, InputIterator2>
189
  mismatch(InputIterator1 first1, InputIterator1 last1,
190
  InputIterator2 first2);
 
 
 
 
 
191
 
192
  template<class InputIterator1, class InputIterator2,
193
  class BinaryPredicate>
194
  pair<InputIterator1, InputIterator2>
195
  mismatch(InputIterator1 first1, InputIterator1 last1,
196
  InputIterator2 first2, BinaryPredicate pred);
 
 
 
 
 
 
197
 
198
  template<class InputIterator1, class InputIterator2>
199
  pair<InputIterator1, InputIterator2>
200
  mismatch(InputIterator1 first1, InputIterator1 last1,
201
  InputIterator2 first2, InputIterator2 last2);
 
 
 
 
 
202
 
203
  template<class InputIterator1, class InputIterator2,
204
  class BinaryPredicate>
205
  pair<InputIterator1, InputIterator2>
206
  mismatch(InputIterator1 first1, InputIterator1 last1,
207
  InputIterator2 first2, InputIterator2 last2,
208
  BinaryPredicate pred);
 
 
 
 
 
 
 
209
  ```
210
 
211
  *Remarks:* If `last2` was not given in the argument list, it denotes
212
  `first2 + (last1 - first1)` below.
213
 
214
- *Returns:* A pair of iterators `i` and `j` such that
215
- `j == first2 + (i - first1)` and `i` is the first iterator in the range
216
- \[`first1`, `last1`) for which the following corresponding conditions
217
- hold:
218
 
219
- - `j` is in the range `[first2, last2)`.
220
- - `!(*i == *(first2 + (i - first1)))`
221
- - `pred(*i, *(first2 + (i - first1))) == false`
222
 
223
- Returns the pair `first1 + min(last1 - first1, last2 - first2)` and
224
- `first2 + min(last1 - first1, last2 - first2)` if such an iterator `i`
225
- is not found.
226
 
227
- *Complexity:* At most `last1 - first1` applications of the corresponding
228
- predicate.
229
 
230
  ### Equal <a id="alg.equal">[[alg.equal]]</a>
231
 
232
  ``` cpp
233
  template<class InputIterator1, class InputIterator2>
234
  bool equal(InputIterator1 first1, InputIterator1 last1,
235
  InputIterator2 first2);
 
 
 
 
236
 
237
  template<class InputIterator1, class InputIterator2,
238
  class BinaryPredicate>
239
  bool equal(InputIterator1 first1, InputIterator1 last1,
240
  InputIterator2 first2, BinaryPredicate pred);
 
 
 
 
 
241
 
242
  template<class InputIterator1, class InputIterator2>
243
  bool equal(InputIterator1 first1, InputIterator1 last1,
244
  InputIterator2 first2, InputIterator2 last2);
 
 
 
 
245
 
246
  template<class InputIterator1, class InputIterator2,
247
  class BinaryPredicate>
248
  bool equal(InputIterator1 first1, InputIterator1 last1,
249
  InputIterator2 first2, InputIterator2 last2,
250
  BinaryPredicate pred);
 
 
 
 
 
 
251
  ```
252
 
253
  *Remarks:* If `last2` was not given in the argument list, it denotes
254
  `first2 + (last1 - first1)` below.
255
 
@@ -257,14 +432,24 @@ template<class InputIterator1, class InputIterator2,
257
  Otherwise return `true` if for every iterator `i` in the range
258
  \[`first1`, `last1`) the following corresponding conditions hold:
259
  `*i == *(first2 + (i - first1)), pred(*i, *(first2 + (i - first1))) != false`.
260
  Otherwise, returns `false`.
261
 
262
- *Complexity:* No applications of the corresponding predicate if
263
- `InputIterator1` and `InputIterator2` meet the requirements of random
264
- access iterators and `last1 - first1 != last2 - first2`. Otherwise, at
265
- most `min(last1 - first1, last2 - first2)` applications of the
 
 
 
 
 
 
 
 
 
 
266
  corresponding predicate.
267
 
268
  ### Is permutation <a id="alg.is_permutation">[[alg.is_permutation]]</a>
269
 
270
  ``` cpp
@@ -300,31 +485,43 @@ returns `true` or `equal(first1, last1, begin, pred)` returns `true`;
300
  otherwise, returns `false`.
301
 
302
  *Complexity:* No applications of the corresponding predicate if
303
  `ForwardIterator1` and `ForwardIterator2` meet the requirements of
304
  random access iterators and `last1 - first1 != last2 - first2`.
305
- Otherwise, exactly `distance(first1, last1)` applications of the
306
- corresponding predicate if `equal(first1, last1, first2, last2)` would
307
- return `true` if `pred` was not given in the argument list or
308
  `equal(first1, last1, first2, last2, pred)` would return `true` if pred
309
  was given in the argument list; otherwise, at worst 𝑂(N^2), where N has
310
- the value `distance(first1, last1)`.
311
 
312
  ### Search <a id="alg.search">[[alg.search]]</a>
313
 
314
  ``` cpp
315
  template<class ForwardIterator1, class ForwardIterator2>
316
  ForwardIterator1
317
  search(ForwardIterator1 first1, ForwardIterator1 last1,
318
  ForwardIterator2 first2, ForwardIterator2 last2);
 
 
 
 
 
319
 
320
  template<class ForwardIterator1, class ForwardIterator2,
321
  class BinaryPredicate>
322
  ForwardIterator1
323
  search(ForwardIterator1 first1, ForwardIterator1 last1,
324
  ForwardIterator2 first2, ForwardIterator2 last2,
325
  BinaryPredicate pred);
 
 
 
 
 
 
 
326
  ```
327
 
328
  *Effects:* Finds a subsequence of equal values in a sequence.
329
 
330
  *Returns:* The first iterator `i` in the range \[`first1`,
@@ -346,10 +543,23 @@ template<class ForwardIterator, class Size, class T>
346
  template<class ForwardIterator, class Size, class T,
347
  class BinaryPredicate>
348
  ForwardIterator
349
  search_n(ForwardIterator first, ForwardIterator last, Size count,
350
  const T& value, BinaryPredicate pred);
 
 
 
 
 
 
 
 
 
 
 
 
 
351
  ```
352
 
353
  *Requires:* The type `Size` shall be convertible to integral
354
  type ([[conv.integral]], [[class.conv]]).
355
 
@@ -362,5 +572,16 @@ following corresponding conditions hold:
362
  such iterator is found.
363
 
364
  *Complexity:* At most `last - first` applications of the corresponding
365
  predicate.
366
 
 
 
 
 
 
 
 
 
 
 
 
 
3
  ### All of <a id="alg.all_of">[[alg.all_of]]</a>
4
 
5
  ``` cpp
6
  template <class InputIterator, class Predicate>
7
  bool all_of(InputIterator first, InputIterator last, Predicate pred);
8
+ template <class ExecutionPolicy, class ForwardIterator, class Predicate>
9
+ bool all_of(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
10
+ Predicate pred);
11
  ```
12
 
13
  *Returns:* `true` if \[`first`, `last`) is empty or if `pred(*i)` is
14
  `true` for every iterator `i` in the range \[`first`, `last`), and
15
  `false` otherwise.
 
19
  ### Any of <a id="alg.any_of">[[alg.any_of]]</a>
20
 
21
  ``` cpp
22
  template <class InputIterator, class Predicate>
23
  bool any_of(InputIterator first, InputIterator last, Predicate pred);
24
+ template <class ExecutionPolicy, class ForwardIterator, class Predicate>
25
+ bool any_of(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
26
+ Predicate pred);
27
  ```
28
 
29
  *Returns:* `false` if \[`first`, `last`) is empty or if there is no
30
  iterator `i` in the range \[`first`, `last`) such that `pred(*i)` is
31
  `true`, and `true` otherwise.
 
35
  ### None of <a id="alg.none_of">[[alg.none_of]]</a>
36
 
37
  ``` cpp
38
  template <class InputIterator, class Predicate>
39
  bool none_of(InputIterator first, InputIterator last, Predicate pred);
40
+ template <class ExecutionPolicy, class ForwardIterator, class Predicate>
41
+ bool none_of(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
42
+ Predicate pred);
43
  ```
44
 
45
  *Returns:* `true` if \[`first`, `last`) is empty or if `pred(*i)` is
46
  `false` for every iterator `i` in the range \[`first`, `last`), and
47
  `false` otherwise.
 
54
  template<class InputIterator, class Function>
55
  Function for_each(InputIterator first, InputIterator last, Function f);
56
  ```
57
 
58
  *Requires:* `Function` shall meet the requirements of
59
+ `MoveConstructible` (Table  [[tab:moveconstructible]]).
60
+
61
+ [*Note 1*: `Function` need not meet the requirements of
62
+ `CopyConstructible` (Table  [[tab:copyconstructible]]). — *end note*]
63
 
64
  *Effects:* Applies `f` to the result of dereferencing every iterator in
65
  the range \[`first`, `last`), starting from `first` and proceeding to
66
+ `last - 1`.
 
 
67
 
68
+ [*Note 2*: If the type of `first` satisfies the requirements of a
69
+ mutable iterator, `f` may apply non-constant functions through the
70
+ dereferenced iterator. — *end note*]
71
+
72
+ *Returns:* `f`.
73
+
74
+ *Complexity:* Applies `f` exactly `last - first` times.
75
+
76
+ *Remarks:* If `f` returns a result, the result is ignored.
77
+
78
+ ``` cpp
79
+ template<class ExecutionPolicy, class ForwardIterator, class Function>
80
+ void for_each(ExecutionPolicy&& exec,
81
+ ForwardIterator first, ForwardIterator last,
82
+ Function f);
83
+ ```
84
+
85
+ *Requires:* `Function` shall meet the requirements of
86
+ `CopyConstructible`.
87
+
88
+ *Effects:* Applies `f` to the result of dereferencing every iterator in
89
+ the range \[`first`, `last`).
90
+
91
+ [*Note 3*: If the type of `first` satisfies the requirements of a
92
+ mutable iterator, `f` may apply non-constant functions through the
93
+ dereferenced iterator. — *end note*]
94
 
95
  *Complexity:* Applies `f` exactly `last - first` times.
96
 
97
  *Remarks:* If `f` returns a result, the result is ignored.
98
+ Implementations do not have the freedom granted under
99
+ [[algorithms.parallel.exec]] to make arbitrary copies of elements from
100
+ the input sequence.
101
+
102
+ [*Note 4*: Does not return a copy of its `Function` parameter, since
103
+ parallelization may not permit efficient state
104
+ accumulation. — *end note*]
105
+
106
+ ``` cpp
107
+ template<class InputIterator, class Size, class Function>
108
+ InputIterator for_each_n(InputIterator first, Size n, Function f);
109
+ ```
110
+
111
+ *Requires:* `Function` shall meet the requirements of
112
+ `MoveConstructible`
113
+
114
+ [*Note 5*: `Function` need not meet the requirements of
115
+ `CopyConstructible`. — *end note*]
116
+
117
+ *Requires:* `n >= 0`.
118
+
119
+ *Effects:* Applies `f` to the result of dereferencing every iterator in
120
+ the range \[`first`, `first + n`) in order.
121
+
122
+ [*Note 6*: If the type of `first` satisfies the requirements of a
123
+ mutable iterator, `f` may apply non-constant functions through the
124
+ dereferenced iterator. — *end note*]
125
+
126
+ *Returns:* `first + n`.
127
+
128
+ *Remarks:* If `f` returns a result, the result is ignored.
129
+
130
+ ``` cpp
131
+ template<class ExecutionPolicy, class ForwardIterator, class Size, class Function>
132
+ ForwardIterator for_each_n(ExecutionPolicy&& exec, ForwardIterator first, Size n,
133
+ Function f);
134
+ ```
135
+
136
+ *Requires:* `Function` shall meet the requirements of
137
+ `CopyConstructible`.
138
+
139
+ *Requires:* `n >= 0`.
140
+
141
+ *Effects:* Applies `f` to the result of dereferencing every iterator in
142
+ the range \[`first`, `first + n`).
143
+
144
+ [*Note 7*: If the type of `first` satisfies the requirements of a
145
+ mutable iterator, `f` may apply non-constant functions through the
146
+ dereferenced iterator. — *end note*]
147
+
148
+ *Returns:* `first + n`.
149
+
150
+ *Remarks:* If `f` returns a result, the result is ignored.
151
+ Implementations do not have the freedom granted under
152
+ [[algorithms.parallel.exec]] to make arbitrary copies of elements from
153
+ the input sequence.
154
 
155
  ### Find <a id="alg.find">[[alg.find]]</a>
156
 
157
  ``` cpp
158
  template<class InputIterator, class T>
159
  InputIterator find(InputIterator first, InputIterator last,
160
  const T& value);
161
+ template<class ExecutionPolicy, class ForwardIterator, class T>
162
+ ForwardIterator find(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
163
+ const T& value);
164
 
165
  template<class InputIterator, class Predicate>
166
  InputIterator find_if(InputIterator first, InputIterator last,
167
  Predicate pred);
168
+ template<class ExecutionPolicy, class ForwardIterator, class Predicate>
169
+ ForwardIterator find_if(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
170
+ Predicate pred);
171
+
172
  template<class InputIterator, class Predicate>
173
  InputIterator find_if_not(InputIterator first, InputIterator last,
174
  Predicate pred);
175
+ template<class ExecutionPolicy, class ForwardIterator, class Predicate>
176
+ ForwardIterator find_if_not(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
177
+ Predicate pred);
178
  ```
179
 
180
  *Returns:* The first iterator `i` in the range \[`first`, `last`) for
181
  which the following corresponding conditions hold: `*i == value`,
182
  `pred(*i) != false`, `pred(*i) == false`. Returns `last` if no such
 
190
  ``` cpp
191
  template<class ForwardIterator1, class ForwardIterator2>
192
  ForwardIterator1
193
  find_end(ForwardIterator1 first1, ForwardIterator1 last1,
194
  ForwardIterator2 first2, ForwardIterator2 last2);
195
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
196
+ ForwardIterator1
197
+ find_end(ExecutionPolicy&& exec,
198
+ ForwardIterator1 first1, ForwardIterator1 last1,
199
+ ForwardIterator2 first2, ForwardIterator2 last2);
200
 
201
  template<class ForwardIterator1, class ForwardIterator2,
202
  class BinaryPredicate>
203
  ForwardIterator1
204
  find_end(ForwardIterator1 first1, ForwardIterator1 last1,
205
  ForwardIterator2 first2, ForwardIterator2 last2,
206
  BinaryPredicate pred);
207
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
208
+ class BinaryPredicate>
209
+ ForwardIterator1
210
+ find_end(ExecutionPolicy&& exec,
211
+ ForwardIterator1 first1, ForwardIterator1 last1,
212
+ ForwardIterator2 first2, ForwardIterator2 last2,
213
+ BinaryPredicate pred);
214
  ```
215
 
216
  *Effects:* Finds a subsequence of equal values in a sequence.
217
 
218
  *Returns:* The last iterator `i` in the range \[`first1`,
 
231
  ``` cpp
232
  template<class InputIterator, class ForwardIterator>
233
  InputIterator
234
  find_first_of(InputIterator first1, InputIterator last1,
235
  ForwardIterator first2, ForwardIterator last2);
236
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
237
+ ForwardIterator1
238
+ find_first_of(ExecutionPolicy&& exec,
239
+ ForwardIterator1 first1, ForwardIterator1 last1,
240
+ ForwardIterator2 first2, ForwardIterator2 last2);
241
 
242
  template<class InputIterator, class ForwardIterator,
243
  class BinaryPredicate>
244
  InputIterator
245
  find_first_of(InputIterator first1, InputIterator last1,
246
  ForwardIterator first2, ForwardIterator last2,
247
  BinaryPredicate pred);
248
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
249
+ class BinaryPredicate>
250
+ ForwardIterator1
251
+ find_first_of(ExecutionPolicy&& exec,
252
+ ForwardIterator1 first1, ForwardIterator1 last1,
253
+ ForwardIterator2 first2, ForwardIterator2 last2,
254
+ BinaryPredicate pred);
255
  ```
256
 
257
  *Effects:* Finds an element that matches one of a set of values.
258
 
259
  *Returns:* The first iterator `i` in the range \[`first1`, `last1`) such
 
268
  ### Adjacent find <a id="alg.adjacent.find">[[alg.adjacent.find]]</a>
269
 
270
  ``` cpp
271
  template<class ForwardIterator>
272
  ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
273
+ template<class ExecutionPolicy, class ForwardIterator>
274
+ ForwardIterator adjacent_find(ExecutionPolicy&& exec,
275
+ ForwardIterator first, ForwardIterator last);
276
 
277
  template<class ForwardIterator, class BinaryPredicate>
278
  ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,
279
  BinaryPredicate pred);
280
+ template<class ExecutionPolicy, class ForwardIterator, class BinaryPredicate>
281
+ ForwardIterator adjacent_find(ExecutionPolicy&& exec,
282
+ ForwardIterator first, ForwardIterator last,
283
+ BinaryPredicate pred);
284
  ```
285
 
286
  *Returns:* The first iterator `i` such that both `i` and `i + 1` are in
287
  the range \[`first`, `last`) for which the following corresponding
288
  conditions hold: `*i == *(i + 1), pred(*i, *(i + 1)) != false`. Returns
289
  `last` if no such iterator is found.
290
 
291
+ *Complexity:* For the overloads with no `ExecutionPolicy`, exactly
292
  `min((i - first) + 1, (last - first) - 1)` applications of the
293
  corresponding predicate, where `i` is `adjacent_find`’s return value.
294
+ For the overloads with an `ExecutionPolicy`, 𝑂(`last - first`)
295
+ applications of the corresponding predicate.
296
 
297
  ### Count <a id="alg.count">[[alg.count]]</a>
298
 
299
  ``` cpp
300
  template<class InputIterator, class T>
301
  typename iterator_traits<InputIterator>::difference_type
302
  count(InputIterator first, InputIterator last, const T& value);
303
+ template<class ExecutionPolicy, class ForwardIterator, class T>
304
+ typename iterator_traits<ForwardIterator>::difference_type
305
+ count(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, const T& value);
306
 
307
  template<class InputIterator, class Predicate>
308
  typename iterator_traits<InputIterator>::difference_type
309
  count_if(InputIterator first, InputIterator last, Predicate pred);
310
+ template<class ExecutionPolicy, class ForwardIterator, class Predicate>
311
+ typename iterator_traits<ForwardIterator>::difference_type
312
+ count_if(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred);
313
  ```
314
 
315
  *Effects:* Returns the number of iterators `i` in the range \[`first`,
316
  `last`) for which the following corresponding conditions hold:
317
  `*i == value, pred(*i) != false`.
 
324
  ``` cpp
325
  template<class InputIterator1, class InputIterator2>
326
  pair<InputIterator1, InputIterator2>
327
  mismatch(InputIterator1 first1, InputIterator1 last1,
328
  InputIterator2 first2);
329
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
330
+ pair<ForwardIterator1, ForwardIterator2>
331
+ mismatch(ExecutionPolicy&& exec,
332
+ ForwardIterator1 first1, ForwardIterator1 last1,
333
+ ForwardIterator2 first2);
334
 
335
  template<class InputIterator1, class InputIterator2,
336
  class BinaryPredicate>
337
  pair<InputIterator1, InputIterator2>
338
  mismatch(InputIterator1 first1, InputIterator1 last1,
339
  InputIterator2 first2, BinaryPredicate pred);
340
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
341
+ class BinaryPredicate>
342
+ pair<ForwardIterator1, ForwardIterator2>
343
+ mismatch(ExecutionPolicy&& exec,
344
+ ForwardIterator1 first1, ForwardIterator1 last1,
345
+ ForwardIterator2 first2, BinaryPredicate pred);
346
 
347
  template<class InputIterator1, class InputIterator2>
348
  pair<InputIterator1, InputIterator2>
349
  mismatch(InputIterator1 first1, InputIterator1 last1,
350
  InputIterator2 first2, InputIterator2 last2);
351
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
352
+ pair<ForwardIterator1, ForwardIterator2>
353
+ mismatch(ExecutionPolicy&& exec,
354
+ ForwardIterator1 first1, ForwardIterator1 last1,
355
+ ForwardIterator2 first2, ForwardIterator2 last2);
356
 
357
  template<class InputIterator1, class InputIterator2,
358
  class BinaryPredicate>
359
  pair<InputIterator1, InputIterator2>
360
  mismatch(InputIterator1 first1, InputIterator1 last1,
361
  InputIterator2 first2, InputIterator2 last2,
362
  BinaryPredicate pred);
363
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
364
+ class BinaryPredicate>
365
+ pair<ForwardIterator1, ForwardIterator2>
366
+ mismatch(ExecutionPolicy&& exec,
367
+ ForwardIterator1 first1, ForwardIterator1 last1,
368
+ ForwardIterator2 first2, ForwardIterator2 last2,
369
+ BinaryPredicate pred);
370
  ```
371
 
372
  *Remarks:* If `last2` was not given in the argument list, it denotes
373
  `first2 + (last1 - first1)` below.
374
 
375
+ *Returns:* A pair of iterators `first1 + n` and `first2 + n`, where `n`
376
+ is the smallest integer such that, respectively,
 
 
377
 
378
+ - `!(*(first1 + n) == *(first2 + n))` or
379
+ - `pred(*(first1 + n), *(first2 + n)) == false`,
 
380
 
381
+ or `min(last1 - first1, last2 - first2)` if no such integer exists.
 
 
382
 
383
+ *Complexity:* At most `min(last1 - first1, last2 - first2)` applications
384
+ of the corresponding predicate.
385
 
386
  ### Equal <a id="alg.equal">[[alg.equal]]</a>
387
 
388
  ``` cpp
389
  template<class InputIterator1, class InputIterator2>
390
  bool equal(InputIterator1 first1, InputIterator1 last1,
391
  InputIterator2 first2);
392
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
393
+ bool equal(ExecutionPolicy&& exec,
394
+ ForwardIterator1 first1, ForwardIterator1 last1,
395
+ ForwardIterator2 first2);
396
 
397
  template<class InputIterator1, class InputIterator2,
398
  class BinaryPredicate>
399
  bool equal(InputIterator1 first1, InputIterator1 last1,
400
  InputIterator2 first2, BinaryPredicate pred);
401
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
402
+ class BinaryPredicate>
403
+ bool equal(ExecutionPolicy&& exec,
404
+ ForwardIterator1 first1, ForwardIterator1 last1,
405
+ ForwardIterator2 first2, BinaryPredicate pred);
406
 
407
  template<class InputIterator1, class InputIterator2>
408
  bool equal(InputIterator1 first1, InputIterator1 last1,
409
  InputIterator2 first2, InputIterator2 last2);
410
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
411
+ bool equal(ExecutionPolicy&& exec,
412
+ ForwardIterator1 first1, ForwardIterator1 last1,
413
+ ForwardIterator2 first2, ForwardIterator2 last2);
414
 
415
  template<class InputIterator1, class InputIterator2,
416
  class BinaryPredicate>
417
  bool equal(InputIterator1 first1, InputIterator1 last1,
418
  InputIterator2 first2, InputIterator2 last2,
419
  BinaryPredicate pred);
420
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
421
+ class BinaryPredicate>
422
+ bool equal(ExecutionPolicy&& exec,
423
+ ForwardIterator1 first1, ForwardIterator1 last1,
424
+ ForwardIterator2 first2, ForwardIterator2 last2,
425
+ BinaryPredicate pred);
426
  ```
427
 
428
  *Remarks:* If `last2` was not given in the argument list, it denotes
429
  `first2 + (last1 - first1)` below.
430
 
 
432
  Otherwise return `true` if for every iterator `i` in the range
433
  \[`first1`, `last1`) the following corresponding conditions hold:
434
  `*i == *(first2 + (i - first1)), pred(*i, *(first2 + (i - first1))) != false`.
435
  Otherwise, returns `false`.
436
 
437
+ *Complexity:*
438
+
439
+ - For the overloads with no `ExecutionPolicy`,
440
+ - if `InputIterator1` and `InputIterator2` meet the requirements of
441
+ random access iterators ([[random.access.iterators]]) and
442
+ `last1 - first1 != last2 - first2`, then no applications of the
443
+ corresponding predicate; otherwise,
444
+ - at most min(`last1 - first1`, `last2 - first2`) applications of the
445
+ corresponding predicate.
446
+ - For the overloads with no `ExecutionPolicy`,
447
+ - if `ForwardIterator1` and `ForwardIterator2` meet the requirements
448
+ of random access iterators and `last1 - first1 != last2 - first2`,
449
+ then no applications of the corresponding predicate; otherwise,
450
+ - 𝑂(min(`last1 - first1`, `last2 - first2`)) applications of the
451
  corresponding predicate.
452
 
453
  ### Is permutation <a id="alg.is_permutation">[[alg.is_permutation]]</a>
454
 
455
  ``` cpp
 
485
  otherwise, returns `false`.
486
 
487
  *Complexity:* No applications of the corresponding predicate if
488
  `ForwardIterator1` and `ForwardIterator2` meet the requirements of
489
  random access iterators and `last1 - first1 != last2 - first2`.
490
+ Otherwise, exactly `last1 - first1` applications of the corresponding
491
+ predicate if `equal(first1, last1, first2, last2)` would return `true`
492
+ if `pred` was not given in the argument list or
493
  `equal(first1, last1, first2, last2, pred)` would return `true` if pred
494
  was given in the argument list; otherwise, at worst 𝑂(N^2), where N has
495
+ the value `last1 - first1`.
496
 
497
  ### Search <a id="alg.search">[[alg.search]]</a>
498
 
499
  ``` cpp
500
  template<class ForwardIterator1, class ForwardIterator2>
501
  ForwardIterator1
502
  search(ForwardIterator1 first1, ForwardIterator1 last1,
503
  ForwardIterator2 first2, ForwardIterator2 last2);
504
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
505
+ ForwardIterator1
506
+ search(ExecutionPolicy&& exec,
507
+ ForwardIterator1 first1, ForwardIterator1 last1,
508
+ ForwardIterator2 first2, ForwardIterator2 last2);
509
 
510
  template<class ForwardIterator1, class ForwardIterator2,
511
  class BinaryPredicate>
512
  ForwardIterator1
513
  search(ForwardIterator1 first1, ForwardIterator1 last1,
514
  ForwardIterator2 first2, ForwardIterator2 last2,
515
  BinaryPredicate pred);
516
+ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
517
+ class BinaryPredicate>
518
+ ForwardIterator1
519
+ search(ExecutionPolicy&& exec,
520
+ ForwardIterator1 first1, ForwardIterator1 last1,
521
+ ForwardIterator2 first2, ForwardIterator2 last2,
522
+ BinaryPredicate pred);
523
  ```
524
 
525
  *Effects:* Finds a subsequence of equal values in a sequence.
526
 
527
  *Returns:* The first iterator `i` in the range \[`first1`,
 
543
  template<class ForwardIterator, class Size, class T,
544
  class BinaryPredicate>
545
  ForwardIterator
546
  search_n(ForwardIterator first, ForwardIterator last, Size count,
547
  const T& value, BinaryPredicate pred);
548
+
549
+ template<class ExecutionPolicy, class ForwardIterator, class Size, class T>
550
+ ForwardIterator
551
+ search_n(ExecutionPolicy&& exec,
552
+ ForwardIterator first, ForwardIterator last,
553
+ Size count, const T& value);
554
+ template<class ExecutionPolicy, class ForwardIterator, class Size, class T,
555
+ class BinaryPredicate>
556
+ ForwardIterator
557
+ search_n(ExecutionPolicy&& exec,
558
+ ForwardIterator first, ForwardIterator last,
559
+ Size count, const T& value,
560
+ BinaryPredicate pred);
561
  ```
562
 
563
  *Requires:* The type `Size` shall be convertible to integral
564
  type ([[conv.integral]], [[class.conv]]).
565
 
 
572
  such iterator is found.
573
 
574
  *Complexity:* At most `last - first` applications of the corresponding
575
  predicate.
576
 
577
+ ``` cpp
578
+ template<class ForwardIterator, class Searcher>
579
+ ForwardIterator search(ForwardIterator first, ForwardIterator last,
580
+ const Searcher& searcher);
581
+ ```
582
+
583
+ *Effects:* Equivalent to: `return searcher(first, last).first;`
584
+
585
+ *Remarks:* `Searcher` need not meet the `CopyConstructible`
586
+ requirements.
587
+