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