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