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