xref: /freebsd/contrib/llvm-project/libcxx/include/algorithm (revision 04eeddc0aa8e0a417a16eaf9d7d095207f4a8623)
1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_ALGORITHM
11#define _LIBCPP_ALGORITHM
12
13/*
14    algorithm synopsis
15
16#include <initializer_list>
17
18namespace std
19{
20
21namespace ranges {
22  template <class I1, class I2>
23    struct in_in_result; // since C++20
24}
25
26template <class InputIterator, class Predicate>
27    constexpr bool     // constexpr in C++20
28    all_of(InputIterator first, InputIterator last, Predicate pred);
29
30template <class InputIterator, class Predicate>
31    constexpr bool     // constexpr in C++20
32    any_of(InputIterator first, InputIterator last, Predicate pred);
33
34template <class InputIterator, class Predicate>
35    constexpr bool     // constexpr in C++20
36    none_of(InputIterator first, InputIterator last, Predicate pred);
37
38template <class InputIterator, class Function>
39    constexpr Function          // constexpr in C++20
40    for_each(InputIterator first, InputIterator last, Function f);
41
42template<class InputIterator, class Size, class Function>
43    constexpr InputIterator     // constexpr in C++20
44    for_each_n(InputIterator first, Size n, Function f); // C++17
45
46template <class InputIterator, class T>
47    constexpr InputIterator     // constexpr in C++20
48    find(InputIterator first, InputIterator last, const T& value);
49
50template <class InputIterator, class Predicate>
51    constexpr InputIterator     // constexpr in C++20
52    find_if(InputIterator first, InputIterator last, Predicate pred);
53
54template<class InputIterator, class Predicate>
55    constexpr InputIterator     // constexpr in C++20
56    find_if_not(InputIterator first, InputIterator last, Predicate pred);
57
58template <class ForwardIterator1, class ForwardIterator2>
59    constexpr ForwardIterator1  // constexpr in C++20
60    find_end(ForwardIterator1 first1, ForwardIterator1 last1,
61             ForwardIterator2 first2, ForwardIterator2 last2);
62
63template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
64    constexpr ForwardIterator1  // constexpr in C++20
65    find_end(ForwardIterator1 first1, ForwardIterator1 last1,
66             ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
67
68template <class ForwardIterator1, class ForwardIterator2>
69    constexpr ForwardIterator1  // constexpr in C++20
70    find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
71                  ForwardIterator2 first2, ForwardIterator2 last2);
72
73template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
74    constexpr ForwardIterator1  // constexpr in C++20
75    find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
76                  ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
77
78template <class ForwardIterator>
79    constexpr ForwardIterator   // constexpr in C++20
80    adjacent_find(ForwardIterator first, ForwardIterator last);
81
82template <class ForwardIterator, class BinaryPredicate>
83    constexpr ForwardIterator   // constexpr in C++20
84    adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
85
86template <class InputIterator, class T>
87    constexpr typename iterator_traits<InputIterator>::difference_type  // constexpr in C++20
88    count(InputIterator first, InputIterator last, const T& value);
89
90template <class InputIterator, class Predicate>
91    constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20
92    count_if(InputIterator first, InputIterator last, Predicate pred);
93
94template <class InputIterator1, class InputIterator2>
95    constexpr pair<InputIterator1, InputIterator2>   // constexpr in C++20
96    mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
97
98template <class InputIterator1, class InputIterator2>
99    constexpr pair<InputIterator1, InputIterator2>   // constexpr in C++20
100    mismatch(InputIterator1 first1, InputIterator1 last1,
101             InputIterator2 first2, InputIterator2 last2); // **C++14**
102
103template <class InputIterator1, class InputIterator2, class BinaryPredicate>
104    constexpr pair<InputIterator1, InputIterator2>   // constexpr in C++20
105    mismatch(InputIterator1 first1, InputIterator1 last1,
106             InputIterator2 first2, BinaryPredicate pred);
107
108template <class InputIterator1, class InputIterator2, class BinaryPredicate>
109    constexpr pair<InputIterator1, InputIterator2>   // constexpr in C++20
110    mismatch(InputIterator1 first1, InputIterator1 last1,
111             InputIterator2 first2, InputIterator2 last2,
112             BinaryPredicate pred); // **C++14**
113
114template <class InputIterator1, class InputIterator2>
115    constexpr bool      // constexpr in C++20
116    equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
117
118template <class InputIterator1, class InputIterator2>
119    constexpr bool      // constexpr in C++20
120    equal(InputIterator1 first1, InputIterator1 last1,
121          InputIterator2 first2, InputIterator2 last2); // **C++14**
122
123template <class InputIterator1, class InputIterator2, class BinaryPredicate>
124    constexpr bool      // constexpr in C++20
125    equal(InputIterator1 first1, InputIterator1 last1,
126          InputIterator2 first2, BinaryPredicate pred);
127
128template <class InputIterator1, class InputIterator2, class BinaryPredicate>
129    constexpr bool      // constexpr in C++20
130    equal(InputIterator1 first1, InputIterator1 last1,
131          InputIterator2 first2, InputIterator2 last2,
132          BinaryPredicate pred); // **C++14**
133
134template<class ForwardIterator1, class ForwardIterator2>
135    constexpr bool      // constexpr in C++20
136    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
137                   ForwardIterator2 first2);
138
139template<class ForwardIterator1, class ForwardIterator2>
140    constexpr bool      // constexpr in C++20
141    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
142                   ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**
143
144template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
145    constexpr bool      // constexpr in C++20
146    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
147                   ForwardIterator2 first2, BinaryPredicate pred);
148
149template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
150    constexpr bool      // constexpr in C++20
151    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
152                   ForwardIterator2 first2, ForwardIterator2 last2,
153                   BinaryPredicate pred);  // **C++14**
154
155template <class ForwardIterator1, class ForwardIterator2>
156    constexpr ForwardIterator1      // constexpr in C++20
157    search(ForwardIterator1 first1, ForwardIterator1 last1,
158           ForwardIterator2 first2, ForwardIterator2 last2);
159
160template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
161    constexpr ForwardIterator1      // constexpr in C++20
162    search(ForwardIterator1 first1, ForwardIterator1 last1,
163           ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
164
165template <class ForwardIterator, class Size, class T>
166    constexpr ForwardIterator       // constexpr in C++20
167    search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
168
169template <class ForwardIterator, class Size, class T, class BinaryPredicate>
170    constexpr ForwardIterator       // constexpr in C++20
171    search_n(ForwardIterator first, ForwardIterator last,
172             Size count, const T& value, BinaryPredicate pred);
173
174template <class InputIterator, class OutputIterator>
175    constexpr OutputIterator      // constexpr in C++20
176    copy(InputIterator first, InputIterator last, OutputIterator result);
177
178template<class InputIterator, class OutputIterator, class Predicate>
179    constexpr OutputIterator      // constexpr in C++20
180    copy_if(InputIterator first, InputIterator last,
181            OutputIterator result, Predicate pred);
182
183template<class InputIterator, class Size, class OutputIterator>
184    constexpr OutputIterator      // constexpr in C++20
185    copy_n(InputIterator first, Size n, OutputIterator result);
186
187template <class BidirectionalIterator1, class BidirectionalIterator2>
188    constexpr BidirectionalIterator2      // constexpr in C++20
189    copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
190                  BidirectionalIterator2 result);
191
192template <class ForwardIterator1, class ForwardIterator2>
193    constexpr ForwardIterator2    // constexpr in C++20
194    swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
195
196template <class ForwardIterator1, class ForwardIterator2>
197    constexpr void                // constexpr in C++20
198    iter_swap(ForwardIterator1 a, ForwardIterator2 b);
199
200template <class InputIterator, class OutputIterator, class UnaryOperation>
201    constexpr OutputIterator      // constexpr in C++20
202    transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
203
204template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
205    constexpr OutputIterator      // constexpr in C++20
206    transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
207              OutputIterator result, BinaryOperation binary_op);
208
209template <class ForwardIterator, class T>
210    constexpr void      // constexpr in C++20
211    replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
212
213template <class ForwardIterator, class Predicate, class T>
214    constexpr void      // constexpr in C++20
215    replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
216
217template <class InputIterator, class OutputIterator, class T>
218    constexpr OutputIterator      // constexpr in C++20
219    replace_copy(InputIterator first, InputIterator last, OutputIterator result,
220                 const T& old_value, const T& new_value);
221
222template <class InputIterator, class OutputIterator, class Predicate, class T>
223    constexpr OutputIterator      // constexpr in C++20
224    replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
225
226template <class ForwardIterator, class T>
227    constexpr void      // constexpr in C++20
228    fill(ForwardIterator first, ForwardIterator last, const T& value);
229
230template <class OutputIterator, class Size, class T>
231    constexpr OutputIterator      // constexpr in C++20
232    fill_n(OutputIterator first, Size n, const T& value);
233
234template <class ForwardIterator, class Generator>
235    constexpr void      // constexpr in C++20
236    generate(ForwardIterator first, ForwardIterator last, Generator gen);
237
238template <class OutputIterator, class Size, class Generator>
239    constexpr OutputIterator      // constexpr in C++20
240    generate_n(OutputIterator first, Size n, Generator gen);
241
242template <class ForwardIterator, class T>
243    constexpr ForwardIterator     // constexpr in C++20
244    remove(ForwardIterator first, ForwardIterator last, const T& value);
245
246template <class ForwardIterator, class Predicate>
247    constexpr ForwardIterator     // constexpr in C++20
248    remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
249
250template <class InputIterator, class OutputIterator, class T>
251    constexpr OutputIterator     // constexpr in C++20
252    remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
253
254template <class InputIterator, class OutputIterator, class Predicate>
255    constexpr OutputIterator     // constexpr in C++20
256    remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
257
258template <class ForwardIterator>
259    constexpr ForwardIterator    // constexpr in C++20
260    unique(ForwardIterator first, ForwardIterator last);
261
262template <class ForwardIterator, class BinaryPredicate>
263    constexpr ForwardIterator    // constexpr in C++20
264    unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
265
266template <class InputIterator, class OutputIterator>
267    constexpr OutputIterator     // constexpr in C++20
268    unique_copy(InputIterator first, InputIterator last, OutputIterator result);
269
270template <class InputIterator, class OutputIterator, class BinaryPredicate>
271    constexpr OutputIterator     // constexpr in C++20
272    unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
273
274template <class BidirectionalIterator>
275    constexpr void               // constexpr in C++20
276    reverse(BidirectionalIterator first, BidirectionalIterator last);
277
278template <class BidirectionalIterator, class OutputIterator>
279    constexpr OutputIterator       // constexpr in C++20
280    reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
281
282template <class ForwardIterator>
283    constexpr ForwardIterator      // constexpr in C++20
284    rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
285
286template <class ForwardIterator, class OutputIterator>
287    constexpr OutputIterator       // constexpr in C++20
288    rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
289
290template <class RandomAccessIterator>
291    void
292    random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17
293
294template <class RandomAccessIterator, class RandomNumberGenerator>
295    void
296    random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
297                   RandomNumberGenerator& rand);  // deprecated in C++14, removed in C++17
298
299template<class PopulationIterator, class SampleIterator,
300         class Distance, class UniformRandomBitGenerator>
301    SampleIterator sample(PopulationIterator first, PopulationIterator last,
302                          SampleIterator out, Distance n,
303                          UniformRandomBitGenerator&& g); // C++17
304
305template<class RandomAccessIterator, class UniformRandomNumberGenerator>
306    void shuffle(RandomAccessIterator first, RandomAccessIterator last,
307                 UniformRandomNumberGenerator&& g);
308
309template<class ForwardIterator>
310  constexpr ForwardIterator
311    shift_left(ForwardIterator first, ForwardIterator last,
312               typename iterator_traits<ForwardIterator>::difference_type n); // C++20
313
314template<class ForwardIterator>
315  constexpr ForwardIterator
316    shift_right(ForwardIterator first, ForwardIterator last,
317                typename iterator_traits<ForwardIterator>::difference_type n); // C++20
318
319template <class InputIterator, class Predicate>
320    constexpr bool  // constexpr in C++20
321    is_partitioned(InputIterator first, InputIterator last, Predicate pred);
322
323template <class ForwardIterator, class Predicate>
324    constexpr ForwardIterator  // constexpr in C++20
325    partition(ForwardIterator first, ForwardIterator last, Predicate pred);
326
327template <class InputIterator, class OutputIterator1,
328          class OutputIterator2, class Predicate>
329    constexpr pair<OutputIterator1, OutputIterator2>   // constexpr in C++20
330    partition_copy(InputIterator first, InputIterator last,
331                   OutputIterator1 out_true, OutputIterator2 out_false,
332                   Predicate pred);
333
334template <class ForwardIterator, class Predicate>
335    ForwardIterator
336    stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
337
338template<class ForwardIterator, class Predicate>
339    constexpr ForwardIterator  // constexpr in C++20
340    partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
341
342template <class ForwardIterator>
343    constexpr bool  // constexpr in C++20
344    is_sorted(ForwardIterator first, ForwardIterator last);
345
346template <class ForwardIterator, class Compare>
347    constexpr bool  // constexpr in C++20
348    is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
349
350template<class ForwardIterator>
351    constexpr ForwardIterator    // constexpr in C++20
352    is_sorted_until(ForwardIterator first, ForwardIterator last);
353
354template <class ForwardIterator, class Compare>
355    constexpr ForwardIterator    // constexpr in C++20
356    is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
357
358template <class RandomAccessIterator>
359    constexpr void               // constexpr in C++20
360    sort(RandomAccessIterator first, RandomAccessIterator last);
361
362template <class RandomAccessIterator, class Compare>
363    constexpr void               // constexpr in C++20
364    sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
365
366template <class RandomAccessIterator>
367    void
368    stable_sort(RandomAccessIterator first, RandomAccessIterator last);
369
370template <class RandomAccessIterator, class Compare>
371    void
372    stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
373
374template <class RandomAccessIterator>
375    constexpr void                    // constexpr in C++20
376    partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
377
378template <class RandomAccessIterator, class Compare>
379    constexpr void                    // constexpr in C++20
380    partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
381
382template <class InputIterator, class RandomAccessIterator>
383    constexpr RandomAccessIterator    // constexpr in C++20
384    partial_sort_copy(InputIterator first, InputIterator last,
385                      RandomAccessIterator result_first, RandomAccessIterator result_last);
386
387template <class InputIterator, class RandomAccessIterator, class Compare>
388    constexpr RandomAccessIterator    // constexpr in C++20
389    partial_sort_copy(InputIterator first, InputIterator last,
390                      RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
391
392template <class RandomAccessIterator>
393    constexpr void                    // constexpr in C++20
394    nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
395
396template <class RandomAccessIterator, class Compare>
397    constexpr void                    // constexpr in C++20
398    nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
399
400template <class ForwardIterator, class T>
401    constexpr ForwardIterator                         // constexpr in C++20
402    lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
403
404template <class ForwardIterator, class T, class Compare>
405    constexpr ForwardIterator                         // constexpr in C++20
406    lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
407
408template <class ForwardIterator, class T>
409    constexpr ForwardIterator                         // constexpr in C++20
410    upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
411
412template <class ForwardIterator, class T, class Compare>
413    constexpr ForwardIterator                         // constexpr in C++20
414    upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
415
416template <class ForwardIterator, class T>
417    constexpr pair<ForwardIterator, ForwardIterator>  // constexpr in C++20
418    equal_range(ForwardIterator first, ForwardIterator last, const T& value);
419
420template <class ForwardIterator, class T, class Compare>
421    constexpr pair<ForwardIterator, ForwardIterator>  // constexpr in C++20
422    equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
423
424template <class ForwardIterator, class T>
425    constexpr bool                                    // constexpr in C++20
426    binary_search(ForwardIterator first, ForwardIterator last, const T& value);
427
428template <class ForwardIterator, class T, class Compare>
429    constexpr bool                                    // constexpr in C++20
430    binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
431
432template <class InputIterator1, class InputIterator2, class OutputIterator>
433    constexpr OutputIterator                          // constexpr in C++20
434    merge(InputIterator1 first1, InputIterator1 last1,
435          InputIterator2 first2, InputIterator2 last2, OutputIterator result);
436
437template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
438    constexpr OutputIterator                          // constexpr in C++20
439    merge(InputIterator1 first1, InputIterator1 last1,
440          InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
441
442template <class BidirectionalIterator>
443    void
444    inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
445
446template <class BidirectionalIterator, class Compare>
447    void
448    inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
449
450template <class InputIterator1, class InputIterator2>
451    constexpr bool                                    // constexpr in C++20
452    includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
453
454template <class InputIterator1, class InputIterator2, class Compare>
455    constexpr bool                                    // constexpr in C++20
456    includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
457
458template <class InputIterator1, class InputIterator2, class OutputIterator>
459    constexpr OutputIterator                          // constexpr in C++20
460    set_union(InputIterator1 first1, InputIterator1 last1,
461              InputIterator2 first2, InputIterator2 last2, OutputIterator result);
462
463template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
464    constexpr OutputIterator                          // constexpr in C++20
465    set_union(InputIterator1 first1, InputIterator1 last1,
466              InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
467
468template <class InputIterator1, class InputIterator2, class OutputIterator>
469    constexpr OutputIterator                         // constexpr in C++20
470    set_intersection(InputIterator1 first1, InputIterator1 last1,
471                     InputIterator2 first2, InputIterator2 last2, OutputIterator result);
472
473template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
474    constexpr OutputIterator                         // constexpr in C++20
475    set_intersection(InputIterator1 first1, InputIterator1 last1,
476                     InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
477
478template <class InputIterator1, class InputIterator2, class OutputIterator>
479    constexpr OutputIterator                         // constexpr in C++20
480    set_difference(InputIterator1 first1, InputIterator1 last1,
481                   InputIterator2 first2, InputIterator2 last2, OutputIterator result);
482
483template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
484    constexpr OutputIterator                         // constexpr in C++20
485    set_difference(InputIterator1 first1, InputIterator1 last1,
486                   InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
487
488template <class InputIterator1, class InputIterator2, class OutputIterator>
489    constexpr OutputIterator                         // constexpr in C++20
490    set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
491                             InputIterator2 first2, InputIterator2 last2, OutputIterator result);
492
493template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
494    constexpr OutputIterator                         // constexpr in C++20
495    set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
496                             InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
497
498template <class RandomAccessIterator>
499    constexpr void                                   // constexpr in C++20
500    push_heap(RandomAccessIterator first, RandomAccessIterator last);
501
502template <class RandomAccessIterator, class Compare>
503    constexpr void                                   // constexpr in C++20
504    push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
505
506template <class RandomAccessIterator>
507    constexpr void                                   // constexpr in C++20
508    pop_heap(RandomAccessIterator first, RandomAccessIterator last);
509
510template <class RandomAccessIterator, class Compare>
511    constexpr void                                   // constexpr in C++20
512    pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
513
514template <class RandomAccessIterator>
515    constexpr void                                   // constexpr in C++20
516    make_heap(RandomAccessIterator first, RandomAccessIterator last);
517
518template <class RandomAccessIterator, class Compare>
519    constexpr void                                   // constexpr in C++20
520    make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
521
522template <class RandomAccessIterator>
523    constexpr void                                   // constexpr in C++20
524    sort_heap(RandomAccessIterator first, RandomAccessIterator last);
525
526template <class RandomAccessIterator, class Compare>
527    constexpr void                                   // constexpr in C++20
528    sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
529
530template <class RandomAccessIterator>
531    constexpr bool   // constexpr in C++20
532    is_heap(RandomAccessIterator first, RandomAccessiterator last);
533
534template <class RandomAccessIterator, class Compare>
535    constexpr bool   // constexpr in C++20
536    is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
537
538template <class RandomAccessIterator>
539    constexpr RandomAccessIterator   // constexpr in C++20
540    is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
541
542template <class RandomAccessIterator, class Compare>
543    constexpr RandomAccessIterator   // constexpr in C++20
544    is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
545
546template <class ForwardIterator>
547    constexpr ForwardIterator        // constexpr in C++14
548    min_element(ForwardIterator first, ForwardIterator last);
549
550template <class ForwardIterator, class Compare>
551    constexpr ForwardIterator        // constexpr in C++14
552    min_element(ForwardIterator first, ForwardIterator last, Compare comp);
553
554template <class T>
555    constexpr const T&               // constexpr in C++14
556    min(const T& a, const T& b);
557
558template <class T, class Compare>
559    constexpr const T&               // constexpr in C++14
560    min(const T& a, const T& b, Compare comp);
561
562template<class T>
563    constexpr T                      // constexpr in C++14
564    min(initializer_list<T> t);
565
566template<class T, class Compare>
567    constexpr T                      // constexpr in C++14
568    min(initializer_list<T> t, Compare comp);
569
570template<class T>
571    constexpr const T& clamp(const T& v, const T& lo, const T& hi);               // C++17
572
573template<class T, class Compare>
574    constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp); // C++17
575
576template <class ForwardIterator>
577    constexpr ForwardIterator        // constexpr in C++14
578    max_element(ForwardIterator first, ForwardIterator last);
579
580template <class ForwardIterator, class Compare>
581    constexpr ForwardIterator        // constexpr in C++14
582    max_element(ForwardIterator first, ForwardIterator last, Compare comp);
583
584template <class T>
585    constexpr const T&               // constexpr in C++14
586    max(const T& a, const T& b);
587
588template <class T, class Compare>
589    constexpr const T&               // constexpr in C++14
590    max(const T& a, const T& b, Compare comp);
591
592template<class T>
593    constexpr T                      // constexpr in C++14
594    max(initializer_list<T> t);
595
596template<class T, class Compare>
597    constexpr T                      // constexpr in C++14
598    max(initializer_list<T> t, Compare comp);
599
600template<class ForwardIterator>
601    constexpr pair<ForwardIterator, ForwardIterator>  // constexpr in C++14
602    minmax_element(ForwardIterator first, ForwardIterator last);
603
604template<class ForwardIterator, class Compare>
605    constexpr pair<ForwardIterator, ForwardIterator>  // constexpr in C++14
606    minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
607
608template<class T>
609    constexpr pair<const T&, const T&>  // constexpr in C++14
610    minmax(const T& a, const T& b);
611
612template<class T, class Compare>
613    constexpr pair<const T&, const T&>  // constexpr in C++14
614    minmax(const T& a, const T& b, Compare comp);
615
616template<class T>
617    constexpr pair<T, T>                // constexpr in C++14
618    minmax(initializer_list<T> t);
619
620template<class T, class Compare>
621    constexpr pair<T, T>                // constexpr in C++14
622    minmax(initializer_list<T> t, Compare comp);
623
624template <class InputIterator1, class InputIterator2>
625    constexpr bool     // constexpr in C++20
626    lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
627
628template <class InputIterator1, class InputIterator2, class Compare>
629    constexpr bool     // constexpr in C++20
630    lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
631                            InputIterator2 first2, InputIterator2 last2, Compare comp);
632
633template <class BidirectionalIterator>
634    constexpr bool     // constexpr in C++20
635    next_permutation(BidirectionalIterator first, BidirectionalIterator last);
636
637template <class BidirectionalIterator, class Compare>
638    constexpr bool     // constexpr in C++20
639    next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
640
641template <class BidirectionalIterator>
642    constexpr bool     // constexpr in C++20
643    prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
644
645template <class BidirectionalIterator, class Compare>
646    constexpr bool     // constexpr in C++20
647    prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
648
649namespace ranges {
650// [algorithms.results], algorithm result types
651template<class InputIterator, class OutputIterator>
652    struct in_out_result;
653}
654
655}  // std
656
657*/
658
659#include <__bits> // __libcpp_clz
660#include <__config>
661#include <__debug>
662#include <cstddef>
663#include <cstring>
664#include <functional>
665#include <initializer_list>
666#include <iterator>
667#include <memory>
668#include <type_traits>
669#include <utility> // swap_ranges
670#include <version>
671
672#include <__algorithm/adjacent_find.h>
673#include <__algorithm/all_of.h>
674#include <__algorithm/any_of.h>
675#include <__algorithm/binary_search.h>
676#include <__algorithm/clamp.h>
677#include <__algorithm/comp.h>
678#include <__algorithm/comp_ref_type.h>
679#include <__algorithm/copy.h>
680#include <__algorithm/copy_backward.h>
681#include <__algorithm/copy_if.h>
682#include <__algorithm/copy_n.h>
683#include <__algorithm/count.h>
684#include <__algorithm/count_if.h>
685#include <__algorithm/equal.h>
686#include <__algorithm/equal_range.h>
687#include <__algorithm/fill.h>
688#include <__algorithm/fill_n.h>
689#include <__algorithm/find.h>
690#include <__algorithm/find_end.h>
691#include <__algorithm/find_first_of.h>
692#include <__algorithm/find_if.h>
693#include <__algorithm/find_if_not.h>
694#include <__algorithm/for_each.h>
695#include <__algorithm/for_each_n.h>
696#include <__algorithm/generate.h>
697#include <__algorithm/generate_n.h>
698#include <__algorithm/half_positive.h>
699#include <__algorithm/in_in_result.h>
700#include <__algorithm/in_out_result.h>
701#include <__algorithm/includes.h>
702#include <__algorithm/inplace_merge.h>
703#include <__algorithm/is_heap.h>
704#include <__algorithm/is_heap_until.h>
705#include <__algorithm/is_partitioned.h>
706#include <__algorithm/is_permutation.h>
707#include <__algorithm/is_sorted.h>
708#include <__algorithm/is_sorted_until.h>
709#include <__algorithm/iter_swap.h>
710#include <__algorithm/lexicographical_compare.h>
711#include <__algorithm/lower_bound.h>
712#include <__algorithm/make_heap.h>
713#include <__algorithm/max.h>
714#include <__algorithm/max_element.h>
715#include <__algorithm/merge.h>
716#include <__algorithm/min.h>
717#include <__algorithm/min_element.h>
718#include <__algorithm/minmax.h>
719#include <__algorithm/minmax_element.h>
720#include <__algorithm/mismatch.h>
721#include <__algorithm/move.h>
722#include <__algorithm/move_backward.h>
723#include <__algorithm/next_permutation.h>
724#include <__algorithm/none_of.h>
725#include <__algorithm/nth_element.h>
726#include <__algorithm/partial_sort.h>
727#include <__algorithm/partial_sort_copy.h>
728#include <__algorithm/partition.h>
729#include <__algorithm/partition_copy.h>
730#include <__algorithm/partition_point.h>
731#include <__algorithm/pop_heap.h>
732#include <__algorithm/prev_permutation.h>
733#include <__algorithm/push_heap.h>
734#include <__algorithm/remove.h>
735#include <__algorithm/remove_copy.h>
736#include <__algorithm/remove_copy_if.h>
737#include <__algorithm/remove_if.h>
738#include <__algorithm/replace.h>
739#include <__algorithm/replace_copy.h>
740#include <__algorithm/replace_copy_if.h>
741#include <__algorithm/replace_if.h>
742#include <__algorithm/reverse.h>
743#include <__algorithm/reverse_copy.h>
744#include <__algorithm/rotate.h>
745#include <__algorithm/rotate_copy.h>
746#include <__algorithm/sample.h>
747#include <__algorithm/search.h>
748#include <__algorithm/search_n.h>
749#include <__algorithm/set_difference.h>
750#include <__algorithm/set_intersection.h>
751#include <__algorithm/set_symmetric_difference.h>
752#include <__algorithm/set_union.h>
753#include <__algorithm/shift_left.h>
754#include <__algorithm/shift_right.h>
755#include <__algorithm/shuffle.h>
756#include <__algorithm/sift_down.h>
757#include <__algorithm/sort.h>
758#include <__algorithm/sort_heap.h>
759#include <__algorithm/stable_partition.h>
760#include <__algorithm/stable_sort.h>
761#include <__algorithm/swap_ranges.h>
762#include <__algorithm/transform.h>
763#include <__algorithm/unique.h>
764#include <__algorithm/unique_copy.h>
765#include <__algorithm/unwrap_iter.h>
766#include <__algorithm/upper_bound.h>
767
768#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
769#pragma GCC system_header
770#endif
771
772#if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
773#   include <__pstl_algorithm>
774#endif
775
776#endif // _LIBCPP_ALGORITHM
777