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#ifndef _LIBCPP_CXX03_LANG
3033    uniform_int_distribution() : uniform_int_distribution(0) {}
3034    explicit uniform_int_distribution(
3035        result_type __a, result_type __b = numeric_limits<result_type>::max())
3036        : __p_(param_type(__a, __b)) {}
3037#else
3038    explicit uniform_int_distribution(
3039        result_type __a = 0,
3040        result_type __b = numeric_limits<result_type>::max())
3041        : __p_(param_type(__a, __b)) {}
3042#endif
3043    explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
3044    void reset() {}
3045
3046    // generating functions
3047    template<class _URNG> result_type operator()(_URNG& __g)
3048        {return (*this)(__g, __p_);}
3049    template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3050
3051    // property functions
3052    result_type a() const {return __p_.a();}
3053    result_type b() const {return __p_.b();}
3054
3055    param_type param() const {return __p_;}
3056    void param(const param_type& __p) {__p_ = __p;}
3057
3058    result_type min() const {return a();}
3059    result_type max() const {return b();}
3060
3061    friend bool operator==(const uniform_int_distribution& __x,
3062                           const uniform_int_distribution& __y)
3063        {return __x.__p_ == __y.__p_;}
3064    friend bool operator!=(const uniform_int_distribution& __x,
3065                           const uniform_int_distribution& __y)
3066            {return !(__x == __y);}
3067};
3068
3069template<class _IntType>
3070template<class _URNG>
3071typename uniform_int_distribution<_IntType>::result_type
3072uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
3073_LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
3074{
3075    typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
3076                                            uint32_t, uint64_t>::type _UIntType;
3077    const _UIntType _Rp = _UIntType(__p.b()) - _UIntType(__p.a()) + _UIntType(1);
3078    if (_Rp == 1)
3079        return __p.a();
3080    const size_t _Dt = numeric_limits<_UIntType>::digits;
3081    typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
3082    if (_Rp == 0)
3083        return static_cast<result_type>(_Eng(__g, _Dt)());
3084    size_t __w = _Dt - __libcpp_clz(_Rp) - 1;
3085    if ((_Rp & (numeric_limits<_UIntType>::max() >> (_Dt - __w))) != 0)
3086        ++__w;
3087    _Eng __e(__g, __w);
3088    _UIntType __u;
3089    do
3090    {
3091        __u = __e();
3092    } while (__u >= _Rp);
3093    return static_cast<result_type>(__u + __p.a());
3094}
3095
3096#if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \
3097  || defined(_LIBCPP_BUILDING_LIBRARY)
3098class _LIBCPP_TYPE_VIS __rs_default;
3099
3100_LIBCPP_FUNC_VIS __rs_default __rs_get();
3101
3102class _LIBCPP_TYPE_VIS __rs_default
3103{
3104    static unsigned __c_;
3105
3106    __rs_default();
3107public:
3108    typedef uint_fast32_t result_type;
3109
3110    static const result_type _Min = 0;
3111    static const result_type _Max = 0xFFFFFFFF;
3112
3113    __rs_default(const __rs_default&);
3114    ~__rs_default();
3115
3116    result_type operator()();
3117
3118    static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
3119    static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
3120
3121    friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
3122};
3123
3124_LIBCPP_FUNC_VIS __rs_default __rs_get();
3125
3126template <class _RandomAccessIterator>
3127_LIBCPP_DEPRECATED_IN_CXX14 void
3128random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
3129{
3130    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3131    typedef uniform_int_distribution<ptrdiff_t> _Dp;
3132    typedef typename _Dp::param_type _Pp;
3133    difference_type __d = __last - __first;
3134    if (__d > 1)
3135    {
3136        _Dp __uid;
3137        __rs_default __g = __rs_get();
3138        for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
3139        {
3140            difference_type __i = __uid(__g, _Pp(0, __d));
3141            if (__i != difference_type(0))
3142                swap(*__first, *(__first + __i));
3143        }
3144    }
3145}
3146
3147template <class _RandomAccessIterator, class _RandomNumberGenerator>
3148_LIBCPP_DEPRECATED_IN_CXX14 void
3149random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3150#ifndef _LIBCPP_CXX03_LANG
3151               _RandomNumberGenerator&& __rand)
3152#else
3153               _RandomNumberGenerator& __rand)
3154#endif
3155{
3156    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3157    difference_type __d = __last - __first;
3158    if (__d > 1)
3159    {
3160        for (--__last; __first < __last; ++__first, (void) --__d)
3161        {
3162            difference_type __i = __rand(__d);
3163            if (__i != difference_type(0))
3164              swap(*__first, *(__first + __i));
3165        }
3166    }
3167}
3168#endif
3169
3170template <class _PopulationIterator, class _SampleIterator, class _Distance,
3171          class _UniformRandomNumberGenerator>
3172_LIBCPP_INLINE_VISIBILITY
3173_SampleIterator __sample(_PopulationIterator __first,
3174                         _PopulationIterator __last, _SampleIterator __output_iter,
3175                         _Distance __n,
3176                         _UniformRandomNumberGenerator & __g,
3177                         input_iterator_tag) {
3178
3179  _Distance __k = 0;
3180  for (; __first != __last && __k < __n; ++__first, (void) ++__k)
3181    __output_iter[__k] = *__first;
3182  _Distance __sz = __k;
3183  for (; __first != __last; ++__first, (void) ++__k) {
3184    _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g);
3185    if (__r < __sz)
3186      __output_iter[__r] = *__first;
3187  }
3188  return __output_iter + _VSTD::min(__n, __k);
3189}
3190
3191template <class _PopulationIterator, class _SampleIterator, class _Distance,
3192          class _UniformRandomNumberGenerator>
3193_LIBCPP_INLINE_VISIBILITY
3194_SampleIterator __sample(_PopulationIterator __first,
3195                         _PopulationIterator __last, _SampleIterator __output_iter,
3196                         _Distance __n,
3197                         _UniformRandomNumberGenerator& __g,
3198                         forward_iterator_tag) {
3199  _Distance __unsampled_sz = _VSTD::distance(__first, __last);
3200  for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
3201    _Distance __r =
3202        _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g);
3203    if (__r < __n) {
3204      *__output_iter++ = *__first;
3205      --__n;
3206    }
3207  }
3208  return __output_iter;
3209}
3210
3211template <class _PopulationIterator, class _SampleIterator, class _Distance,
3212          class _UniformRandomNumberGenerator>
3213_LIBCPP_INLINE_VISIBILITY
3214_SampleIterator __sample(_PopulationIterator __first,
3215                         _PopulationIterator __last, _SampleIterator __output_iter,
3216                         _Distance __n, _UniformRandomNumberGenerator& __g) {
3217  typedef typename iterator_traits<_PopulationIterator>::iterator_category
3218        _PopCategory;
3219  typedef typename iterator_traits<_PopulationIterator>::difference_type
3220        _Difference;
3221  static_assert(__is_cpp17_forward_iterator<_PopulationIterator>::value ||
3222                __is_cpp17_random_access_iterator<_SampleIterator>::value,
3223                "SampleIterator must meet the requirements of RandomAccessIterator");
3224  typedef typename common_type<_Distance, _Difference>::type _CommonType;
3225  _LIBCPP_ASSERT(__n >= 0, "N must be a positive number.");
3226  return _VSTD::__sample(
3227      __first, __last, __output_iter, _CommonType(__n),
3228      __g, _PopCategory());
3229}
3230
3231#if _LIBCPP_STD_VER > 14
3232template <class _PopulationIterator, class _SampleIterator, class _Distance,
3233          class _UniformRandomNumberGenerator>
3234inline _LIBCPP_INLINE_VISIBILITY
3235_SampleIterator sample(_PopulationIterator __first,
3236                       _PopulationIterator __last, _SampleIterator __output_iter,
3237                       _Distance __n, _UniformRandomNumberGenerator&& __g) {
3238    return _VSTD::__sample(__first, __last, __output_iter, __n, __g);
3239}
3240#endif // _LIBCPP_STD_VER > 14
3241
3242template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
3243    void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3244                 _UniformRandomNumberGenerator&& __g)
3245{
3246    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3247    typedef uniform_int_distribution<ptrdiff_t> _Dp;
3248    typedef typename _Dp::param_type _Pp;
3249    difference_type __d = __last - __first;
3250    if (__d > 1)
3251    {
3252        _Dp __uid;
3253        for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
3254        {
3255            difference_type __i = __uid(__g, _Pp(0, __d));
3256            if (__i != difference_type(0))
3257                swap(*__first, *(__first + __i));
3258        }
3259    }
3260}
3261
3262template <class _InputIterator, class _Predicate>
3263_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
3264is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3265{
3266    for (; __first != __last; ++__first)
3267        if (!__pred(*__first))
3268            break;
3269    if ( __first == __last )
3270        return true;
3271    ++__first;
3272    for (; __first != __last; ++__first)
3273        if (__pred(*__first))
3274            return false;
3275    return true;
3276}
3277
3278// partition
3279
3280template <class _Predicate, class _ForwardIterator>
3281_ForwardIterator
3282__partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
3283{
3284    while (true)
3285    {
3286        if (__first == __last)
3287            return __first;
3288        if (!__pred(*__first))
3289            break;
3290        ++__first;
3291    }
3292    for (_ForwardIterator __p = __first; ++__p != __last;)
3293    {
3294        if (__pred(*__p))
3295        {
3296            swap(*__first, *__p);
3297            ++__first;
3298        }
3299    }
3300    return __first;
3301}
3302
3303template <class _Predicate, class _BidirectionalIterator>
3304_BidirectionalIterator
3305__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3306            bidirectional_iterator_tag)
3307{
3308    while (true)
3309    {
3310        while (true)
3311        {
3312            if (__first == __last)
3313                return __first;
3314            if (!__pred(*__first))
3315                break;
3316            ++__first;
3317        }
3318        do
3319        {
3320            if (__first == --__last)
3321                return __first;
3322        } while (!__pred(*__last));
3323        swap(*__first, *__last);
3324        ++__first;
3325    }
3326}
3327
3328template <class _ForwardIterator, class _Predicate>
3329inline _LIBCPP_INLINE_VISIBILITY
3330_ForwardIterator
3331partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3332{
3333    return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>
3334                            (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3335}
3336
3337// partition_copy
3338
3339template <class _InputIterator, class _OutputIterator1,
3340          class _OutputIterator2, class _Predicate>
3341_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_OutputIterator1, _OutputIterator2>
3342partition_copy(_InputIterator __first, _InputIterator __last,
3343               _OutputIterator1 __out_true, _OutputIterator2 __out_false,
3344               _Predicate __pred)
3345{
3346    for (; __first != __last; ++__first)
3347    {
3348        if (__pred(*__first))
3349        {
3350            *__out_true = *__first;
3351            ++__out_true;
3352        }
3353        else
3354        {
3355            *__out_false = *__first;
3356            ++__out_false;
3357        }
3358    }
3359    return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
3360}
3361
3362// partition_point
3363
3364template<class _ForwardIterator, class _Predicate>
3365_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
3366partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3367{
3368    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3369    difference_type __len = _VSTD::distance(__first, __last);
3370    while (__len != 0)
3371    {
3372        difference_type __l2 = _VSTD::__half_positive(__len);
3373        _ForwardIterator __m = __first;
3374        _VSTD::advance(__m, __l2);
3375        if (__pred(*__m))
3376        {
3377            __first = ++__m;
3378            __len -= __l2 + 1;
3379        }
3380        else
3381            __len = __l2;
3382    }
3383    return __first;
3384}
3385
3386// stable_partition
3387
3388template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
3389_ForwardIterator
3390__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3391                   _Distance __len, _Pair __p, forward_iterator_tag __fit)
3392{
3393    // *__first is known to be false
3394    // __len >= 1
3395    if (__len == 1)
3396        return __first;
3397    if (__len == 2)
3398    {
3399        _ForwardIterator __m = __first;
3400        if (__pred(*++__m))
3401        {
3402            swap(*__first, *__m);
3403            return __m;
3404        }
3405        return __first;
3406    }
3407    if (__len <= __p.second)
3408    {   // The buffer is big enough to use
3409        typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3410        __destruct_n __d(0);
3411        unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3412        // Move the falses into the temporary buffer, and the trues to the front of the line
3413        // Update __first to always point to the end of the trues
3414        value_type* __t = __p.first;
3415        ::new ((void*)__t) value_type(_VSTD::move(*__first));
3416        __d.template __incr<value_type>();
3417        ++__t;
3418        _ForwardIterator __i = __first;
3419        while (++__i != __last)
3420        {
3421            if (__pred(*__i))
3422            {
3423                *__first = _VSTD::move(*__i);
3424                ++__first;
3425            }
3426            else
3427            {
3428                ::new ((void*)__t) value_type(_VSTD::move(*__i));
3429                __d.template __incr<value_type>();
3430                ++__t;
3431            }
3432        }
3433        // All trues now at start of range, all falses in buffer
3434        // Move falses back into range, but don't mess up __first which points to first false
3435        __i = __first;
3436        for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i)
3437            *__i = _VSTD::move(*__t2);
3438        // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3439        return __first;
3440    }
3441    // Else not enough buffer, do in place
3442    // __len >= 3
3443    _ForwardIterator __m = __first;
3444    _Distance __len2 = __len / 2;  // __len2 >= 2
3445    _VSTD::advance(__m, __len2);
3446    // recurse on [__first, __m), *__first know to be false
3447    // F?????????????????
3448    // f       m         l
3449    typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3450    _ForwardIterator __first_false = _VSTD::__stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
3451    // TTTFFFFF??????????
3452    // f  ff   m         l
3453    // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3454    _ForwardIterator __m1 = __m;
3455    _ForwardIterator __second_false = __last;
3456    _Distance __len_half = __len - __len2;
3457    while (__pred(*__m1))
3458    {
3459        if (++__m1 == __last)
3460            goto __second_half_done;
3461        --__len_half;
3462    }
3463    // TTTFFFFFTTTF??????
3464    // f  ff   m  m1     l
3465    __second_false = _VSTD::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
3466__second_half_done:
3467    // TTTFFFFFTTTTTFFFFF
3468    // f  ff   m    sf   l
3469    return _VSTD::rotate(__first_false, __m, __second_false);
3470    // TTTTTTTTFFFFFFFFFF
3471    //         |
3472}
3473
3474struct __return_temporary_buffer
3475{
3476    template <class _Tp>
3477    _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}
3478};
3479
3480template <class _Predicate, class _ForwardIterator>
3481_ForwardIterator
3482__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3483                   forward_iterator_tag)
3484{
3485    const unsigned __alloc_limit = 3;  // might want to make this a function of trivial assignment
3486    // Either prove all true and return __first or point to first false
3487    while (true)
3488    {
3489        if (__first == __last)
3490            return __first;
3491        if (!__pred(*__first))
3492            break;
3493        ++__first;
3494    }
3495    // We now have a reduced range [__first, __last)
3496    // *__first is known to be false
3497    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3498    typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3499    difference_type __len = _VSTD::distance(__first, __last);
3500    pair<value_type*, ptrdiff_t> __p(0, 0);
3501    unique_ptr<value_type, __return_temporary_buffer> __h;
3502    if (__len >= __alloc_limit)
3503    {
3504        __p = _VSTD::get_temporary_buffer<value_type>(__len);
3505        __h.reset(__p.first);
3506    }
3507    return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type>
3508                             (__first, __last, __pred, __len, __p, forward_iterator_tag());
3509}
3510
3511template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
3512_BidirectionalIterator
3513__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3514                   _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
3515{
3516    // *__first is known to be false
3517    // *__last is known to be true
3518    // __len >= 2
3519    if (__len == 2)
3520    {
3521        swap(*__first, *__last);
3522        return __last;
3523    }
3524    if (__len == 3)
3525    {
3526        _BidirectionalIterator __m = __first;
3527        if (__pred(*++__m))
3528        {
3529            swap(*__first, *__m);
3530            swap(*__m, *__last);
3531            return __last;
3532        }
3533        swap(*__m, *__last);
3534        swap(*__first, *__m);
3535        return __m;
3536    }
3537    if (__len <= __p.second)
3538    {   // The buffer is big enough to use
3539        typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3540        __destruct_n __d(0);
3541        unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3542        // Move the falses into the temporary buffer, and the trues to the front of the line
3543        // Update __first to always point to the end of the trues
3544        value_type* __t = __p.first;
3545        ::new ((void*)__t) value_type(_VSTD::move(*__first));
3546        __d.template __incr<value_type>();
3547        ++__t;
3548        _BidirectionalIterator __i = __first;
3549        while (++__i != __last)
3550        {
3551            if (__pred(*__i))
3552            {
3553                *__first = _VSTD::move(*__i);
3554                ++__first;
3555            }
3556            else
3557            {
3558                ::new ((void*)__t) value_type(_VSTD::move(*__i));
3559                __d.template __incr<value_type>();
3560                ++__t;
3561            }
3562        }
3563        // move *__last, known to be true
3564        *__first = _VSTD::move(*__i);
3565        __i = ++__first;
3566        // All trues now at start of range, all falses in buffer
3567        // Move falses back into range, but don't mess up __first which points to first false
3568        for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i)
3569            *__i = _VSTD::move(*__t2);
3570        // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3571        return __first;
3572    }
3573    // Else not enough buffer, do in place
3574    // __len >= 4
3575    _BidirectionalIterator __m = __first;
3576    _Distance __len2 = __len / 2;  // __len2 >= 2
3577    _VSTD::advance(__m, __len2);
3578    // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
3579    // F????????????????T
3580    // f       m        l
3581    _BidirectionalIterator __m1 = __m;
3582    _BidirectionalIterator __first_false = __first;
3583    _Distance __len_half = __len2;
3584    while (!__pred(*--__m1))
3585    {
3586        if (__m1 == __first)
3587            goto __first_half_done;
3588        --__len_half;
3589    }
3590    // F???TFFF?????????T
3591    // f   m1  m        l
3592    typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3593    __first_false = _VSTD::__stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3594__first_half_done:
3595    // TTTFFFFF?????????T
3596    // f  ff   m        l
3597    // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3598    __m1 = __m;
3599    _BidirectionalIterator __second_false = __last;
3600    ++__second_false;
3601    __len_half = __len - __len2;
3602    while (__pred(*__m1))
3603    {
3604        if (++__m1 == __last)
3605            goto __second_half_done;
3606        --__len_half;
3607    }
3608    // TTTFFFFFTTTF?????T
3609    // f  ff   m  m1    l
3610    __second_false = _VSTD::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
3611__second_half_done:
3612    // TTTFFFFFTTTTTFFFFF
3613    // f  ff   m    sf  l
3614    return _VSTD::rotate(__first_false, __m, __second_false);
3615    // TTTTTTTTFFFFFFFFFF
3616    //         |
3617}
3618
3619template <class _Predicate, class _BidirectionalIterator>
3620_BidirectionalIterator
3621__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3622                   bidirectional_iterator_tag)
3623{
3624    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3625    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3626    const difference_type __alloc_limit = 4;  // might want to make this a function of trivial assignment
3627    // Either prove all true and return __first or point to first false
3628    while (true)
3629    {
3630        if (__first == __last)
3631            return __first;
3632        if (!__pred(*__first))
3633            break;
3634        ++__first;
3635    }
3636    // __first points to first false, everything prior to __first is already set.
3637    // Either prove [__first, __last) is all false and return __first, or point __last to last true
3638    do
3639    {
3640        if (__first == --__last)
3641            return __first;
3642    } while (!__pred(*__last));
3643    // We now have a reduced range [__first, __last]
3644    // *__first is known to be false
3645    // *__last is known to be true
3646    // __len >= 2
3647    difference_type __len = _VSTD::distance(__first, __last) + 1;
3648    pair<value_type*, ptrdiff_t> __p(0, 0);
3649    unique_ptr<value_type, __return_temporary_buffer> __h;
3650    if (__len >= __alloc_limit)
3651    {
3652        __p = _VSTD::get_temporary_buffer<value_type>(__len);
3653        __h.reset(__p.first);
3654    }
3655    return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type>
3656                             (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3657}
3658
3659template <class _ForwardIterator, class _Predicate>
3660inline _LIBCPP_INLINE_VISIBILITY
3661_ForwardIterator
3662stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3663{
3664    return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type>
3665                             (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3666}
3667
3668// is_sorted_until
3669
3670template <class _ForwardIterator, class _Compare>
3671_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
3672is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3673{
3674    if (__first != __last)
3675    {
3676        _ForwardIterator __i = __first;
3677        while (++__i != __last)
3678        {
3679            if (__comp(*__i, *__first))
3680                return __i;
3681            __first = __i;
3682        }
3683    }
3684    return __last;
3685}
3686
3687template<class _ForwardIterator>
3688_LIBCPP_NODISCARD_EXT inline
3689_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3690_ForwardIterator
3691is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3692{
3693    return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3694}
3695
3696// is_sorted
3697
3698template <class _ForwardIterator, class _Compare>
3699_LIBCPP_NODISCARD_EXT inline
3700_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3701bool
3702is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3703{
3704    return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
3705}
3706
3707template<class _ForwardIterator>
3708_LIBCPP_NODISCARD_EXT inline
3709_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3710bool
3711is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3712{
3713    return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3714}
3715
3716// sort
3717
3718// stable, 2-3 compares, 0-2 swaps
3719
3720template <class _Compare, class _ForwardIterator>
3721unsigned
3722__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
3723{
3724    unsigned __r = 0;
3725    if (!__c(*__y, *__x))          // if x <= y
3726    {
3727        if (!__c(*__z, *__y))      // if y <= z
3728            return __r;            // x <= y && y <= z
3729                                   // x <= y && y > z
3730        swap(*__y, *__z);          // x <= z && y < z
3731        __r = 1;
3732        if (__c(*__y, *__x))       // if x > y
3733        {
3734            swap(*__x, *__y);      // x < y && y <= z
3735            __r = 2;
3736        }
3737        return __r;                // x <= y && y < z
3738    }
3739    if (__c(*__z, *__y))           // x > y, if y > z
3740    {
3741        swap(*__x, *__z);          // x < y && y < z
3742        __r = 1;
3743        return __r;
3744    }
3745    swap(*__x, *__y);              // x > y && y <= z
3746    __r = 1;                       // x < y && x <= z
3747    if (__c(*__z, *__y))           // if y > z
3748    {
3749        swap(*__y, *__z);          // x <= y && y < z
3750        __r = 2;
3751    }
3752    return __r;
3753}                                  // x <= y && y <= z
3754
3755// stable, 3-6 compares, 0-5 swaps
3756
3757template <class _Compare, class _ForwardIterator>
3758unsigned
3759__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3760            _ForwardIterator __x4, _Compare __c)
3761{
3762    unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c);
3763    if (__c(*__x4, *__x3))
3764    {
3765        swap(*__x3, *__x4);
3766        ++__r;
3767        if (__c(*__x3, *__x2))
3768        {
3769            swap(*__x2, *__x3);
3770            ++__r;
3771            if (__c(*__x2, *__x1))
3772            {
3773                swap(*__x1, *__x2);
3774                ++__r;
3775            }
3776        }
3777    }
3778    return __r;
3779}
3780
3781// stable, 4-10 compares, 0-9 swaps
3782
3783template <class _Compare, class _ForwardIterator>
3784_LIBCPP_HIDDEN
3785unsigned
3786__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3787            _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
3788{
3789    unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
3790    if (__c(*__x5, *__x4))
3791    {
3792        swap(*__x4, *__x5);
3793        ++__r;
3794        if (__c(*__x4, *__x3))
3795        {
3796            swap(*__x3, *__x4);
3797            ++__r;
3798            if (__c(*__x3, *__x2))
3799            {
3800                swap(*__x2, *__x3);
3801                ++__r;
3802                if (__c(*__x2, *__x1))
3803                {
3804                    swap(*__x1, *__x2);
3805                    ++__r;
3806                }
3807            }
3808        }
3809    }
3810    return __r;
3811}
3812
3813// Assumes size > 0
3814template <class _Compare, class _BidirectionalIterator>
3815void
3816__selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
3817{
3818    _BidirectionalIterator __lm1 = __last;
3819    for (--__lm1; __first != __lm1; ++__first)
3820    {
3821        _BidirectionalIterator __i = _VSTD::min_element<_BidirectionalIterator,
3822                                                        typename add_lvalue_reference<_Compare>::type>
3823                                                       (__first, __last, __comp);
3824        if (__i != __first)
3825            swap(*__first, *__i);
3826    }
3827}
3828
3829template <class _Compare, class _BidirectionalIterator>
3830void
3831__insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
3832{
3833    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3834    if (__first != __last)
3835    {
3836        _BidirectionalIterator __i = __first;
3837        for (++__i; __i != __last; ++__i)
3838        {
3839            _BidirectionalIterator __j = __i;
3840            value_type __t(_VSTD::move(*__j));
3841            for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t,  *--__k); --__j)
3842                *__j = _VSTD::move(*__k);
3843            *__j = _VSTD::move(__t);
3844        }
3845    }
3846}
3847
3848template <class _Compare, class _RandomAccessIterator>
3849void
3850__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3851{
3852    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3853    _RandomAccessIterator __j = __first+2;
3854    _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp);
3855    for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3856    {
3857        if (__comp(*__i, *__j))
3858        {
3859            value_type __t(_VSTD::move(*__i));
3860            _RandomAccessIterator __k = __j;
3861            __j = __i;
3862            do
3863            {
3864                *__j = _VSTD::move(*__k);
3865                __j = __k;
3866            } while (__j != __first && __comp(__t, *--__k));
3867            *__j = _VSTD::move(__t);
3868        }
3869        __j = __i;
3870    }
3871}
3872
3873template <class _Compare, class _RandomAccessIterator>
3874bool
3875__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3876{
3877    switch (__last - __first)
3878    {
3879    case 0:
3880    case 1:
3881        return true;
3882    case 2:
3883        if (__comp(*--__last, *__first))
3884            swap(*__first, *__last);
3885        return true;
3886    case 3:
3887        _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3888        return true;
3889    case 4:
3890        _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3891        return true;
3892    case 5:
3893        _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3894        return true;
3895    }
3896    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3897    _RandomAccessIterator __j = __first+2;
3898    _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp);
3899    const unsigned __limit = 8;
3900    unsigned __count = 0;
3901    for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3902    {
3903        if (__comp(*__i, *__j))
3904        {
3905            value_type __t(_VSTD::move(*__i));
3906            _RandomAccessIterator __k = __j;
3907            __j = __i;
3908            do
3909            {
3910                *__j = _VSTD::move(*__k);
3911                __j = __k;
3912            } while (__j != __first && __comp(__t, *--__k));
3913            *__j = _VSTD::move(__t);
3914            if (++__count == __limit)
3915                return ++__i == __last;
3916        }
3917        __j = __i;
3918    }
3919    return true;
3920}
3921
3922template <class _Compare, class _BidirectionalIterator>
3923void
3924__insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1,
3925                      typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp)
3926{
3927    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3928    if (__first1 != __last1)
3929    {
3930        __destruct_n __d(0);
3931        unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
3932        value_type* __last2 = __first2;
3933        ::new ((void*)__last2) value_type(_VSTD::move(*__first1));
3934        __d.template __incr<value_type>();
3935        for (++__last2; ++__first1 != __last1; ++__last2)
3936        {
3937            value_type* __j2 = __last2;
3938            value_type* __i2 = __j2;
3939            if (__comp(*__first1, *--__i2))
3940            {
3941                ::new ((void*)__j2) value_type(_VSTD::move(*__i2));
3942                __d.template __incr<value_type>();
3943                for (--__j2; __i2 != __first2 && __comp(*__first1,  *--__i2); --__j2)
3944                    *__j2 = _VSTD::move(*__i2);
3945                *__j2 = _VSTD::move(*__first1);
3946            }
3947            else
3948            {
3949                ::new ((void*)__j2) value_type(_VSTD::move(*__first1));
3950                __d.template __incr<value_type>();
3951            }
3952        }
3953        __h.release();
3954    }
3955}
3956
3957template <class _Compare, class _RandomAccessIterator>
3958void
3959__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3960{
3961    // _Compare is known to be a reference type
3962    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3963    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3964    const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
3965                                    is_trivially_copy_assignable<value_type>::value ? 30 : 6;
3966    while (true)
3967    {
3968    __restart:
3969        difference_type __len = __last - __first;
3970        switch (__len)
3971        {
3972        case 0:
3973        case 1:
3974            return;
3975        case 2:
3976            if (__comp(*--__last, *__first))
3977                swap(*__first, *__last);
3978            return;
3979        case 3:
3980            _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3981            return;
3982        case 4:
3983            _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3984            return;
3985        case 5:
3986            _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3987            return;
3988        }
3989        if (__len <= __limit)
3990        {
3991            _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
3992            return;
3993        }
3994        // __len > 5
3995        _RandomAccessIterator __m = __first;
3996        _RandomAccessIterator __lm1 = __last;
3997        --__lm1;
3998        unsigned __n_swaps;
3999        {
4000        difference_type __delta;
4001        if (__len >= 1000)
4002        {
4003            __delta = __len/2;
4004            __m += __delta;
4005            __delta /= 2;
4006            __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
4007        }
4008        else
4009        {
4010            __delta = __len/2;
4011            __m += __delta;
4012            __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
4013        }
4014        }
4015        // *__m is median
4016        // partition [__first, __m) < *__m and *__m <= [__m, __last)
4017        // (this inhibits tossing elements equivalent to __m around unnecessarily)
4018        _RandomAccessIterator __i = __first;
4019        _RandomAccessIterator __j = __lm1;
4020        // j points beyond range to be tested, *__m is known to be <= *__lm1
4021        // The search going up is known to be guarded but the search coming down isn't.
4022        // Prime the downward search with a guard.
4023        if (!__comp(*__i, *__m))  // if *__first == *__m
4024        {
4025            // *__first == *__m, *__first doesn't go in first part
4026            // manually guard downward moving __j against __i
4027            while (true)
4028            {
4029                if (__i == --__j)
4030                {
4031                    // *__first == *__m, *__m <= all other elements
4032                    // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
4033                    ++__i;  // __first + 1
4034                    __j = __last;
4035                    if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
4036                    {
4037                        while (true)
4038                        {
4039                            if (__i == __j)
4040                                return;  // [__first, __last) all equivalent elements
4041                            if (__comp(*__first, *__i))
4042                            {
4043                                swap(*__i, *__j);
4044                                ++__n_swaps;
4045                                ++__i;
4046                                break;
4047                            }
4048                            ++__i;
4049                        }
4050                    }
4051                    // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
4052                    if (__i == __j)
4053                        return;
4054                    while (true)
4055                    {
4056                        while (!__comp(*__first, *__i))
4057                            ++__i;
4058                        while (__comp(*__first, *--__j))
4059                            ;
4060                        if (__i >= __j)
4061                            break;
4062                        swap(*__i, *__j);
4063                        ++__n_swaps;
4064                        ++__i;
4065                    }
4066                    // [__first, __i) == *__first and *__first < [__i, __last)
4067                    // The first part is sorted, sort the second part
4068                    // _VSTD::__sort<_Compare>(__i, __last, __comp);
4069                    __first = __i;
4070                    goto __restart;
4071                }
4072                if (__comp(*__j, *__m))
4073                {
4074                    swap(*__i, *__j);
4075                    ++__n_swaps;
4076                    break;  // found guard for downward moving __j, now use unguarded partition
4077                }
4078            }
4079        }
4080        // It is known that *__i < *__m
4081        ++__i;
4082        // j points beyond range to be tested, *__m is known to be <= *__lm1
4083        // if not yet partitioned...
4084        if (__i < __j)
4085        {
4086            // known that *(__i - 1) < *__m
4087            // known that __i <= __m
4088            while (true)
4089            {
4090                // __m still guards upward moving __i
4091                while (__comp(*__i, *__m))
4092                    ++__i;
4093                // It is now known that a guard exists for downward moving __j
4094                while (!__comp(*--__j, *__m))
4095                    ;
4096                if (__i > __j)
4097                    break;
4098                swap(*__i, *__j);
4099                ++__n_swaps;
4100                // It is known that __m != __j
4101                // If __m just moved, follow it
4102                if (__m == __i)
4103                    __m = __j;
4104                ++__i;
4105            }
4106        }
4107        // [__first, __i) < *__m and *__m <= [__i, __last)
4108        if (__i != __m && __comp(*__m, *__i))
4109        {
4110            swap(*__i, *__m);
4111            ++__n_swaps;
4112        }
4113        // [__first, __i) < *__i and *__i <= [__i+1, __last)
4114        // If we were given a perfect partition, see if insertion sort is quick...
4115        if (__n_swaps == 0)
4116        {
4117            bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
4118            if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
4119            {
4120                if (__fs)
4121                    return;
4122                __last = __i;
4123                continue;
4124            }
4125            else
4126            {
4127                if (__fs)
4128                {
4129                    __first = ++__i;
4130                    continue;
4131                }
4132            }
4133        }
4134        // sort smaller range with recursive call and larger with tail recursion elimination
4135        if (__i - __first < __last - __i)
4136        {
4137            _VSTD::__sort<_Compare>(__first, __i, __comp);
4138            // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4139            __first = ++__i;
4140        }
4141        else
4142        {
4143            _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4144            // _VSTD::__sort<_Compare>(__first, __i, __comp);
4145            __last = __i;
4146        }
4147    }
4148}
4149
4150// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
4151template <class _RandomAccessIterator, class _Compare>
4152inline _LIBCPP_INLINE_VISIBILITY
4153void
4154sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4155{
4156    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4157    _VSTD::__sort<_Comp_ref>(__first, __last, _Comp_ref(__comp));
4158}
4159
4160template <class _RandomAccessIterator>
4161inline _LIBCPP_INLINE_VISIBILITY
4162void
4163sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4164{
4165    _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4166}
4167
4168template <class _Tp>
4169inline _LIBCPP_INLINE_VISIBILITY
4170void
4171sort(_Tp** __first, _Tp** __last)
4172{
4173    _VSTD::sort((uintptr_t*)__first, (uintptr_t*)__last, __less<uintptr_t>());
4174}
4175
4176template <class _Tp>
4177inline _LIBCPP_INLINE_VISIBILITY
4178void
4179sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
4180{
4181    _VSTD::sort(__first.base(), __last.base());
4182}
4183
4184template <class _Tp, class _Compare>
4185inline _LIBCPP_INLINE_VISIBILITY
4186void
4187sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
4188{
4189    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4190    _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
4191}
4192
4193_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
4194_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4195_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4196_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4197_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))
4198_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4199_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&))
4200_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4201_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&))
4202_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4203_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4204_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>&))
4205_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&))
4206_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&))
4207_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4208
4209_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))
4210_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4211_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4212_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4213_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))
4214_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4215_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&))
4216_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4217_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&))
4218_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4219_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4220_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>&))
4221_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&))
4222_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&))
4223_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4224
4225_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>&))
4226
4227// lower_bound
4228
4229template <class _Compare, class _ForwardIterator, class _Tp>
4230_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
4231__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4232{
4233    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4234    difference_type __len = _VSTD::distance(__first, __last);
4235    while (__len != 0)
4236    {
4237        difference_type __l2 = _VSTD::__half_positive(__len);
4238        _ForwardIterator __m = __first;
4239        _VSTD::advance(__m, __l2);
4240        if (__comp(*__m, __value_))
4241        {
4242            __first = ++__m;
4243            __len -= __l2 + 1;
4244        }
4245        else
4246            __len = __l2;
4247    }
4248    return __first;
4249}
4250
4251template <class _ForwardIterator, class _Tp, class _Compare>
4252_LIBCPP_NODISCARD_EXT inline
4253_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4254_ForwardIterator
4255lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4256{
4257    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4258    return _VSTD::__lower_bound<_Comp_ref>(__first, __last, __value_, __comp);
4259}
4260
4261template <class _ForwardIterator, class _Tp>
4262_LIBCPP_NODISCARD_EXT inline
4263_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4264_ForwardIterator
4265lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4266{
4267    return _VSTD::lower_bound(__first, __last, __value_,
4268                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4269}
4270
4271// upper_bound
4272
4273template <class _Compare, class _ForwardIterator, class _Tp>
4274_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
4275__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4276{
4277    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4278    difference_type __len = _VSTD::distance(__first, __last);
4279    while (__len != 0)
4280    {
4281        difference_type __l2 = _VSTD::__half_positive(__len);
4282        _ForwardIterator __m = __first;
4283        _VSTD::advance(__m, __l2);
4284        if (__comp(__value_, *__m))
4285            __len = __l2;
4286        else
4287        {
4288            __first = ++__m;
4289            __len -= __l2 + 1;
4290        }
4291    }
4292    return __first;
4293}
4294
4295template <class _ForwardIterator, class _Tp, class _Compare>
4296_LIBCPP_NODISCARD_EXT inline
4297_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4298_ForwardIterator
4299upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4300{
4301    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4302    return _VSTD::__upper_bound<_Comp_ref>(__first, __last, __value_, __comp);
4303}
4304
4305template <class _ForwardIterator, class _Tp>
4306_LIBCPP_NODISCARD_EXT inline
4307_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4308_ForwardIterator
4309upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4310{
4311    return _VSTD::upper_bound(__first, __last, __value_,
4312                             __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
4313}
4314
4315// equal_range
4316
4317template <class _Compare, class _ForwardIterator, class _Tp>
4318_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator>
4319__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4320{
4321    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4322    difference_type __len = _VSTD::distance(__first, __last);
4323    while (__len != 0)
4324    {
4325        difference_type __l2 = _VSTD::__half_positive(__len);
4326        _ForwardIterator __m = __first;
4327        _VSTD::advance(__m, __l2);
4328        if (__comp(*__m, __value_))
4329        {
4330            __first = ++__m;
4331            __len -= __l2 + 1;
4332        }
4333        else if (__comp(__value_, *__m))
4334        {
4335            __last = __m;
4336            __len = __l2;
4337        }
4338        else
4339        {
4340            _ForwardIterator __mp1 = __m;
4341            return pair<_ForwardIterator, _ForwardIterator>
4342                   (
4343                      _VSTD::__lower_bound<_Compare>(__first, __m, __value_, __comp),
4344                      _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value_, __comp)
4345                   );
4346        }
4347    }
4348    return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4349}
4350
4351template <class _ForwardIterator, class _Tp, class _Compare>
4352_LIBCPP_NODISCARD_EXT inline
4353_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4354pair<_ForwardIterator, _ForwardIterator>
4355equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4356{
4357    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4358    return _VSTD::__equal_range<_Comp_ref>(__first, __last, __value_, __comp);
4359}
4360
4361template <class _ForwardIterator, class _Tp>
4362_LIBCPP_NODISCARD_EXT inline
4363_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4364pair<_ForwardIterator, _ForwardIterator>
4365equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4366{
4367    return _VSTD::equal_range(__first, __last, __value_,
4368                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4369}
4370
4371// binary_search
4372
4373template <class _Compare, class _ForwardIterator, class _Tp>
4374inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4375bool
4376__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4377{
4378    __first = _VSTD::__lower_bound<_Compare>(__first, __last, __value_, __comp);
4379    return __first != __last && !__comp(__value_, *__first);
4380}
4381
4382template <class _ForwardIterator, class _Tp, class _Compare>
4383_LIBCPP_NODISCARD_EXT inline
4384_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4385bool
4386binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4387{
4388    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4389    return _VSTD::__binary_search<_Comp_ref>(__first, __last, __value_, __comp);
4390}
4391
4392template <class _ForwardIterator, class _Tp>
4393_LIBCPP_NODISCARD_EXT inline
4394_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4395bool
4396binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4397{
4398    return _VSTD::binary_search(__first, __last, __value_,
4399                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4400}
4401
4402// merge
4403
4404template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4405_LIBCPP_CONSTEXPR_AFTER_CXX17
4406_OutputIterator
4407__merge(_InputIterator1 __first1, _InputIterator1 __last1,
4408        _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4409{
4410    for (; __first1 != __last1; ++__result)
4411    {
4412        if (__first2 == __last2)
4413            return _VSTD::copy(__first1, __last1, __result);
4414        if (__comp(*__first2, *__first1))
4415        {
4416            *__result = *__first2;
4417            ++__first2;
4418        }
4419        else
4420        {
4421            *__result = *__first1;
4422            ++__first1;
4423        }
4424    }
4425    return _VSTD::copy(__first2, __last2, __result);
4426}
4427
4428template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4429inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4430_OutputIterator
4431merge(_InputIterator1 __first1, _InputIterator1 __last1,
4432      _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4433{
4434    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4435    return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4436}
4437
4438template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4439inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4440_OutputIterator
4441merge(_InputIterator1 __first1, _InputIterator1 __last1,
4442      _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4443{
4444    typedef typename iterator_traits<_InputIterator1>::value_type __v1;
4445    typedef typename iterator_traits<_InputIterator2>::value_type __v2;
4446    return _VSTD::merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
4447}
4448
4449// inplace_merge
4450
4451template <class _Compare, class _InputIterator1, class _InputIterator2,
4452          class _OutputIterator>
4453void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
4454                          _InputIterator2 __first2, _InputIterator2 __last2,
4455                          _OutputIterator __result, _Compare __comp)
4456{
4457    for (; __first1 != __last1; ++__result)
4458    {
4459        if (__first2 == __last2)
4460        {
4461            _VSTD::move(__first1, __last1, __result);
4462            return;
4463        }
4464
4465        if (__comp(*__first2, *__first1))
4466        {
4467            *__result = _VSTD::move(*__first2);
4468            ++__first2;
4469        }
4470        else
4471        {
4472            *__result = _VSTD::move(*__first1);
4473            ++__first1;
4474        }
4475    }
4476    // __first2 through __last2 are already in the right spot.
4477}
4478
4479template <class _Compare, class _BidirectionalIterator>
4480void
4481__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4482                _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4483                                 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4484                typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
4485{
4486    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4487    __destruct_n __d(0);
4488    unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4489    if (__len1 <= __len2)
4490    {
4491        value_type* __p = __buff;
4492        for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
4493            ::new ((void*)__p) value_type(_VSTD::move(*__i));
4494        _VSTD::__half_inplace_merge<_Compare>(__buff, __p, __middle, __last, __first, __comp);
4495    }
4496    else
4497    {
4498        value_type* __p = __buff;
4499        for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
4500            ::new ((void*)__p) value_type(_VSTD::move(*__i));
4501        typedef reverse_iterator<_BidirectionalIterator> _RBi;
4502        typedef reverse_iterator<value_type*> _Rv;
4503        typedef __invert<_Compare> _Inverted;
4504        _VSTD::__half_inplace_merge<_Inverted>(_Rv(__p), _Rv(__buff),
4505                                    _RBi(__middle), _RBi(__first),
4506                                    _RBi(__last), _Inverted(__comp));
4507    }
4508}
4509
4510template <class _Compare, class _BidirectionalIterator>
4511void
4512__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4513                _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4514                                 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4515                typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
4516{
4517    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4518    while (true)
4519    {
4520        // if __middle == __last, we're done
4521        if (__len2 == 0)
4522            return;
4523        if (__len1 <= __buff_size || __len2 <= __buff_size)
4524            return _VSTD::__buffered_inplace_merge<_Compare>
4525                   (__first, __middle, __last, __comp, __len1, __len2, __buff);
4526        // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
4527        for (; true; ++__first, (void) --__len1)
4528        {
4529            if (__len1 == 0)
4530                return;
4531            if (__comp(*__middle, *__first))
4532                break;
4533        }
4534        // __first < __middle < __last
4535        // *__first > *__middle
4536        // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4537        //     all elements in:
4538        //         [__first, __m1)  <= [__middle, __m2)
4539        //         [__middle, __m2) <  [__m1, __middle)
4540        //         [__m1, __middle) <= [__m2, __last)
4541        //     and __m1 or __m2 is in the middle of its range
4542        _BidirectionalIterator __m1;  // "median" of [__first, __middle)
4543        _BidirectionalIterator __m2;  // "median" of [__middle, __last)
4544        difference_type __len11;      // distance(__first, __m1)
4545        difference_type __len21;      // distance(__middle, __m2)
4546        // binary search smaller range
4547        if (__len1 < __len2)
4548        {   // __len >= 1, __len2 >= 2
4549            __len21 = __len2 / 2;
4550            __m2 = __middle;
4551            _VSTD::advance(__m2, __len21);
4552            __m1 = _VSTD::__upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4553            __len11 = _VSTD::distance(__first, __m1);
4554        }
4555        else
4556        {
4557            if (__len1 == 1)
4558            {   // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
4559                // It is known *__first > *__middle
4560                swap(*__first, *__middle);
4561                return;
4562            }
4563            // __len1 >= 2, __len2 >= 1
4564            __len11 = __len1 / 2;
4565            __m1 = __first;
4566            _VSTD::advance(__m1, __len11);
4567            __m2 = _VSTD::__lower_bound<_Compare>(__middle, __last, *__m1, __comp);
4568            __len21 = _VSTD::distance(__middle, __m2);
4569        }
4570        difference_type __len12 = __len1 - __len11;  // distance(__m1, __middle)
4571        difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)
4572        // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4573        // swap middle two partitions
4574        __middle = _VSTD::rotate(__m1, __middle, __m2);
4575        // __len12 and __len21 now have swapped meanings
4576        // merge smaller range with recursive call and larger with tail recursion elimination
4577        if (__len11 + __len21 < __len12 + __len22)
4578        {
4579            _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4580//          _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4581            __first = __middle;
4582            __middle = __m2;
4583            __len1 = __len12;
4584            __len2 = __len22;
4585        }
4586        else
4587        {
4588            _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4589//          _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4590            __last = __middle;
4591            __middle = __m1;
4592            __len1 = __len11;
4593            __len2 = __len21;
4594        }
4595    }
4596}
4597
4598template <class _BidirectionalIterator, class _Compare>
4599inline _LIBCPP_INLINE_VISIBILITY
4600void
4601inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4602              _Compare __comp)
4603{
4604    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4605    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4606    difference_type __len1 = _VSTD::distance(__first, __middle);
4607    difference_type __len2 = _VSTD::distance(__middle, __last);
4608    difference_type __buf_size = _VSTD::min(__len1, __len2);
4609    pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
4610    unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
4611    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4612    return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4613                                            __buf.first, __buf.second);
4614}
4615
4616template <class _BidirectionalIterator>
4617inline _LIBCPP_INLINE_VISIBILITY
4618void
4619inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
4620{
4621    _VSTD::inplace_merge(__first, __middle, __last,
4622                        __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4623}
4624
4625// stable_sort
4626
4627template <class _Compare, class _InputIterator1, class _InputIterator2>
4628void
4629__merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
4630        _InputIterator2 __first2, _InputIterator2 __last2,
4631        typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
4632{
4633    typedef typename iterator_traits<_InputIterator1>::value_type value_type;
4634    __destruct_n __d(0);
4635    unique_ptr<value_type, __destruct_n&> __h(__result, __d);
4636    for (; true; ++__result)
4637    {
4638        if (__first1 == __last1)
4639        {
4640            for (; __first2 != __last2; ++__first2, ++__result, (void)__d.template __incr<value_type>())
4641                ::new ((void*)__result) value_type(_VSTD::move(*__first2));
4642            __h.release();
4643            return;
4644        }
4645        if (__first2 == __last2)
4646        {
4647            for (; __first1 != __last1; ++__first1, ++__result, (void)__d.template __incr<value_type>())
4648                ::new ((void*)__result) value_type(_VSTD::move(*__first1));
4649            __h.release();
4650            return;
4651        }
4652        if (__comp(*__first2, *__first1))
4653        {
4654            ::new ((void*)__result) value_type(_VSTD::move(*__first2));
4655            __d.template __incr<value_type>();
4656            ++__first2;
4657        }
4658        else
4659        {
4660            ::new ((void*)__result) value_type(_VSTD::move(*__first1));
4661            __d.template __incr<value_type>();
4662            ++__first1;
4663        }
4664    }
4665}
4666
4667template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4668void
4669__merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
4670        _InputIterator2 __first2, _InputIterator2 __last2,
4671        _OutputIterator __result, _Compare __comp)
4672{
4673    for (; __first1 != __last1; ++__result)
4674    {
4675        if (__first2 == __last2)
4676        {
4677            for (; __first1 != __last1; ++__first1, (void) ++__result)
4678                *__result = _VSTD::move(*__first1);
4679            return;
4680        }
4681        if (__comp(*__first2, *__first1))
4682        {
4683            *__result = _VSTD::move(*__first2);
4684            ++__first2;
4685        }
4686        else
4687        {
4688            *__result = _VSTD::move(*__first1);
4689            ++__first1;
4690        }
4691    }
4692    for (; __first2 != __last2; ++__first2, (void) ++__result)
4693        *__result = _VSTD::move(*__first2);
4694}
4695
4696template <class _Compare, class _RandomAccessIterator>
4697void
4698__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4699              typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4700              typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
4701
4702template <class _Compare, class _RandomAccessIterator>
4703void
4704__stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
4705                   typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4706                   typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
4707{
4708    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4709    switch (__len)
4710    {
4711    case 0:
4712        return;
4713    case 1:
4714        ::new ((void*)__first2) value_type(_VSTD::move(*__first1));
4715        return;
4716    case 2:
4717        __destruct_n __d(0);
4718        unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
4719        if (__comp(*--__last1, *__first1))
4720        {
4721            ::new ((void*)__first2) value_type(_VSTD::move(*__last1));
4722            __d.template __incr<value_type>();
4723            ++__first2;
4724            ::new ((void*)__first2) value_type(_VSTD::move(*__first1));
4725        }
4726        else
4727        {
4728            ::new ((void*)__first2) value_type(_VSTD::move(*__first1));
4729            __d.template __incr<value_type>();
4730            ++__first2;
4731            ::new ((void*)__first2) value_type(_VSTD::move(*__last1));
4732        }
4733        __h2.release();
4734        return;
4735    }
4736    if (__len <= 8)
4737    {
4738        _VSTD::__insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
4739        return;
4740    }
4741    typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4742    _RandomAccessIterator __m = __first1 + __l2;
4743    _VSTD::__stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
4744    _VSTD::__stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
4745    _VSTD::__merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
4746}
4747
4748template <class _Tp>
4749struct __stable_sort_switch
4750{
4751    static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
4752};
4753
4754template <class _Compare, class _RandomAccessIterator>
4755void
4756__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4757              typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4758              typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
4759{
4760    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4761    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4762    switch (__len)
4763    {
4764    case 0:
4765    case 1:
4766        return;
4767    case 2:
4768        if (__comp(*--__last, *__first))
4769            swap(*__first, *__last);
4770        return;
4771    }
4772    if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4773    {
4774        _VSTD::__insertion_sort<_Compare>(__first, __last, __comp);
4775        return;
4776    }
4777    typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4778    _RandomAccessIterator __m = __first + __l2;
4779    if (__len <= __buff_size)
4780    {
4781        __destruct_n __d(0);
4782        unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4783        _VSTD::__stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4784        __d.__set(__l2, (value_type*)nullptr);
4785        _VSTD::__stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
4786        __d.__set(__len, (value_type*)nullptr);
4787        _VSTD::__merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4788//         _VSTD::__merge<_Compare>(move_iterator<value_type*>(__buff),
4789//                                  move_iterator<value_type*>(__buff + __l2),
4790//                                  move_iterator<_RandomAccessIterator>(__buff + __l2),
4791//                                  move_iterator<_RandomAccessIterator>(__buff + __len),
4792//                                  __first, __comp);
4793        return;
4794    }
4795    _VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4796    _VSTD::__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
4797    _VSTD::__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4798}
4799
4800template <class _RandomAccessIterator, class _Compare>
4801inline _LIBCPP_INLINE_VISIBILITY
4802void
4803stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4804{
4805    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4806    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4807    difference_type __len = __last - __first;
4808    pair<value_type*, ptrdiff_t> __buf(0, 0);
4809    unique_ptr<value_type, __return_temporary_buffer> __h;
4810    if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4811    {
4812        __buf = _VSTD::get_temporary_buffer<value_type>(__len);
4813        __h.reset(__buf.first);
4814    }
4815    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4816    _VSTD::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4817}
4818
4819template <class _RandomAccessIterator>
4820inline _LIBCPP_INLINE_VISIBILITY
4821void
4822stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4823{
4824    _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4825}
4826
4827// is_heap_until
4828
4829template <class _RandomAccessIterator, class _Compare>
4830_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
4831is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4832{
4833    typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4834    difference_type __len = __last - __first;
4835    difference_type __p = 0;
4836    difference_type __c = 1;
4837    _RandomAccessIterator __pp = __first;
4838    while (__c < __len)
4839    {
4840        _RandomAccessIterator __cp = __first + __c;
4841        if (__comp(*__pp, *__cp))
4842            return __cp;
4843        ++__c;
4844        ++__cp;
4845        if (__c == __len)
4846            return __last;
4847        if (__comp(*__pp, *__cp))
4848            return __cp;
4849        ++__p;
4850        ++__pp;
4851        __c = 2 * __p + 1;
4852    }
4853    return __last;
4854}
4855
4856template<class _RandomAccessIterator>
4857_LIBCPP_NODISCARD_EXT inline
4858_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4859_RandomAccessIterator
4860is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4861{
4862    return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4863}
4864
4865// is_heap
4866
4867template <class _RandomAccessIterator, class _Compare>
4868_LIBCPP_NODISCARD_EXT inline
4869_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4870bool
4871is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4872{
4873    return _VSTD::is_heap_until(__first, __last, __comp) == __last;
4874}
4875
4876template<class _RandomAccessIterator>
4877_LIBCPP_NODISCARD_EXT inline
4878_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4879bool
4880is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4881{
4882    return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4883}
4884
4885// push_heap
4886
4887template <class _Compare, class _RandomAccessIterator>
4888void
4889__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4890          typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4891{
4892    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4893    if (__len > 1)
4894    {
4895        __len = (__len - 2) / 2;
4896        _RandomAccessIterator __ptr = __first + __len;
4897        if (__comp(*__ptr, *--__last))
4898        {
4899            value_type __t(_VSTD::move(*__last));
4900            do
4901            {
4902                *__last = _VSTD::move(*__ptr);
4903                __last = __ptr;
4904                if (__len == 0)
4905                    break;
4906                __len = (__len - 1) / 2;
4907                __ptr = __first + __len;
4908            } while (__comp(*__ptr, __t));
4909            *__last = _VSTD::move(__t);
4910        }
4911    }
4912}
4913
4914template <class _RandomAccessIterator, class _Compare>
4915inline _LIBCPP_INLINE_VISIBILITY
4916void
4917push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4918{
4919    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4920    _VSTD::__sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
4921}
4922
4923template <class _RandomAccessIterator>
4924inline _LIBCPP_INLINE_VISIBILITY
4925void
4926push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4927{
4928    _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4929}
4930
4931// pop_heap
4932
4933template <class _Compare, class _RandomAccessIterator>
4934void
4935__sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/,
4936            _Compare __comp,
4937            typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4938            _RandomAccessIterator __start)
4939{
4940    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4941    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4942    // left-child of __start is at 2 * __start + 1
4943    // right-child of __start is at 2 * __start + 2
4944    difference_type __child = __start - __first;
4945
4946    if (__len < 2 || (__len - 2) / 2 < __child)
4947        return;
4948
4949    __child = 2 * __child + 1;
4950    _RandomAccessIterator __child_i = __first + __child;
4951
4952    if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4953        // right-child exists and is greater than left-child
4954        ++__child_i;
4955        ++__child;
4956    }
4957
4958    // check if we are in heap-order
4959    if (__comp(*__child_i, *__start))
4960        // we are, __start is larger than it's largest child
4961        return;
4962
4963    value_type __top(_VSTD::move(*__start));
4964    do
4965    {
4966        // we are not in heap-order, swap the parent with it's largest child
4967        *__start = _VSTD::move(*__child_i);
4968        __start = __child_i;
4969
4970        if ((__len - 2) / 2 < __child)
4971            break;
4972
4973        // recompute the child based off of the updated parent
4974        __child = 2 * __child + 1;
4975        __child_i = __first + __child;
4976
4977        if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4978            // right-child exists and is greater than left-child
4979            ++__child_i;
4980            ++__child;
4981        }
4982
4983        // check if we are in heap-order
4984    } while (!__comp(*__child_i, __top));
4985    *__start = _VSTD::move(__top);
4986}
4987
4988template <class _Compare, class _RandomAccessIterator>
4989inline _LIBCPP_INLINE_VISIBILITY
4990void
4991__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4992           typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4993{
4994    if (__len > 1)
4995    {
4996        swap(*__first, *--__last);
4997        _VSTD::__sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);
4998    }
4999}
5000
5001template <class _RandomAccessIterator, class _Compare>
5002inline _LIBCPP_INLINE_VISIBILITY
5003void
5004pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5005{
5006    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5007    _VSTD::__pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
5008}
5009
5010template <class _RandomAccessIterator>
5011inline _LIBCPP_INLINE_VISIBILITY
5012void
5013pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5014{
5015    _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5016}
5017
5018// make_heap
5019
5020template <class _Compare, class _RandomAccessIterator>
5021void
5022__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5023{
5024    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5025    difference_type __n = __last - __first;
5026    if (__n > 1)
5027    {
5028        // start from the first parent, there is no need to consider children
5029        for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start)
5030        {
5031            _VSTD::__sift_down<_Compare>(__first, __last, __comp, __n, __first + __start);
5032        }
5033    }
5034}
5035
5036template <class _RandomAccessIterator, class _Compare>
5037inline _LIBCPP_INLINE_VISIBILITY
5038void
5039make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5040{
5041    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5042    _VSTD::__make_heap<_Comp_ref>(__first, __last, __comp);
5043}
5044
5045template <class _RandomAccessIterator>
5046inline _LIBCPP_INLINE_VISIBILITY
5047void
5048make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5049{
5050    _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5051}
5052
5053// sort_heap
5054
5055template <class _Compare, class _RandomAccessIterator>
5056void
5057__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5058{
5059    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5060    for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n)
5061        _VSTD::__pop_heap<_Compare>(__first, __last, __comp, __n);
5062}
5063
5064template <class _RandomAccessIterator, class _Compare>
5065inline _LIBCPP_INLINE_VISIBILITY
5066void
5067sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5068{
5069    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5070    _VSTD::__sort_heap<_Comp_ref>(__first, __last, __comp);
5071}
5072
5073template <class _RandomAccessIterator>
5074inline _LIBCPP_INLINE_VISIBILITY
5075void
5076sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5077{
5078    _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5079}
5080
5081// partial_sort
5082
5083template <class _Compare, class _RandomAccessIterator>
5084void
5085__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5086             _Compare __comp)
5087{
5088    _VSTD::__make_heap<_Compare>(__first, __middle, __comp);
5089    typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
5090    for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
5091    {
5092        if (__comp(*__i, *__first))
5093        {
5094            swap(*__i, *__first);
5095            _VSTD::__sift_down<_Compare>(__first, __middle, __comp, __len, __first);
5096        }
5097    }
5098    _VSTD::__sort_heap<_Compare>(__first, __middle, __comp);
5099}
5100
5101template <class _RandomAccessIterator, class _Compare>
5102inline _LIBCPP_INLINE_VISIBILITY
5103void
5104partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5105             _Compare __comp)
5106{
5107    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5108    _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
5109}
5110
5111template <class _RandomAccessIterator>
5112inline _LIBCPP_INLINE_VISIBILITY
5113void
5114partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
5115{
5116    _VSTD::partial_sort(__first, __middle, __last,
5117                       __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5118}
5119
5120// partial_sort_copy
5121
5122template <class _Compare, class _InputIterator, class _RandomAccessIterator>
5123_RandomAccessIterator
5124__partial_sort_copy(_InputIterator __first, _InputIterator __last,
5125                    _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5126{
5127    _RandomAccessIterator __r = __result_first;
5128    if (__r != __result_last)
5129    {
5130        for (; __first != __last && __r != __result_last; ++__first, (void) ++__r)
5131            *__r = *__first;
5132        _VSTD::__make_heap<_Compare>(__result_first, __r, __comp);
5133        typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
5134        for (; __first != __last; ++__first)
5135            if (__comp(*__first, *__result_first))
5136            {
5137                *__result_first = *__first;
5138                _VSTD::__sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first);
5139            }
5140        _VSTD::__sort_heap<_Compare>(__result_first, __r, __comp);
5141    }
5142    return __r;
5143}
5144
5145template <class _InputIterator, class _RandomAccessIterator, class _Compare>
5146inline _LIBCPP_INLINE_VISIBILITY
5147_RandomAccessIterator
5148partial_sort_copy(_InputIterator __first, _InputIterator __last,
5149                  _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5150{
5151    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5152    return _VSTD::__partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
5153}
5154
5155template <class _InputIterator, class _RandomAccessIterator>
5156inline _LIBCPP_INLINE_VISIBILITY
5157_RandomAccessIterator
5158partial_sort_copy(_InputIterator __first, _InputIterator __last,
5159                  _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
5160{
5161    return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
5162                                   __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5163}
5164
5165// nth_element
5166
5167template <class _Compare, class _RandomAccessIterator>
5168void
5169__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5170{
5171    // _Compare is known to be a reference type
5172    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5173    const difference_type __limit = 7;
5174    while (true)
5175    {
5176    __restart:
5177        if (__nth == __last)
5178            return;
5179        difference_type __len = __last - __first;
5180        switch (__len)
5181        {
5182        case 0:
5183        case 1:
5184            return;
5185        case 2:
5186            if (__comp(*--__last, *__first))
5187                swap(*__first, *__last);
5188            return;
5189        case 3:
5190            {
5191            _RandomAccessIterator __m = __first;
5192            _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
5193            return;
5194            }
5195        }
5196        if (__len <= __limit)
5197        {
5198            _VSTD::__selection_sort<_Compare>(__first, __last, __comp);
5199            return;
5200        }
5201        // __len > __limit >= 3
5202        _RandomAccessIterator __m = __first + __len/2;
5203        _RandomAccessIterator __lm1 = __last;
5204        unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
5205        // *__m is median
5206        // partition [__first, __m) < *__m and *__m <= [__m, __last)
5207        // (this inhibits tossing elements equivalent to __m around unnecessarily)
5208        _RandomAccessIterator __i = __first;
5209        _RandomAccessIterator __j = __lm1;
5210        // j points beyond range to be tested, *__lm1 is known to be <= *__m
5211        // The search going up is known to be guarded but the search coming down isn't.
5212        // Prime the downward search with a guard.
5213        if (!__comp(*__i, *__m))  // if *__first == *__m
5214        {
5215            // *__first == *__m, *__first doesn't go in first part
5216            // manually guard downward moving __j against __i
5217            while (true)
5218            {
5219                if (__i == --__j)
5220                {
5221                    // *__first == *__m, *__m <= all other elements
5222                    // Partition instead into [__first, __i) == *__first and *__first < [__i, __last)
5223                    ++__i;  // __first + 1
5224                    __j = __last;
5225                    if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
5226                    {
5227                        while (true)
5228                        {
5229                            if (__i == __j)
5230                                return;  // [__first, __last) all equivalent elements
5231                            if (__comp(*__first, *__i))
5232                            {
5233                                swap(*__i, *__j);
5234                                ++__n_swaps;
5235                                ++__i;
5236                                break;
5237                            }
5238                            ++__i;
5239                        }
5240                    }
5241                    // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
5242                    if (__i == __j)
5243                        return;
5244                    while (true)
5245                    {
5246                        while (!__comp(*__first, *__i))
5247                            ++__i;
5248                        while (__comp(*__first, *--__j))
5249                            ;
5250                        if (__i >= __j)
5251                            break;
5252                        swap(*__i, *__j);
5253                        ++__n_swaps;
5254                        ++__i;
5255                    }
5256                    // [__first, __i) == *__first and *__first < [__i, __last)
5257                    // The first part is sorted,
5258                    if (__nth < __i)
5259                        return;
5260                    // __nth_element the second part
5261                    // _VSTD::__nth_element<_Compare>(__i, __nth, __last, __comp);
5262                    __first = __i;
5263                    goto __restart;
5264                }
5265                if (__comp(*__j, *__m))
5266                {
5267                    swap(*__i, *__j);
5268                    ++__n_swaps;
5269                    break;  // found guard for downward moving __j, now use unguarded partition
5270                }
5271            }
5272        }
5273        ++__i;
5274        // j points beyond range to be tested, *__lm1 is known to be <= *__m
5275        // if not yet partitioned...
5276        if (__i < __j)
5277        {
5278            // known that *(__i - 1) < *__m
5279            while (true)
5280            {
5281                // __m still guards upward moving __i
5282                while (__comp(*__i, *__m))
5283                    ++__i;
5284                // It is now known that a guard exists for downward moving __j
5285                while (!__comp(*--__j, *__m))
5286                    ;
5287                if (__i >= __j)
5288                    break;
5289                swap(*__i, *__j);
5290                ++__n_swaps;
5291                // It is known that __m != __j
5292                // If __m just moved, follow it
5293                if (__m == __i)
5294                    __m = __j;
5295                ++__i;
5296            }
5297        }
5298        // [__first, __i) < *__m and *__m <= [__i, __last)
5299        if (__i != __m && __comp(*__m, *__i))
5300        {
5301            swap(*__i, *__m);
5302            ++__n_swaps;
5303        }
5304        // [__first, __i) < *__i and *__i <= [__i+1, __last)
5305        if (__nth == __i)
5306            return;
5307        if (__n_swaps == 0)
5308        {
5309            // We were given a perfectly partitioned sequence.  Coincidence?
5310            if (__nth < __i)
5311            {
5312                // Check for [__first, __i) already sorted
5313                __j = __m = __first;
5314                while (++__j != __i)
5315                {
5316                    if (__comp(*__j, *__m))
5317                        // not yet sorted, so sort
5318                        goto not_sorted;
5319                    __m = __j;
5320                }
5321                // [__first, __i) sorted
5322                return;
5323            }
5324            else
5325            {
5326                // Check for [__i, __last) already sorted
5327                __j = __m = __i;
5328                while (++__j != __last)
5329                {
5330                    if (__comp(*__j, *__m))
5331                        // not yet sorted, so sort
5332                        goto not_sorted;
5333                    __m = __j;
5334                }
5335                // [__i, __last) sorted
5336                return;
5337            }
5338        }
5339not_sorted:
5340        // __nth_element on range containing __nth
5341        if (__nth < __i)
5342        {
5343            // _VSTD::__nth_element<_Compare>(__first, __nth, __i, __comp);
5344            __last = __i;
5345        }
5346        else
5347        {
5348            // _VSTD::__nth_element<_Compare>(__i+1, __nth, __last, __comp);
5349            __first = ++__i;
5350        }
5351    }
5352}
5353
5354template <class _RandomAccessIterator, class _Compare>
5355inline _LIBCPP_INLINE_VISIBILITY
5356void
5357nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5358{
5359    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5360    _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp);
5361}
5362
5363template <class _RandomAccessIterator>
5364inline _LIBCPP_INLINE_VISIBILITY
5365void
5366nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
5367{
5368    _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5369}
5370
5371// includes
5372
5373template <class _Compare, class _InputIterator1, class _InputIterator2>
5374_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
5375__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5376           _Compare __comp)
5377{
5378    for (; __first2 != __last2; ++__first1)
5379    {
5380        if (__first1 == __last1 || __comp(*__first2, *__first1))
5381            return false;
5382        if (!__comp(*__first1, *__first2))
5383            ++__first2;
5384    }
5385    return true;
5386}
5387
5388template <class _InputIterator1, class _InputIterator2, class _Compare>
5389_LIBCPP_NODISCARD_EXT inline
5390_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5391bool
5392includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5393         _Compare __comp)
5394{
5395    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5396    return _VSTD::__includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5397}
5398
5399template <class _InputIterator1, class _InputIterator2>
5400_LIBCPP_NODISCARD_EXT inline
5401_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5402bool
5403includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
5404{
5405    return _VSTD::includes(__first1, __last1, __first2, __last2,
5406                          __less<typename iterator_traits<_InputIterator1>::value_type,
5407                                 typename iterator_traits<_InputIterator2>::value_type>());
5408}
5409
5410// set_union
5411
5412template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5413_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
5414__set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5415            _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5416{
5417    for (; __first1 != __last1; ++__result)
5418    {
5419        if (__first2 == __last2)
5420            return _VSTD::copy(__first1, __last1, __result);
5421        if (__comp(*__first2, *__first1))
5422        {
5423            *__result = *__first2;
5424            ++__first2;
5425        }
5426        else
5427        {
5428            if (!__comp(*__first1, *__first2))
5429                ++__first2;
5430            *__result = *__first1;
5431            ++__first1;
5432        }
5433    }
5434    return _VSTD::copy(__first2, __last2, __result);
5435}
5436
5437template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5438inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5439_OutputIterator
5440set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5441          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5442{
5443    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5444    return _VSTD::__set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5445}
5446
5447template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5448inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5449_OutputIterator
5450set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5451          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5452{
5453    return _VSTD::set_union(__first1, __last1, __first2, __last2, __result,
5454                          __less<typename iterator_traits<_InputIterator1>::value_type,
5455                                 typename iterator_traits<_InputIterator2>::value_type>());
5456}
5457
5458// set_intersection
5459
5460template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5461_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
5462__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5463                   _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5464{
5465    while (__first1 != __last1 && __first2 != __last2)
5466    {
5467        if (__comp(*__first1, *__first2))
5468            ++__first1;
5469        else
5470        {
5471            if (!__comp(*__first2, *__first1))
5472            {
5473                *__result = *__first1;
5474                ++__result;
5475                ++__first1;
5476            }
5477            ++__first2;
5478        }
5479    }
5480    return __result;
5481}
5482
5483template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5484inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5485_OutputIterator
5486set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5487                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5488{
5489    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5490    return _VSTD::__set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5491}
5492
5493template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5494inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5495_OutputIterator
5496set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5497                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5498{
5499    return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result,
5500                                  __less<typename iterator_traits<_InputIterator1>::value_type,
5501                                         typename iterator_traits<_InputIterator2>::value_type>());
5502}
5503
5504// set_difference
5505
5506template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5507_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
5508__set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5509                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5510{
5511    while (__first1 != __last1)
5512    {
5513        if (__first2 == __last2)
5514            return _VSTD::copy(__first1, __last1, __result);
5515        if (__comp(*__first1, *__first2))
5516        {
5517            *__result = *__first1;
5518            ++__result;
5519            ++__first1;
5520        }
5521        else
5522        {
5523            if (!__comp(*__first2, *__first1))
5524                ++__first1;
5525            ++__first2;
5526        }
5527    }
5528    return __result;
5529}
5530
5531template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5532inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5533_OutputIterator
5534set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5535               _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5536{
5537    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5538    return _VSTD::__set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5539}
5540
5541template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5542inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5543_OutputIterator
5544set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5545               _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5546{
5547    return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result,
5548                                __less<typename iterator_traits<_InputIterator1>::value_type,
5549                                       typename iterator_traits<_InputIterator2>::value_type>());
5550}
5551
5552// set_symmetric_difference
5553
5554template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5555_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
5556__set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5557                           _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5558{
5559    while (__first1 != __last1)
5560    {
5561        if (__first2 == __last2)
5562            return _VSTD::copy(__first1, __last1, __result);
5563        if (__comp(*__first1, *__first2))
5564        {
5565            *__result = *__first1;
5566            ++__result;
5567            ++__first1;
5568        }
5569        else
5570        {
5571            if (__comp(*__first2, *__first1))
5572            {
5573                *__result = *__first2;
5574                ++__result;
5575            }
5576            else
5577                ++__first1;
5578            ++__first2;
5579        }
5580    }
5581    return _VSTD::copy(__first2, __last2, __result);
5582}
5583
5584template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5585inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5586_OutputIterator
5587set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5588                         _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5589{
5590    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5591    return _VSTD::__set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5592}
5593
5594template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5595inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5596_OutputIterator
5597set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5598                         _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5599{
5600    return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
5601                                          __less<typename iterator_traits<_InputIterator1>::value_type,
5602                                                 typename iterator_traits<_InputIterator2>::value_type>());
5603}
5604
5605// lexicographical_compare
5606
5607template <class _Compare, class _InputIterator1, class _InputIterator2>
5608_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
5609__lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5610                          _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5611{
5612    for (; __first2 != __last2; ++__first1, (void) ++__first2)
5613    {
5614        if (__first1 == __last1 || __comp(*__first1, *__first2))
5615            return true;
5616        if (__comp(*__first2, *__first1))
5617            return false;
5618    }
5619    return false;
5620}
5621
5622template <class _InputIterator1, class _InputIterator2, class _Compare>
5623_LIBCPP_NODISCARD_EXT inline
5624_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5625bool
5626lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5627                        _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5628{
5629    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5630    return _VSTD::__lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5631}
5632
5633template <class _InputIterator1, class _InputIterator2>
5634_LIBCPP_NODISCARD_EXT inline
5635_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5636bool
5637lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5638                        _InputIterator2 __first2, _InputIterator2 __last2)
5639{
5640    return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,
5641                                         __less<typename iterator_traits<_InputIterator1>::value_type,
5642                                                typename iterator_traits<_InputIterator2>::value_type>());
5643}
5644
5645// next_permutation
5646
5647template <class _Compare, class _BidirectionalIterator>
5648bool
5649__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5650{
5651    _BidirectionalIterator __i = __last;
5652    if (__first == __last || __first == --__i)
5653        return false;
5654    while (true)
5655    {
5656        _BidirectionalIterator __ip1 = __i;
5657        if (__comp(*--__i, *__ip1))
5658        {
5659            _BidirectionalIterator __j = __last;
5660            while (!__comp(*__i, *--__j))
5661                ;
5662            swap(*__i, *__j);
5663            _VSTD::reverse(__ip1, __last);
5664            return true;
5665        }
5666        if (__i == __first)
5667        {
5668            _VSTD::reverse(__first, __last);
5669            return false;
5670        }
5671    }
5672}
5673
5674template <class _BidirectionalIterator, class _Compare>
5675inline _LIBCPP_INLINE_VISIBILITY
5676bool
5677next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5678{
5679    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5680    return _VSTD::__next_permutation<_Comp_ref>(__first, __last, __comp);
5681}
5682
5683template <class _BidirectionalIterator>
5684inline _LIBCPP_INLINE_VISIBILITY
5685bool
5686next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5687{
5688    return _VSTD::next_permutation(__first, __last,
5689                                  __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5690}
5691
5692// prev_permutation
5693
5694template <class _Compare, class _BidirectionalIterator>
5695bool
5696__prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5697{
5698    _BidirectionalIterator __i = __last;
5699    if (__first == __last || __first == --__i)
5700        return false;
5701    while (true)
5702    {
5703        _BidirectionalIterator __ip1 = __i;
5704        if (__comp(*__ip1, *--__i))
5705        {
5706            _BidirectionalIterator __j = __last;
5707            while (!__comp(*--__j, *__i))
5708                ;
5709            swap(*__i, *__j);
5710            _VSTD::reverse(__ip1, __last);
5711            return true;
5712        }
5713        if (__i == __first)
5714        {
5715            _VSTD::reverse(__first, __last);
5716            return false;
5717        }
5718    }
5719}
5720
5721template <class _BidirectionalIterator, class _Compare>
5722inline _LIBCPP_INLINE_VISIBILITY
5723bool
5724prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5725{
5726    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
5727    return _VSTD::__prev_permutation<_Comp_ref>(__first, __last, __comp);
5728}
5729
5730template <class _BidirectionalIterator>
5731inline _LIBCPP_INLINE_VISIBILITY
5732bool
5733prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5734{
5735    return _VSTD::prev_permutation(__first, __last,
5736                                  __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5737}
5738
5739_LIBCPP_END_NAMESPACE_STD
5740
5741_LIBCPP_POP_MACROS
5742
5743#if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
5744#   include <__pstl_algorithm>
5745#endif
5746
5747#endif  // _LIBCPP_ALGORITHM
5748