From Jason Turner

[algorithms.general]

C++14 → C++17 32.1 KB 643 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/tmp9pq_cls7/{from.md → to.md} +1 -638
tmp/tmp9pq_cls7/{from.md → to.md} RENAMED
@@ -3,11 +3,11 @@
3
  This Clause describes components that C++programs may use to perform
4
  algorithmic operations on containers (Clause  [[containers]]) and other
5
  sequences.
6
 
7
  The following subclauses describe components for non-modifying sequence
8
- operation, modifying sequence operations, sorting and related
9
  operations, and algorithms from the ISO C library, as summarized in
10
  Table  [[tab:algorithms.summary]].
11
 
12
  **Table: Algorithms library summary** <a id="tab:algorithms.summary">[tab:algorithms.summary]</a>
13
 
@@ -16,643 +16,6 @@ Table  [[tab:algorithms.summary]].
16
  | [[alg.nonmodifying]] | Non-modifying sequence operations | |
17
  | [[alg.modifying.operations]] | Mutating sequence operations | `<algorithm>` |
18
  | [[alg.sorting]] | Sorting and related operations | |
19
  | [[alg.c.library]] | C library algorithms | `<cstdlib>` |
20
 
21
- ``` cpp
22
- #include <initializer_list>
23
-
24
- namespace std {
25
-
26
- // [alg.nonmodifying], non-modifying sequence operations:
27
- template <class InputIterator, class Predicate>
28
- bool all_of(InputIterator first, InputIterator last, Predicate pred);
29
- template <class InputIterator, class Predicate>
30
- bool any_of(InputIterator first, InputIterator last, Predicate pred);
31
- template <class InputIterator, class Predicate>
32
- bool none_of(InputIterator first, InputIterator last, Predicate pred);
33
-
34
- template<class InputIterator, class Function>
35
- Function for_each(InputIterator first, InputIterator last, Function f);
36
- template<class InputIterator, class T>
37
- InputIterator find(InputIterator first, InputIterator last,
38
- const T& value);
39
- template<class InputIterator, class Predicate>
40
- InputIterator find_if(InputIterator first, InputIterator last,
41
- Predicate pred);
42
- template<class InputIterator, class Predicate>
43
- InputIterator find_if_not(InputIterator first, InputIterator last,
44
- Predicate pred);
45
- template<class ForwardIterator1, class ForwardIterator2>
46
- ForwardIterator1
47
- find_end(ForwardIterator1 first1, ForwardIterator1 last1,
48
- ForwardIterator2 first2, ForwardIterator2 last2);
49
- template<class ForwardIterator1, class ForwardIterator2,
50
- class BinaryPredicate>
51
- ForwardIterator1
52
- find_end(ForwardIterator1 first1, ForwardIterator1 last1,
53
- ForwardIterator2 first2, ForwardIterator2 last2,
54
- BinaryPredicate pred);
55
-
56
- template<class InputIterator, class ForwardIterator>
57
- InputIterator
58
- find_first_of(InputIterator first1, InputIterator last1,
59
- ForwardIterator first2, ForwardIterator last2);
60
- template<class InputIterator, class ForwardIterator,
61
- class BinaryPredicate>
62
- InputIterator
63
- find_first_of(InputIterator first1, InputIterator last1,
64
- ForwardIterator first2, ForwardIterator last2,
65
- BinaryPredicate pred);
66
-
67
- template<class ForwardIterator>
68
- ForwardIterator adjacent_find(ForwardIterator first,
69
- ForwardIterator last);
70
- template<class ForwardIterator, class BinaryPredicate>
71
- ForwardIterator adjacent_find(ForwardIterator first,
72
- ForwardIterator last,
73
- BinaryPredicate pred);
74
-
75
- template<class InputIterator, class T>
76
- typename iterator_traits<InputIterator>::difference_type
77
- count(InputIterator first, InputIterator last, const T& value);
78
- template<class InputIterator, class Predicate>
79
- typename iterator_traits<InputIterator>::difference_type
80
- count_if(InputIterator first, InputIterator last, Predicate pred);
81
-
82
- template<class InputIterator1, class InputIterator2>
83
- pair<InputIterator1, InputIterator2>
84
- mismatch(InputIterator1 first1, InputIterator1 last1,
85
- InputIterator2 first2);
86
- template
87
- <class InputIterator1, class InputIterator2, class BinaryPredicate>
88
- pair<InputIterator1, InputIterator2>
89
- mismatch(InputIterator1 first1, InputIterator1 last1,
90
- InputIterator2 first2, BinaryPredicate pred);
91
-
92
- template<class InputIterator1, class InputIterator2>
93
- pair<InputIterator1, InputIterator2>
94
- mismatch(InputIterator1 first1, InputIterator1 last1,
95
- InputIterator2 first2, InputIterator2 last2);
96
-
97
- template
98
- <class InputIterator1, class InputIterator2, class BinaryPredicate>
99
- pair<InputIterator1, InputIterator2>
100
- mismatch(InputIterator1 first1, InputIterator1 last1,
101
- InputIterator2 first2, InputIterator2 last2,
102
- BinaryPredicate pred);
103
-
104
- template<class InputIterator1, class InputIterator2>
105
- bool equal(InputIterator1 first1, InputIterator1 last1,
106
- InputIterator2 first2);
107
- template
108
- <class InputIterator1, class InputIterator2, class BinaryPredicate>
109
- bool equal(InputIterator1 first1, InputIterator1 last1,
110
- InputIterator2 first2, BinaryPredicate pred);
111
-
112
- template<class InputIterator1, class InputIterator2>
113
- bool equal(InputIterator1 first1, InputIterator1 last1,
114
- InputIterator2 first2, InputIterator2 last2);
115
-
116
- template
117
- <class InputIterator1, class InputIterator2, class BinaryPredicate>
118
- bool equal(InputIterator1 first1, InputIterator1 last1,
119
- InputIterator2 first2, InputIterator2 last2,
120
- BinaryPredicate pred);
121
-
122
- template<class ForwardIterator1, class ForwardIterator2>
123
- bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
124
- ForwardIterator2 first2);
125
- template<class ForwardIterator1, class ForwardIterator2,
126
- class BinaryPredicate>
127
- bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
128
- ForwardIterator2 first2, BinaryPredicate pred);
129
-
130
- template<class ForwardIterator1, class ForwardIterator2>
131
- bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
132
- ForwardIterator2 first2, ForwardIterator2 last2);
133
-
134
- template<class ForwardIterator1, class ForwardIterator2,
135
- class BinaryPredicate>
136
- bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
137
- ForwardIterator2 first2, ForwardIterator2 last2,
138
- BinaryPredicate pred);
139
-
140
- template<class ForwardIterator1, class ForwardIterator2>
141
- ForwardIterator1 search(
142
- ForwardIterator1 first1, ForwardIterator1 last1,
143
- ForwardIterator2 first2, ForwardIterator2 last2);
144
- template<class ForwardIterator1, class ForwardIterator2,
145
- class BinaryPredicate>
146
- ForwardIterator1 search(
147
- ForwardIterator1 first1, ForwardIterator1 last1,
148
- ForwardIterator2 first2, ForwardIterator2 last2,
149
- BinaryPredicate pred);
150
- template<class ForwardIterator, class Size, class T>
151
- ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
152
- Size count, const T& value);
153
- template
154
- <class ForwardIterator, class Size, class T, class BinaryPredicate>
155
- ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
156
- Size count, const T& value,
157
- BinaryPredicate pred);
158
-
159
- // [alg.modifying.operations], modifying sequence operations:
160
- // [alg.copy], copy:
161
- template<class InputIterator, class OutputIterator>
162
- OutputIterator copy(InputIterator first, InputIterator last,
163
- OutputIterator result);
164
- template<class InputIterator, class Size, class OutputIterator>
165
- OutputIterator copy_n(InputIterator first, Size n,
166
- OutputIterator result);
167
- template<class InputIterator, class OutputIterator, class Predicate>
168
- OutputIterator copy_if(InputIterator first, InputIterator last,
169
- OutputIterator result, Predicate pred);
170
- template<class BidirectionalIterator1, class BidirectionalIterator2>
171
- BidirectionalIterator2 copy_backward(
172
- BidirectionalIterator1 first, BidirectionalIterator1 last,
173
- BidirectionalIterator2 result);
174
-
175
- // [alg.move], move:
176
- template<class InputIterator, class OutputIterator>
177
- OutputIterator move(InputIterator first, InputIterator last,
178
- OutputIterator result);
179
- template<class BidirectionalIterator1, class BidirectionalIterator2>
180
- BidirectionalIterator2 move_backward(
181
- BidirectionalIterator1 first, BidirectionalIterator1 last,
182
- BidirectionalIterator2 result);
183
-
184
- // [alg.swap], swap:
185
- template<class ForwardIterator1, class ForwardIterator2>
186
- ForwardIterator2 swap_ranges(ForwardIterator1 first1,
187
- ForwardIterator1 last1, ForwardIterator2 first2);
188
- template<class ForwardIterator1, class ForwardIterator2>
189
- void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
190
-
191
- template<class InputIterator, class OutputIterator, class UnaryOperation>
192
- OutputIterator transform(InputIterator first, InputIterator last,
193
- OutputIterator result, UnaryOperation op);
194
- template<class InputIterator1, class InputIterator2, class OutputIterator,
195
- class BinaryOperation>
196
- OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
197
- InputIterator2 first2, OutputIterator result,
198
- BinaryOperation binary_op);
199
-
200
- template<class ForwardIterator, class T>
201
- void replace(ForwardIterator first, ForwardIterator last,
202
- const T& old_value, const T& new_value);
203
- template<class ForwardIterator, class Predicate, class T>
204
- void replace_if(ForwardIterator first, ForwardIterator last,
205
- Predicate pred, const T& new_value);
206
- template<class InputIterator, class OutputIterator, class T>
207
- OutputIterator replace_copy(InputIterator first, InputIterator last,
208
- OutputIterator result,
209
- const T& old_value, const T& new_value);
210
- template<class InputIterator, class OutputIterator, class Predicate, class T>
211
- OutputIterator replace_copy_if(InputIterator first, InputIterator last,
212
- OutputIterator result,
213
- Predicate pred, const T& new_value);
214
-
215
- template<class ForwardIterator, class T>
216
- void fill(ForwardIterator first, ForwardIterator last, const T& value);
217
- template<class OutputIterator, class Size, class T>
218
- OutputIterator fill_n(OutputIterator first, Size n, const T& value);
219
-
220
- template<class ForwardIterator, class Generator>
221
- void generate(ForwardIterator first, ForwardIterator last,
222
- Generator gen);
223
- template<class OutputIterator, class Size, class Generator>
224
- OutputIterator generate_n(OutputIterator first, Size n, Generator gen);
225
-
226
- template<class ForwardIterator, class T>
227
- ForwardIterator remove(ForwardIterator first, ForwardIterator last,
228
- const T& value);
229
- template<class ForwardIterator, class Predicate>
230
- ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
231
- Predicate pred);
232
- template<class InputIterator, class OutputIterator, class T>
233
- OutputIterator remove_copy(InputIterator first, InputIterator last,
234
- OutputIterator result, const T& value);
235
- template<class InputIterator, class OutputIterator, class Predicate>
236
- OutputIterator remove_copy_if(InputIterator first, InputIterator last,
237
- OutputIterator result, Predicate pred);
238
-
239
- template<class ForwardIterator>
240
- ForwardIterator unique(ForwardIterator first, ForwardIterator last);
241
- template<class ForwardIterator, class BinaryPredicate>
242
- ForwardIterator unique(ForwardIterator first, ForwardIterator last,
243
- BinaryPredicate pred);
244
- template<class InputIterator, class OutputIterator>
245
- OutputIterator unique_copy(InputIterator first, InputIterator last,
246
- OutputIterator result);
247
- template<class InputIterator, class OutputIterator, class BinaryPredicate>
248
- OutputIterator unique_copy(InputIterator first, InputIterator last,
249
- OutputIterator result, BinaryPredicate pred);
250
-
251
- template<class BidirectionalIterator>
252
- void reverse(BidirectionalIterator first, BidirectionalIterator last);
253
- template<class BidirectionalIterator, class OutputIterator>
254
- OutputIterator reverse_copy(BidirectionalIterator first,
255
- BidirectionalIterator last,
256
- OutputIterator result);
257
-
258
- template<class ForwardIterator>
259
- ForwardIterator rotate(ForwardIterator first, ForwardIterator middle,
260
- ForwardIterator last);
261
- template<class ForwardIterator, class OutputIterator>
262
- OutputIterator rotate_copy(
263
- ForwardIterator first, ForwardIterator middle,
264
- ForwardIterator last, OutputIterator result);
265
-
266
- // [depr.alg.random.shuffle], random_shuffle (deprecated):
267
- template<class RandomAccessIterator>
268
- void random_shuffle(RandomAccessIterator first,
269
- RandomAccessIterator last);
270
- template<class RandomAccessIterator, class RandomNumberGenerator>
271
- void random_shuffle(RandomAccessIterator first,
272
- RandomAccessIterator last,
273
- RandomNumberGenerator&& rng);
274
-
275
- // [alg.random.shuffle], shuffle:
276
- template<class RandomAccessIterator, class UniformRandomNumberGenerator>
277
- void shuffle(RandomAccessIterator first,
278
- RandomAccessIterator last,
279
- UniformRandomNumberGenerator&& g);
280
-
281
- // [alg.partitions], partitions:
282
- template <class InputIterator, class Predicate>
283
- bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
284
-
285
- template<class ForwardIterator, class Predicate>
286
- ForwardIterator partition(ForwardIterator first,
287
- ForwardIterator last,
288
- Predicate pred);
289
- template<class BidirectionalIterator, class Predicate>
290
- BidirectionalIterator stable_partition(BidirectionalIterator first,
291
- BidirectionalIterator last,
292
- Predicate pred);
293
- template <class InputIterator, class OutputIterator1,
294
- class OutputIterator2, class Predicate>
295
- pair<OutputIterator1, OutputIterator2>
296
- partition_copy(InputIterator first, InputIterator last,
297
- OutputIterator1 out_true, OutputIterator2 out_false,
298
- Predicate pred);
299
- template<class ForwardIterator, class Predicate>
300
- ForwardIterator partition_point(ForwardIterator first,
301
- ForwardIterator last,
302
- Predicate pred);
303
-
304
- // [alg.sorting], sorting and related operations:
305
- // [alg.sort], sorting:
306
- template<class RandomAccessIterator>
307
- void sort(RandomAccessIterator first, RandomAccessIterator last);
308
- template<class RandomAccessIterator, class Compare>
309
- void sort(RandomAccessIterator first, RandomAccessIterator last,
310
- Compare comp);
311
-
312
- template<class RandomAccessIterator>
313
- void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
314
- template<class RandomAccessIterator, class Compare>
315
- void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
316
- Compare comp);
317
-
318
- template<class RandomAccessIterator>
319
- void partial_sort(RandomAccessIterator first,
320
- RandomAccessIterator middle,
321
- RandomAccessIterator last);
322
- template<class RandomAccessIterator, class Compare>
323
- void partial_sort(RandomAccessIterator first,
324
- RandomAccessIterator middle,
325
- RandomAccessIterator last, Compare comp);
326
- template<class InputIterator, class RandomAccessIterator>
327
- RandomAccessIterator partial_sort_copy(
328
- InputIterator first, InputIterator last,
329
- RandomAccessIterator result_first,
330
- RandomAccessIterator result_last);
331
- template<class InputIterator, class RandomAccessIterator, class Compare>
332
- RandomAccessIterator partial_sort_copy(
333
- InputIterator first, InputIterator last,
334
- RandomAccessIterator result_first,
335
- RandomAccessIterator result_last,
336
- Compare comp);
337
- template<class ForwardIterator>
338
- bool is_sorted(ForwardIterator first, ForwardIterator last);
339
- template<class ForwardIterator, class Compare>
340
- bool is_sorted(ForwardIterator first, ForwardIterator last,
341
- Compare comp);
342
- template<class ForwardIterator>
343
- ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
344
- template<class ForwardIterator, class Compare>
345
- ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,
346
- Compare comp);
347
-
348
- template<class RandomAccessIterator>
349
- void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
350
- RandomAccessIterator last);
351
- template<class RandomAccessIterator, class Compare>
352
- void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
353
- RandomAccessIterator last, Compare comp);
354
-
355
- // [alg.binary.search], binary search:
356
- template<class ForwardIterator, class T>
357
- ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
358
- const T& value);
359
- template<class ForwardIterator, class T, class Compare>
360
- ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
361
- const T& value, Compare comp);
362
-
363
- template<class ForwardIterator, class T>
364
- ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
365
- const T& value);
366
- template<class ForwardIterator, class T, class Compare>
367
- ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
368
- const T& value, Compare comp);
369
-
370
- template<class ForwardIterator, class T>
371
- pair<ForwardIterator, ForwardIterator>
372
- equal_range(ForwardIterator first, ForwardIterator last,
373
- const T& value);
374
- template<class ForwardIterator, class T, class Compare>
375
- pair<ForwardIterator, ForwardIterator>
376
- equal_range(ForwardIterator first, ForwardIterator last,
377
- const T& value, Compare comp);
378
-
379
- template<class ForwardIterator, class T>
380
- bool binary_search(ForwardIterator first, ForwardIterator last,
381
- const T& value);
382
- template<class ForwardIterator, class T, class Compare>
383
- bool binary_search(ForwardIterator first, ForwardIterator last,
384
- const T& value, Compare comp);
385
-
386
- // [alg.merge], merge:
387
- template<class InputIterator1, class InputIterator2, class OutputIterator>
388
- OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
389
- InputIterator2 first2, InputIterator2 last2,
390
- OutputIterator result);
391
- template<class InputIterator1, class InputIterator2, class OutputIterator,
392
- class Compare>
393
- OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
394
- InputIterator2 first2, InputIterator2 last2,
395
- OutputIterator result, Compare comp);
396
-
397
- template<class BidirectionalIterator>
398
- void inplace_merge(BidirectionalIterator first,
399
- BidirectionalIterator middle,
400
- BidirectionalIterator last);
401
- template<class BidirectionalIterator, class Compare>
402
- void inplace_merge(BidirectionalIterator first,
403
- BidirectionalIterator middle,
404
- BidirectionalIterator last, Compare comp);
405
-
406
- // [alg.set.operations], set operations:
407
- template<class InputIterator1, class InputIterator2>
408
- bool includes(InputIterator1 first1, InputIterator1 last1,
409
- InputIterator2 first2, InputIterator2 last2);
410
- template<class InputIterator1, class InputIterator2, class Compare>
411
- bool includes(
412
- InputIterator1 first1, InputIterator1 last1,
413
- InputIterator2 first2, InputIterator2 last2, Compare comp);
414
-
415
- template<class InputIterator1, class InputIterator2, class OutputIterator>
416
- OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
417
- InputIterator2 first2, InputIterator2 last2,
418
- OutputIterator result);
419
- template<class InputIterator1, class InputIterator2, class OutputIterator,
420
- class Compare>
421
- OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
422
- InputIterator2 first2, InputIterator2 last2,
423
- OutputIterator result, Compare comp);
424
-
425
- template<class InputIterator1, class InputIterator2, class OutputIterator>
426
- OutputIterator set_intersection(
427
- InputIterator1 first1, InputIterator1 last1,
428
- InputIterator2 first2, InputIterator2 last2,
429
- OutputIterator result);
430
- template<class InputIterator1, class InputIterator2, class OutputIterator,
431
- class Compare>
432
- OutputIterator set_intersection(
433
- InputIterator1 first1, InputIterator1 last1,
434
- InputIterator2 first2, InputIterator2 last2,
435
- OutputIterator result, Compare comp);
436
-
437
- template<class InputIterator1, class InputIterator2, class OutputIterator>
438
- OutputIterator set_difference(
439
- InputIterator1 first1, InputIterator1 last1,
440
- InputIterator2 first2, InputIterator2 last2,
441
- OutputIterator result);
442
- template<class InputIterator1, class InputIterator2, class OutputIterator,
443
- class Compare>
444
- OutputIterator set_difference(
445
- InputIterator1 first1, InputIterator1 last1,
446
- InputIterator2 first2, InputIterator2 last2,
447
- OutputIterator result, Compare comp);
448
-
449
- template<class InputIterator1, class InputIterator2, class OutputIterator>
450
- OutputIterator set_symmetric_difference(
451
- InputIterator1 first1, InputIterator1 last1,
452
- InputIterator2 first2, InputIterator2 last2,
453
- OutputIterator result);
454
- template<class InputIterator1, class InputIterator2, class OutputIterator,
455
- class Compare>
456
- OutputIterator set_symmetric_difference(
457
- InputIterator1 first1, InputIterator1 last1,
458
- InputIterator2 first2, InputIterator2 last2,
459
- OutputIterator result, Compare comp);
460
-
461
- // [alg.heap.operations], heap operations:
462
- template<class RandomAccessIterator>
463
- void push_heap(RandomAccessIterator first, RandomAccessIterator last);
464
- template<class RandomAccessIterator, class Compare>
465
- void push_heap(RandomAccessIterator first, RandomAccessIterator last,
466
- Compare comp);
467
-
468
- template<class RandomAccessIterator>
469
- void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
470
- template<class RandomAccessIterator, class Compare>
471
- void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
472
- Compare comp);
473
-
474
- template<class RandomAccessIterator>
475
- void make_heap(RandomAccessIterator first, RandomAccessIterator last);
476
- template<class RandomAccessIterator, class Compare>
477
- void make_heap(RandomAccessIterator first, RandomAccessIterator last,
478
- Compare comp);
479
-
480
- template<class RandomAccessIterator>
481
- void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
482
- template<class RandomAccessIterator, class Compare>
483
- void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
484
- Compare comp);
485
-
486
- template<class RandomAccessIterator>
487
- bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
488
- template<class RandomAccessIterator, class Compare>
489
- bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
490
- template<class RandomAccessIterator>
491
- RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
492
- template<class RandomAccessIterator, class Compare>
493
- RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
494
- Compare comp);
495
-
496
- // [alg.min.max], minimum and maximum:
497
- template<class T> constexpr const T& min(const T& a, const T& b);
498
- template<class T, class Compare>
499
- constexpr const T& min(const T& a, const T& b, Compare comp);
500
- template<class T>
501
- constexpr T min(initializer_list<T> t);
502
- template<class T, class Compare>
503
- constexpr T min(initializer_list<T> t, Compare comp);
504
-
505
- template<class T> constexpr const T& max(const T& a, const T& b);
506
- template<class T, class Compare>
507
- constexpr const T& max(const T& a, const T& b, Compare comp);
508
- template<class T>
509
- constexpr T max(initializer_list<T> t);
510
- template<class T, class Compare>
511
- constexpr T max(initializer_list<T> t, Compare comp);
512
-
513
- template<class T> constexpr pair<const T&, const T&> minmax(const T& a, const T& b);
514
- template<class T, class Compare>
515
- constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
516
- template<class T>
517
- constexpr pair<T, T> minmax(initializer_list<T> t);
518
- template<class T, class Compare>
519
- constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
520
-
521
- template<class ForwardIterator>
522
- ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
523
- template<class ForwardIterator, class Compare>
524
- ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
525
- Compare comp);
526
- template<class ForwardIterator>
527
- ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
528
- template<class ForwardIterator, class Compare>
529
- ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
530
- Compare comp);
531
- template<class ForwardIterator>
532
- pair<ForwardIterator, ForwardIterator>
533
- minmax_element(ForwardIterator first, ForwardIterator last);
534
- template<class ForwardIterator, class Compare>
535
- pair<ForwardIterator, ForwardIterator>
536
- minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
537
-
538
- template<class InputIterator1, class InputIterator2>
539
- bool lexicographical_compare(
540
- InputIterator1 first1, InputIterator1 last1,
541
- InputIterator2 first2, InputIterator2 last2);
542
- template<class InputIterator1, class InputIterator2, class Compare>
543
- bool lexicographical_compare(
544
- InputIterator1 first1, InputIterator1 last1,
545
- InputIterator2 first2, InputIterator2 last2,
546
- Compare comp);
547
-
548
- // [alg.permutation.generators], permutations:
549
- template<class BidirectionalIterator>
550
- bool next_permutation(BidirectionalIterator first,
551
- BidirectionalIterator last);
552
- template<class BidirectionalIterator, class Compare>
553
- bool next_permutation(BidirectionalIterator first,
554
- BidirectionalIterator last, Compare comp);
555
- template<class BidirectionalIterator>
556
- bool prev_permutation(BidirectionalIterator first,
557
- BidirectionalIterator last);
558
- template<class BidirectionalIterator, class Compare>
559
- bool prev_permutation(BidirectionalIterator first,
560
- BidirectionalIterator last, Compare comp);
561
- }
562
- ```
563
-
564
- All of the algorithms are separated from the particular implementations
565
- of data structures and are parameterized by iterator types. Because of
566
- this, they can work with program-defined data structures, as long as
567
- these data structures have iterator types satisfying the assumptions on
568
- the algorithms.
569
-
570
- For purposes of determining the existence of data races, algorithms
571
- shall not modify objects referenced through an iterator argument unless
572
- the specification requires such modification.
573
-
574
- Throughout this Clause, the names of template parameters are used to
575
- express type requirements.
576
-
577
- - If an algorithm’s template parameter is named `InputIterator`,
578
- `InputIterator1`, or `InputIterator2`, the template argument shall
579
- satisfy the requirements of an input iterator ([[input.iterators]]).
580
- - If an algorithm’s template parameter is named `OutputIterator`,
581
- `OutputIterator1`, or `OutputIterator2`, the template argument shall
582
- satisfy the requirements of an output iterator (
583
- [[output.iterators]]).
584
- - If an algorithm’s template parameter is named `ForwardIterator`,
585
- `ForwardIterator1`, or `ForwardIterator2`, the template argument shall
586
- satisfy the requirements of a forward iterator (
587
- [[forward.iterators]]).
588
- - If an algorithm’s template parameter is named `BidirectionalIterator`,
589
- `BidirectionalIterator1`, or `BidirectionalIterator2`, the template
590
- argument shall satisfy the requirements of a bidirectional iterator (
591
- [[bidirectional.iterators]]).
592
- - If an algorithm’s template parameter is named `RandomAccessIterator`,
593
- `RandomAccessIterator1`, or `RandomAccessIterator2`, the template
594
- argument shall satisfy the requirements of a random-access iterator (
595
- [[random.access.iterators]]).
596
-
597
- If an algorithm’s section says that a value pointed to by any iterator
598
- passed as an argument is modified, then that algorithm has an additional
599
- type requirement: The type of that argument shall satisfy the
600
- requirements of a mutable iterator ([[iterator.requirements]]). This
601
- requirement does not affect arguments that are named `OutputIterator`,
602
- `OutputIterator1`, or `OutputIterator2`, because output iterators must
603
- always be mutable.
604
-
605
- Both in-place and copying versions are provided for certain
606
- algorithms.[^1] When such a version is provided for *algorithm* it is
607
- called *algorithm`_copy`*. Algorithms that take predicates end with the
608
- suffix `_if` (which follows the suffix `_copy`).
609
-
610
- The `Predicate` parameter is used whenever an algorithm expects a
611
- function object ([[function.objects]]) that, when applied to the result
612
- of dereferencing the corresponding iterator, returns a value testable as
613
- `true`. In other words, if an algorithm takes `Predicate pred` as its
614
- argument and `first` as its iterator argument, it should work correctly
615
- in the construct `pred(*first)` contextually converted to `bool`
616
- (Clause  [[conv]]). The function object `pred` shall not apply any
617
- non-constant function through the dereferenced iterator.
618
-
619
- The `BinaryPredicate` parameter is used whenever an algorithm expects a
620
- function object that when applied to the result of dereferencing two
621
- corresponding iterators or to dereferencing an iterator and type `T`
622
- when `T` is part of the signature returns a value testable as `true`. In
623
- other words, if an algorithm takes `BinaryPredicate binary_pred` as its
624
- argument and `first1` and `first2` as its iterator arguments, it should
625
- work correctly in the construct `binary_pred(*first1, *first2)`
626
- contextually converted to `bool` (Clause  [[conv]]). `BinaryPredicate`
627
- always takes the first iterator’s `value_type` as its first argument,
628
- that is, in those cases when `T value` is part of the signature, it
629
- should work correctly in the construct `binary_pred(*first1, value)`
630
- contextually converted to `bool` (Clause  [[conv]]). `binary_pred` shall
631
- not apply any non-constant function through the dereferenced iterators.
632
-
633
- Unless otherwise specified, algorithms that take function objects as
634
- arguments are permitted to copy those function objects freely.
635
- Programmers for whom object identity is important should consider using
636
- a wrapper class that points to a noncopied implementation object such as
637
- `reference_wrapper<T>` ([[refwrap]]), or some equivalent solution.
638
-
639
- When the description of an algorithm gives an expression such as
640
- `*first == value` for a condition, the expression shall evaluate to
641
- either true or false in boolean contexts.
642
-
643
- In the description of the algorithms operators `+` and `-` are used for
644
- some of the iterator categories for which they do not have to be
645
- defined. In these cases the semantics of `a+n` is the same as that of
646
-
647
- ``` cpp
648
- X tmp = a;
649
- advance(tmp, n);
650
- return tmp;
651
- ```
652
-
653
- and that of `b-a` is the same as of
654
-
655
- ``` cpp
656
- return distance(a, b);
657
- ```
658
 
 
3
  This Clause describes components that C++programs may use to perform
4
  algorithmic operations on containers (Clause  [[containers]]) and other
5
  sequences.
6
 
7
  The following subclauses describe components for non-modifying sequence
8
+ operations, modifying sequence operations, sorting and related
9
  operations, and algorithms from the ISO C library, as summarized in
10
  Table  [[tab:algorithms.summary]].
11
 
12
  **Table: Algorithms library summary** <a id="tab:algorithms.summary">[tab:algorithms.summary]</a>
13
 
 
16
  | [[alg.nonmodifying]] | Non-modifying sequence operations | |
17
  | [[alg.modifying.operations]] | Mutating sequence operations | `<algorithm>` |
18
  | [[alg.sorting]] | Sorting and related operations | |
19
  | [[alg.c.library]] | C library algorithms | `<cstdlib>` |
20
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
21