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