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
21template <class InputIterator, class Predicate>
22    constexpr bool     // constexpr in C++20
23    all_of(InputIterator first, InputIterator last, Predicate pred);
24
25template <class InputIterator, class Predicate>
26    constexpr bool     // constexpr in C++20
27    any_of(InputIterator first, InputIterator last, Predicate pred);
28
29template <class InputIterator, class Predicate>
30    constexpr bool     // constexpr in C++20
31    none_of(InputIterator first, InputIterator last, Predicate pred);
32
33template <class InputIterator, class Function>
34    constexpr Function          // constexpr in C++20
35    for_each(InputIterator first, InputIterator last, Function f);
36
37template<class InputIterator, class Size, class Function>
38    constexpr InputIterator     // constexpr in C++20
39    for_each_n(InputIterator first, Size n, Function f); // C++17
40
41template <class InputIterator, class T>
42    constexpr InputIterator     // constexpr in C++20
43    find(InputIterator first, InputIterator last, const T& value);
44
45template <class InputIterator, class Predicate>
46    constexpr InputIterator     // constexpr in C++20
47    find_if(InputIterator first, InputIterator last, Predicate pred);
48
49template<class InputIterator, class Predicate>
50    constexpr InputIterator     // constexpr in C++20
51    find_if_not(InputIterator first, InputIterator last, Predicate pred);
52
53template <class ForwardIterator1, class ForwardIterator2>
54    constexpr ForwardIterator1  // constexpr in C++20
55    find_end(ForwardIterator1 first1, ForwardIterator1 last1,
56             ForwardIterator2 first2, ForwardIterator2 last2);
57
58template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
59    constexpr ForwardIterator1  // constexpr in C++20
60    find_end(ForwardIterator1 first1, ForwardIterator1 last1,
61             ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
62
63template <class ForwardIterator1, class ForwardIterator2>
64    constexpr ForwardIterator1  // constexpr in C++20
65    find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
66                  ForwardIterator2 first2, ForwardIterator2 last2);
67
68template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
69    constexpr ForwardIterator1  // constexpr in C++20
70    find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
71                  ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
72
73template <class ForwardIterator>
74    constexpr ForwardIterator   // constexpr in C++20
75    adjacent_find(ForwardIterator first, ForwardIterator last);
76
77template <class ForwardIterator, class BinaryPredicate>
78    constexpr ForwardIterator   // constexpr in C++20
79    adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
80
81template <class InputIterator, class T>
82    constexpr typename iterator_traits<InputIterator>::difference_type  // constexpr in C++20
83    count(InputIterator first, InputIterator last, const T& value);
84
85template <class InputIterator, class Predicate>
86    constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20
87    count_if(InputIterator first, InputIterator last, Predicate pred);
88
89template <class InputIterator1, class InputIterator2>
90    constexpr pair<InputIterator1, InputIterator2>   // constexpr in C++20
91    mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
92
93template <class InputIterator1, class InputIterator2>
94    constexpr pair<InputIterator1, InputIterator2>   // constexpr in C++20
95    mismatch(InputIterator1 first1, InputIterator1 last1,
96             InputIterator2 first2, InputIterator2 last2); // **C++14**
97
98template <class InputIterator1, class InputIterator2, class BinaryPredicate>
99    constexpr pair<InputIterator1, InputIterator2>   // constexpr in C++20
100    mismatch(InputIterator1 first1, InputIterator1 last1,
101             InputIterator2 first2, BinaryPredicate pred);
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, InputIterator2 last2,
107             BinaryPredicate pred); // **C++14**
108
109template <class InputIterator1, class InputIterator2>
110    constexpr bool      // constexpr in C++20
111    equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
112
113template <class InputIterator1, class InputIterator2>
114    constexpr bool      // constexpr in C++20
115    equal(InputIterator1 first1, InputIterator1 last1,
116          InputIterator2 first2, InputIterator2 last2); // **C++14**
117
118template <class InputIterator1, class InputIterator2, class BinaryPredicate>
119    constexpr bool      // constexpr in C++20
120    equal(InputIterator1 first1, InputIterator1 last1,
121          InputIterator2 first2, BinaryPredicate pred);
122
123template <class InputIterator1, class InputIterator2, class BinaryPredicate>
124    constexpr bool      // constexpr in C++20
125    equal(InputIterator1 first1, InputIterator1 last1,
126          InputIterator2 first2, InputIterator2 last2,
127          BinaryPredicate pred); // **C++14**
128
129template<class ForwardIterator1, class ForwardIterator2>
130    constexpr bool      // constexpr in C++20
131    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
132                   ForwardIterator2 first2);
133
134template<class ForwardIterator1, class ForwardIterator2>
135    constexpr bool      // constexpr in C++20
136    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
137                   ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**
138
139template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
140    constexpr bool      // constexpr in C++20
141    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
142                   ForwardIterator2 first2, BinaryPredicate pred);
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, ForwardIterator2 last2,
148                   BinaryPredicate pred);  // **C++14**
149
150template <class ForwardIterator1, class ForwardIterator2>
151    constexpr ForwardIterator1      // constexpr in C++20
152    search(ForwardIterator1 first1, ForwardIterator1 last1,
153           ForwardIterator2 first2, ForwardIterator2 last2);
154
155template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
156    constexpr ForwardIterator1      // constexpr in C++20
157    search(ForwardIterator1 first1, ForwardIterator1 last1,
158           ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
159
160template <class ForwardIterator, class Size, class T>
161    constexpr ForwardIterator       // constexpr in C++20
162    search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
163
164template <class ForwardIterator, class Size, class T, class BinaryPredicate>
165    constexpr ForwardIterator       // constexpr in C++20
166    search_n(ForwardIterator first, ForwardIterator last,
167             Size count, const T& value, BinaryPredicate pred);
168
169template <class InputIterator, class OutputIterator>
170    constexpr OutputIterator      // constexpr in C++20
171    copy(InputIterator first, InputIterator last, OutputIterator result);
172
173template<class InputIterator, class OutputIterator, class Predicate>
174    constexpr OutputIterator      // constexpr in C++20
175    copy_if(InputIterator first, InputIterator last,
176            OutputIterator result, Predicate pred);
177
178template<class InputIterator, class Size, class OutputIterator>
179    constexpr OutputIterator      // constexpr in C++20
180    copy_n(InputIterator first, Size n, OutputIterator result);
181
182template <class BidirectionalIterator1, class BidirectionalIterator2>
183    constexpr BidirectionalIterator2      // constexpr in C++20
184    copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
185                  BidirectionalIterator2 result);
186
187template <class ForwardIterator1, class ForwardIterator2>
188    constexpr ForwardIterator2    // constexpr in C++20
189    swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
190
191template <class ForwardIterator1, class ForwardIterator2>
192    constexpr void                // constexpr in C++20
193    iter_swap(ForwardIterator1 a, ForwardIterator2 b);
194
195template <class InputIterator, class OutputIterator, class UnaryOperation>
196    constexpr OutputIterator      // constexpr in C++20
197    transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
198
199template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
200    constexpr OutputIterator      // constexpr in C++20
201    transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
202              OutputIterator result, BinaryOperation binary_op);
203
204template <class ForwardIterator, class T>
205    constexpr void      // constexpr in C++20
206    replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
207
208template <class ForwardIterator, class Predicate, class T>
209    constexpr void      // constexpr in C++20
210    replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
211
212template <class InputIterator, class OutputIterator, class T>
213    constexpr OutputIterator      // constexpr in C++20
214    replace_copy(InputIterator first, InputIterator last, OutputIterator result,
215                 const T& old_value, const T& new_value);
216
217template <class InputIterator, class OutputIterator, class Predicate, class T>
218    constexpr OutputIterator      // constexpr in C++20
219    replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
220
221template <class ForwardIterator, class T>
222    constexpr void      // constexpr in C++20
223    fill(ForwardIterator first, ForwardIterator last, const T& value);
224
225template <class OutputIterator, class Size, class T>
226    constexpr OutputIterator      // constexpr in C++20
227    fill_n(OutputIterator first, Size n, const T& value);
228
229template <class ForwardIterator, class Generator>
230    constexpr void      // constexpr in C++20
231    generate(ForwardIterator first, ForwardIterator last, Generator gen);
232
233template <class OutputIterator, class Size, class Generator>
234    constexpr OutputIterator      // constexpr in C++20
235    generate_n(OutputIterator first, Size n, Generator gen);
236
237template <class ForwardIterator, class T>
238    constexpr ForwardIterator     // constexpr in C++20
239    remove(ForwardIterator first, ForwardIterator last, const T& value);
240
241template <class ForwardIterator, class Predicate>
242    constexpr ForwardIterator     // constexpr in C++20
243    remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
244
245template <class InputIterator, class OutputIterator, class T>
246    constexpr OutputIterator     // constexpr in C++20
247    remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
248
249template <class InputIterator, class OutputIterator, class Predicate>
250    constexpr OutputIterator     // constexpr in C++20
251    remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
252
253template <class ForwardIterator>
254    constexpr ForwardIterator    // constexpr in C++20
255    unique(ForwardIterator first, ForwardIterator last);
256
257template <class ForwardIterator, class BinaryPredicate>
258    constexpr ForwardIterator    // constexpr in C++20
259    unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
260
261template <class InputIterator, class OutputIterator>
262    constexpr OutputIterator     // constexpr in C++20
263    unique_copy(InputIterator first, InputIterator last, OutputIterator result);
264
265template <class InputIterator, class OutputIterator, class BinaryPredicate>
266    constexpr OutputIterator     // constexpr in C++20
267    unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
268
269template <class BidirectionalIterator>
270    void
271    reverse(BidirectionalIterator first, BidirectionalIterator last);
272
273template <class BidirectionalIterator, class OutputIterator>
274    constexpr OutputIterator       // constexpr in C++20
275    reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
276
277template <class ForwardIterator>
278    constexpr ForwardIterator      // constexpr in C++20
279    rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
280
281template <class ForwardIterator, class OutputIterator>
282    constexpr OutputIterator       // constexpr in C++20
283    rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
284
285template <class RandomAccessIterator>
286    void
287    random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17
288
289template <class RandomAccessIterator, class RandomNumberGenerator>
290    void
291    random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
292                   RandomNumberGenerator& rand);  // deprecated in C++14, removed in C++17
293
294template<class PopulationIterator, class SampleIterator,
295         class Distance, class UniformRandomBitGenerator>
296    SampleIterator sample(PopulationIterator first, PopulationIterator last,
297                          SampleIterator out, Distance n,
298                          UniformRandomBitGenerator&& g); // C++17
299
300template<class RandomAccessIterator, class UniformRandomNumberGenerator>
301    void shuffle(RandomAccessIterator first, RandomAccessIterator last,
302                 UniformRandomNumberGenerator&& g);
303
304template <class InputIterator, class Predicate>
305    constexpr bool  // constexpr in C++20
306    is_partitioned(InputIterator first, InputIterator last, Predicate pred);
307
308template <class ForwardIterator, class Predicate>
309    ForwardIterator
310    partition(ForwardIterator first, ForwardIterator last, Predicate pred);
311
312template <class InputIterator, class OutputIterator1,
313          class OutputIterator2, class Predicate>
314    constexpr pair<OutputIterator1, OutputIterator2>   // constexpr in C++20
315    partition_copy(InputIterator first, InputIterator last,
316                   OutputIterator1 out_true, OutputIterator2 out_false,
317                   Predicate pred);
318
319template <class ForwardIterator, class Predicate>
320    ForwardIterator
321    stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
322
323template<class ForwardIterator, class Predicate>
324    constexpr ForwardIterator  // constexpr in C++20
325    partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
326
327template <class ForwardIterator>
328    constexpr bool  // constexpr in C++20
329    is_sorted(ForwardIterator first, ForwardIterator last);
330
331template <class ForwardIterator, class Compare>
332    constexpr bool  // constexpr in C++20
333    is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
334
335template<class ForwardIterator>
336    constexpr ForwardIterator    // constexpr in C++20
337    is_sorted_until(ForwardIterator first, ForwardIterator last);
338
339template <class ForwardIterator, class Compare>
340    constexpr ForwardIterator    // constexpr in C++20
341    is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
342
343template <class RandomAccessIterator>
344    void
345    sort(RandomAccessIterator first, RandomAccessIterator last);
346
347template <class RandomAccessIterator, class Compare>
348    void
349    sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
350
351template <class RandomAccessIterator>
352    void
353    stable_sort(RandomAccessIterator first, RandomAccessIterator last);
354
355template <class RandomAccessIterator, class Compare>
356    void
357    stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
358
359template <class RandomAccessIterator>
360    void
361    partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
362
363template <class RandomAccessIterator, class Compare>
364    void
365    partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
366
367template <class InputIterator, class RandomAccessIterator>
368    RandomAccessIterator
369    partial_sort_copy(InputIterator first, InputIterator last,
370                      RandomAccessIterator result_first, RandomAccessIterator result_last);
371
372template <class InputIterator, class RandomAccessIterator, class Compare>
373    RandomAccessIterator
374    partial_sort_copy(InputIterator first, InputIterator last,
375                      RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
376
377template <class RandomAccessIterator>
378    void
379    nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
380
381template <class RandomAccessIterator, class Compare>
382    void
383    nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
384
385template <class ForwardIterator, class T>
386    constexpr ForwardIterator                         // constexpr in C++20
387    lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
388
389template <class ForwardIterator, class T, class Compare>
390    constexpr ForwardIterator                         // constexpr in C++20
391    lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
392
393template <class ForwardIterator, class T>
394    constexpr ForwardIterator                         // constexpr in C++20
395    upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
396
397template <class ForwardIterator, class T, class Compare>
398    constexpr ForwardIterator                         // constexpr in C++20
399    upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
400
401template <class ForwardIterator, class T>
402    constexpr pair<ForwardIterator, ForwardIterator>  // constexpr in C++20
403    equal_range(ForwardIterator first, ForwardIterator last, const T& value);
404
405template <class ForwardIterator, class T, class Compare>
406    constexpr pair<ForwardIterator, ForwardIterator>  // constexpr in C++20
407    equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
408
409template <class ForwardIterator, class T>
410    constexpr bool                                    // constexpr in C++20
411    binary_search(ForwardIterator first, ForwardIterator last, const T& value);
412
413template <class ForwardIterator, class T, class Compare>
414    constexpr bool                                    // constexpr in C++20
415    binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
416
417template <class InputIterator1, class InputIterator2, class OutputIterator>
418    constexpr OutputIterator                          // constexpr in C++20
419    merge(InputIterator1 first1, InputIterator1 last1,
420          InputIterator2 first2, InputIterator2 last2, OutputIterator result);
421
422template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
423    constexpr OutputIterator                          // constexpr in C++20
424    merge(InputIterator1 first1, InputIterator1 last1,
425          InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
426
427template <class BidirectionalIterator>
428    void
429    inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
430
431template <class BidirectionalIterator, class Compare>
432    void
433    inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
434
435template <class InputIterator1, class InputIterator2>
436    constexpr bool                                    // constexpr in C++20
437    includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
438
439template <class InputIterator1, class InputIterator2, class Compare>
440    constexpr bool                                    // constexpr in C++20
441    includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
442
443template <class InputIterator1, class InputIterator2, class OutputIterator>
444    constexpr OutputIterator                          // constexpr in C++20
445    set_union(InputIterator1 first1, InputIterator1 last1,
446              InputIterator2 first2, InputIterator2 last2, OutputIterator result);
447
448template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
449    constexpr OutputIterator                          // constexpr in C++20
450    set_union(InputIterator1 first1, InputIterator1 last1,
451              InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
452
453template <class InputIterator1, class InputIterator2, class OutputIterator>
454    constexpr OutputIterator                         // constexpr in C++20
455    set_intersection(InputIterator1 first1, InputIterator1 last1,
456                     InputIterator2 first2, InputIterator2 last2, OutputIterator result);
457
458template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
459    constexpr OutputIterator                         // constexpr in C++20
460    set_intersection(InputIterator1 first1, InputIterator1 last1,
461                     InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
462
463template <class InputIterator1, class InputIterator2, class OutputIterator>
464    constexpr OutputIterator                         // constexpr in C++20
465    set_difference(InputIterator1 first1, InputIterator1 last1,
466                   InputIterator2 first2, InputIterator2 last2, OutputIterator result);
467
468template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
469    constexpr OutputIterator                         // constexpr in C++20
470    set_difference(InputIterator1 first1, InputIterator1 last1,
471                   InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
472
473template <class InputIterator1, class InputIterator2, class OutputIterator>
474    constexpr OutputIterator                         // constexpr in C++20
475    set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
476                             InputIterator2 first2, InputIterator2 last2, OutputIterator result);
477
478template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
479    constexpr OutputIterator                         // constexpr in C++20
480    set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
481                             InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
482
483template <class RandomAccessIterator>
484    void
485    push_heap(RandomAccessIterator first, RandomAccessIterator last);
486
487template <class RandomAccessIterator, class Compare>
488    void
489    push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
490
491template <class RandomAccessIterator>
492    void
493    pop_heap(RandomAccessIterator first, RandomAccessIterator last);
494
495template <class RandomAccessIterator, class Compare>
496    void
497    pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
498
499template <class RandomAccessIterator>
500    void
501    make_heap(RandomAccessIterator first, RandomAccessIterator last);
502
503template <class RandomAccessIterator, class Compare>
504    void
505    make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
506
507template <class RandomAccessIterator>
508    void
509    sort_heap(RandomAccessIterator first, RandomAccessIterator last);
510
511template <class RandomAccessIterator, class Compare>
512    void
513    sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
514
515template <class RandomAccessIterator>
516    constexpr bool   // constexpr in C++20
517    is_heap(RandomAccessIterator first, RandomAccessiterator last);
518
519template <class RandomAccessIterator, class Compare>
520    constexpr bool   // constexpr in C++20
521    is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
522
523template <class RandomAccessIterator>
524    constexpr RandomAccessIterator   // constexpr in C++20
525    is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
526
527template <class RandomAccessIterator, class Compare>
528    constexpr RandomAccessIterator   // constexpr in C++20
529    is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
530
531template <class ForwardIterator>
532    constexpr ForwardIterator        // constexpr in C++14
533    min_element(ForwardIterator first, ForwardIterator last);
534
535template <class ForwardIterator, class Compare>
536    constexpr ForwardIterator        // constexpr in C++14
537    min_element(ForwardIterator first, ForwardIterator last, Compare comp);
538
539template <class T>
540    constexpr const T&               // constexpr in C++14
541    min(const T& a, const T& b);
542
543template <class T, class Compare>
544    constexpr const T&               // constexpr in C++14
545    min(const T& a, const T& b, Compare comp);
546
547template<class T>
548    constexpr T                      // constexpr in C++14
549    min(initializer_list<T> t);
550
551template<class T, class Compare>
552    constexpr T                      // constexpr in C++14
553    min(initializer_list<T> t, Compare comp);
554
555template<class T>
556    constexpr const T& clamp(const T& v, const T& lo, const T& hi);               // C++17
557
558template<class T, class Compare>
559    constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp); // C++17
560
561template <class ForwardIterator>
562    constexpr ForwardIterator        // constexpr in C++14
563    max_element(ForwardIterator first, ForwardIterator last);
564
565template <class ForwardIterator, class Compare>
566    constexpr ForwardIterator        // constexpr in C++14
567    max_element(ForwardIterator first, ForwardIterator last, Compare comp);
568
569template <class T>
570    constexpr const T&               // constexpr in C++14
571    max(const T& a, const T& b);
572
573template <class T, class Compare>
574    constexpr const T&               // constexpr in C++14
575    max(const T& a, const T& b, Compare comp);
576
577template<class T>
578    constexpr T                      // constexpr in C++14
579    max(initializer_list<T> t);
580
581template<class T, class Compare>
582    constexpr T                      // constexpr in C++14
583    max(initializer_list<T> t, Compare comp);
584
585template<class ForwardIterator>
586    constexpr pair<ForwardIterator, ForwardIterator>  // constexpr in C++14
587    minmax_element(ForwardIterator first, ForwardIterator last);
588
589template<class ForwardIterator, class Compare>
590    constexpr pair<ForwardIterator, ForwardIterator>  // constexpr in C++14
591    minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
592
593template<class T>
594    constexpr pair<const T&, const T&>  // constexpr in C++14
595    minmax(const T& a, const T& b);
596
597template<class T, class Compare>
598    constexpr pair<const T&, const T&>  // constexpr in C++14
599    minmax(const T& a, const T& b, Compare comp);
600
601template<class T>
602    constexpr pair<T, T>                // constexpr in C++14
603    minmax(initializer_list<T> t);
604
605template<class T, class Compare>
606    constexpr pair<T, T>                // constexpr in C++14
607    minmax(initializer_list<T> t, Compare comp);
608
609template <class InputIterator1, class InputIterator2>
610    constexpr bool     // constexpr in C++20
611    lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
612
613template <class InputIterator1, class InputIterator2, class Compare>
614    constexpr bool     // constexpr in C++20
615    lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
616                            InputIterator2 first2, InputIterator2 last2, Compare comp);
617
618template <class BidirectionalIterator>
619    bool
620    next_permutation(BidirectionalIterator first, BidirectionalIterator last);
621
622template <class BidirectionalIterator, class Compare>
623    bool
624    next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
625
626template <class BidirectionalIterator>
627    bool
628    prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
629
630template <class BidirectionalIterator, class Compare>
631    bool
632    prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
633
634}  // std
635
636*/
637
638#include <__config>
639#include <initializer_list>
640#include <type_traits>
641#include <cstring>
642#include <utility> // needed to provide swap_ranges.
643#include <memory>
644#include <functional>
645#include <iterator>
646#include <cstddef>
647#include <bit>
648#include <version>
649
650#include <__debug>
651
652#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
653#pragma GCC system_header
654#endif
655
656_LIBCPP_PUSH_MACROS
657#include <__undef_macros>
658
659
660_LIBCPP_BEGIN_NAMESPACE_STD
661
662// I'd like to replace these with _VSTD::equal_to<void>, but can't because:
663//   * That only works with C++14 and later, and
664//   * We haven't included <functional> here.
665template <class _T1, class _T2 = _T1>
666struct __equal_to
667{
668    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
669    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;}
670    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;}
671    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;}
672};
673
674template <class _T1>
675struct __equal_to<_T1, _T1>
676{
677    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
678    bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
679};
680
681template <class _T1>
682struct __equal_to<const _T1, _T1>
683{
684    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
685    bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
686};
687
688template <class _T1>
689struct __equal_to<_T1, const _T1>
690{
691    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
692    bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
693};
694
695template <class _T1, class _T2 = _T1>
696struct __less
697{
698    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
699    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
700
701    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
702    bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;}
703
704    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
705    bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;}
706
707    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
708    bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;}
709};
710
711template <class _T1>
712struct __less<_T1, _T1>
713{
714    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
715    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
716};
717
718template <class _T1>
719struct __less<const _T1, _T1>
720{
721    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
722    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
723};
724
725template <class _T1>
726struct __less<_T1, const _T1>
727{
728    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
729    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
730};
731
732template <class _Predicate>
733class __invert // invert the sense of a comparison
734{
735private:
736    _Predicate __p_;
737public:
738    _LIBCPP_INLINE_VISIBILITY __invert() {}
739
740    _LIBCPP_INLINE_VISIBILITY
741    explicit __invert(_Predicate __p) : __p_(__p) {}
742
743    template <class _T1>
744    _LIBCPP_INLINE_VISIBILITY
745    bool operator()(const _T1& __x) {return !__p_(__x);}
746
747    template <class _T1, class _T2>
748    _LIBCPP_INLINE_VISIBILITY
749    bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);}
750};
751
752// Perform division by two quickly for positive integers (llvm.org/PR39129)
753
754template <typename _Integral>
755_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
756typename enable_if
757<
758    is_integral<_Integral>::value,
759    _Integral
760>::type
761__half_positive(_Integral __value)
762{
763    return static_cast<_Integral>(static_cast<typename make_unsigned<_Integral>::type>(__value) / 2);
764}
765
766template <typename _Tp>
767_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
768typename enable_if
769<
770    !is_integral<_Tp>::value,
771    _Tp
772>::type
773__half_positive(_Tp __value)
774{
775    return __value / 2;
776}
777
778#ifdef _LIBCPP_DEBUG
779
780template <class _Compare>
781struct __debug_less
782{
783    _Compare &__comp_;
784    _LIBCPP_CONSTEXPR_AFTER_CXX17
785    __debug_less(_Compare& __c) : __comp_(__c) {}
786
787    template <class _Tp, class _Up>
788    _LIBCPP_CONSTEXPR_AFTER_CXX17
789    bool operator()(const _Tp& __x,  const _Up& __y)
790    {
791        bool __r = __comp_(__x, __y);
792        if (__r)
793            __do_compare_assert(0, __y, __x);
794        return __r;
795    }
796
797    template <class _Tp, class _Up>
798    _LIBCPP_CONSTEXPR_AFTER_CXX17
799    bool operator()(_Tp& __x,  _Up& __y)
800    {
801        bool __r = __comp_(__x, __y);
802        if (__r)
803            __do_compare_assert(0, __y, __x);
804        return __r;
805    }
806
807    template <class _LHS, class _RHS>
808    _LIBCPP_CONSTEXPR_AFTER_CXX17
809    inline _LIBCPP_INLINE_VISIBILITY
810    decltype((void)_VSTD::declval<_Compare&>()(
811        _VSTD::declval<_LHS &>(), _VSTD::declval<_RHS &>()))
812    __do_compare_assert(int, _LHS & __l, _RHS & __r) {
813        _LIBCPP_ASSERT(!__comp_(__l, __r),
814            "Comparator does not induce a strict weak ordering");
815    }
816
817    template <class _LHS, class _RHS>
818    _LIBCPP_CONSTEXPR_AFTER_CXX17
819    inline _LIBCPP_INLINE_VISIBILITY
820    void __do_compare_assert(long, _LHS &, _RHS &) {}
821};
822
823#endif // _LIBCPP_DEBUG
824
825template <class _Comp>
826struct __comp_ref_type {
827  // Pass the comparator by lvalue reference. Or in debug mode, using a
828  // debugging wrapper that stores a reference.
829#ifndef _LIBCPP_DEBUG
830  typedef typename add_lvalue_reference<_Comp>::type type;
831#else
832  typedef __debug_less<_Comp> type;
833#endif
834};
835
836// all_of
837
838template <class _InputIterator, class _Predicate>
839_LIBCPP_NODISCARD_EXT inline
840_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
841bool
842all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
843{
844    for (; __first != __last; ++__first)
845        if (!__pred(*__first))
846            return false;
847    return true;
848}
849
850// any_of
851
852template <class _InputIterator, class _Predicate>
853_LIBCPP_NODISCARD_EXT inline
854_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
855bool
856any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
857{
858    for (; __first != __last; ++__first)
859        if (__pred(*__first))
860            return true;
861    return false;
862}
863
864// none_of
865
866template <class _InputIterator, class _Predicate>
867_LIBCPP_NODISCARD_EXT inline
868_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
869bool
870none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
871{
872    for (; __first != __last; ++__first)
873        if (__pred(*__first))
874            return false;
875    return true;
876}
877
878// for_each
879
880template <class _InputIterator, class _Function>
881inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
882_Function
883for_each(_InputIterator __first, _InputIterator __last, _Function __f)
884{
885    for (; __first != __last; ++__first)
886        __f(*__first);
887    return __f;
888}
889
890#if _LIBCPP_STD_VER > 14
891// for_each_n
892
893template <class _InputIterator, class _Size, class _Function>
894inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
895_InputIterator
896for_each_n(_InputIterator __first, _Size __orig_n, _Function __f)
897{
898    typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize;
899    _IntegralSize __n = __orig_n;
900    while (__n > 0)
901    {
902         __f(*__first);
903         ++__first;
904         --__n;
905    }
906    return __first;
907}
908#endif
909
910// find
911
912template <class _InputIterator, class _Tp>
913_LIBCPP_NODISCARD_EXT inline
914_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
915_InputIterator
916find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
917{
918    for (; __first != __last; ++__first)
919        if (*__first == __value_)
920            break;
921    return __first;
922}
923
924// find_if
925
926template <class _InputIterator, class _Predicate>
927_LIBCPP_NODISCARD_EXT inline
928_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
929_InputIterator
930find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
931{
932    for (; __first != __last; ++__first)
933        if (__pred(*__first))
934            break;
935    return __first;
936}
937
938// find_if_not
939
940template<class _InputIterator, class _Predicate>
941_LIBCPP_NODISCARD_EXT inline
942_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
943_InputIterator
944find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
945{
946    for (; __first != __last; ++__first)
947        if (!__pred(*__first))
948            break;
949    return __first;
950}
951
952// find_end
953
954template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
955_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1
956__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
957           _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
958           forward_iterator_tag, forward_iterator_tag)
959{
960    // modeled after search algorithm
961    _ForwardIterator1 __r = __last1;  // __last1 is the "default" answer
962    if (__first2 == __last2)
963        return __r;
964    while (true)
965    {
966        while (true)
967        {
968            if (__first1 == __last1)         // if source exhausted return last correct answer
969                return __r;                  //    (or __last1 if never found)
970            if (__pred(*__first1, *__first2))
971                break;
972            ++__first1;
973        }
974        // *__first1 matches *__first2, now match elements after here
975        _ForwardIterator1 __m1 = __first1;
976        _ForwardIterator2 __m2 = __first2;
977        while (true)
978        {
979            if (++__m2 == __last2)
980            {                         // Pattern exhaused, record answer and search for another one
981                __r = __first1;
982                ++__first1;
983                break;
984            }
985            if (++__m1 == __last1)     // Source exhausted, return last answer
986                return __r;
987            if (!__pred(*__m1, *__m2))  // mismatch, restart with a new __first
988            {
989                ++__first1;
990                break;
991            }  // else there is a match, check next elements
992        }
993    }
994}
995
996template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2>
997_LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator1
998__find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,
999           _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred,
1000           bidirectional_iterator_tag, bidirectional_iterator_tag)
1001{
1002    // modeled after search algorithm (in reverse)
1003    if (__first2 == __last2)
1004        return __last1;  // Everything matches an empty sequence
1005    _BidirectionalIterator1 __l1 = __last1;
1006    _BidirectionalIterator2 __l2 = __last2;
1007    --__l2;
1008    while (true)
1009    {
1010        // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks
1011        while (true)
1012        {
1013            if (__first1 == __l1)  // return __last1 if no element matches *__first2
1014                return __last1;
1015            if (__pred(*--__l1, *__l2))
1016                break;
1017        }
1018        // *__l1 matches *__l2, now match elements before here
1019        _BidirectionalIterator1 __m1 = __l1;
1020        _BidirectionalIterator2 __m2 = __l2;
1021        while (true)
1022        {
1023            if (__m2 == __first2)  // If pattern exhausted, __m1 is the answer (works for 1 element pattern)
1024                return __m1;
1025            if (__m1 == __first1)  // Otherwise if source exhaused, pattern not found
1026                return __last1;
1027            if (!__pred(*--__m1, *--__m2))  // if there is a mismatch, restart with a new __l1
1028            {
1029                break;
1030            }  // else there is a match, check next elements
1031        }
1032    }
1033}
1034
1035template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1036_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1
1037__find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1038           _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1039           random_access_iterator_tag, random_access_iterator_tag)
1040{
1041    // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
1042    typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;
1043    if (__len2 == 0)
1044        return __last1;
1045    typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;
1046    if (__len1 < __len2)
1047        return __last1;
1048    const _RandomAccessIterator1 __s = __first1 + (__len2 - 1);  // End of pattern match can't go before here
1049    _RandomAccessIterator1 __l1 = __last1;
1050    _RandomAccessIterator2 __l2 = __last2;
1051    --__l2;
1052    while (true)
1053    {
1054        while (true)
1055        {
1056            if (__s == __l1)
1057                return __last1;
1058            if (__pred(*--__l1, *__l2))
1059                break;
1060        }
1061        _RandomAccessIterator1 __m1 = __l1;
1062        _RandomAccessIterator2 __m2 = __l2;
1063        while (true)
1064        {
1065            if (__m2 == __first2)
1066                return __m1;
1067                                 // no need to check range on __m1 because __s guarantees we have enough source
1068            if (!__pred(*--__m1, *--__m2))
1069            {
1070                break;
1071            }
1072        }
1073    }
1074}
1075
1076template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1077_LIBCPP_NODISCARD_EXT inline
1078_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1079_ForwardIterator1
1080find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1081         _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1082{
1083    return _VSTD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type>
1084                         (__first1, __last1, __first2, __last2, __pred,
1085                          typename iterator_traits<_ForwardIterator1>::iterator_category(),
1086                          typename iterator_traits<_ForwardIterator2>::iterator_category());
1087}
1088
1089template <class _ForwardIterator1, class _ForwardIterator2>
1090_LIBCPP_NODISCARD_EXT inline
1091_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1092_ForwardIterator1
1093find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1094         _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1095{
1096    typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1097    typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1098    return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1099}
1100
1101// find_first_of
1102
1103template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1104_LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator1
1105__find_first_of_ce(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1106              _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1107{
1108    for (; __first1 != __last1; ++__first1)
1109        for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1110            if (__pred(*__first1, *__j))
1111                return __first1;
1112    return __last1;
1113}
1114
1115
1116template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1117_LIBCPP_NODISCARD_EXT inline
1118_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1119_ForwardIterator1
1120find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1121              _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1122{
1123    return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred);
1124}
1125
1126template <class _ForwardIterator1, class _ForwardIterator2>
1127_LIBCPP_NODISCARD_EXT inline
1128_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1129_ForwardIterator1
1130find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1131              _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1132{
1133    typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1134    typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1135    return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1136}
1137
1138// adjacent_find
1139
1140template <class _ForwardIterator, class _BinaryPredicate>
1141_LIBCPP_NODISCARD_EXT inline
1142_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1143_ForwardIterator
1144adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
1145{
1146    if (__first != __last)
1147    {
1148        _ForwardIterator __i = __first;
1149        while (++__i != __last)
1150        {
1151            if (__pred(*__first, *__i))
1152                return __first;
1153            __first = __i;
1154        }
1155    }
1156    return __last;
1157}
1158
1159template <class _ForwardIterator>
1160_LIBCPP_NODISCARD_EXT inline
1161_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1162_ForwardIterator
1163adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
1164{
1165    typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1166    return _VSTD::adjacent_find(__first, __last, __equal_to<__v>());
1167}
1168
1169// count
1170
1171template <class _InputIterator, class _Tp>
1172_LIBCPP_NODISCARD_EXT inline
1173_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1174typename iterator_traits<_InputIterator>::difference_type
1175count(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
1176{
1177    typename iterator_traits<_InputIterator>::difference_type __r(0);
1178    for (; __first != __last; ++__first)
1179        if (*__first == __value_)
1180            ++__r;
1181    return __r;
1182}
1183
1184// count_if
1185
1186template <class _InputIterator, class _Predicate>
1187_LIBCPP_NODISCARD_EXT inline
1188_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1189typename iterator_traits<_InputIterator>::difference_type
1190count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
1191{
1192    typename iterator_traits<_InputIterator>::difference_type __r(0);
1193    for (; __first != __last; ++__first)
1194        if (__pred(*__first))
1195            ++__r;
1196    return __r;
1197}
1198
1199// mismatch
1200
1201template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1202_LIBCPP_NODISCARD_EXT inline
1203_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1204pair<_InputIterator1, _InputIterator2>
1205mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1206         _InputIterator2 __first2, _BinaryPredicate __pred)
1207{
1208    for (; __first1 != __last1; ++__first1, (void) ++__first2)
1209        if (!__pred(*__first1, *__first2))
1210            break;
1211    return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1212}
1213
1214template <class _InputIterator1, class _InputIterator2>
1215_LIBCPP_NODISCARD_EXT inline
1216_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1217pair<_InputIterator1, _InputIterator2>
1218mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1219{
1220    typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1221    typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1222    return _VSTD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1223}
1224
1225#if _LIBCPP_STD_VER > 11
1226template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1227_LIBCPP_NODISCARD_EXT inline
1228_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1229pair<_InputIterator1, _InputIterator2>
1230mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1231         _InputIterator2 __first2, _InputIterator2 __last2,
1232         _BinaryPredicate __pred)
1233{
1234    for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1235        if (!__pred(*__first1, *__first2))
1236            break;
1237    return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1238}
1239
1240template <class _InputIterator1, class _InputIterator2>
1241_LIBCPP_NODISCARD_EXT inline
1242_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1243pair<_InputIterator1, _InputIterator2>
1244mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1245         _InputIterator2 __first2, _InputIterator2 __last2)
1246{
1247    typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1248    typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1249    return _VSTD::mismatch(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1250}
1251#endif
1252
1253// equal
1254
1255template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1256_LIBCPP_NODISCARD_EXT inline
1257_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1258bool
1259equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred)
1260{
1261    for (; __first1 != __last1; ++__first1, (void) ++__first2)
1262        if (!__pred(*__first1, *__first2))
1263            return false;
1264    return true;
1265}
1266
1267template <class _InputIterator1, class _InputIterator2>
1268_LIBCPP_NODISCARD_EXT inline
1269_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1270bool
1271equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1272{
1273    typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1274    typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1275    return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1276}
1277
1278#if _LIBCPP_STD_VER > 11
1279template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2>
1280inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1281bool
1282__equal(_InputIterator1 __first1, _InputIterator1 __last1,
1283        _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred,
1284        input_iterator_tag, input_iterator_tag )
1285{
1286    for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1287        if (!__pred(*__first1, *__first2))
1288            return false;
1289    return __first1 == __last1 && __first2 == __last2;
1290}
1291
1292template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1293inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1294bool
1295__equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1296        _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1297      random_access_iterator_tag, random_access_iterator_tag )
1298{
1299    if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
1300        return false;
1301    return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2,
1302                        typename add_lvalue_reference<_BinaryPredicate>::type>
1303                       (__first1, __last1, __first2, __pred );
1304}
1305
1306template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1307_LIBCPP_NODISCARD_EXT inline
1308_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1309bool
1310equal(_InputIterator1 __first1, _InputIterator1 __last1,
1311      _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred )
1312{
1313    return _VSTD::__equal<typename add_lvalue_reference<_BinaryPredicate>::type>
1314       (__first1, __last1, __first2, __last2, __pred,
1315        typename iterator_traits<_InputIterator1>::iterator_category(),
1316        typename iterator_traits<_InputIterator2>::iterator_category());
1317}
1318
1319template <class _InputIterator1, class _InputIterator2>
1320_LIBCPP_NODISCARD_EXT inline
1321_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1322bool
1323equal(_InputIterator1 __first1, _InputIterator1 __last1,
1324      _InputIterator2 __first2, _InputIterator2 __last2)
1325{
1326    typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1327    typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1328    return _VSTD::__equal(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(),
1329        typename iterator_traits<_InputIterator1>::iterator_category(),
1330        typename iterator_traits<_InputIterator2>::iterator_category());
1331}
1332#endif
1333
1334// is_permutation
1335
1336template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1337_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
1338is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1339               _ForwardIterator2 __first2, _BinaryPredicate __pred)
1340{
1341//  shorten sequences as much as possible by lopping of any equal prefix
1342    for (; __first1 != __last1; ++__first1, (void) ++__first2)
1343        if (!__pred(*__first1, *__first2))
1344            break;
1345    if (__first1 == __last1)
1346        return true;
1347
1348//  __first1 != __last1 && *__first1 != *__first2
1349    typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1350    _D1 __l1 = _VSTD::distance(__first1, __last1);
1351    if (__l1 == _D1(1))
1352        return false;
1353    _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1);
1354    // For each element in [f1, l1) see if there are the same number of
1355    //    equal elements in [f2, l2)
1356    for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
1357    {
1358    //  Have we already counted the number of *__i in [f1, l1)?
1359        _ForwardIterator1 __match = __first1;
1360        for (; __match != __i; ++__match)
1361            if (__pred(*__match, *__i))
1362                break;
1363        if (__match == __i) {
1364            // Count number of *__i in [f2, l2)
1365            _D1 __c2 = 0;
1366            for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1367                if (__pred(*__i, *__j))
1368                    ++__c2;
1369            if (__c2 == 0)
1370                return false;
1371            // Count number of *__i in [__i, l1) (we can start with 1)
1372            _D1 __c1 = 1;
1373            for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
1374                if (__pred(*__i, *__j))
1375                    ++__c1;
1376            if (__c1 != __c2)
1377                return false;
1378        }
1379    }
1380    return true;
1381}
1382
1383template<class _ForwardIterator1, class _ForwardIterator2>
1384_LIBCPP_NODISCARD_EXT inline
1385_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1386bool
1387is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1388               _ForwardIterator2 __first2)
1389{
1390    typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1391    typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1392    return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1393}
1394
1395#if _LIBCPP_STD_VER > 11
1396template<class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
1397_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
1398__is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1399                 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1400                 _BinaryPredicate __pred,
1401                 forward_iterator_tag, forward_iterator_tag )
1402{
1403//  shorten sequences as much as possible by lopping of any equal prefix
1404    for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1405        if (!__pred(*__first1, *__first2))
1406            break;
1407    if (__first1 == __last1)
1408        return __first2 == __last2;
1409    else if (__first2 == __last2)
1410        return false;
1411
1412    typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1413    _D1 __l1 = _VSTD::distance(__first1, __last1);
1414
1415    typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2;
1416    _D2 __l2 = _VSTD::distance(__first2, __last2);
1417    if (__l1 != __l2)
1418        return false;
1419
1420    // For each element in [f1, l1) see if there are the same number of
1421    //    equal elements in [f2, l2)
1422    for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
1423    {
1424    //  Have we already counted the number of *__i in [f1, l1)?
1425        _ForwardIterator1 __match = __first1;
1426        for (; __match != __i; ++__match)
1427            if (__pred(*__match, *__i))
1428                break;
1429        if (__match == __i) {
1430            // Count number of *__i in [f2, l2)
1431            _D1 __c2 = 0;
1432            for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1433                if (__pred(*__i, *__j))
1434                    ++__c2;
1435            if (__c2 == 0)
1436                return false;
1437            // Count number of *__i in [__i, l1) (we can start with 1)
1438            _D1 __c1 = 1;
1439            for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
1440                if (__pred(*__i, *__j))
1441                    ++__c1;
1442            if (__c1 != __c2)
1443                return false;
1444        }
1445    }
1446    return true;
1447}
1448
1449template<class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1450_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
1451__is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1,
1452               _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2,
1453               _BinaryPredicate __pred,
1454               random_access_iterator_tag, random_access_iterator_tag )
1455{
1456    if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
1457        return false;
1458    return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2,
1459                                 typename add_lvalue_reference<_BinaryPredicate>::type>
1460                                (__first1, __last1, __first2, __pred );
1461}
1462
1463template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1464_LIBCPP_NODISCARD_EXT inline
1465_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1466bool
1467is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1468               _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1469               _BinaryPredicate __pred )
1470{
1471    return _VSTD::__is_permutation<typename add_lvalue_reference<_BinaryPredicate>::type>
1472       (__first1, __last1, __first2, __last2, __pred,
1473        typename iterator_traits<_ForwardIterator1>::iterator_category(),
1474        typename iterator_traits<_ForwardIterator2>::iterator_category());
1475}
1476
1477template<class _ForwardIterator1, class _ForwardIterator2>
1478_LIBCPP_NODISCARD_EXT inline
1479_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1480bool
1481is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1482               _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1483{
1484    typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1485    typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1486    return _VSTD::__is_permutation(__first1, __last1, __first2, __last2,
1487        __equal_to<__v1, __v2>(),
1488        typename iterator_traits<_ForwardIterator1>::iterator_category(),
1489        typename iterator_traits<_ForwardIterator2>::iterator_category());
1490}
1491#endif
1492
1493// search
1494// __search is in <functional>
1495
1496template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1497_LIBCPP_NODISCARD_EXT inline
1498_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1499_ForwardIterator1
1500search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1501       _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1502{
1503    return _VSTD::__search<typename add_lvalue_reference<_BinaryPredicate>::type>
1504                         (__first1, __last1, __first2, __last2, __pred,
1505                          typename iterator_traits<_ForwardIterator1>::iterator_category(),
1506                          typename iterator_traits<_ForwardIterator2>::iterator_category())
1507            .first;
1508}
1509
1510template <class _ForwardIterator1, class _ForwardIterator2>
1511_LIBCPP_NODISCARD_EXT inline
1512_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1513_ForwardIterator1
1514search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1515       _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1516{
1517    typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1518    typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1519    return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1520}
1521
1522
1523#if _LIBCPP_STD_VER > 14
1524template <class _ForwardIterator, class _Searcher>
1525_LIBCPP_NODISCARD_EXT _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1526_ForwardIterator search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher &__s)
1527{ return __s(__f, __l).first; }
1528#endif
1529
1530// search_n
1531
1532template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp>
1533_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
1534__search_n(_ForwardIterator __first, _ForwardIterator __last,
1535           _Size __count, const _Tp& __value_, _BinaryPredicate __pred, forward_iterator_tag)
1536{
1537    if (__count <= 0)
1538        return __first;
1539    while (true)
1540    {
1541        // Find first element in sequence that matchs __value_, with a mininum of loop checks
1542        while (true)
1543        {
1544            if (__first == __last)  // return __last if no element matches __value_
1545                return __last;
1546            if (__pred(*__first, __value_))
1547                break;
1548            ++__first;
1549        }
1550        // *__first matches __value_, now match elements after here
1551        _ForwardIterator __m = __first;
1552        _Size __c(0);
1553        while (true)
1554        {
1555            if (++__c == __count)  // If pattern exhausted, __first is the answer (works for 1 element pattern)
1556                return __first;
1557            if (++__m == __last)  // Otherwise if source exhaused, pattern not found
1558                return __last;
1559            if (!__pred(*__m, __value_))  // if there is a mismatch, restart with a new __first
1560            {
1561                __first = __m;
1562                ++__first;
1563                break;
1564            }  // else there is a match, check next elements
1565        }
1566    }
1567}
1568
1569template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp>
1570_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
1571__search_n(_RandomAccessIterator __first, _RandomAccessIterator __last,
1572           _Size __count, const _Tp& __value_, _BinaryPredicate __pred, random_access_iterator_tag)
1573{
1574    if (__count <= 0)
1575        return __first;
1576    _Size __len = static_cast<_Size>(__last - __first);
1577    if (__len < __count)
1578        return __last;
1579    const _RandomAccessIterator __s = __last - (__count - 1);  // Start of pattern match can't go beyond here
1580    while (true)
1581    {
1582        // Find first element in sequence that matchs __value_, with a mininum of loop checks
1583        while (true)
1584        {
1585            if (__first >= __s)  // return __last if no element matches __value_
1586                return __last;
1587            if (__pred(*__first, __value_))
1588                break;
1589            ++__first;
1590        }
1591        // *__first matches __value_, now match elements after here
1592        _RandomAccessIterator __m = __first;
1593        _Size __c(0);
1594        while (true)
1595        {
1596            if (++__c == __count)  // If pattern exhausted, __first is the answer (works for 1 element pattern)
1597                return __first;
1598             ++__m;          // no need to check range on __m because __s guarantees we have enough source
1599            if (!__pred(*__m, __value_))  // if there is a mismatch, restart with a new __first
1600            {
1601                __first = __m;
1602                ++__first;
1603                break;
1604            }  // else there is a match, check next elements
1605        }
1606    }
1607}
1608
1609template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
1610_LIBCPP_NODISCARD_EXT inline
1611_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1612_ForwardIterator
1613search_n(_ForwardIterator __first, _ForwardIterator __last,
1614         _Size __count, const _Tp& __value_, _BinaryPredicate __pred)
1615{
1616    return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>
1617           (__first, __last, _VSTD::__convert_to_integral(__count), __value_, __pred,
1618           typename iterator_traits<_ForwardIterator>::iterator_category());
1619}
1620
1621template <class _ForwardIterator, class _Size, class _Tp>
1622_LIBCPP_NODISCARD_EXT inline
1623_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1624_ForwardIterator
1625search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
1626{
1627    typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1628    return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count),
1629                           __value_, __equal_to<__v, _Tp>());
1630}
1631
1632// copy
1633template <class _Iter>
1634inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
1635_Iter
1636__unwrap_iter(_Iter __i)
1637{
1638    return __i;
1639}
1640
1641template <class _Tp>
1642inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
1643typename enable_if
1644<
1645    is_trivially_copy_assignable<_Tp>::value,
1646    _Tp*
1647>::type
1648__unwrap_iter(move_iterator<_Tp*> __i)
1649{
1650    return __i.base();
1651}
1652
1653#if _LIBCPP_DEBUG_LEVEL < 2
1654
1655template <class _Tp>
1656inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
1657typename enable_if
1658<
1659    is_trivially_copy_assignable<_Tp>::value,
1660    _Tp*
1661>::type
1662__unwrap_iter(__wrap_iter<_Tp*> __i)
1663{
1664    return __i.base();
1665}
1666
1667template <class _Tp>
1668inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
1669typename enable_if
1670<
1671    is_trivially_copy_assignable<_Tp>::value,
1672    const _Tp*
1673>::type
1674__unwrap_iter(__wrap_iter<const _Tp*> __i)
1675{
1676    return __i.base();
1677}
1678
1679#else
1680
1681template <class _Tp>
1682inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
1683typename enable_if
1684<
1685    is_trivially_copy_assignable<_Tp>::value,
1686    __wrap_iter<_Tp*>
1687>::type
1688__unwrap_iter(__wrap_iter<_Tp*> __i)
1689{
1690    return __i;
1691}
1692
1693#endif  // _LIBCPP_DEBUG_LEVEL < 2
1694
1695template <class _InputIterator, class _OutputIterator>
1696inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1697_OutputIterator
1698__copy_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1699{
1700    for (; __first != __last; ++__first, (void) ++__result)
1701        *__result = *__first;
1702    return __result;
1703}
1704
1705template <class _InputIterator, class _OutputIterator>
1706inline _LIBCPP_INLINE_VISIBILITY
1707_OutputIterator
1708__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1709{
1710    return _VSTD::__copy_constexpr(__first, __last, __result);
1711}
1712
1713template <class _Tp, class _Up>
1714inline _LIBCPP_INLINE_VISIBILITY
1715typename enable_if
1716<
1717    is_same<typename remove_const<_Tp>::type, _Up>::value &&
1718    is_trivially_copy_assignable<_Up>::value,
1719    _Up*
1720>::type
1721__copy(_Tp* __first, _Tp* __last, _Up* __result)
1722{
1723    const size_t __n = static_cast<size_t>(__last - __first);
1724    if (__n > 0)
1725        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1726    return __result + __n;
1727}
1728
1729template <class _InputIterator, class _OutputIterator>
1730inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1731_OutputIterator
1732copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1733{
1734    if (__libcpp_is_constant_evaluated()) {
1735        return _VSTD::__copy_constexpr(
1736            _VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result));
1737    } else {
1738        return _VSTD::__copy(
1739            _VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result));
1740    }
1741}
1742
1743// copy_backward
1744
1745template <class _BidirectionalIterator, class _OutputIterator>
1746inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1747_OutputIterator
1748__copy_backward_constexpr(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
1749{
1750    while (__first != __last)
1751        *--__result = *--__last;
1752    return __result;
1753}
1754
1755template <class _BidirectionalIterator, class _OutputIterator>
1756inline _LIBCPP_INLINE_VISIBILITY
1757_OutputIterator
1758__copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
1759{
1760    return _VSTD::__copy_backward_constexpr(__first, __last, __result);
1761}
1762
1763template <class _Tp, class _Up>
1764inline _LIBCPP_INLINE_VISIBILITY
1765typename enable_if
1766<
1767    is_same<typename remove_const<_Tp>::type, _Up>::value &&
1768    is_trivially_copy_assignable<_Up>::value,
1769    _Up*
1770>::type
1771__copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
1772{
1773    const size_t __n = static_cast<size_t>(__last - __first);
1774    if (__n > 0)
1775    {
1776        __result -= __n;
1777        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1778    }
1779    return __result;
1780}
1781
1782template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1783inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1784_BidirectionalIterator2
1785copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1786              _BidirectionalIterator2 __result)
1787{
1788    if (__libcpp_is_constant_evaluated()) {
1789        return _VSTD::__copy_backward_constexpr(_VSTD::__unwrap_iter(__first),
1790                                                _VSTD::__unwrap_iter(__last),
1791                                                _VSTD::__unwrap_iter(__result));
1792    } else {
1793        return _VSTD::__copy_backward(_VSTD::__unwrap_iter(__first),
1794                                      _VSTD::__unwrap_iter(__last),
1795                                      _VSTD::__unwrap_iter(__result));
1796    }
1797}
1798
1799// copy_if
1800
1801template<class _InputIterator, class _OutputIterator, class _Predicate>
1802inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1803_OutputIterator
1804copy_if(_InputIterator __first, _InputIterator __last,
1805        _OutputIterator __result, _Predicate __pred)
1806{
1807    for (; __first != __last; ++__first)
1808    {
1809        if (__pred(*__first))
1810        {
1811            *__result = *__first;
1812            ++__result;
1813        }
1814    }
1815    return __result;
1816}
1817
1818// copy_n
1819
1820template<class _InputIterator, class _Size, class _OutputIterator>
1821inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1822typename enable_if
1823<
1824    __is_cpp17_input_iterator<_InputIterator>::value &&
1825   !__is_cpp17_random_access_iterator<_InputIterator>::value,
1826    _OutputIterator
1827>::type
1828copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1829{
1830    typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize;
1831    _IntegralSize __n = __orig_n;
1832    if (__n > 0)
1833    {
1834        *__result = *__first;
1835        ++__result;
1836        for (--__n; __n > 0; --__n)
1837        {
1838            ++__first;
1839            *__result = *__first;
1840            ++__result;
1841        }
1842    }
1843    return __result;
1844}
1845
1846template<class _InputIterator, class _Size, class _OutputIterator>
1847inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1848typename enable_if
1849<
1850    __is_cpp17_random_access_iterator<_InputIterator>::value,
1851    _OutputIterator
1852>::type
1853copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1854{
1855    typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize;
1856    _IntegralSize __n = __orig_n;
1857    return _VSTD::copy(__first, __first + __n, __result);
1858}
1859
1860// move
1861
1862// __move_constexpr exists so that __move doesn't call itself when delegating to the constexpr
1863// version of __move.
1864template <class _InputIterator, class _OutputIterator>
1865inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1866_OutputIterator
1867__move_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1868{
1869    for (; __first != __last; ++__first, (void) ++__result)
1870        *__result = _VSTD::move(*__first);
1871    return __result;
1872}
1873
1874template <class _InputIterator, class _OutputIterator>
1875inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1876_OutputIterator
1877__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1878{
1879    return _VSTD::__move_constexpr(__first, __last, __result);
1880}
1881
1882template <class _Tp, class _Up>
1883inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1884typename enable_if
1885<
1886    is_same<typename remove_const<_Tp>::type, _Up>::value &&
1887    is_trivially_copy_assignable<_Up>::value,
1888    _Up*
1889>::type
1890__move(_Tp* __first, _Tp* __last, _Up* __result)
1891{
1892    if (__libcpp_is_constant_evaluated())
1893        return _VSTD::__move_constexpr(__first, __last, __result);
1894    const size_t __n = static_cast<size_t>(__last - __first);
1895    if (__n > 0)
1896        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1897    return __result + __n;
1898}
1899
1900template <class _InputIterator, class _OutputIterator>
1901inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1902_OutputIterator
1903move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1904{
1905    return _VSTD::__move(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result));
1906}
1907
1908// move_backward
1909
1910// __move_backward_constexpr exists so that __move_backward doesn't call itself when delegating to
1911// the constexpr version of __move_backward.
1912template <class _InputIterator, class _OutputIterator>
1913inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1914_OutputIterator
1915__move_backward_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1916{
1917    while (__first != __last)
1918        *--__result = _VSTD::move(*--__last);
1919    return __result;
1920}
1921
1922template <class _InputIterator, class _OutputIterator>
1923inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1924_OutputIterator
1925__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1926{
1927    return _VSTD::__move_backward_constexpr(__first, __last, __result);
1928}
1929
1930template <class _Tp, class _Up>
1931inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1932typename enable_if
1933<
1934    is_same<typename remove_const<_Tp>::type, _Up>::value &&
1935    is_trivially_copy_assignable<_Up>::value,
1936    _Up*
1937>::type
1938__move_backward(_Tp* __first, _Tp* __last, _Up* __result)
1939{
1940    if (__libcpp_is_constant_evaluated())
1941        return _VSTD::__move_backward_constexpr(__first, __last, __result);
1942    const size_t __n = static_cast<size_t>(__last - __first);
1943    if (__n > 0)
1944    {
1945        __result -= __n;
1946        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1947    }
1948    return __result;
1949}
1950
1951template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1952inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1953_BidirectionalIterator2
1954move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1955              _BidirectionalIterator2 __result)
1956{
1957    return _VSTD::__move_backward(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _VSTD::__unwrap_iter(__result));
1958}
1959
1960// iter_swap
1961
1962// moved to <type_traits> for better swap / noexcept support
1963
1964// transform
1965
1966template <class _InputIterator, class _OutputIterator, class _UnaryOperation>
1967inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1968_OutputIterator
1969transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op)
1970{
1971    for (; __first != __last; ++__first, (void) ++__result)
1972        *__result = __op(*__first);
1973    return __result;
1974}
1975
1976template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation>
1977inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1978_OutputIterator
1979transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
1980          _OutputIterator __result, _BinaryOperation __binary_op)
1981{
1982    for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result)
1983        *__result = __binary_op(*__first1, *__first2);
1984    return __result;
1985}
1986
1987// replace
1988
1989template <class _ForwardIterator, class _Tp>
1990inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1991void
1992replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value)
1993{
1994    for (; __first != __last; ++__first)
1995        if (*__first == __old_value)
1996            *__first = __new_value;
1997}
1998
1999// replace_if
2000
2001template <class _ForwardIterator, class _Predicate, class _Tp>
2002inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2003void
2004replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value)
2005{
2006    for (; __first != __last; ++__first)
2007        if (__pred(*__first))
2008            *__first = __new_value;
2009}
2010
2011// replace_copy
2012
2013template <class _InputIterator, class _OutputIterator, class _Tp>
2014inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2015_OutputIterator
2016replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
2017             const _Tp& __old_value, const _Tp& __new_value)
2018{
2019    for (; __first != __last; ++__first, (void) ++__result)
2020        if (*__first == __old_value)
2021            *__result = __new_value;
2022        else
2023            *__result = *__first;
2024    return __result;
2025}
2026
2027// replace_copy_if
2028
2029template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp>
2030inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2031_OutputIterator
2032replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
2033                _Predicate __pred, const _Tp& __new_value)
2034{
2035    for (; __first != __last; ++__first, (void) ++__result)
2036        if (__pred(*__first))
2037            *__result = __new_value;
2038        else
2039            *__result = *__first;
2040    return __result;
2041}
2042
2043// fill_n
2044
2045template <class _OutputIterator, class _Size, class _Tp>
2046inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2047_OutputIterator
2048__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2049{
2050    for (; __n > 0; ++__first, (void) --__n)
2051        *__first = __value_;
2052    return __first;
2053}
2054
2055template <class _OutputIterator, class _Size, class _Tp>
2056inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2057_OutputIterator
2058fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2059{
2060   return _VSTD::__fill_n(__first, _VSTD::__convert_to_integral(__n), __value_);
2061}
2062
2063// fill
2064
2065template <class _ForwardIterator, class _Tp>
2066inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2067void
2068__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
2069{
2070    for (; __first != __last; ++__first)
2071        *__first = __value_;
2072}
2073
2074template <class _RandomAccessIterator, class _Tp>
2075inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2076void
2077__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag)
2078{
2079    _VSTD::fill_n(__first, __last - __first, __value_);
2080}
2081
2082template <class _ForwardIterator, class _Tp>
2083inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2084void
2085fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2086{
2087    _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category());
2088}
2089
2090// generate
2091
2092template <class _ForwardIterator, class _Generator>
2093inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2094void
2095generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
2096{
2097    for (; __first != __last; ++__first)
2098        *__first = __gen();
2099}
2100
2101// generate_n
2102
2103template <class _OutputIterator, class _Size, class _Generator>
2104inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2105_OutputIterator
2106generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen)
2107{
2108    typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize;
2109    _IntegralSize __n = __orig_n;
2110    for (; __n > 0; ++__first, (void) --__n)
2111        *__first = __gen();
2112    return __first;
2113}
2114
2115// remove
2116
2117template <class _ForwardIterator, class _Tp>
2118_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
2119remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2120{
2121    __first = _VSTD::find(__first, __last, __value_);
2122    if (__first != __last)
2123    {
2124        _ForwardIterator __i = __first;
2125        while (++__i != __last)
2126        {
2127            if (!(*__i == __value_))
2128            {
2129                *__first = _VSTD::move(*__i);
2130                ++__first;
2131            }
2132        }
2133    }
2134    return __first;
2135}
2136
2137// remove_if
2138
2139template <class _ForwardIterator, class _Predicate>
2140_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
2141remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2142{
2143    __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
2144                           (__first, __last, __pred);
2145    if (__first != __last)
2146    {
2147        _ForwardIterator __i = __first;
2148        while (++__i != __last)
2149        {
2150            if (!__pred(*__i))
2151            {
2152                *__first = _VSTD::move(*__i);
2153                ++__first;
2154            }
2155        }
2156    }
2157    return __first;
2158}
2159
2160// remove_copy
2161
2162template <class _InputIterator, class _OutputIterator, class _Tp>
2163inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2164_OutputIterator
2165remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_)
2166{
2167    for (; __first != __last; ++__first)
2168    {
2169        if (!(*__first == __value_))
2170        {
2171            *__result = *__first;
2172            ++__result;
2173        }
2174    }
2175    return __result;
2176}
2177
2178// remove_copy_if
2179
2180template <class _InputIterator, class _OutputIterator, class _Predicate>
2181inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2182_OutputIterator
2183remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
2184{
2185    for (; __first != __last; ++__first)
2186    {
2187        if (!__pred(*__first))
2188        {
2189            *__result = *__first;
2190            ++__result;
2191        }
2192    }
2193    return __result;
2194}
2195
2196// unique
2197
2198template <class _ForwardIterator, class _BinaryPredicate>
2199_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
2200unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
2201{
2202    __first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type>
2203                                 (__first, __last, __pred);
2204    if (__first != __last)
2205    {
2206        // ...  a  a  ?  ...
2207        //      f     i
2208        _ForwardIterator __i = __first;
2209        for (++__i; ++__i != __last;)
2210            if (!__pred(*__first, *__i))
2211                *++__first = _VSTD::move(*__i);
2212        ++__first;
2213    }
2214    return __first;
2215}
2216
2217template <class _ForwardIterator>
2218_LIBCPP_NODISCARD_EXT inline
2219_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2220_ForwardIterator
2221unique(_ForwardIterator __first, _ForwardIterator __last)
2222{
2223    typedef typename iterator_traits<_ForwardIterator>::value_type __v;
2224    return _VSTD::unique(__first, __last, __equal_to<__v>());
2225}
2226
2227// unique_copy
2228
2229template <class _BinaryPredicate, class _InputIterator, class _OutputIterator>
2230_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
2231__unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2232              input_iterator_tag, output_iterator_tag)
2233{
2234    if (__first != __last)
2235    {
2236        typename iterator_traits<_InputIterator>::value_type __t(*__first);
2237        *__result = __t;
2238        ++__result;
2239        while (++__first != __last)
2240        {
2241            if (!__pred(__t, *__first))
2242            {
2243                __t = *__first;
2244                *__result = __t;
2245                ++__result;
2246            }
2247        }
2248    }
2249    return __result;
2250}
2251
2252template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator>
2253_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
2254__unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2255              forward_iterator_tag, output_iterator_tag)
2256{
2257    if (__first != __last)
2258    {
2259        _ForwardIterator __i = __first;
2260        *__result = *__i;
2261        ++__result;
2262        while (++__first != __last)
2263        {
2264            if (!__pred(*__i, *__first))
2265            {
2266                *__result = *__first;
2267                ++__result;
2268                __i = __first;
2269            }
2270        }
2271    }
2272    return __result;
2273}
2274
2275template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator>
2276_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
2277__unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred,
2278              input_iterator_tag, forward_iterator_tag)
2279{
2280    if (__first != __last)
2281    {
2282        *__result = *__first;
2283        while (++__first != __last)
2284            if (!__pred(*__result, *__first))
2285                *++__result = *__first;
2286        ++__result;
2287    }
2288    return __result;
2289}
2290
2291template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
2292inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2293_OutputIterator
2294unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred)
2295{
2296    return _VSTD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type>
2297                              (__first, __last, __result, __pred,
2298                               typename iterator_traits<_InputIterator>::iterator_category(),
2299                               typename iterator_traits<_OutputIterator>::iterator_category());
2300}
2301
2302template <class _InputIterator, class _OutputIterator>
2303inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2304_OutputIterator
2305unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
2306{
2307    typedef typename iterator_traits<_InputIterator>::value_type __v;
2308    return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());
2309}
2310
2311// reverse
2312
2313template <class _BidirectionalIterator>
2314inline _LIBCPP_INLINE_VISIBILITY
2315void
2316__reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
2317{
2318    while (__first != __last)
2319    {
2320        if (__first == --__last)
2321            break;
2322        _VSTD::iter_swap(__first, __last);
2323        ++__first;
2324    }
2325}
2326
2327template <class _RandomAccessIterator>
2328inline _LIBCPP_INLINE_VISIBILITY
2329void
2330__reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
2331{
2332    if (__first != __last)
2333        for (; __first < --__last; ++__first)
2334            _VSTD::iter_swap(__first, __last);
2335}
2336
2337template <class _BidirectionalIterator>
2338inline _LIBCPP_INLINE_VISIBILITY
2339void
2340reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
2341{
2342    _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());
2343}
2344
2345// reverse_copy
2346
2347template <class _BidirectionalIterator, class _OutputIterator>
2348inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2349_OutputIterator
2350reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
2351{
2352    for (; __first != __last; ++__result)
2353        *__result = *--__last;
2354    return __result;
2355}
2356
2357// rotate
2358
2359template <class _ForwardIterator>
2360_LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
2361__rotate_left(_ForwardIterator __first, _ForwardIterator __last)
2362{
2363    typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2364    value_type __tmp = _VSTD::move(*__first);
2365    _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
2366    *__lm1 = _VSTD::move(__tmp);
2367    return __lm1;
2368}
2369
2370template <class _BidirectionalIterator>
2371_LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator
2372__rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
2373{
2374    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
2375    _BidirectionalIterator __lm1 = _VSTD::prev(__last);
2376    value_type __tmp = _VSTD::move(*__lm1);
2377    _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
2378    *__first = _VSTD::move(__tmp);
2379    return __fp1;
2380}
2381
2382template <class _ForwardIterator>
2383_LIBCPP_CONSTEXPR_AFTER_CXX14 _ForwardIterator
2384__rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2385{
2386    _ForwardIterator __i = __middle;
2387    while (true)
2388    {
2389        swap(*__first, *__i);
2390        ++__first;
2391        if (++__i == __last)
2392            break;
2393        if (__first == __middle)
2394            __middle = __i;
2395    }
2396    _ForwardIterator __r = __first;
2397    if (__first != __middle)
2398    {
2399        __i = __middle;
2400        while (true)
2401        {
2402            swap(*__first, *__i);
2403            ++__first;
2404            if (++__i == __last)
2405            {
2406                if (__first == __middle)
2407                    break;
2408                __i = __middle;
2409            }
2410            else if (__first == __middle)
2411                __middle = __i;
2412        }
2413    }
2414    return __r;
2415}
2416
2417template<typename _Integral>
2418inline _LIBCPP_INLINE_VISIBILITY
2419_LIBCPP_CONSTEXPR_AFTER_CXX14 _Integral
2420__algo_gcd(_Integral __x, _Integral __y)
2421{
2422    do
2423    {
2424        _Integral __t = __x % __y;
2425        __x = __y;
2426        __y = __t;
2427    } while (__y);
2428    return __x;
2429}
2430
2431template<typename _RandomAccessIterator>
2432_LIBCPP_CONSTEXPR_AFTER_CXX14 _RandomAccessIterator
2433__rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
2434{
2435    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2436    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
2437
2438    const difference_type __m1 = __middle - __first;
2439    const difference_type __m2 = __last - __middle;
2440    if (__m1 == __m2)
2441    {
2442        _VSTD::swap_ranges(__first, __middle, __middle);
2443        return __middle;
2444    }
2445    const difference_type __g = _VSTD::__algo_gcd(__m1, __m2);
2446    for (_RandomAccessIterator __p = __first + __g; __p != __first;)
2447    {
2448        value_type __t(_VSTD::move(*--__p));
2449        _RandomAccessIterator __p1 = __p;
2450        _RandomAccessIterator __p2 = __p1 + __m1;
2451        do
2452        {
2453            *__p1 = _VSTD::move(*__p2);
2454            __p1 = __p2;
2455            const difference_type __d = __last - __p2;
2456            if (__m1 < __d)
2457                __p2 += __m1;
2458            else
2459                __p2 = __first + (__m1 - __d);
2460        } while (__p2 != __p);
2461        *__p1 = _VSTD::move(__t);
2462    }
2463    return __first + __m2;
2464}
2465
2466template <class _ForwardIterator>
2467inline _LIBCPP_INLINE_VISIBILITY
2468_LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
2469__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
2470         _VSTD::forward_iterator_tag)
2471{
2472    typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type;
2473    if (_VSTD::is_trivially_move_assignable<value_type>::value)
2474    {
2475        if (_VSTD::next(__first) == __middle)
2476            return _VSTD::__rotate_left(__first, __last);
2477    }
2478    return _VSTD::__rotate_forward(__first, __middle, __last);
2479}
2480
2481template <class _BidirectionalIterator>
2482inline _LIBCPP_INLINE_VISIBILITY
2483_LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator
2484__rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
2485         _VSTD::bidirectional_iterator_tag)
2486{
2487    typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type;
2488    if (_VSTD::is_trivially_move_assignable<value_type>::value)
2489    {
2490        if (_VSTD::next(__first) == __middle)
2491            return _VSTD::__rotate_left(__first, __last);
2492        if (_VSTD::next(__middle) == __last)
2493            return _VSTD::__rotate_right(__first, __last);
2494    }
2495    return _VSTD::__rotate_forward(__first, __middle, __last);
2496}
2497
2498template <class _RandomAccessIterator>
2499inline _LIBCPP_INLINE_VISIBILITY
2500_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator
2501__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
2502         _VSTD::random_access_iterator_tag)
2503{
2504    typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
2505    if (_VSTD::is_trivially_move_assignable<value_type>::value)
2506    {
2507        if (_VSTD::next(__first) == __middle)
2508            return _VSTD::__rotate_left(__first, __last);
2509        if (_VSTD::next(__middle) == __last)
2510            return _VSTD::__rotate_right(__first, __last);
2511        return _VSTD::__rotate_gcd(__first, __middle, __last);
2512    }
2513    return _VSTD::__rotate_forward(__first, __middle, __last);
2514}
2515
2516template <class _ForwardIterator>
2517inline _LIBCPP_INLINE_VISIBILITY
2518_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
2519rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2520{
2521    if (__first == __middle)
2522        return __last;
2523    if (__middle == __last)
2524        return __first;
2525    return _VSTD::__rotate(__first, __middle, __last,
2526                           typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());
2527}
2528
2529// rotate_copy
2530
2531template <class _ForwardIterator, class _OutputIterator>
2532inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2533_OutputIterator
2534rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
2535{
2536    return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));
2537}
2538
2539// min_element
2540
2541template <class _ForwardIterator, class _Compare>
2542_LIBCPP_NODISCARD_EXT inline
2543_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2544_ForwardIterator
2545min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2546{
2547    static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value,
2548        "std::min_element requires a ForwardIterator");
2549    if (__first != __last)
2550    {
2551        _ForwardIterator __i = __first;
2552        while (++__i != __last)
2553            if (__comp(*__i, *__first))
2554                __first = __i;
2555    }
2556    return __first;
2557}
2558
2559template <class _ForwardIterator>
2560_LIBCPP_NODISCARD_EXT inline
2561_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2562_ForwardIterator
2563min_element(_ForwardIterator __first, _ForwardIterator __last)
2564{
2565    return _VSTD::min_element(__first, __last,
2566              __less<typename iterator_traits<_ForwardIterator>::value_type>());
2567}
2568
2569// min
2570
2571template <class _Tp, class _Compare>
2572_LIBCPP_NODISCARD_EXT inline
2573_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2574const _Tp&
2575min(const _Tp& __a, const _Tp& __b, _Compare __comp)
2576{
2577    return __comp(__b, __a) ? __b : __a;
2578}
2579
2580template <class _Tp>
2581_LIBCPP_NODISCARD_EXT inline
2582_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2583const _Tp&
2584min(const _Tp& __a, const _Tp& __b)
2585{
2586    return _VSTD::min(__a, __b, __less<_Tp>());
2587}
2588
2589#ifndef _LIBCPP_CXX03_LANG
2590
2591template<class _Tp, class _Compare>
2592_LIBCPP_NODISCARD_EXT inline
2593_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2594_Tp
2595min(initializer_list<_Tp> __t, _Compare __comp)
2596{
2597    return *_VSTD::min_element(__t.begin(), __t.end(), __comp);
2598}
2599
2600template<class _Tp>
2601_LIBCPP_NODISCARD_EXT inline
2602_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2603_Tp
2604min(initializer_list<_Tp> __t)
2605{
2606    return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>());
2607}
2608
2609#endif  // _LIBCPP_CXX03_LANG
2610
2611// max_element
2612
2613template <class _ForwardIterator, class _Compare>
2614_LIBCPP_NODISCARD_EXT inline
2615_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2616_ForwardIterator
2617max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2618{
2619    static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value,
2620        "std::max_element requires a ForwardIterator");
2621    if (__first != __last)
2622    {
2623        _ForwardIterator __i = __first;
2624        while (++__i != __last)
2625            if (__comp(*__first, *__i))
2626                __first = __i;
2627    }
2628    return __first;
2629}
2630
2631
2632template <class _ForwardIterator>
2633_LIBCPP_NODISCARD_EXT inline
2634_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2635_ForwardIterator
2636max_element(_ForwardIterator __first, _ForwardIterator __last)
2637{
2638    return _VSTD::max_element(__first, __last,
2639              __less<typename iterator_traits<_ForwardIterator>::value_type>());
2640}
2641
2642// max
2643
2644template <class _Tp, class _Compare>
2645_LIBCPP_NODISCARD_EXT inline
2646_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2647const _Tp&
2648max(const _Tp& __a, const _Tp& __b, _Compare __comp)
2649{
2650    return __comp(__a, __b) ? __b : __a;
2651}
2652
2653template <class _Tp>
2654_LIBCPP_NODISCARD_EXT inline
2655_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2656const _Tp&
2657max(const _Tp& __a, const _Tp& __b)
2658{
2659    return _VSTD::max(__a, __b, __less<_Tp>());
2660}
2661
2662#ifndef _LIBCPP_CXX03_LANG
2663
2664template<class _Tp, class _Compare>
2665_LIBCPP_NODISCARD_EXT inline
2666_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2667_Tp
2668max(initializer_list<_Tp> __t, _Compare __comp)
2669{
2670    return *_VSTD::max_element(__t.begin(), __t.end(), __comp);
2671}
2672
2673template<class _Tp>
2674_LIBCPP_NODISCARD_EXT inline
2675_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2676_Tp
2677max(initializer_list<_Tp> __t)
2678{
2679    return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>());
2680}
2681
2682#endif  // _LIBCPP_CXX03_LANG
2683
2684#if _LIBCPP_STD_VER > 14
2685// clamp
2686template<class _Tp, class _Compare>
2687_LIBCPP_NODISCARD_EXT inline
2688_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
2689const _Tp&
2690clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
2691{
2692    _LIBCPP_ASSERT(!__comp(__hi, __lo), "Bad bounds passed to std::clamp");
2693    return __comp(__v, __lo) ? __lo : __comp(__hi, __v) ? __hi : __v;
2694
2695}
2696
2697template<class _Tp>
2698_LIBCPP_NODISCARD_EXT inline
2699_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
2700const _Tp&
2701clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi)
2702{
2703    return _VSTD::clamp(__v, __lo, __hi, __less<_Tp>());
2704}
2705#endif
2706
2707// minmax_element
2708
2709template <class _ForwardIterator, class _Compare>
2710_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX11
2711pair<_ForwardIterator, _ForwardIterator>
2712minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2713{
2714  static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value,
2715        "std::minmax_element requires a ForwardIterator");
2716  pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);
2717  if (__first != __last)
2718  {
2719      if (++__first != __last)
2720      {
2721          if (__comp(*__first, *__result.first))
2722              __result.first = __first;
2723          else
2724              __result.second = __first;
2725          while (++__first != __last)
2726          {
2727              _ForwardIterator __i = __first;
2728              if (++__first == __last)
2729              {
2730                  if (__comp(*__i, *__result.first))
2731                      __result.first = __i;
2732                  else if (!__comp(*__i, *__result.second))
2733                      __result.second = __i;
2734                  break;
2735              }
2736              else
2737              {
2738                  if (__comp(*__first, *__i))
2739                  {
2740                      if (__comp(*__first, *__result.first))
2741                          __result.first = __first;
2742                      if (!__comp(*__i, *__result.second))
2743                          __result.second = __i;
2744                  }
2745                  else
2746                  {
2747                      if (__comp(*__i, *__result.first))
2748                          __result.first = __i;
2749                      if (!__comp(*__first, *__result.second))
2750                          __result.second = __first;
2751                  }
2752              }
2753          }
2754      }
2755  }
2756  return __result;
2757}
2758
2759template <class _ForwardIterator>
2760_LIBCPP_NODISCARD_EXT inline
2761_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2762pair<_ForwardIterator, _ForwardIterator>
2763minmax_element(_ForwardIterator __first, _ForwardIterator __last)
2764{
2765    return _VSTD::minmax_element(__first, __last,
2766              __less<typename iterator_traits<_ForwardIterator>::value_type>());
2767}
2768
2769// minmax
2770
2771template<class _Tp, class _Compare>
2772_LIBCPP_NODISCARD_EXT inline
2773_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2774pair<const _Tp&, const _Tp&>
2775minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
2776{
2777    return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) :
2778                              pair<const _Tp&, const _Tp&>(__a, __b);
2779}
2780
2781template<class _Tp>
2782_LIBCPP_NODISCARD_EXT inline
2783_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2784pair<const _Tp&, const _Tp&>
2785minmax(const _Tp& __a, const _Tp& __b)
2786{
2787    return _VSTD::minmax(__a, __b, __less<_Tp>());
2788}
2789
2790#ifndef _LIBCPP_CXX03_LANG
2791
2792template<class _Tp, class _Compare>
2793_LIBCPP_NODISCARD_EXT inline
2794_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2795pair<_Tp, _Tp>
2796minmax(initializer_list<_Tp> __t, _Compare __comp)
2797{
2798    typedef typename initializer_list<_Tp>::const_iterator _Iter;
2799    _Iter __first = __t.begin();
2800    _Iter __last  = __t.end();
2801    pair<_Tp, _Tp> __result(*__first, *__first);
2802
2803    ++__first;
2804    if (__t.size() % 2 == 0)
2805    {
2806        if (__comp(*__first,  __result.first))
2807            __result.first  = *__first;
2808        else
2809            __result.second = *__first;
2810        ++__first;
2811    }
2812
2813    while (__first != __last)
2814    {
2815        _Tp __prev = *__first++;
2816        if (__comp(*__first, __prev)) {
2817            if ( __comp(*__first, __result.first)) __result.first  = *__first;
2818            if (!__comp(__prev, __result.second))  __result.second = __prev;
2819            }
2820        else {
2821            if ( __comp(__prev, __result.first))    __result.first  = __prev;
2822            if (!__comp(*__first, __result.second)) __result.second = *__first;
2823            }
2824
2825        __first++;
2826    }
2827    return __result;
2828}
2829
2830template<class _Tp>
2831_LIBCPP_NODISCARD_EXT inline
2832_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2833pair<_Tp, _Tp>
2834minmax(initializer_list<_Tp> __t)
2835{
2836    return _VSTD::minmax(__t, __less<_Tp>());
2837}
2838
2839#endif  // _LIBCPP_CXX03_LANG
2840
2841// random_shuffle
2842
2843// __independent_bits_engine
2844
2845template <unsigned long long _Xp, size_t _Rp>
2846struct __log2_imp
2847{
2848    static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp
2849                                           : __log2_imp<_Xp, _Rp - 1>::value;
2850};
2851
2852template <unsigned long long _Xp>
2853struct __log2_imp<_Xp, 0>
2854{
2855    static const size_t value = 0;
2856};
2857
2858template <size_t _Rp>
2859struct __log2_imp<0, _Rp>
2860{
2861    static const size_t value = _Rp + 1;
2862};
2863
2864template <class _UIntType, _UIntType _Xp>
2865struct __log2
2866{
2867    static const size_t value = __log2_imp<_Xp,
2868                                         sizeof(_UIntType) * __CHAR_BIT__ - 1>::value;
2869};
2870
2871template<class _Engine, class _UIntType>
2872class __independent_bits_engine
2873{
2874public:
2875    // types
2876    typedef _UIntType result_type;
2877
2878private:
2879    typedef typename _Engine::result_type _Engine_result_type;
2880    typedef typename conditional
2881        <
2882            sizeof(_Engine_result_type) <= sizeof(result_type),
2883                result_type,
2884                _Engine_result_type
2885        >::type _Working_result_type;
2886
2887    _Engine& __e_;
2888    size_t __w_;
2889    size_t __w0_;
2890    size_t __n_;
2891    size_t __n0_;
2892    _Working_result_type __y0_;
2893    _Working_result_type __y1_;
2894    _Engine_result_type __mask0_;
2895    _Engine_result_type __mask1_;
2896
2897#ifdef _LIBCPP_CXX03_LANG
2898    static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
2899                                          + _Working_result_type(1);
2900#else
2901    static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()
2902                                                      + _Working_result_type(1);
2903#endif
2904    static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value;
2905    static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits;
2906    static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
2907
2908public:
2909    // constructors and seeding functions
2910    __independent_bits_engine(_Engine& __e, size_t __w);
2911
2912    // generating functions
2913    result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
2914
2915private:
2916    result_type __eval(false_type);
2917    result_type __eval(true_type);
2918};
2919
2920template<class _Engine, class _UIntType>
2921__independent_bits_engine<_Engine, _UIntType>
2922    ::__independent_bits_engine(_Engine& __e, size_t __w)
2923        : __e_(__e),
2924          __w_(__w)
2925{
2926    __n_ = __w_ / __m + (__w_ % __m != 0);
2927    __w0_ = __w_ / __n_;
2928    if (_Rp == 0)
2929        __y0_ = _Rp;
2930    else if (__w0_ < _WDt)
2931        __y0_ = (_Rp >> __w0_) << __w0_;
2932    else
2933        __y0_ = 0;
2934    if (_Rp - __y0_ > __y0_ / __n_)
2935    {
2936        ++__n_;
2937        __w0_ = __w_ / __n_;
2938        if (__w0_ < _WDt)
2939            __y0_ = (_Rp >> __w0_) << __w0_;
2940        else
2941            __y0_ = 0;
2942    }
2943    __n0_ = __n_ - __w_ % __n_;
2944    if (__w0_ < _WDt - 1)
2945        __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1);
2946    else
2947        __y1_ = 0;
2948    __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :
2949                          _Engine_result_type(0);
2950    __mask1_ = __w0_ < _EDt - 1 ?
2951                               _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :
2952                               _Engine_result_type(~0);
2953}
2954
2955template<class _Engine, class _UIntType>
2956inline
2957_UIntType
2958__independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
2959{
2960    return static_cast<result_type>(__e_() & __mask0_);
2961}
2962
2963template<class _Engine, class _UIntType>
2964_UIntType
2965__independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
2966{
2967    const size_t _WRt = numeric_limits<result_type>::digits;
2968    result_type _Sp = 0;
2969    for (size_t __k = 0; __k < __n0_; ++__k)
2970    {
2971        _Engine_result_type __u;
2972        do
2973        {
2974            __u = __e_() - _Engine::min();
2975        } while (__u >= __y0_);
2976        if (__w0_ < _WRt)
2977            _Sp <<= __w0_;
2978        else
2979            _Sp = 0;
2980        _Sp += __u & __mask0_;
2981    }
2982    for (size_t __k = __n0_; __k < __n_; ++__k)
2983    {
2984        _Engine_result_type __u;
2985        do
2986        {
2987            __u = __e_() - _Engine::min();
2988        } while (__u >= __y1_);
2989        if (__w0_ < _WRt - 1)
2990            _Sp <<= __w0_ + 1;
2991        else
2992            _Sp = 0;
2993        _Sp += __u & __mask1_;
2994    }
2995    return _Sp;
2996}
2997
2998// uniform_int_distribution
2999
3000template<class _IntType = int>
3001class uniform_int_distribution
3002{
3003public:
3004    // types
3005    typedef _IntType result_type;
3006
3007    class param_type
3008    {
3009        result_type __a_;
3010        result_type __b_;
3011    public:
3012        typedef uniform_int_distribution distribution_type;
3013
3014        explicit param_type(result_type __a = 0,
3015                            result_type __b = numeric_limits<result_type>::max())
3016            : __a_(__a), __b_(__b) {}
3017
3018        result_type a() const {return __a_;}
3019        result_type b() const {return __b_;}
3020
3021        friend bool operator==(const param_type& __x, const param_type& __y)
3022            {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
3023        friend bool operator!=(const param_type& __x, const param_type& __y)
3024            {return !(__x == __y);}
3025    };
3026
3027private:
3028    param_type __p_;
3029
3030public:
3031    // constructors and reset functions
3032    explicit uniform_int_distribution(result_type __a = 0,
3033                                      result_type __b = numeric_limits<result_type>::max())
3034        : __p_(param_type(__a, __b)) {}
3035    explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
3036    void reset() {}
3037
3038    // generating functions
3039    template<class _URNG> result_type operator()(_URNG& __g)
3040        {return (*this)(__g, __p_);}
3041    template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3042
3043    // property functions
3044    result_type a() const {return __p_.a();}
3045    result_type b() const {return __p_.b();}
3046
3047    param_type param() const {return __p_;}
3048    void param(const param_type& __p) {__p_ = __p;}
3049
3050    result_type min() const {return a();}
3051    result_type max() const {return b();}
3052
3053    friend bool operator==(const uniform_int_distribution& __x,
3054                           const uniform_int_distribution& __y)
3055        {return __x.__p_ == __y.__p_;}
3056    friend bool operator!=(const uniform_int_distribution& __x,
3057                           const uniform_int_distribution& __y)
3058            {return !(__x == __y);}
3059};
3060
3061template<class _IntType>
3062template<class _URNG>
3063typename uniform_int_distribution<_IntType>::result_type
3064uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
3065_LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
3066{
3067    typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
3068                                            uint32_t, uint64_t>::type _UIntType;
3069    const _UIntType _Rp = _UIntType(__p.b()) - _UIntType(__p.a()) + _UIntType(1);
3070    if (_Rp == 1)
3071        return __p.a();
3072    const size_t _Dt = numeric_limits<_UIntType>::digits;
3073    typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
3074    if (_Rp == 0)
3075        return static_cast<result_type>(_Eng(__g, _Dt)());
3076    size_t __w = _Dt - __libcpp_clz(_Rp) - 1;
3077    if ((_Rp & (numeric_limits<_UIntType>::max() >> (_Dt - __w))) != 0)
3078        ++__w;
3079    _Eng __e(__g, __w);
3080    _UIntType __u;
3081    do
3082    {
3083        __u = __e();
3084    } while (__u >= _Rp);
3085    return static_cast<result_type>(__u + __p.a());
3086}
3087
3088#if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \
3089  || defined(_LIBCPP_BUILDING_LIBRARY)
3090class _LIBCPP_TYPE_VIS __rs_default;
3091
3092_LIBCPP_FUNC_VIS __rs_default __rs_get();
3093
3094class _LIBCPP_TYPE_VIS __rs_default
3095{
3096    static unsigned __c_;
3097
3098    __rs_default();
3099public:
3100    typedef uint_fast32_t result_type;
3101
3102    static const result_type _Min = 0;
3103    static const result_type _Max = 0xFFFFFFFF;
3104
3105    __rs_default(const __rs_default&);
3106    ~__rs_default();
3107
3108    result_type operator()();
3109
3110    static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
3111    static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
3112
3113    friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
3114};
3115
3116_LIBCPP_FUNC_VIS __rs_default __rs_get();
3117
3118template <class _RandomAccessIterator>
3119_LIBCPP_DEPRECATED_IN_CXX14 void
3120random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
3121{
3122    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3123    typedef uniform_int_distribution<ptrdiff_t> _Dp;
3124    typedef typename _Dp::param_type _Pp;
3125    difference_type __d = __last - __first;
3126    if (__d > 1)
3127    {
3128        _Dp __uid;
3129        __rs_default __g = __rs_get();
3130        for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
3131        {
3132            difference_type __i = __uid(__g, _Pp(0, __d));
3133            if (__i != difference_type(0))
3134                swap(*__first, *(__first + __i));
3135        }
3136    }
3137}
3138
3139template <class _RandomAccessIterator, class _RandomNumberGenerator>
3140_LIBCPP_DEPRECATED_IN_CXX14 void
3141random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3142#ifndef _LIBCPP_CXX03_LANG
3143               _RandomNumberGenerator&& __rand)
3144#else
3145               _RandomNumberGenerator& __rand)
3146#endif
3147{
3148    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3149    difference_type __d = __last - __first;
3150    if (__d > 1)
3151    {
3152        for (--__last; __first < __last; ++__first, (void) --__d)
3153        {
3154            difference_type __i = __rand(__d);
3155            if (__i != difference_type(0))
3156              swap(*__first, *(__first + __i));
3157        }
3158    }
3159}
3160#endif
3161
3162template <class _PopulationIterator, class _SampleIterator, class _Distance,
3163          class _UniformRandomNumberGenerator>
3164_LIBCPP_INLINE_VISIBILITY
3165_SampleIterator __sample(_PopulationIterator __first,
3166                         _PopulationIterator __last, _SampleIterator __output_iter,
3167                         _Distance __n,
3168                         _UniformRandomNumberGenerator & __g,
3169                         input_iterator_tag) {
3170
3171  _Distance __k = 0;
3172  for (; __first != __last && __k < __n; ++__first, (void) ++__k)
3173    __output_iter[__k] = *__first;
3174  _Distance __sz = __k;
3175  for (; __first != __last; ++__first, (void) ++__k) {
3176    _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g);
3177    if (__r < __sz)
3178      __output_iter[__r] = *__first;
3179  }
3180  return __output_iter + _VSTD::min(__n, __k);
3181}
3182
3183template <class _PopulationIterator, class _SampleIterator, class _Distance,
3184          class _UniformRandomNumberGenerator>
3185_LIBCPP_INLINE_VISIBILITY
3186_SampleIterator __sample(_PopulationIterator __first,
3187                         _PopulationIterator __last, _SampleIterator __output_iter,
3188                         _Distance __n,
3189                         _UniformRandomNumberGenerator& __g,
3190                         forward_iterator_tag) {
3191  _Distance __unsampled_sz = _VSTD::distance(__first, __last);
3192  for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
3193    _Distance __r =
3194        _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g);
3195    if (__r < __n) {
3196      *__output_iter++ = *__first;
3197      --__n;
3198    }
3199  }
3200  return __output_iter;
3201}
3202
3203template <class _PopulationIterator, class _SampleIterator, class _Distance,
3204          class _UniformRandomNumberGenerator>
3205_LIBCPP_INLINE_VISIBILITY
3206_SampleIterator __sample(_PopulationIterator __first,
3207                         _PopulationIterator __last, _SampleIterator __output_iter,
3208                         _Distance __n, _UniformRandomNumberGenerator& __g) {
3209  typedef typename iterator_traits<_PopulationIterator>::iterator_category
3210        _PopCategory;
3211  typedef typename iterator_traits<_PopulationIterator>::difference_type
3212        _Difference;
3213  static_assert(__is_cpp17_forward_iterator<_PopulationIterator>::value ||
3214                __is_cpp17_random_access_iterator<_SampleIterator>::value,
3215                "SampleIterator must meet the requirements of RandomAccessIterator");
3216  typedef typename common_type<_Distance, _Difference>::type _CommonType;
3217  _LIBCPP_ASSERT(__n >= 0, "N must be a positive number.");
3218  return _VSTD::__sample(
3219      __first, __last, __output_iter, _CommonType(__n),
3220      __g, _PopCategory());
3221}
3222
3223#if _LIBCPP_STD_VER > 14
3224template <class _PopulationIterator, class _SampleIterator, class _Distance,
3225          class _UniformRandomNumberGenerator>
3226inline _LIBCPP_INLINE_VISIBILITY
3227_SampleIterator sample(_PopulationIterator __first,
3228                       _PopulationIterator __last, _SampleIterator __output_iter,
3229                       _Distance __n, _UniformRandomNumberGenerator&& __g) {
3230    return _VSTD::__sample(__first, __last, __output_iter, __n, __g);
3231}
3232#endif // _LIBCPP_STD_VER > 14
3233
3234template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
3235    void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3236                 _UniformRandomNumberGenerator&& __g)
3237{
3238    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3239    typedef uniform_int_distribution<ptrdiff_t> _Dp;
3240    typedef typename _Dp::param_type _Pp;
3241    difference_type __d = __last - __first;
3242    if (__d > 1)
3243    {
3244        _Dp __uid;
3245        for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
3246        {
3247            difference_type __i = __uid(__g, _Pp(0, __d));
3248            if (__i != difference_type(0))
3249                swap(*__first, *(__first + __i));
3250        }
3251    }
3252}
3253
3254template <class _InputIterator, class _Predicate>
3255_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
3256is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3257{
3258    for (; __first != __last; ++__first)
3259        if (!__pred(*__first))
3260            break;
3261    if ( __first == __last )
3262        return true;
3263    ++__first;
3264    for (; __first != __last; ++__first)
3265        if (__pred(*__first))
3266            return false;
3267    return true;
3268}
3269
3270// partition
3271
3272template <class _Predicate, class _ForwardIterator>
3273_ForwardIterator
3274__partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
3275{
3276    while (true)
3277    {
3278        if (__first == __last)
3279            return __first;
3280        if (!__pred(*__first))
3281            break;
3282        ++__first;
3283    }
3284    for (_ForwardIterator __p = __first; ++__p != __last;)
3285    {
3286        if (__pred(*__p))
3287        {
3288            swap(*__first, *__p);
3289            ++__first;
3290        }
3291    }
3292    return __first;
3293}
3294
3295template <class _Predicate, class _BidirectionalIterator>
3296_BidirectionalIterator
3297__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3298            bidirectional_iterator_tag)
3299{
3300    while (true)
3301    {
3302        while (true)
3303        {
3304            if (__first == __last)
3305                return __first;
3306            if (!__pred(*__first))
3307                break;
3308            ++__first;
3309        }
3310        do
3311        {
3312            if (__first == --__last)
3313                return __first;
3314        } while (!__pred(*__last));
3315        swap(*__first, *__last);
3316        ++__first;
3317    }
3318}
3319
3320template <class _ForwardIterator, class _Predicate>
3321inline _LIBCPP_INLINE_VISIBILITY
3322_ForwardIterator
3323partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3324{
3325    return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>
3326                            (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3327}
3328
3329// partition_copy
3330
3331template <class _InputIterator, class _OutputIterator1,
3332          class _OutputIterator2, class _Predicate>
3333_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_OutputIterator1, _OutputIterator2>
3334partition_copy(_InputIterator __first, _InputIterator __last,
3335               _OutputIterator1 __out_true, _OutputIterator2 __out_false,
3336               _Predicate __pred)
3337{
3338    for (; __first != __last; ++__first)
3339    {
3340        if (__pred(*__first))
3341        {
3342            *__out_true = *__first;
3343            ++__out_true;
3344        }
3345        else
3346        {
3347            *__out_false = *__first;
3348            ++__out_false;
3349        }
3350    }
3351    return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
3352}
3353
3354// partition_point
3355
3356template<class _ForwardIterator, class _Predicate>
3357_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
3358partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3359{
3360    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3361    difference_type __len = _VSTD::distance(__first, __last);
3362    while (__len != 0)
3363    {
3364        difference_type __l2 = _VSTD::__half_positive(__len);
3365        _ForwardIterator __m = __first;
3366        _VSTD::advance(__m, __l2);
3367        if (__pred(*__m))
3368        {
3369            __first = ++__m;
3370            __len -= __l2 + 1;
3371        }
3372        else
3373            __len = __l2;
3374    }
3375    return __first;
3376}
3377
3378// stable_partition
3379
3380template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
3381_ForwardIterator
3382__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3383                   _Distance __len, _Pair __p, forward_iterator_tag __fit)
3384{
3385    // *__first is known to be false
3386    // __len >= 1
3387    if (__len == 1)
3388        return __first;
3389    if (__len == 2)
3390    {
3391        _ForwardIterator __m = __first;
3392        if (__pred(*++__m))
3393        {
3394            swap(*__first, *__m);
3395            return __m;
3396        }
3397        return __first;
3398    }
3399    if (__len <= __p.second)
3400    {   // The buffer is big enough to use
3401        typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3402        __destruct_n __d(0);
3403        unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3404        // Move the falses into the temporary buffer, and the trues to the front of the line
3405        // Update __first to always point to the end of the trues
3406        value_type* __t = __p.first;
3407        ::new(__t) value_type(_VSTD::move(*__first));
3408        __d.template __incr<value_type>();
3409        ++__t;
3410        _ForwardIterator __i = __first;
3411        while (++__i != __last)
3412        {
3413            if (__pred(*__i))
3414            {
3415                *__first = _VSTD::move(*__i);
3416                ++__first;
3417            }
3418            else
3419            {
3420                ::new(__t) value_type(_VSTD::move(*__i));
3421                __d.template __incr<value_type>();
3422                ++__t;
3423            }
3424        }
3425        // All trues now at start of range, all falses in buffer
3426        // Move falses back into range, but don't mess up __first which points to first false
3427        __i = __first;
3428        for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i)
3429            *__i = _VSTD::move(*__t2);
3430        // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3431        return __first;
3432    }
3433    // Else not enough buffer, do in place
3434    // __len >= 3
3435    _ForwardIterator __m = __first;
3436    _Distance __len2 = __len / 2;  // __len2 >= 2
3437    _VSTD::advance(__m, __len2);
3438    // recurse on [__first, __m), *__first know to be false
3439    // F?????????????????
3440    // f       m         l
3441    typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3442    _ForwardIterator __first_false = _VSTD::__stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
3443    // TTTFFFFF??????????
3444    // f  ff   m         l
3445    // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3446    _ForwardIterator __m1 = __m;
3447    _ForwardIterator __second_false = __last;
3448    _Distance __len_half = __len - __len2;
3449    while (__pred(*__m1))
3450    {
3451        if (++__m1 == __last)
3452            goto __second_half_done;
3453        --__len_half;
3454    }
3455    // TTTFFFFFTTTF??????
3456    // f  ff   m  m1     l
3457    __second_false = _VSTD::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
3458__second_half_done:
3459    // TTTFFFFFTTTTTFFFFF
3460    // f  ff   m    sf   l
3461    return _VSTD::rotate(__first_false, __m, __second_false);
3462    // TTTTTTTTFFFFFFFFFF
3463    //         |
3464}
3465
3466struct __return_temporary_buffer
3467{
3468    template <class _Tp>
3469    _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}
3470};
3471
3472template <class _Predicate, class _ForwardIterator>
3473_ForwardIterator
3474__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3475                   forward_iterator_tag)
3476{
3477    const unsigned __alloc_limit = 3;  // might want to make this a function of trivial assignment
3478    // Either prove all true and return __first or point to first false
3479    while (true)
3480    {
3481        if (__first == __last)
3482            return __first;
3483        if (!__pred(*__first))
3484            break;
3485        ++__first;
3486    }
3487    // We now have a reduced range [__first, __last)
3488    // *__first is known to be false
3489    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3490    typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3491    difference_type __len = _VSTD::distance(__first, __last);
3492    pair<value_type*, ptrdiff_t> __p(0, 0);
3493    unique_ptr<value_type, __return_temporary_buffer> __h;
3494    if (__len >= __alloc_limit)
3495    {
3496        __p = _VSTD::get_temporary_buffer<value_type>(__len);
3497        __h.reset(__p.first);
3498    }
3499    return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type>
3500                             (__first, __last, __pred, __len, __p, forward_iterator_tag());
3501}
3502
3503template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
3504_BidirectionalIterator
3505__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3506                   _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
3507{
3508    // *__first is known to be false
3509    // *__last is known to be true
3510    // __len >= 2
3511    if (__len == 2)
3512    {
3513        swap(*__first, *__last);
3514        return __last;
3515    }
3516    if (__len == 3)
3517    {
3518        _BidirectionalIterator __m = __first;
3519        if (__pred(*++__m))
3520        {
3521            swap(*__first, *__m);
3522            swap(*__m, *__last);
3523            return __last;
3524        }
3525        swap(*__m, *__last);
3526        swap(*__first, *__m);
3527        return __m;
3528    }
3529    if (__len <= __p.second)
3530    {   // The buffer is big enough to use
3531        typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3532        __destruct_n __d(0);
3533        unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3534        // Move the falses into the temporary buffer, and the trues to the front of the line
3535        // Update __first to always point to the end of the trues
3536        value_type* __t = __p.first;
3537        ::new(__t) value_type(_VSTD::move(*__first));
3538        __d.template __incr<value_type>();
3539        ++__t;
3540        _BidirectionalIterator __i = __first;
3541        while (++__i != __last)
3542        {
3543            if (__pred(*__i))
3544            {
3545                *__first = _VSTD::move(*__i);
3546                ++__first;
3547            }
3548            else
3549            {
3550                ::new(__t) value_type(_VSTD::move(*__i));
3551                __d.template __incr<value_type>();
3552                ++__t;
3553            }
3554        }
3555        // move *__last, known to be true
3556        *__first = _VSTD::move(*__i);
3557        __i = ++__first;
3558        // All trues now at start of range, all falses in buffer
3559        // Move falses back into range, but don't mess up __first which points to first false
3560        for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i)
3561            *__i = _VSTD::move(*__t2);
3562        // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3563        return __first;
3564    }
3565    // Else not enough buffer, do in place
3566    // __len >= 4
3567    _BidirectionalIterator __m = __first;
3568    _Distance __len2 = __len / 2;  // __len2 >= 2
3569    _VSTD::advance(__m, __len2);
3570    // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
3571    // F????????????????T
3572    // f       m        l
3573    _BidirectionalIterator __m1 = __m;
3574    _BidirectionalIterator __first_false = __first;
3575    _Distance __len_half = __len2;
3576    while (!__pred(*--__m1))
3577    {
3578        if (__m1 == __first)
3579            goto __first_half_done;
3580        --__len_half;
3581    }
3582    // F???TFFF?????????T
3583    // f   m1  m        l
3584    typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3585    __first_false = _VSTD::__stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3586__first_half_done:
3587    // TTTFFFFF?????????T
3588    // f  ff   m        l
3589    // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3590    __m1 = __m;
3591    _BidirectionalIterator __second_false = __last;
3592    ++__second_false;
3593    __len_half = __len - __len2;
3594    while (__pred(*__m1))
3595    {
3596        if (++__m1 == __last)
3597            goto __second_half_done;
3598        --__len_half;
3599    }
3600    // TTTFFFFFTTTF?????T
3601    // f  ff   m  m1    l
3602    __second_false = _VSTD::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
3603__second_half_done:
3604    // TTTFFFFFTTTTTFFFFF
3605    // f  ff   m    sf  l
3606    return _VSTD::rotate(__first_false, __m, __second_false);
3607    // TTTTTTTTFFFFFFFFFF
3608    //         |
3609}
3610
3611template <class _Predicate, class _BidirectionalIterator>
3612_BidirectionalIterator
3613__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3614                   bidirectional_iterator_tag)
3615{
3616    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3617    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3618    const difference_type __alloc_limit = 4;  // might want to make this a function of trivial assignment
3619    // Either prove all true and return __first or point to first false
3620    while (true)
3621    {
3622        if (__first == __last)
3623            return __first;
3624        if (!__pred(*__first))
3625            break;
3626        ++__first;
3627    }
3628    // __first points to first false, everything prior to __first is already set.
3629    // Either prove [__first, __last) is all false and return __first, or point __last to last true
3630    do
3631    {
3632        if (__first == --__last)
3633            return __first;
3634    } while (!__pred(*__last));
3635    // We now have a reduced range [__first, __last]
3636    // *__first is known to be false
3637    // *__last is known to be true
3638    // __len >= 2
3639    difference_type __len = _VSTD::distance(__first, __last) + 1;
3640    pair<value_type*, ptrdiff_t> __p(0, 0);
3641    unique_ptr<value_type, __return_temporary_buffer> __h;
3642    if (__len >= __alloc_limit)
3643    {
3644        __p = _VSTD::get_temporary_buffer<value_type>(__len);
3645        __h.reset(__p.first);
3646    }
3647    return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type>
3648                             (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3649}
3650
3651template <class _ForwardIterator, class _Predicate>
3652inline _LIBCPP_INLINE_VISIBILITY
3653_ForwardIterator
3654stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3655{
3656    return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type>
3657                             (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3658}
3659
3660// is_sorted_until
3661
3662template <class _ForwardIterator, class _Compare>
3663_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
3664is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3665{
3666    if (__first != __last)
3667    {
3668        _ForwardIterator __i = __first;
3669        while (++__i != __last)
3670        {
3671            if (__comp(*__i, *__first))
3672                return __i;
3673            __first = __i;
3674        }
3675    }
3676    return __last;
3677}
3678
3679template<class _ForwardIterator>
3680_LIBCPP_NODISCARD_EXT inline
3681_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3682_ForwardIterator
3683is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3684{
3685    return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3686}
3687
3688// is_sorted
3689
3690template <class _ForwardIterator, class _Compare>
3691_LIBCPP_NODISCARD_EXT inline
3692_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3693bool
3694is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3695{
3696    return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
3697}
3698
3699template<class _ForwardIterator>
3700_LIBCPP_NODISCARD_EXT inline
3701_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3702bool
3703is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3704{
3705    return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3706}
3707
3708// sort
3709
3710// stable, 2-3 compares, 0-2 swaps
3711
3712template <class _Compare, class _ForwardIterator>
3713unsigned
3714__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
3715{
3716    unsigned __r = 0;
3717    if (!__c(*__y, *__x))          // if x <= y
3718    {
3719        if (!__c(*__z, *__y))      // if y <= z
3720            return __r;            // x <= y && y <= z
3721                                   // x <= y && y > z
3722        swap(*__y, *__z);          // x <= z && y < z
3723        __r = 1;
3724        if (__c(*__y, *__x))       // if x > y
3725        {
3726            swap(*__x, *__y);      // x < y && y <= z
3727            __r = 2;
3728        }
3729        return __r;                // x <= y && y < z
3730    }
3731    if (__c(*__z, *__y))           // x > y, if y > z
3732    {
3733        swap(*__x, *__z);          // x < y && y < z
3734        __r = 1;
3735        return __r;
3736    }
3737    swap(*__x, *__y);              // x > y && y <= z
3738    __r = 1;                       // x < y && x <= z
3739    if (__c(*__z, *__y))           // if y > z
3740    {
3741        swap(*__y, *__z);          // x <= y && y < z
3742        __r = 2;
3743    }
3744    return __r;
3745}                                  // x <= y && y <= z
3746
3747// stable, 3-6 compares, 0-5 swaps
3748
3749template <class _Compare, class _ForwardIterator>
3750unsigned
3751__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3752            _ForwardIterator __x4, _Compare __c)
3753{
3754    unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c);
3755    if (__c(*__x4, *__x3))
3756    {
3757        swap(*__x3, *__x4);
3758        ++__r;
3759        if (__c(*__x3, *__x2))
3760        {
3761            swap(*__x2, *__x3);
3762            ++__r;
3763            if (__c(*__x2, *__x1))
3764            {
3765                swap(*__x1, *__x2);
3766                ++__r;
3767            }
3768        }
3769    }
3770    return __r;
3771}
3772
3773// stable, 4-10 compares, 0-9 swaps
3774
3775template <class _Compare, class _ForwardIterator>
3776_LIBCPP_HIDDEN
3777unsigned
3778__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3779            _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
3780{
3781    unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
3782    if (__c(*__x5, *__x4))
3783    {
3784        swap(*__x4, *__x5);
3785        ++__r;
3786        if (__c(*__x4, *__x3))
3787        {
3788            swap(*__x3, *__x4);
3789            ++__r;
3790            if (__c(*__x3, *__x2))
3791            {
3792                swap(*__x2, *__x3);
3793                ++__r;
3794                if (__c(*__x2, *__x1))
3795                {
3796                    swap(*__x1, *__x2);
3797                    ++__r;
3798                }
3799            }
3800        }
3801    }
3802    return __r;
3803}
3804
3805// Assumes size > 0
3806template <class _Compare, class _BirdirectionalIterator>
3807void
3808__selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3809{
3810    _BirdirectionalIterator __lm1 = __last;
3811    for (--__lm1; __first != __lm1; ++__first)
3812    {
3813        _BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator,
3814                                                        typename add_lvalue_reference<_Compare>::type>
3815                                                       (__first, __last, __comp);
3816        if (__i != __first)
3817            swap(*__first, *__i);
3818    }
3819}
3820
3821template <class _Compare, class _BirdirectionalIterator>
3822void
3823__insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3824{
3825    typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3826    if (__first != __last)
3827    {
3828        _BirdirectionalIterator __i = __first;
3829        for (++__i; __i != __last; ++__i)
3830        {
3831            _BirdirectionalIterator __j = __i;
3832            value_type __t(_VSTD::move(*__j));
3833            for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t,  *--__k); --__j)
3834                *__j = _VSTD::move(*__k);
3835            *__j = _VSTD::move(__t);
3836        }
3837    }
3838}
3839
3840template <class _Compare, class _RandomAccessIterator>
3841void
3842__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3843{
3844    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3845    _RandomAccessIterator __j = __first+2;
3846    _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp);
3847    for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3848    {
3849        if (__comp(*__i, *__j))
3850        {
3851            value_type __t(_VSTD::move(*__i));
3852            _RandomAccessIterator __k = __j;
3853            __j = __i;
3854            do
3855            {
3856                *__j = _VSTD::move(*__k);
3857                __j = __k;
3858            } while (__j != __first && __comp(__t, *--__k));
3859            *__j = _VSTD::move(__t);
3860        }
3861        __j = __i;
3862    }
3863}
3864
3865template <class _Compare, class _RandomAccessIterator>
3866bool
3867__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3868{
3869    switch (__last - __first)
3870    {
3871    case 0:
3872    case 1:
3873        return true;
3874    case 2:
3875        if (__comp(*--__last, *__first))
3876            swap(*__first, *__last);
3877        return true;
3878    case 3:
3879        _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3880        return true;
3881    case 4:
3882        _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3883        return true;
3884    case 5:
3885        _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3886        return true;
3887    }
3888    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3889    _RandomAccessIterator __j = __first+2;
3890    _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp);
3891    const unsigned __limit = 8;
3892    unsigned __count = 0;
3893    for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3894    {
3895        if (__comp(*__i, *__j))
3896        {
3897            value_type __t(_VSTD::move(*__i));
3898            _RandomAccessIterator __k = __j;
3899            __j = __i;
3900            do
3901            {
3902                *__j = _VSTD::move(*__k);
3903                __j = __k;
3904            } while (__j != __first && __comp(__t, *--__k));
3905            *__j = _VSTD::move(__t);
3906            if (++__count == __limit)
3907                return ++__i == __last;
3908        }
3909        __j = __i;
3910    }
3911    return true;
3912}
3913
3914template <class _Compare, class _BirdirectionalIterator>
3915void
3916__insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
3917                      typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
3918{
3919    typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3920    if (__first1 != __last1)
3921    {
3922        __destruct_n __d(0);
3923        unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
3924        value_type* __last2 = __first2;
3925        ::new(__last2) value_type(_VSTD::move(*__first1));
3926        __d.template __incr<value_type>();
3927        for (++__last2; ++__first1 != __last1; ++__last2)
3928        {
3929            value_type* __j2 = __last2;
3930            value_type* __i2 = __j2;
3931            if (__comp(*__first1, *--__i2))
3932            {
3933                ::new(__j2) value_type(_VSTD::move(*__i2));
3934                __d.template __incr<value_type>();
3935                for (--__j2; __i2 != __first2 && __comp(*__first1,  *--__i2); --__j2)
3936                    *__j2 = _VSTD::move(*__i2);
3937                *__j2 = _VSTD::move(*__first1);
3938            }
3939            else
3940            {
3941                ::new(__j2) value_type(_VSTD::move(*__first1));
3942                __d.template __incr<value_type>();
3943            }
3944        }
3945        __h.release();
3946    }
3947}
3948
3949template <class _Compare, class _RandomAccessIterator>
3950void
3951__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3952{
3953    // _Compare is known to be a reference type
3954    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3955    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3956    const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
3957                                    is_trivially_copy_assignable<value_type>::value ? 30 : 6;
3958    while (true)
3959    {
3960    __restart:
3961        difference_type __len = __last - __first;
3962        switch (__len)
3963        {
3964        case 0:
3965        case 1:
3966            return;
3967        case 2:
3968            if (__comp(*--__last, *__first))
3969                swap(*__first, *__last);
3970            return;
3971        case 3:
3972            _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3973            return;
3974        case 4:
3975            _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3976            return;
3977        case 5:
3978            _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3979            return;
3980        }
3981        if (__len <= __limit)
3982        {
3983            _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
3984            return;
3985        }
3986        // __len > 5
3987        _RandomAccessIterator __m = __first;
3988        _RandomAccessIterator __lm1 = __last;
3989        --__lm1;
3990        unsigned __n_swaps;
3991        {
3992        difference_type __delta;
3993        if (__len >= 1000)
3994        {
3995            __delta = __len/2;
3996            __m += __delta;
3997            __delta /= 2;
3998            __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
3999        }
4000        else
4001        {
4002            __delta = __len/2;
4003            __m += __delta;
4004            __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
4005        }
4006        }
4007        // *__m is median
4008        // partition [__first, __m) < *__m and *__m <= [__m, __last)
4009        // (this inhibits tossing elements equivalent to __m around unnecessarily)
4010        _RandomAccessIterator __i = __first;
4011        _RandomAccessIterator __j = __lm1;
4012        // j points beyond range to be tested, *__m is known to be <= *__lm1
4013        // The search going up is known to be guarded but the search coming down isn't.
4014        // Prime the downward search with a guard.
4015        if (!__comp(*__i, *__m))  // if *__first == *__m
4016        {
4017            // *__first == *__m, *__first doesn't go in first part
4018            // manually guard downward moving __j against __i
4019            while (true)
4020            {
4021                if (__i == --__j)
4022                {
4023                    // *__first == *__m, *__m <= all other elements
4024                    // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
4025                    ++__i;  // __first + 1
4026                    __j = __last;
4027                    if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
4028                    {
4029                        while (true)
4030                        {
4031                            if (__i == __j)
4032                                return;  // [__first, __last) all equivalent elements
4033                            if (__comp(*__first, *__i))
4034                            {
4035                                swap(*__i, *__j);
4036                                ++__n_swaps;
4037                                ++__i;
4038                                break;
4039                            }
4040                            ++__i;
4041                        }
4042                    }
4043                    // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
4044                    if (__i == __j)
4045                        return;
4046                    while (true)
4047                    {
4048                        while (!__comp(*__first, *__i))
4049                            ++__i;
4050                        while (__comp(*__first, *--__j))
4051                            ;
4052                        if (__i >= __j)
4053                            break;
4054                        swap(*__i, *__j);
4055                        ++__n_swaps;
4056                        ++__i;
4057                    }
4058                    // [__first, __i) == *__first and *__first < [__i, __last)
4059                    // The first part is sorted, sort the secod part
4060                    // _VSTD::__sort<_Compare>(__i, __last, __comp);
4061                    __first = __i;
4062                    goto __restart;
4063                }
4064                if (__comp(*__j, *__m))
4065                {
4066                    swap(*__i, *__j);
4067                    ++__n_swaps;
4068                    break;  // found guard for downward moving __j, now use unguarded partition
4069                }
4070            }
4071        }
4072        // It is known that *__i < *__m
4073        ++__i;
4074        // j points beyond range to be tested, *__m is known to be <= *__lm1
4075        // if not yet partitioned...
4076        if (__i < __j)
4077        {
4078            // known that *(__i - 1) < *__m
4079            // known that __i <= __m
4080            while (true)
4081            {
4082                // __m still guards upward moving __i
4083                while (__comp(*__i, *__m))
4084                    ++__i;
4085                // It is now known that a guard exists for downward moving __j
4086                while (!__comp(*--__j, *__m))
4087                    ;
4088                if (__i > __j)
4089                    break;
4090                swap(*__i, *__j);
4091                ++__n_swaps;
4092                // It is known that __m != __j
4093                // If __m just moved, follow it
4094                if (__m == __i)
4095                    __m = __j;
4096                ++__i;
4097            }
4098        }
4099        // [__first, __i) < *__m and *__m <= [__i, __last)
4100        if (__i != __m && __comp(*__m, *__i))
4101        {
4102            swap(*__i, *__m);
4103            ++__n_swaps;
4104        }
4105        // [__first, __i) < *__i and *__i <= [__i+1, __last)
4106        // If we were given a perfect partition, see if insertion sort is quick...
4107        if (__n_swaps == 0)
4108        {
4109            bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
4110            if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
4111            {
4112                if (__fs)
4113                    return;
4114                __last = __i;
4115                continue;
4116            }
4117            else
4118            {
4119                if (__fs)
4120                {
4121                    __first = ++__i;
4122                    continue;
4123                }
4124            }
4125        }
4126        // sort smaller range with recursive call and larger with tail recursion elimination
4127        if (__i - __first < __last - __i)
4128        {
4129            _VSTD::__sort<_Compare>(__first, __i, __comp);
4130            // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4131            __first = ++__i;
4132        }
4133        else
4134        {
4135            _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4136            // _VSTD::__sort<_Compare>(__first, __i, __comp);
4137            __last = __i;
4138        }
4139    }
4140}
4141
4142// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
4143template <class _RandomAccessIterator, class _Compare>
4144inline _LIBCPP_INLINE_VISIBILITY
4145void
4146sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4147{
4148    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4149    _VSTD::__sort<_Comp_ref>(__first, __last, _Comp_ref(__comp));
4150}
4151
4152template <class _RandomAccessIterator>
4153inline _LIBCPP_INLINE_VISIBILITY
4154void
4155sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4156{
4157    _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4158}
4159
4160template <class _Tp>
4161inline _LIBCPP_INLINE_VISIBILITY
4162void
4163sort(_Tp** __first, _Tp** __last)
4164{
4165    _VSTD::sort((uintptr_t*)__first, (uintptr_t*)__last, __less<uintptr_t>());
4166}
4167
4168template <class _Tp>
4169inline _LIBCPP_INLINE_VISIBILITY
4170void
4171sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
4172{
4173    _VSTD::sort(__first.base(), __last.base());
4174}
4175
4176template <class _Tp, class _Compare>
4177inline _LIBCPP_INLINE_VISIBILITY
4178void
4179sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
4180{
4181    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4182    _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
4183}
4184
4185_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
4186_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4187_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4188_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4189_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))
4190_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4191_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&))
4192_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4193_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&))
4194_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4195_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4196_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&))
4197_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&))
4198_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&))
4199_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4200
4201_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))
4202_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4203_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4204_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4205_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))
4206_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4207_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&))
4208_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4209_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&))
4210_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4211_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4212_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&))
4213_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&))
4214_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&))
4215_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4216
4217_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&))
4218
4219// lower_bound
4220
4221template <class _Compare, class _ForwardIterator, class _Tp>
4222_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
4223__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4224{
4225    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4226    difference_type __len = _VSTD::distance(__first, __last);
4227    while (__len != 0)
4228    {
4229        difference_type __l2 = _VSTD::__half_positive(__len);
4230        _ForwardIterator __m = __first;
4231        _VSTD::advance(__m, __l2);
4232        if (__comp(*__m, __value_))
4233        {
4234            __first = ++__m;
4235            __len -= __l2 + 1;
4236        }
4237        else
4238            __len = __l2;
4239    }
4240    return __first;
4241}
4242
4243template <class _ForwardIterator, class _Tp, class _Compare>
4244_LIBCPP_NODISCARD_EXT inline
4245_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4246_ForwardIterator
4247lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4248{
4249    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4250    return _VSTD::__lower_bound<_Comp_ref>(__first, __last, __value_, __comp);
4251}
4252
4253template <class _ForwardIterator, class _Tp>
4254_LIBCPP_NODISCARD_EXT inline
4255_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4256_ForwardIterator
4257lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4258{
4259    return _VSTD::lower_bound(__first, __last, __value_,
4260                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4261}
4262
4263// upper_bound
4264
4265template <class _Compare, class _ForwardIterator, class _Tp>
4266_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
4267__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4268{
4269    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4270    difference_type __len = _VSTD::distance(__first, __last);
4271    while (__len != 0)
4272    {
4273        difference_type __l2 = _VSTD::__half_positive(__len);
4274        _ForwardIterator __m = __first;
4275        _VSTD::advance(__m, __l2);
4276        if (__comp(__value_, *__m))
4277            __len = __l2;
4278        else
4279        {
4280            __first = ++__m;
4281            __len -= __l2 + 1;
4282        }
4283    }
4284    return __first;
4285}
4286
4287template <class _ForwardIterator, class _Tp, class _Compare>
4288_LIBCPP_NODISCARD_EXT inline
4289_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4290_ForwardIterator
4291upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4292{
4293    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4294    return _VSTD::__upper_bound<_Comp_ref>(__first, __last, __value_, __comp);
4295}
4296
4297template <class _ForwardIterator, class _Tp>
4298_LIBCPP_NODISCARD_EXT inline
4299_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4300_ForwardIterator
4301upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4302{
4303    return _VSTD::upper_bound(__first, __last, __value_,
4304                             __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
4305}
4306
4307// equal_range
4308
4309template <class _Compare, class _ForwardIterator, class _Tp>
4310_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator>
4311__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4312{
4313    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4314    difference_type __len = _VSTD::distance(__first, __last);
4315    while (__len != 0)
4316    {
4317        difference_type __l2 = _VSTD::__half_positive(__len);
4318        _ForwardIterator __m = __first;
4319        _VSTD::advance(__m, __l2);
4320        if (__comp(*__m, __value_))
4321        {
4322            __first = ++__m;
4323            __len -= __l2 + 1;
4324        }
4325        else if (__comp(__value_, *__m))
4326        {
4327            __last = __m;
4328            __len = __l2;
4329        }
4330        else
4331        {
4332            _ForwardIterator __mp1 = __m;
4333            return pair<_ForwardIterator, _ForwardIterator>
4334                   (
4335                      _VSTD::__lower_bound<_Compare>(__first, __m, __value_, __comp),
4336                      _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value_, __comp)
4337                   );
4338        }
4339    }
4340    return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4341}
4342
4343template <class _ForwardIterator, class _Tp, class _Compare>
4344_LIBCPP_NODISCARD_EXT inline
4345_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4346pair<_ForwardIterator, _ForwardIterator>
4347equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4348{
4349    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4350    return _VSTD::__equal_range<_Comp_ref>(__first, __last, __value_, __comp);
4351}
4352
4353template <class _ForwardIterator, class _Tp>
4354_LIBCPP_NODISCARD_EXT inline
4355_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4356pair<_ForwardIterator, _ForwardIterator>
4357equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4358{
4359    return _VSTD::equal_range(__first, __last, __value_,
4360                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4361}
4362
4363// binary_search
4364
4365template <class _Compare, class _ForwardIterator, class _Tp>
4366inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4367bool
4368__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4369{
4370    __first = _VSTD::__lower_bound<_Compare>(__first, __last, __value_, __comp);
4371    return __first != __last && !__comp(__value_, *__first);
4372}
4373
4374template <class _ForwardIterator, class _Tp, class _Compare>
4375_LIBCPP_NODISCARD_EXT inline
4376_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4377bool
4378binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4379{
4380    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4381    return _VSTD::__binary_search<_Comp_ref>(__first, __last, __value_, __comp);
4382}
4383
4384template <class _ForwardIterator, class _Tp>
4385_LIBCPP_NODISCARD_EXT inline
4386_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4387bool
4388binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4389{
4390    return _VSTD::binary_search(__first, __last, __value_,
4391                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4392}
4393
4394// merge
4395
4396template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4397_LIBCPP_CONSTEXPR_AFTER_CXX17
4398_OutputIterator
4399__merge(_InputIterator1 __first1, _InputIterator1 __last1,
4400        _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4401{
4402    for (; __first1 != __last1; ++__result)
4403    {
4404        if (__first2 == __last2)
4405            return _VSTD::copy(__first1, __last1, __result);
4406        if (__comp(*__first2, *__first1))
4407        {
4408            *__result = *__first2;
4409            ++__first2;
4410        }
4411        else
4412        {
4413            *__result = *__first1;
4414            ++__first1;
4415        }
4416    }
4417    return _VSTD::copy(__first2, __last2, __result);
4418}
4419
4420template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4421inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4422_OutputIterator
4423merge(_InputIterator1 __first1, _InputIterator1 __last1,
4424      _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4425{
4426    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4427    return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4428}
4429
4430template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4431inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4432_OutputIterator
4433merge(_InputIterator1 __first1, _InputIterator1 __last1,
4434      _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4435{
4436    typedef typename iterator_traits<_InputIterator1>::value_type __v1;
4437    typedef typename iterator_traits<_InputIterator2>::value_type __v2;
4438    return _VSTD::merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
4439}
4440
4441// inplace_merge
4442
4443template <class _Compare, class _InputIterator1, class _InputIterator2,
4444          class _OutputIterator>
4445void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
4446                          _InputIterator2 __first2, _InputIterator2 __last2,
4447                          _OutputIterator __result, _Compare __comp)
4448{
4449    for (; __first1 != __last1; ++__result)
4450    {
4451        if (__first2 == __last2)
4452        {
4453            _VSTD::move(__first1, __last1, __result);
4454            return;
4455        }
4456
4457        if (__comp(*__first2, *__first1))
4458        {
4459            *__result = _VSTD::move(*__first2);
4460            ++__first2;
4461        }
4462        else
4463        {
4464            *__result = _VSTD::move(*__first1);
4465            ++__first1;
4466        }
4467    }
4468    // __first2 through __last2 are already in the right spot.
4469}
4470
4471template <class _Compare, class _BidirectionalIterator>
4472void
4473__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4474                _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4475                                 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4476                typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
4477{
4478    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4479    __destruct_n __d(0);
4480    unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4481    if (__len1 <= __len2)
4482    {
4483        value_type* __p = __buff;
4484        for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
4485            ::new(__p) value_type(_VSTD::move(*__i));
4486        _VSTD::__half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);
4487    }
4488    else
4489    {
4490        value_type* __p = __buff;
4491        for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
4492            ::new(__p) value_type(_VSTD::move(*__i));
4493        typedef reverse_iterator<_BidirectionalIterator> _RBi;
4494        typedef reverse_iterator<value_type*> _Rv;
4495        _VSTD::__half_inplace_merge(_Rv(__p), _Rv(__buff),
4496                                    _RBi(__middle), _RBi(__first),
4497                                    _RBi(__last), _VSTD::__invert<_Compare>(__comp));
4498    }
4499}
4500
4501template <class _Compare, class _BidirectionalIterator>
4502void
4503__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4504                _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4505                                 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4506                typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
4507{
4508    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4509    while (true)
4510    {
4511        // if __middle == __last, we're done
4512        if (__len2 == 0)
4513            return;
4514        if (__len1 <= __buff_size || __len2 <= __buff_size)
4515            return _VSTD::__buffered_inplace_merge<_Compare>
4516                   (__first, __middle, __last, __comp, __len1, __len2, __buff);
4517        // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
4518        for (; true; ++__first, (void) --__len1)
4519        {
4520            if (__len1 == 0)
4521                return;
4522            if (__comp(*__middle, *__first))
4523                break;
4524        }
4525        // __first < __middle < __last
4526        // *__first > *__middle
4527        // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4528        //     all elements in:
4529        //         [__first, __m1)  <= [__middle, __m2)
4530        //         [__middle, __m2) <  [__m1, __middle)
4531        //         [__m1, __middle) <= [__m2, __last)
4532        //     and __m1 or __m2 is in the middle of its range
4533        _BidirectionalIterator __m1;  // "median" of [__first, __middle)
4534        _BidirectionalIterator __m2;  // "median" of [__middle, __last)
4535        difference_type __len11;      // distance(__first, __m1)
4536        difference_type __len21;      // distance(__middle, __m2)
4537        // binary search smaller range
4538        if (__len1 < __len2)
4539        {   // __len >= 1, __len2 >= 2
4540            __len21 = __len2 / 2;
4541            __m2 = __middle;
4542            _VSTD::advance(__m2, __len21);
4543            __m1 = _VSTD::__upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4544            __len11 = _VSTD::distance(__first, __m1);
4545        }
4546        else
4547        {
4548            if (__len1 == 1)
4549            {   // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
4550                // It is known *__first > *__middle
4551                swap(*__first, *__middle);
4552                return;
4553            }
4554            // __len1 >= 2, __len2 >= 1
4555            __len11 = __len1 / 2;
4556            __m1 = __first;
4557            _VSTD::advance(__m1, __len11);
4558            __m2 = _VSTD::__lower_bound<_Compare>(__middle, __last, *__m1, __comp);
4559            __len21 = _VSTD::distance(__middle, __m2);
4560        }
4561        difference_type __len12 = __len1 - __len11;  // distance(__m1, __middle)
4562        difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)
4563        // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4564        // swap middle two partitions
4565        __middle = _VSTD::rotate(__m1, __middle, __m2);
4566        // __len12 and __len21 now have swapped meanings
4567        // merge smaller range with recurisve call and larger with tail recursion elimination
4568        if (__len11 + __len21 < __len12 + __len22)
4569        {
4570            _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4571//          _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4572            __first = __middle;
4573            __middle = __m2;
4574            __len1 = __len12;
4575            __len2 = __len22;
4576        }
4577        else
4578        {
4579            _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4580//          _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4581            __last = __middle;
4582            __middle = __m1;
4583            __len1 = __len11;
4584            __len2 = __len21;
4585        }
4586    }
4587}
4588
4589template <class _BidirectionalIterator, class _Compare>
4590inline _LIBCPP_INLINE_VISIBILITY
4591void
4592inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4593              _Compare __comp)
4594{
4595    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4596    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4597    difference_type __len1 = _VSTD::distance(__first, __middle);
4598    difference_type __len2 = _VSTD::distance(__middle, __last);
4599    difference_type __buf_size = _VSTD::min(__len1, __len2);
4600    pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
4601    unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
4602    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4603    return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4604                                            __buf.first, __buf.second);
4605}
4606
4607template <class _BidirectionalIterator>
4608inline _LIBCPP_INLINE_VISIBILITY
4609void
4610inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
4611{
4612    _VSTD::inplace_merge(__first, __middle, __last,
4613                        __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4614}
4615
4616// stable_sort
4617
4618template <class _Compare, class _InputIterator1, class _InputIterator2>
4619void
4620__merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
4621        _InputIterator2 __first2, _InputIterator2 __last2,
4622        typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
4623{
4624    typedef typename iterator_traits<_InputIterator1>::value_type value_type;
4625    __destruct_n __d(0);
4626    unique_ptr<value_type, __destruct_n&> __h(__result, __d);
4627    for (; true; ++__result)
4628    {
4629        if (__first1 == __last1)
4630        {
4631            for (; __first2 != __last2; ++__first2, ++__result, (void)__d.template __incr<value_type>())
4632                ::new (__result) value_type(_VSTD::move(*__first2));
4633            __h.release();
4634            return;
4635        }
4636        if (__first2 == __last2)
4637        {
4638            for (; __first1 != __last1; ++__first1, ++__result, (void)__d.template __incr<value_type>())
4639                ::new (__result) value_type(_VSTD::move(*__first1));
4640            __h.release();
4641            return;
4642        }
4643        if (__comp(*__first2, *__first1))
4644        {
4645            ::new (__result) value_type(_VSTD::move(*__first2));
4646            __d.template __incr<value_type>();
4647            ++__first2;
4648        }
4649        else
4650        {
4651            ::new (__result) value_type(_VSTD::move(*__first1));
4652            __d.template __incr<value_type>();
4653            ++__first1;
4654        }
4655    }
4656}
4657
4658template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4659void
4660__merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
4661        _InputIterator2 __first2, _InputIterator2 __last2,
4662        _OutputIterator __result, _Compare __comp)
4663{
4664    for (; __first1 != __last1; ++__result)
4665    {
4666        if (__first2 == __last2)
4667        {
4668            for (; __first1 != __last1; ++__first1, (void) ++__result)
4669                *__result = _VSTD::move(*__first1);
4670            return;
4671        }
4672        if (__comp(*__first2, *__first1))
4673        {
4674            *__result = _VSTD::move(*__first2);
4675            ++__first2;
4676        }
4677        else
4678        {
4679            *__result = _VSTD::move(*__first1);
4680            ++__first1;
4681        }
4682    }
4683    for (; __first2 != __last2; ++__first2, (void) ++__result)
4684        *__result = _VSTD::move(*__first2);
4685}
4686
4687template <class _Compare, class _RandomAccessIterator>
4688void
4689__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4690              typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4691              typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
4692
4693template <class _Compare, class _RandomAccessIterator>
4694void
4695__stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
4696                   typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4697                   typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
4698{
4699    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4700    switch (__len)
4701    {
4702    case 0:
4703        return;
4704    case 1:
4705        ::new(__first2) value_type(_VSTD::move(*__first1));
4706        return;
4707    case 2:
4708        __destruct_n __d(0);
4709        unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
4710        if (__comp(*--__last1, *__first1))
4711        {
4712            ::new(__first2) value_type(_VSTD::move(*__last1));
4713            __d.template __incr<value_type>();
4714            ++__first2;
4715            ::new(__first2) value_type(_VSTD::move(*__first1));
4716        }
4717        else
4718        {
4719            ::new(__first2) value_type(_VSTD::move(*__first1));
4720            __d.template __incr<value_type>();
4721            ++__first2;
4722            ::new(__first2) value_type(_VSTD::move(*__last1));
4723        }
4724        __h2.release();
4725        return;
4726    }
4727    if (__len <= 8)
4728    {
4729        _VSTD::__insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
4730        return;
4731    }
4732    typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4733    _RandomAccessIterator __m = __first1 + __l2;
4734    _VSTD::__stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
4735    _VSTD::__stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
4736    _VSTD::__merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
4737}
4738
4739template <class _Tp>
4740struct __stable_sort_switch
4741{
4742    static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
4743};
4744
4745template <class _Compare, class _RandomAccessIterator>
4746void
4747__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4748              typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4749              typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
4750{
4751    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4752    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4753    switch (__len)
4754    {
4755    case 0:
4756    case 1:
4757        return;
4758    case 2:
4759        if (__comp(*--__last, *__first))
4760            swap(*__first, *__last);
4761        return;
4762    }
4763    if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4764    {
4765        _VSTD::__insertion_sort<_Compare>(__first, __last, __comp);
4766        return;
4767    }
4768    typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4769    _RandomAccessIterator __m = __first + __l2;
4770    if (__len <= __buff_size)
4771    {
4772        __destruct_n __d(0);
4773        unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4774        _VSTD::__stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4775        __d.__set(__l2, (value_type*)nullptr);
4776        _VSTD::__stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
4777        __d.__set(__len, (value_type*)nullptr);
4778        _VSTD::__merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4779//         _VSTD::__merge<_Compare>(move_iterator<value_type*>(__buff),
4780//                                  move_iterator<value_type*>(__buff + __l2),
4781//                                  move_iterator<_RandomAccessIterator>(__buff + __l2),
4782//                                  move_iterator<_RandomAccessIterator>(__buff + __len),
4783//                                  __first, __comp);
4784        return;
4785    }
4786    _VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4787    _VSTD::__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
4788    _VSTD::__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4789}
4790
4791template <class _RandomAccessIterator, class _Compare>
4792inline _LIBCPP_INLINE_VISIBILITY
4793void
4794stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4795{
4796    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4797    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4798    difference_type __len = __last - __first;
4799    pair<value_type*, ptrdiff_t> __buf(0, 0);
4800    unique_ptr<value_type, __return_temporary_buffer> __h;
4801    if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4802    {
4803        __buf = _VSTD::get_temporary_buffer<value_type>(__len);
4804        __h.reset(__buf.first);
4805    }
4806    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4807    _VSTD::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4808}
4809
4810template <class _RandomAccessIterator>
4811inline _LIBCPP_INLINE_VISIBILITY
4812void
4813stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4814{
4815    _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4816}
4817
4818// is_heap_until
4819
4820template <class _RandomAccessIterator, class _Compare>
4821_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
4822is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4823{
4824    typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4825    difference_type __len = __last - __first;
4826    difference_type __p = 0;
4827    difference_type __c = 1;
4828    _RandomAccessIterator __pp = __first;
4829    while (__c < __len)
4830    {
4831        _RandomAccessIterator __cp = __first + __c;
4832        if (__comp(*__pp, *__cp))
4833            return __cp;
4834        ++__c;
4835        ++__cp;
4836        if (__c == __len)
4837            return __last;
4838        if (__comp(*__pp, *__cp))
4839            return __cp;
4840        ++__p;
4841        ++__pp;
4842        __c = 2 * __p + 1;
4843    }
4844    return __last;
4845}
4846
4847template<class _RandomAccessIterator>
4848_LIBCPP_NODISCARD_EXT inline
4849_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4850_RandomAccessIterator
4851is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4852{
4853    return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4854}
4855
4856// is_heap
4857
4858template <class _RandomAccessIterator, class _Compare>
4859_LIBCPP_NODISCARD_EXT inline
4860_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4861bool
4862is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4863{
4864    return _VSTD::is_heap_until(__first, __last, __comp) == __last;
4865}
4866
4867template<class _RandomAccessIterator>
4868_LIBCPP_NODISCARD_EXT inline
4869_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4870bool
4871is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4872{
4873    return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4874}
4875
4876// push_heap
4877
4878template <class _Compare, class _RandomAccessIterator>
4879void
4880__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4881          typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4882{
4883    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4884    if (__len > 1)
4885    {
4886        __len = (__len - 2) / 2;
4887        _RandomAccessIterator __ptr = __first + __len;
4888        if (__comp(*__ptr, *--__last))
4889        {
4890            value_type __t(_VSTD::move(*__last));
4891            do
4892            {
4893                *__last = _VSTD::move(*__ptr);
4894                __last = __ptr;
4895                if (__len == 0)
4896                    break;
4897                __len = (__len - 1) / 2;
4898                __ptr = __first + __len;
4899            } while (__comp(*__ptr, __t));
4900            *__last = _VSTD::move(__t);
4901        }
4902    }
4903}
4904
4905template <class _RandomAccessIterator, class _Compare>
4906inline _LIBCPP_INLINE_VISIBILITY
4907void
4908push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4909{
4910    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4911    _VSTD::__sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
4912}
4913
4914template <class _RandomAccessIterator>
4915inline _LIBCPP_INLINE_VISIBILITY
4916void
4917push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4918{
4919    _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4920}
4921
4922// pop_heap
4923
4924template <class _Compare, class _RandomAccessIterator>
4925void
4926__sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/,
4927            _Compare __comp,
4928            typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4929            _RandomAccessIterator __start)
4930{
4931    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4932    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4933    // left-child of __start is at 2 * __start + 1
4934    // right-child of __start is at 2 * __start + 2
4935    difference_type __child = __start - __first;
4936
4937    if (__len < 2 || (__len - 2) / 2 < __child)
4938        return;
4939
4940    __child = 2 * __child + 1;
4941    _RandomAccessIterator __child_i = __first + __child;
4942
4943    if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4944        // right-child exists and is greater than left-child
4945        ++__child_i;
4946        ++__child;
4947    }
4948
4949    // check if we are in heap-order
4950    if (__comp(*__child_i, *__start))
4951        // we are, __start is larger than it's largest child
4952        return;
4953
4954    value_type __top(_VSTD::move(*__start));
4955    do
4956    {
4957        // we are not in heap-order, swap the parent with it's largest child
4958        *__start = _VSTD::move(*__child_i);
4959        __start = __child_i;
4960
4961        if ((__len - 2) / 2 < __child)
4962            break;
4963
4964        // recompute the child based off of the updated parent
4965        __child = 2 * __child + 1;
4966        __child_i = __first + __child;
4967
4968        if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4969            // right-child exists and is greater than left-child
4970            ++__child_i;
4971            ++__child;
4972        }
4973
4974        // check if we are in heap-order
4975    } while (!__comp(*__child_i, __top));
4976    *__start = _VSTD::move(__top);
4977}
4978
4979template <class _Compare, class _RandomAccessIterator>
4980inline _LIBCPP_INLINE_VISIBILITY
4981void
4982__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4983           typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4984{
4985    if (__len > 1)
4986    {
4987        swap(*__first, *--__last);
4988        _VSTD::__sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);
4989    }
4990}
4991
4992template <class _RandomAccessIterator, class _Compare>
4993inline _LIBCPP_INLINE_VISIBILITY
4994void
4995pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4996{
4997    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4998    _VSTD::__pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
4999}
5000
5001template <class _RandomAccessIterator>
5002inline _LIBCPP_INLINE_VISIBILITY
5003void
5004pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5005{
5006    _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5007}
5008
5009// make_heap
5010
5011template <class _Compare, class _RandomAccessIterator>
5012void
5013__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5014{
5015    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5016    difference_type __n = __last - __first;
5017    if (__n > 1)
5018    {
5019        // start from the first parent, there is no need to consider children
5020        for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start)
5021        {
5022            _VSTD::__sift_down<_Compare>(__first, __last, __comp, __n, __first + __start);
5023        }
5024    }
5025}
5026
5027template <class _RandomAccessIterator, class _Compare>
5028inline _LIBCPP_INLINE_VISIBILITY
5029void
5030make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5031{
5032    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5033    _VSTD::__make_heap<_Comp_ref>(__first, __last, __comp);
5034}
5035
5036template <class _RandomAccessIterator>
5037inline _LIBCPP_INLINE_VISIBILITY
5038void
5039make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5040{
5041    _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5042}
5043
5044// sort_heap
5045
5046template <class _Compare, class _RandomAccessIterator>
5047void
5048__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5049{
5050    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5051    for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n)
5052        _VSTD::__pop_heap<_Compare>(__first, __last, __comp, __n);
5053}
5054
5055template <class _RandomAccessIterator, class _Compare>
5056inline _LIBCPP_INLINE_VISIBILITY
5057void
5058sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5059{
5060    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5061    _VSTD::__sort_heap<_Comp_ref>(__first, __last, __comp);
5062}
5063
5064template <class _RandomAccessIterator>
5065inline _LIBCPP_INLINE_VISIBILITY
5066void
5067sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5068{
5069    _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5070}
5071
5072// partial_sort
5073
5074template <class _Compare, class _RandomAccessIterator>
5075void
5076__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5077             _Compare __comp)
5078{
5079    _VSTD::__make_heap<_Compare>(__first, __middle, __comp);
5080    typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
5081    for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
5082    {
5083        if (__comp(*__i, *__first))
5084        {
5085            swap(*__i, *__first);
5086            _VSTD::__sift_down<_Compare>(__first, __middle, __comp, __len, __first);
5087        }
5088    }
5089    _VSTD::__sort_heap<_Compare>(__first, __middle, __comp);
5090}
5091
5092template <class _RandomAccessIterator, class _Compare>
5093inline _LIBCPP_INLINE_VISIBILITY
5094void
5095partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5096             _Compare __comp)
5097{
5098    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5099    _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
5100}
5101
5102template <class _RandomAccessIterator>
5103inline _LIBCPP_INLINE_VISIBILITY
5104void
5105partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
5106{
5107    _VSTD::partial_sort(__first, __middle, __last,
5108                       __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5109}
5110
5111// partial_sort_copy
5112
5113template <class _Compare, class _InputIterator, class _RandomAccessIterator>
5114_RandomAccessIterator
5115__partial_sort_copy(_InputIterator __first, _InputIterator __last,
5116                    _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5117{
5118    _RandomAccessIterator __r = __result_first;
5119    if (__r != __result_last)
5120    {
5121        for (; __first != __last && __r != __result_last; ++__first, (void) ++__r)
5122            *__r = *__first;
5123        _VSTD::__make_heap<_Compare>(__result_first, __r, __comp);
5124        typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
5125        for (; __first != __last; ++__first)
5126            if (__comp(*__first, *__result_first))
5127            {
5128                *__result_first = *__first;
5129                _VSTD::__sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first);
5130            }
5131        _VSTD::__sort_heap<_Compare>(__result_first, __r, __comp);
5132    }
5133    return __r;
5134}
5135
5136template <class _InputIterator, class _RandomAccessIterator, class _Compare>
5137inline _LIBCPP_INLINE_VISIBILITY
5138_RandomAccessIterator
5139partial_sort_copy(_InputIterator __first, _InputIterator __last,
5140                  _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5141{
5142    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5143    return _VSTD::__partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
5144}
5145
5146template <class _InputIterator, class _RandomAccessIterator>
5147inline _LIBCPP_INLINE_VISIBILITY
5148_RandomAccessIterator
5149partial_sort_copy(_InputIterator __first, _InputIterator __last,
5150                  _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
5151{
5152    return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
5153                                   __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5154}
5155
5156// nth_element
5157
5158template <class _Compare, class _RandomAccessIterator>
5159void
5160__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5161{
5162    // _Compare is known to be a reference type
5163    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5164    const difference_type __limit = 7;
5165    while (true)
5166    {
5167    __restart:
5168        if (__nth == __last)
5169            return;
5170        difference_type __len = __last - __first;
5171        switch (__len)
5172        {
5173        case 0:
5174        case 1:
5175            return;
5176        case 2:
5177            if (__comp(*--__last, *__first))
5178                swap(*__first, *__last);
5179            return;
5180        case 3:
5181            {
5182            _RandomAccessIterator __m = __first;
5183            _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
5184            return;
5185            }
5186        }
5187        if (__len <= __limit)
5188        {
5189            _VSTD::__selection_sort<_Compare>(__first, __last, __comp);
5190            return;
5191        }
5192        // __len > __limit >= 3
5193        _RandomAccessIterator __m = __first + __len/2;
5194        _RandomAccessIterator __lm1 = __last;
5195        unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
5196        // *__m is median
5197        // partition [__first, __m) < *__m and *__m <= [__m, __last)
5198        // (this inhibits tossing elements equivalent to __m around unnecessarily)
5199        _RandomAccessIterator __i = __first;
5200        _RandomAccessIterator __j = __lm1;
5201        // j points beyond range to be tested, *__lm1 is known to be <= *__m
5202        // The search going up is known to be guarded but the search coming down isn't.
5203        // Prime the downward search with a guard.
5204        if (!__comp(*__i, *__m))  // if *__first == *__m
5205        {
5206            // *__first == *__m, *__first doesn't go in first part
5207            // manually guard downward moving __j against __i
5208            while (true)
5209            {
5210                if (__i == --__j)
5211                {
5212                    // *__first == *__m, *__m <= all other elements
5213                    // Partition instead into [__first, __i) == *__first and *__first < [__i, __last)
5214                    ++__i;  // __first + 1
5215                    __j = __last;
5216                    if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
5217                    {
5218                        while (true)
5219                        {
5220                            if (__i == __j)
5221                                return;  // [__first, __last) all equivalent elements
5222                            if (__comp(*__first, *__i))
5223                            {
5224                                swap(*__i, *__j);
5225                                ++__n_swaps;
5226                                ++__i;
5227                                break;
5228                            }
5229                            ++__i;
5230                        }
5231                    }
5232                    // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
5233                    if (__i == __j)
5234                        return;
5235                    while (true)
5236                    {
5237                        while (!__comp(*__first, *__i))
5238                            ++__i;
5239                        while (__comp(*__first, *--__j))
5240                            ;
5241                        if (__i >= __j)
5242                            break;
5243                        swap(*__i, *__j);
5244                        ++__n_swaps;
5245                        ++__i;
5246                    }
5247                    // [__first, __i) == *__first and *__first < [__i, __last)
5248                    // The first part is sorted,
5249                    if (__nth < __i)
5250                        return;
5251                    // __nth_element the second part
5252                    // _VSTD::__nth_element<_Compare>(__i, __nth, __last, __comp);
5253                    __first = __i;
5254                    goto __restart;
5255                }
5256                if (__comp(*__j, *__m))
5257                {
5258                    swap(*__i, *__j);
5259                    ++__n_swaps;
5260                    break;  // found guard for downward moving __j, now use unguarded partition
5261                }
5262            }
5263        }
5264        ++__i;
5265        // j points beyond range to be tested, *__lm1 is known to be <= *__m
5266        // if not yet partitioned...
5267        if (__i < __j)
5268        {
5269            // known that *(__i - 1) < *__m
5270            while (true)
5271            {
5272                // __m still guards upward moving __i
5273                while (__comp(*__i, *__m))
5274                    ++__i;
5275                // It is now known that a guard exists for downward moving __j
5276                while (!__comp(*--__j, *__m))
5277                    ;
5278                if (__i >= __j)
5279                    break;
5280                swap(*__i, *__j);
5281                ++__n_swaps;
5282                // It is known that __m != __j
5283                // If __m just moved, follow it
5284                if (__m == __i)
5285                    __m = __j;
5286                ++__i;
5287            }
5288        }
5289        // [__first, __i) < *__m and *__m <= [__i, __last)
5290        if (__i != __m && __comp(*__m, *__i))
5291        {
5292            swap(*__i, *__m);
5293            ++__n_swaps;
5294        }
5295        // [__first, __i) < *__i and *__i <= [__i+1, __last)
5296        if (__nth == __i)
5297            return;
5298        if (__n_swaps == 0)
5299        {
5300            // We were given a perfectly partitioned sequence.  Coincidence?
5301            if (__nth < __i)
5302            {
5303                // Check for [__first, __i) already sorted
5304                __j = __m = __first;
5305                while (++__j != __i)
5306                {
5307                    if (__comp(*__j, *__m))
5308                        // not yet sorted, so sort
5309                        goto not_sorted;
5310                    __m = __j;
5311                }
5312                // [__first, __i) sorted
5313                return;
5314            }
5315            else
5316            {
5317                // Check for [__i, __last) already sorted
5318                __j = __m = __i;
5319                while (++__j != __last)
5320                {
5321                    if (__comp(*__j, *__m))
5322                        // not yet sorted, so sort
5323                        goto not_sorted;
5324                    __m = __j;
5325                }
5326                // [__i, __last) sorted
5327                return;
5328            }
5329        }
5330not_sorted:
5331        // __nth_element on range containing __nth
5332        if (__nth < __i)
5333        {
5334            // _VSTD::__nth_element<_Compare>(__first, __nth, __i, __comp);
5335            __last = __i;
5336        }
5337        else
5338        {
5339            // _VSTD::__nth_element<_Compare>(__i+1, __nth, __last, __comp);
5340            __first = ++__i;
5341        }
5342    }
5343}
5344
5345template <class _RandomAccessIterator, class _Compare>
5346inline _LIBCPP_INLINE_VISIBILITY
5347void
5348nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5349{
5350    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5351    _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp);
5352}
5353
5354template <class _RandomAccessIterator>
5355inline _LIBCPP_INLINE_VISIBILITY
5356void
5357nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
5358{
5359    _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5360}
5361
5362// includes
5363
5364template <class _Compare, class _InputIterator1, class _InputIterator2>
5365_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
5366__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5367           _Compare __comp)
5368{
5369    for (; __first2 != __last2; ++__first1)
5370    {
5371        if (__first1 == __last1 || __comp(*__first2, *__first1))
5372            return false;
5373        if (!__comp(*__first1, *__first2))
5374            ++__first2;
5375    }
5376    return true;
5377}
5378
5379template <class _InputIterator1, class _InputIterator2, class _Compare>
5380_LIBCPP_NODISCARD_EXT inline
5381_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5382bool
5383includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5384         _Compare __comp)
5385{
5386    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5387    return _VSTD::__includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5388}
5389
5390template <class _InputIterator1, class _InputIterator2>
5391_LIBCPP_NODISCARD_EXT inline
5392_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5393bool
5394includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
5395{
5396    return _VSTD::includes(__first1, __last1, __first2, __last2,
5397                          __less<typename iterator_traits<_InputIterator1>::value_type,
5398                                 typename iterator_traits<_InputIterator2>::value_type>());
5399}
5400
5401// set_union
5402
5403template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5404_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
5405__set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5406            _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5407{
5408    for (; __first1 != __last1; ++__result)
5409    {
5410        if (__first2 == __last2)
5411            return _VSTD::copy(__first1, __last1, __result);
5412        if (__comp(*__first2, *__first1))
5413        {
5414            *__result = *__first2;
5415            ++__first2;
5416        }
5417        else
5418        {
5419            if (!__comp(*__first1, *__first2))
5420                ++__first2;
5421            *__result = *__first1;
5422            ++__first1;
5423        }
5424    }
5425    return _VSTD::copy(__first2, __last2, __result);
5426}
5427
5428template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5429inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5430_OutputIterator
5431set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5432          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5433{
5434    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5435    return _VSTD::__set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5436}
5437
5438template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5439inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5440_OutputIterator
5441set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5442          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5443{
5444    return _VSTD::set_union(__first1, __last1, __first2, __last2, __result,
5445                          __less<typename iterator_traits<_InputIterator1>::value_type,
5446                                 typename iterator_traits<_InputIterator2>::value_type>());
5447}
5448
5449// set_intersection
5450
5451template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5452_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
5453__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5454                   _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5455{
5456    while (__first1 != __last1 && __first2 != __last2)
5457    {
5458        if (__comp(*__first1, *__first2))
5459            ++__first1;
5460        else
5461        {
5462            if (!__comp(*__first2, *__first1))
5463            {
5464                *__result = *__first1;
5465                ++__result;
5466                ++__first1;
5467            }
5468            ++__first2;
5469        }
5470    }
5471    return __result;
5472}
5473
5474template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5475inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5476_OutputIterator
5477set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5478                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5479{
5480    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5481    return _VSTD::__set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5482}
5483
5484template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5485inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5486_OutputIterator
5487set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5488                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5489{
5490    return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result,
5491                                  __less<typename iterator_traits<_InputIterator1>::value_type,
5492                                         typename iterator_traits<_InputIterator2>::value_type>());
5493}
5494
5495// set_difference
5496
5497template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5498_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
5499__set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5500                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5501{
5502    while (__first1 != __last1)
5503    {
5504        if (__first2 == __last2)
5505            return _VSTD::copy(__first1, __last1, __result);
5506        if (__comp(*__first1, *__first2))
5507        {
5508            *__result = *__first1;
5509            ++__result;
5510            ++__first1;
5511        }
5512        else
5513        {
5514            if (!__comp(*__first2, *__first1))
5515                ++__first1;
5516            ++__first2;
5517        }
5518    }
5519    return __result;
5520}
5521
5522template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5523inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5524_OutputIterator
5525set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5526               _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5527{
5528    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5529    return _VSTD::__set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5530}
5531
5532template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5533inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5534_OutputIterator
5535set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5536               _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5537{
5538    return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result,
5539                                __less<typename iterator_traits<_InputIterator1>::value_type,
5540                                       typename iterator_traits<_InputIterator2>::value_type>());
5541}
5542
5543// set_symmetric_difference
5544
5545template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5546_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
5547__set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5548                           _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5549{
5550    while (__first1 != __last1)
5551    {
5552        if (__first2 == __last2)
5553            return _VSTD::copy(__first1, __last1, __result);
5554        if (__comp(*__first1, *__first2))
5555        {
5556            *__result = *__first1;
5557            ++__result;
5558            ++__first1;
5559        }
5560        else
5561        {
5562            if (__comp(*__first2, *__first1))
5563            {
5564                *__result = *__first2;
5565                ++__result;
5566            }
5567            else
5568                ++__first1;
5569            ++__first2;
5570        }
5571    }
5572    return _VSTD::copy(__first2, __last2, __result);
5573}
5574
5575template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5576inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5577_OutputIterator
5578set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5579                         _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5580{
5581    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5582    return _VSTD::__set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5583}
5584
5585template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5586inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5587_OutputIterator
5588set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5589                         _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5590{
5591    return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
5592                                          __less<typename iterator_traits<_InputIterator1>::value_type,
5593                                                 typename iterator_traits<_InputIterator2>::value_type>());
5594}
5595
5596// lexicographical_compare
5597
5598template <class _Compare, class _InputIterator1, class _InputIterator2>
5599_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
5600__lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5601                          _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5602{
5603    for (; __first2 != __last2; ++__first1, (void) ++__first2)
5604    {
5605        if (__first1 == __last1 || __comp(*__first1, *__first2))
5606            return true;
5607        if (__comp(*__first2, *__first1))
5608            return false;
5609    }
5610    return false;
5611}
5612
5613template <class _InputIterator1, class _InputIterator2, class _Compare>
5614_LIBCPP_NODISCARD_EXT inline
5615_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5616bool
5617lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5618                        _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5619{
5620    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5621    return _VSTD::__lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5622}
5623
5624template <class _InputIterator1, class _InputIterator2>
5625_LIBCPP_NODISCARD_EXT inline
5626_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5627bool
5628lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5629                        _InputIterator2 __first2, _InputIterator2 __last2)
5630{
5631    return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,
5632                                         __less<typename iterator_traits<_InputIterator1>::value_type,
5633                                                typename iterator_traits<_InputIterator2>::value_type>());
5634}
5635
5636// next_permutation
5637
5638template <class _Compare, class _BidirectionalIterator>
5639bool
5640__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5641{
5642    _BidirectionalIterator __i = __last;
5643    if (__first == __last || __first == --__i)
5644        return false;
5645    while (true)
5646    {
5647        _BidirectionalIterator __ip1 = __i;
5648        if (__comp(*--__i, *__ip1))
5649        {
5650            _BidirectionalIterator __j = __last;
5651            while (!__comp(*__i, *--__j))
5652                ;
5653            swap(*__i, *__j);
5654            _VSTD::reverse(__ip1, __last);
5655            return true;
5656        }
5657        if (__i == __first)
5658        {
5659            _VSTD::reverse(__first, __last);
5660            return false;
5661        }
5662    }
5663}
5664
5665template <class _BidirectionalIterator, class _Compare>
5666inline _LIBCPP_INLINE_VISIBILITY
5667bool
5668next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5669{
5670    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5671    return _VSTD::__next_permutation<_Comp_ref>(__first, __last, __comp);
5672}
5673
5674template <class _BidirectionalIterator>
5675inline _LIBCPP_INLINE_VISIBILITY
5676bool
5677next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5678{
5679    return _VSTD::next_permutation(__first, __last,
5680                                  __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5681}
5682
5683// prev_permutation
5684
5685template <class _Compare, class _BidirectionalIterator>
5686bool
5687__prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5688{
5689    _BidirectionalIterator __i = __last;
5690    if (__first == __last || __first == --__i)
5691        return false;
5692    while (true)
5693    {
5694        _BidirectionalIterator __ip1 = __i;
5695        if (__comp(*__ip1, *--__i))
5696        {
5697            _BidirectionalIterator __j = __last;
5698            while (!__comp(*--__j, *__i))
5699                ;
5700            swap(*__i, *__j);
5701            _VSTD::reverse(__ip1, __last);
5702            return true;
5703        }
5704        if (__i == __first)
5705        {
5706            _VSTD::reverse(__first, __last);
5707            return false;
5708        }
5709    }
5710}
5711
5712template <class _BidirectionalIterator, class _Compare>
5713inline _LIBCPP_INLINE_VISIBILITY
5714bool
5715prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5716{
5717    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5718    return _VSTD::__prev_permutation<_Comp_ref>(__first, __last, __comp);
5719}
5720
5721template <class _BidirectionalIterator>
5722inline _LIBCPP_INLINE_VISIBILITY
5723bool
5724prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5725{
5726    return _VSTD::prev_permutation(__first, __last,
5727                                  __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5728}
5729
5730_LIBCPP_END_NAMESPACE_STD
5731
5732_LIBCPP_POP_MACROS
5733
5734#if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
5735#   include <__pstl_algorithm>
5736#endif
5737
5738#endif  // _LIBCPP_ALGORITHM
5739