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