1// -*- C++ -*-
2//===-------------------------- algorithm ---------------------------------===//
3//
4//                     The LLVM Compiler Infrastructure
5//
6// This file is distributed under the University of Illinois Open Source
7// License. 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    has_trivial_copy_assign<_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    has_trivial_copy_assign<_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    has_trivial_copy_assign<_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    has_trivial_copy_assign<_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    for (; __n > 0; --__n, ++__first, ++__result)
1563        *__result = *__first;
1564    return __result;
1565}
1566
1567template<class _InputIterator, class _Size, class _OutputIterator>
1568inline _LIBCPP_INLINE_VISIBILITY
1569typename enable_if
1570<
1571    __is_random_access_iterator<_InputIterator>::value,
1572    _OutputIterator
1573>::type
1574copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1575{
1576    return copy(__first, __first + __n, __result);
1577}
1578
1579// move
1580
1581template <class _InputIterator, class _OutputIterator>
1582inline _LIBCPP_INLINE_VISIBILITY
1583_OutputIterator
1584__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1585{
1586    for (; __first != __last; ++__first, ++__result)
1587        *__result = _STD::move(*__first);
1588    return __result;
1589}
1590
1591template <class _Tp, class _Up>
1592inline _LIBCPP_INLINE_VISIBILITY
1593typename enable_if
1594<
1595    is_same<typename remove_const<_Tp>::type, _Up>::value &&
1596    has_trivial_copy_assign<_Up>::value,
1597    _Up*
1598>::type
1599__move(_Tp* __first, _Tp* __last, _Up* __result)
1600{
1601    const size_t __n = static_cast<size_t>(__last - __first);
1602    _STD::memmove(__result, __first, __n * sizeof(_Up));
1603    return __result + __n;
1604}
1605
1606template <class _InputIterator, class _OutputIterator>
1607inline _LIBCPP_INLINE_VISIBILITY
1608_OutputIterator
1609move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1610{
1611    return _STD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1612}
1613
1614// move_backward
1615
1616template <class _InputIterator, class _OutputIterator>
1617inline _LIBCPP_INLINE_VISIBILITY
1618_OutputIterator
1619__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1620{
1621    while (__first != __last)
1622        *--__result = _STD::move(*--__last);
1623    return __result;
1624}
1625
1626template <class _Tp, class _Up>
1627inline _LIBCPP_INLINE_VISIBILITY
1628typename enable_if
1629<
1630    is_same<typename remove_const<_Tp>::type, _Up>::value &&
1631    has_trivial_copy_assign<_Up>::value,
1632    _Up*
1633>::type
1634__move_backward(_Tp* __first, _Tp* __last, _Up* __result)
1635{
1636    const size_t __n = static_cast<size_t>(__last - __first);
1637    __result -= __n;
1638    _STD::memmove(__result, __first, __n * sizeof(_Up));
1639    return __result;
1640}
1641
1642template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1643inline _LIBCPP_INLINE_VISIBILITY
1644_BidirectionalIterator2
1645move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1646              _BidirectionalIterator2 __result)
1647{
1648    return _STD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1649}
1650
1651// iter_swap
1652
1653template <class _ForwardIterator1, class _ForwardIterator2>
1654inline _LIBCPP_INLINE_VISIBILITY
1655void
1656iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
1657{
1658    swap(*__a, *__b);
1659}
1660
1661// transform
1662
1663template <class _InputIterator, class _OutputIterator, class _UnaryOperation>
1664inline _LIBCPP_INLINE_VISIBILITY
1665_OutputIterator
1666transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op)
1667{
1668    for (; __first != __last; ++__first, ++__result)
1669        *__result = __op(*__first);
1670    return __result;
1671}
1672
1673template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation>
1674inline _LIBCPP_INLINE_VISIBILITY
1675_OutputIterator
1676transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
1677          _OutputIterator __result, _BinaryOperation __binary_op)
1678{
1679    for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
1680        *__result = __binary_op(*__first1, *__first2);
1681    return __result;
1682}
1683
1684// replace
1685
1686template <class _ForwardIterator, class _Tp>
1687inline _LIBCPP_INLINE_VISIBILITY
1688void
1689replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value)
1690{
1691    for (; __first != __last; ++__first)
1692        if (*__first == __old_value)
1693            *__first = __new_value;
1694}
1695
1696// replace_if
1697
1698template <class _ForwardIterator, class _Predicate, class _Tp>
1699inline _LIBCPP_INLINE_VISIBILITY
1700void
1701replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value)
1702{
1703    for (; __first != __last; ++__first)
1704        if (__pred(*__first))
1705            *__first = __new_value;
1706}
1707
1708// replace_copy
1709
1710template <class _InputIterator, class _OutputIterator, class _Tp>
1711inline _LIBCPP_INLINE_VISIBILITY
1712_OutputIterator
1713replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1714             const _Tp& __old_value, const _Tp& __new_value)
1715{
1716    for (; __first != __last; ++__first, ++__result)
1717        if (*__first == __old_value)
1718            *__result = __new_value;
1719        else
1720            *__result = *__first;
1721    return __result;
1722}
1723
1724// replace_copy_if
1725
1726template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp>
1727inline _LIBCPP_INLINE_VISIBILITY
1728_OutputIterator
1729replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1730                _Predicate __pred, const _Tp& __new_value)
1731{
1732    for (; __first != __last; ++__first, ++__result)
1733        if (__pred(*__first))
1734            *__result = __new_value;
1735        else
1736            *__result = *__first;
1737    return __result;
1738}
1739
1740// fill_n
1741
1742template <class _OutputIterator, class _Size, class _Tp>
1743inline _LIBCPP_INLINE_VISIBILITY
1744_OutputIterator
1745__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value, false_type)
1746{
1747    for (; __n > 0; ++__first, --__n)
1748        *__first = __value;
1749    return __first;
1750}
1751
1752template <class _OutputIterator, class _Size, class _Tp>
1753inline _LIBCPP_INLINE_VISIBILITY
1754_OutputIterator
1755__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value, true_type)
1756{
1757    if (__n > 0)
1758        _STD::memset(__first, (unsigned char)__value, (size_t)(__n));
1759    return __first + __n;
1760}
1761
1762template <class _OutputIterator, class _Size, class _Tp>
1763inline _LIBCPP_INLINE_VISIBILITY
1764_OutputIterator
1765fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
1766{
1767   return _STD::__fill_n(__first, __n, __value, integral_constant<bool,
1768                                              is_pointer<_OutputIterator>::value &&
1769                                              has_trivial_copy_assign<_Tp>::value     &&
1770                                              sizeof(_Tp) == 1>());
1771}
1772
1773// fill
1774
1775template <class _ForwardIterator, class _Tp>
1776inline _LIBCPP_INLINE_VISIBILITY
1777void
1778__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, forward_iterator_tag)
1779{
1780    for (; __first != __last; ++__first)
1781        *__first = __value;
1782}
1783
1784template <class _RandomAccessIterator, class _Tp>
1785inline _LIBCPP_INLINE_VISIBILITY
1786void
1787__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value, random_access_iterator_tag)
1788{
1789    _STD::fill_n(__first, __last - __first, __value);
1790}
1791
1792template <class _ForwardIterator, class _Tp>
1793inline _LIBCPP_INLINE_VISIBILITY
1794void
1795fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
1796{
1797    _STD::__fill(__first, __last, __value, typename iterator_traits<_ForwardIterator>::iterator_category());
1798}
1799
1800// generate
1801
1802template <class _ForwardIterator, class _Generator>
1803inline _LIBCPP_INLINE_VISIBILITY
1804void
1805generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
1806{
1807    for (; __first != __last; ++__first)
1808        *__first = __gen();
1809}
1810
1811// generate_n
1812
1813template <class _OutputIterator, class _Size, class _Generator>
1814inline _LIBCPP_INLINE_VISIBILITY
1815_OutputIterator
1816generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
1817{
1818    for (; __n > 0; ++__first, --__n)
1819        *__first = __gen();
1820    return __first;
1821}
1822
1823// remove
1824
1825template <class _ForwardIterator, class _Tp>
1826_ForwardIterator
1827remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
1828{
1829    __first = _STD::find(__first, __last, __value);
1830    if (__first != __last)
1831    {
1832        _ForwardIterator __i = __first;
1833        while (++__i != __last)
1834        {
1835            if (!(*__i == __value))
1836            {
1837                *__first = _STD::move(*__i);
1838                ++__first;
1839            }
1840        }
1841    }
1842    return __first;
1843}
1844
1845// remove_if
1846
1847template <class _ForwardIterator, class _Predicate>
1848_ForwardIterator
1849remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
1850{
1851    __first = _STD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
1852                           (__first, __last, __pred);
1853    if (__first != __last)
1854    {
1855        _ForwardIterator __i = __first;
1856        while (++__i != __last)
1857        {
1858            if (!__pred(*__i))
1859            {
1860                *__first = _STD::move(*__i);
1861                ++__first;
1862            }
1863        }
1864    }
1865    return __first;
1866}
1867
1868// remove_copy
1869
1870template <class _InputIterator, class _OutputIterator, class _Tp>
1871inline _LIBCPP_INLINE_VISIBILITY
1872_OutputIterator
1873remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value)
1874{
1875    for (; __first != __last; ++__first)
1876    {
1877        if (!(*__first == __value))
1878        {
1879            *__result = *__first;
1880            ++__result;
1881        }
1882    }
1883    return __result;
1884}
1885
1886// remove_copy_if
1887
1888template <class _InputIterator, class _OutputIterator, class _Predicate>
1889inline _LIBCPP_INLINE_VISIBILITY
1890_OutputIterator
1891remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
1892{
1893    for (; __first != __last; ++__first)
1894    {
1895        if (!__pred(*__first))
1896        {
1897            *__result = *__first;
1898            ++__result;
1899        }
1900    }
1901    return __result;
1902}
1903
1904// unique
1905
1906template <class _ForwardIterator, class _BinaryPredicate>
1907_ForwardIterator
1908unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
1909{
1910    __first = _STD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type>
1911                                 (__first, __last, __pred);
1912    if (__first != __last)
1913    {
1914        // ...  a  a  ?  ...
1915        //      f     i
1916        _ForwardIterator __i = __first;
1917        for (++__i; ++__i != __last;)
1918            if (!__pred(*__first, *__i))
1919                *++__first = _STD::move(*__i);
1920        ++__first;
1921    }
1922    return __first;
1923}
1924
1925template <class _ForwardIterator>
1926inline _LIBCPP_INLINE_VISIBILITY
1927_ForwardIterator
1928unique(_ForwardIterator __first, _ForwardIterator __last)
1929{
1930    typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1931    return _STD::unique(__first, __last, __equal_to<__v>());
1932}
1933
1934// unique_copy
1935
1936template <class _BinaryPredicate, class _InputIterator, class _OutputIterator>
1937_OutputIterator
1938__unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
1939              input_iterator_tag, output_iterator_tag)
1940{
1941    if (__first != __last)
1942    {
1943        typename iterator_traits<_InputIterator>::value_type __t(*__first);
1944        *__result = __t;
1945        ++__result;
1946        while (++__first != __last)
1947        {
1948            if (!__pred(__t, *__first))
1949            {
1950                __t = *__first;
1951                *__result = __t;
1952                ++__result;
1953            }
1954        }
1955    }
1956    return __result;
1957}
1958
1959template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator>
1960_OutputIterator
1961__unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
1962              forward_iterator_tag, output_iterator_tag)
1963{
1964    if (__first != __last)
1965    {
1966        _ForwardIterator __i = __first;
1967        *__result = *__i;
1968        ++__result;
1969        while (++__first != __last)
1970        {
1971            if (!__pred(*__i, *__first))
1972            {
1973                *__result = *__first;
1974                ++__result;
1975                __i = __first;
1976            }
1977        }
1978    }
1979    return __result;
1980}
1981
1982template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator>
1983_ForwardIterator
1984__unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred,
1985              input_iterator_tag, forward_iterator_tag)
1986{
1987    if (__first != __last)
1988    {
1989        *__result = *__first;
1990        while (++__first != __last)
1991            if (!__pred(*__result, *__first))
1992                *++__result = *__first;
1993        ++__result;
1994    }
1995    return __result;
1996}
1997
1998template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
1999inline _LIBCPP_INLINE_VISIBILITY
2000_OutputIterator
2001unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred)
2002{
2003    return _STD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type>
2004                              (__first, __last, __result, __pred,
2005                               typename iterator_traits<_InputIterator>::iterator_category(),
2006                               typename iterator_traits<_OutputIterator>::iterator_category());
2007}
2008
2009template <class _InputIterator, class _OutputIterator>
2010inline _LIBCPP_INLINE_VISIBILITY
2011_OutputIterator
2012unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
2013{
2014    typedef typename iterator_traits<_InputIterator>::value_type __v;
2015    return _STD::unique_copy(__first, __last, __result, __equal_to<__v>());
2016}
2017
2018// reverse
2019
2020template <class _BidirectionalIterator>
2021inline _LIBCPP_INLINE_VISIBILITY
2022void
2023__reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
2024{
2025    while (__first != __last)
2026    {
2027        if (__first == --__last)
2028            break;
2029        swap(*__first, *__last);
2030        ++__first;
2031    }
2032}
2033
2034template <class _RandomAccessIterator>
2035inline _LIBCPP_INLINE_VISIBILITY
2036void
2037__reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
2038{
2039    if (__first != __last)
2040        for (; __first < --__last; ++__first)
2041            swap(*__first, *__last);
2042}
2043
2044template <class _BidirectionalIterator>
2045inline _LIBCPP_INLINE_VISIBILITY
2046void
2047reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
2048{
2049    _STD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());
2050}
2051
2052// reverse_copy
2053
2054template <class _BidirectionalIterator, class _OutputIterator>
2055inline _LIBCPP_INLINE_VISIBILITY
2056_OutputIterator
2057reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
2058{
2059    for (; __first != __last; ++__result)
2060        *__result = *--__last;
2061    return __result;
2062}
2063
2064// rotate
2065
2066template <class _ForwardIterator>
2067_ForwardIterator
2068__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, false_type)
2069{
2070    if (__first == __middle)
2071        return __last;
2072    if (__middle == __last)
2073        return __first;
2074    _ForwardIterator __i = __middle;
2075    while (true)
2076    {
2077        swap(*__first, *__i);
2078        ++__first;
2079        if (++__i == __last)
2080            break;
2081        if (__first == __middle)
2082            __middle = __i;
2083    }
2084    _ForwardIterator __r = __first;
2085    if (__first != __middle)
2086    {
2087        __i = __middle;
2088        while (true)
2089        {
2090            swap(*__first, *__i);
2091            ++__first;
2092            if (++__i == __last)
2093            {
2094                if (__first == __middle)
2095                    break;
2096                __i = __middle;
2097            }
2098            else if (__first == __middle)
2099                __middle = __i;
2100        }
2101    }
2102    return __r;
2103}
2104
2105template<typename _Integral>
2106inline _LIBCPP_INLINE_VISIBILITY
2107_Integral
2108__gcd(_Integral __x, _Integral __y)
2109{
2110    do
2111    {
2112        _Integral __t = __x % __y;
2113        __x = __y;
2114        __y = __t;
2115    } while (__y);
2116    return __x;
2117}
2118
2119template<typename _RandomAccessIterator>
2120_RandomAccessIterator
2121__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, true_type)
2122{
2123    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2124    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
2125
2126    if (__first == __middle)
2127        return __last;
2128    if (__middle == __last)
2129        return __first;
2130    const difference_type __m1 = __middle - __first;
2131    const difference_type __m2 = __last - __middle;
2132    if (__m1 == __m2)
2133    {
2134        _STD::swap_ranges(__first, __middle, __middle);
2135        return __middle;
2136    }
2137    const difference_type __g = __gcd(__m1, __m2);
2138    for (_RandomAccessIterator __p = __first + __g; __p != __first;)
2139    {
2140        value_type __t(*--__p);
2141        _RandomAccessIterator __p1 = __p;
2142        _RandomAccessIterator __p2 = __p1 + __m1;
2143        do
2144        {
2145            *__p1 = *__p2;
2146            __p1 = __p2;
2147            const difference_type __d = __last - __p2;
2148            if (__m1 < __d)
2149                __p2 += __m1;
2150            else
2151                __p2 = __first + (__m1 - __d);
2152        } while (__p2 != __p);
2153        *__p1 = __t;
2154    }
2155    return __first + __m2;
2156}
2157
2158template <class _ForwardIterator>
2159inline _LIBCPP_INLINE_VISIBILITY
2160_ForwardIterator
2161rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2162{
2163    return _STD::__rotate(__first, __middle, __last,
2164                          integral_constant
2165                          <
2166                               bool,
2167                               is_convertible
2168                               <
2169                                   typename iterator_traits<_ForwardIterator>::iterator_category,
2170                                   random_access_iterator_tag
2171                               >::value &&
2172                               has_trivial_copy_assign
2173                               <
2174                                   typename iterator_traits<_ForwardIterator>::value_type
2175                               >::value
2176                           >());
2177}
2178
2179// rotate_copy
2180
2181template <class _ForwardIterator, class _OutputIterator>
2182inline _LIBCPP_INLINE_VISIBILITY
2183_OutputIterator
2184rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
2185{
2186    return _STD::copy(__first, __middle, _STD::copy(__middle, __last, __result));
2187}
2188
2189// min_element
2190
2191template <class _ForwardIterator, class _Compare>
2192inline _LIBCPP_INLINE_VISIBILITY
2193_ForwardIterator
2194min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2195{
2196    if (__first != __last)
2197    {
2198        _ForwardIterator __i = __first;
2199        while (++__i != __last)
2200            if (__comp(*__i, *__first))
2201                __first = __i;
2202    }
2203    return __first;
2204}
2205
2206template <class _ForwardIterator>
2207inline _LIBCPP_INLINE_VISIBILITY
2208_ForwardIterator
2209min_element(_ForwardIterator __first, _ForwardIterator __last)
2210{
2211    return _STD::min_element(__first, __last,
2212              __less<typename iterator_traits<_ForwardIterator>::value_type>());
2213}
2214
2215// min
2216
2217template <class _Tp, class _Compare>
2218inline _LIBCPP_INLINE_VISIBILITY
2219const _Tp&
2220min(const _Tp& __a, const _Tp& __b, _Compare __comp)
2221{
2222    return __comp(__b, __a) ? __b : __a;
2223}
2224
2225template <class _Tp>
2226inline _LIBCPP_INLINE_VISIBILITY
2227const _Tp&
2228min(const _Tp& __a, const _Tp& __b)
2229{
2230    return _STD::min(__a, __b, __less<_Tp>());
2231}
2232
2233template<class _Tp, class _Compare>
2234inline _LIBCPP_INLINE_VISIBILITY
2235_Tp
2236min(initializer_list<_Tp> __t, _Compare __comp)
2237{
2238    return *_STD::min_element(__t.begin(), __t.end(), __comp);
2239}
2240
2241template<class _Tp>
2242inline _LIBCPP_INLINE_VISIBILITY
2243_Tp
2244min(initializer_list<_Tp> __t)
2245{
2246    return *_STD::min_element(__t.begin(), __t.end());
2247}
2248
2249// max_element
2250
2251template <class _ForwardIterator, class _Compare>
2252inline _LIBCPP_INLINE_VISIBILITY
2253_ForwardIterator
2254max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2255{
2256    if (__first != __last)
2257    {
2258        _ForwardIterator __i = __first;
2259        while (++__i != __last)
2260            if (__comp(*__first, *__i))
2261                __first = __i;
2262    }
2263    return __first;
2264}
2265
2266template <class _ForwardIterator>
2267inline _LIBCPP_INLINE_VISIBILITY
2268_ForwardIterator
2269max_element(_ForwardIterator __first, _ForwardIterator __last)
2270{
2271    return _STD::max_element(__first, __last,
2272              __less<typename iterator_traits<_ForwardIterator>::value_type>());
2273}
2274
2275// max
2276
2277template <class _Tp, class _Compare>
2278inline _LIBCPP_INLINE_VISIBILITY
2279const _Tp&
2280max(const _Tp& __a, const _Tp& __b, _Compare __comp)
2281{
2282    return __comp(__a, __b) ? __b : __a;
2283}
2284
2285template <class _Tp>
2286inline _LIBCPP_INLINE_VISIBILITY
2287const _Tp&
2288max(const _Tp& __a, const _Tp& __b)
2289{
2290    return _STD::max(__a, __b, __less<_Tp>());
2291}
2292
2293template<class _Tp, class _Compare>
2294inline _LIBCPP_INLINE_VISIBILITY
2295_Tp
2296max(initializer_list<_Tp> __t, _Compare __comp)
2297{
2298    return *_STD::max_element(__t.begin(), __t.end(), __comp);
2299}
2300
2301template<class _Tp>
2302inline _LIBCPP_INLINE_VISIBILITY
2303_Tp
2304max(initializer_list<_Tp> __t)
2305{
2306    return *_STD::max_element(__t.begin(), __t.end());
2307}
2308
2309// minmax_element
2310
2311template <class _ForwardIterator, class _Compare>
2312std::pair<_ForwardIterator, _ForwardIterator>
2313minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2314{
2315  std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);
2316  if (__first != __last)
2317  {
2318      if (++__first != __last)
2319      {
2320          if (__comp(*__first, *__result.first))
2321          {
2322              __result.second = __result.first;
2323              __result.first = __first;
2324          }
2325          else
2326              __result.second = __first;
2327          while (++__first != __last)
2328          {
2329              _ForwardIterator __i = __first;
2330              if (++__first == __last)
2331              {
2332                  if (__comp(*__i, *__result.first))
2333                      __result.first = __i;
2334                  else if (!__comp(*__i, *__result.second))
2335                      __result.second = __i;
2336                  break;
2337              }
2338              else
2339              {
2340                  if (__comp(*__first, *__i))
2341                  {
2342                      if (__comp(*__first, *__result.first))
2343                          __result.first = __first;
2344                      if (!__comp(*__i, *__result.second))
2345                          __result.second = __i;
2346                  }
2347                  else
2348                  {
2349                      if (__comp(*__i, *__result.first))
2350                          __result.first = __i;
2351                      if (!__comp(*__first, *__result.second))
2352                          __result.second = __first;
2353                  }
2354              }
2355          }
2356      }
2357  }
2358  return __result;
2359}
2360
2361template <class _ForwardIterator>
2362inline _LIBCPP_INLINE_VISIBILITY
2363std::pair<_ForwardIterator, _ForwardIterator>
2364minmax_element(_ForwardIterator __first, _ForwardIterator __last)
2365{
2366    return _STD::minmax_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
2367}
2368
2369// minmax
2370
2371template<class _Tp, class _Compare>
2372inline _LIBCPP_INLINE_VISIBILITY
2373pair<const _Tp&, const _Tp&>
2374minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
2375{
2376    return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) :
2377                              pair<const _Tp&, const _Tp&>(__a, __b);
2378}
2379
2380template<class _Tp>
2381inline _LIBCPP_INLINE_VISIBILITY
2382pair<const _Tp&, const _Tp&>
2383minmax(const _Tp& __a, const _Tp& __b)
2384{
2385    return _STD::minmax(__a, __b, __less<_Tp>());
2386}
2387
2388template<class _Tp>
2389inline _LIBCPP_INLINE_VISIBILITY
2390pair<_Tp, _Tp>
2391minmax(initializer_list<_Tp> __t)
2392{
2393    pair<const _Tp*, const _Tp*> __p =
2394                                   _STD::minmax_element(__t.begin(), __t.end());
2395    return pair<_Tp, _Tp>(*__p.first, *__p.second);
2396}
2397
2398template<class _Tp, class _Compare>
2399inline _LIBCPP_INLINE_VISIBILITY
2400pair<_Tp, _Tp>
2401minmax(initializer_list<_Tp> __t, _Compare __comp)
2402{
2403    pair<const _Tp*, const _Tp*> __p =
2404                           _STD::minmax_element(__t.begin(), __t.end(), __comp);
2405    return pair<_Tp, _Tp>(*__p.first, *__p.second);
2406}
2407
2408// random_shuffle
2409
2410// __independent_bits_engine
2411
2412template <unsigned long long _X, size_t _R>
2413struct __log2_imp
2414{
2415    static const size_t value = _X & ((unsigned long long)(1) << _R) ? _R
2416                                           : __log2_imp<_X, _R - 1>::value;
2417};
2418
2419template <unsigned long long _X>
2420struct __log2_imp<_X, 0>
2421{
2422    static const size_t value = 0;
2423};
2424
2425template <size_t _R>
2426struct __log2_imp<0, _R>
2427{
2428    static const size_t value = _R + 1;
2429};
2430
2431template <class _UI, _UI _X>
2432struct __log2
2433{
2434    static const size_t value = __log2_imp<_X,
2435                                         sizeof(_UI) * __CHAR_BIT__ - 1>::value;
2436};
2437
2438template<class _Engine, class _UIntType>
2439class __independent_bits_engine
2440{
2441public:
2442    // types
2443    typedef _UIntType result_type;
2444
2445private:
2446    typedef typename _Engine::result_type _Engine_result_type;
2447    typedef typename conditional
2448        <
2449            sizeof(_Engine_result_type) <= sizeof(result_type),
2450                result_type,
2451                _Engine_result_type
2452        >::type _Working_result_type;
2453
2454    _Engine& __e_;
2455    size_t __w_;
2456    size_t __w0_;
2457    size_t __n_;
2458    size_t __n0_;
2459    _Working_result_type __y0_;
2460    _Working_result_type __y1_;
2461    _Engine_result_type __mask0_;
2462    _Engine_result_type __mask1_;
2463
2464    static const _Working_result_type _R = _Engine::_Max - _Engine::_Min
2465                                                         + _Working_result_type(1);
2466    static const size_t __m = __log2<_Working_result_type, _R>::value;
2467    static const size_t _WDt = numeric_limits<_Working_result_type>::digits;
2468    static const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
2469
2470public:
2471    // constructors and seeding functions
2472    __independent_bits_engine(_Engine& __e, size_t __w);
2473
2474    // generating functions
2475    result_type operator()() {return __eval(integral_constant<bool, _R != 0>());}
2476
2477private:
2478    result_type __eval(false_type);
2479    result_type __eval(true_type);
2480};
2481
2482template<class _Engine, class _UIntType>
2483__independent_bits_engine<_Engine, _UIntType>
2484    ::__independent_bits_engine(_Engine& __e, size_t __w)
2485        : __e_(__e),
2486          __w_(__w)
2487{
2488    __n_ = __w_ / __m + (__w_ % __m != 0);
2489    __w0_ = __w_ / __n_;
2490    if (_R == 0)
2491        __y0_ = _R;
2492    else if (__w0_ < _WDt)
2493        __y0_ = (_R >> __w0_) << __w0_;
2494    else
2495        __y0_ = 0;
2496    if (_R - __y0_ > __y0_ / __n_)
2497    {
2498        ++__n_;
2499        __w0_ = __w_ / __n_;
2500        if (__w0_ < _WDt)
2501            __y0_ = (_R >> __w0_) << __w0_;
2502        else
2503            __y0_ = 0;
2504    }
2505    __n0_ = __n_ - __w_ % __n_;
2506    if (__w0_ < _WDt - 1)
2507        __y1_ = (_R >> (__w0_ + 1)) << (__w0_ + 1);
2508    else
2509        __y1_ = 0;
2510    __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :
2511                          _Engine_result_type(0);
2512    __mask1_ = __w0_ < _EDt - 1 ?
2513                               _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :
2514                               _Engine_result_type(~0);
2515}
2516
2517template<class _Engine, class _UIntType>
2518inline
2519_UIntType
2520__independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
2521{
2522    return static_cast<result_type>(__e_() & __mask0_);
2523}
2524
2525template<class _Engine, class _UIntType>
2526_UIntType
2527__independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
2528{
2529    result_type _S = 0;
2530    for (size_t __k = 0; __k < __n0_; ++__k)
2531    {
2532        _Engine_result_type __u;
2533        do
2534        {
2535            __u = __e_() - _Engine::min();
2536        } while (__u >= __y0_);
2537        if (__w0_ < _EDt)
2538            _S <<= __w0_;
2539        else
2540            _S = 0;
2541        _S += __u & __mask0_;
2542    }
2543    for (size_t __k = __n0_; __k < __n_; ++__k)
2544    {
2545        _Engine_result_type __u;
2546        do
2547        {
2548            __u = __e_() - _Engine::min();
2549        } while (__u >= __y1_);
2550        if (__w0_ < _EDt - 1)
2551            _S <<= __w0_ + 1;
2552        else
2553            _S = 0;
2554        _S += __u & __mask1_;
2555    }
2556    return _S;
2557}
2558
2559// uniform_int_distribution
2560
2561template<class _IntType = int>
2562class uniform_int_distribution
2563{
2564public:
2565    // types
2566    typedef _IntType result_type;
2567
2568    class param_type
2569    {
2570        result_type __a_;
2571        result_type __b_;
2572    public:
2573        typedef uniform_int_distribution distribution_type;
2574
2575        explicit param_type(result_type __a = 0,
2576                            result_type __b = numeric_limits<result_type>::max())
2577            : __a_(__a), __b_(__b) {}
2578
2579        result_type a() const {return __a_;}
2580        result_type b() const {return __b_;}
2581
2582        friend bool operator==(const param_type& __x, const param_type& __y)
2583            {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
2584        friend bool operator!=(const param_type& __x, const param_type& __y)
2585            {return !(__x == __y);}
2586    };
2587
2588private:
2589    param_type __p_;
2590
2591public:
2592    // constructors and reset functions
2593    explicit uniform_int_distribution(result_type __a = 0,
2594                                      result_type __b = numeric_limits<result_type>::max())
2595        : __p_(param_type(__a, __b)) {}
2596    explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
2597    void reset() {}
2598
2599    // generating functions
2600    template<class _URNG> result_type operator()(_URNG& __g)
2601        {return (*this)(__g, __p_);}
2602    template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
2603
2604    // property functions
2605    result_type a() const {return __p_.a();}
2606    result_type b() const {return __p_.b();}
2607
2608    param_type param() const {return __p_;}
2609    void param(const param_type& __p) {__p_ = __p;}
2610
2611    result_type min() const {return a();}
2612    result_type max() const {return b();}
2613
2614    friend bool operator==(const uniform_int_distribution& __x,
2615                           const uniform_int_distribution& __y)
2616        {return __x.__p_ == __y.__p_;}
2617    friend bool operator!=(const uniform_int_distribution& __x,
2618                           const uniform_int_distribution& __y)
2619            {return !(__x == __y);}
2620};
2621
2622template<class _IntType>
2623template<class _URNG>
2624typename uniform_int_distribution<_IntType>::result_type
2625uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
2626{
2627    typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
2628                                            uint32_t, uint64_t>::type _UIntType;
2629    const _UIntType _R = __p.b() - __p.a() + _UIntType(1);
2630    if (_R == 1)
2631        return __p.a();
2632    const size_t _Dt = numeric_limits<_UIntType>::digits;
2633    typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
2634    if (_R == 0)
2635        return static_cast<result_type>(_Eng(__g, _Dt)());
2636    size_t __w = _Dt - __clz(_R) - 1;
2637    if ((_R & (_UIntType(~0) >> (_Dt - __w))) != 0)
2638        ++__w;
2639    _Eng __e(__g, __w);
2640    _UIntType __u;
2641    do
2642    {
2643        __u = __e();
2644    } while (__u >= _R);
2645    return static_cast<result_type>(__u + __p.a());
2646}
2647
2648class __rs_default;
2649
2650__rs_default __rs_get();
2651
2652class __rs_default
2653{
2654    static unsigned __c_;
2655
2656    __rs_default();
2657public:
2658    typedef unsigned result_type;
2659
2660    static const result_type _Min = 0;
2661    static const result_type _Max = 0xFFFFFFFF;
2662
2663    __rs_default(const __rs_default&);
2664    ~__rs_default();
2665
2666    result_type operator()();
2667
2668    static const/*expr*/ result_type min() {return _Min;}
2669    static const/*expr*/ result_type max() {return _Max;}
2670
2671    friend __rs_default __rs_get();
2672};
2673
2674__rs_default __rs_get();
2675
2676template <class _RandomAccessIterator>
2677void
2678random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
2679{
2680    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2681    typedef uniform_int_distribution<ptrdiff_t> _D;
2682    typedef typename _D::param_type _P;
2683    difference_type __d = __last - __first;
2684    if (__d > 1)
2685    {
2686        _D __uid;
2687        __rs_default __g = __rs_get();
2688        for (--__last, --__d; __first < __last; ++__first, --__d)
2689            swap(*__first, *(__first + __uid(__g, _P(0, __d))));
2690    }
2691}
2692
2693template <class _RandomAccessIterator, class _RandomNumberGenerator>
2694void
2695random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
2696#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2697               _RandomNumberGenerator&& __rand)
2698#else
2699               _RandomNumberGenerator& __rand)
2700#endif
2701{
2702    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2703    difference_type __d = __last - __first;
2704    if (__d > 1)
2705    {
2706        for (--__last; __first < __last; ++__first, --__d)
2707            swap(*__first, *(__first + __rand(__d)));
2708    }
2709}
2710
2711template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
2712    void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
2713                 _UniformRandomNumberGenerator& __g)
2714{
2715    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2716    typedef uniform_int_distribution<ptrdiff_t> _D;
2717    typedef typename _D::param_type _P;
2718    difference_type __d = __last - __first;
2719    if (__d > 1)
2720    {
2721        _D __uid;
2722        for (--__last, --__d; __first < __last; ++__first, --__d)
2723            swap(*__first, *(__first + __uid(__g, _P(0, __d))));
2724    }
2725}
2726
2727template <class _InputIterator, class _Predicate>
2728bool
2729is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2730{
2731    for (; __first != __last; ++__first)
2732        if (!__pred(*__first))
2733            break;
2734    for (; __first != __last; ++__first)
2735        if (__pred(*__first))
2736            return false;
2737    return true;
2738}
2739
2740// partition
2741
2742template <class _Predicate, class _ForwardIterator>
2743_ForwardIterator
2744__partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
2745{
2746    while (true)
2747    {
2748        if (__first == __last)
2749            return __first;
2750        if (!__pred(*__first))
2751            break;
2752        ++__first;
2753    }
2754    for (_ForwardIterator __p = __first; ++__p != __last;)
2755    {
2756        if (__pred(*__p))
2757        {
2758            swap(*__first, *__p);
2759            ++__first;
2760        }
2761    }
2762    return __first;
2763}
2764
2765template <class _Predicate, class _BidirectionalIterator>
2766_BidirectionalIterator
2767__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
2768            bidirectional_iterator_tag)
2769{
2770    while (true)
2771    {
2772        while (true)
2773        {
2774            if (__first == __last)
2775                return __first;
2776            if (!__pred(*__first))
2777                break;
2778            ++__first;
2779        }
2780        do
2781        {
2782            if (__first == --__last)
2783                return __first;
2784        } while (!__pred(*__last));
2785        swap(*__first, *__last);
2786        ++__first;
2787    }
2788}
2789
2790template <class _ForwardIterator, class _Predicate>
2791inline _LIBCPP_INLINE_VISIBILITY
2792_ForwardIterator
2793partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2794{
2795    return _STD::__partition<typename add_lvalue_reference<_Predicate>::type>
2796                            (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
2797}
2798
2799// partition_copy
2800
2801template <class _InputIterator, class _OutputIterator1,
2802          class _OutputIterator2, class _Predicate>
2803pair<_OutputIterator1, _OutputIterator2>
2804partition_copy(_InputIterator __first, _InputIterator __last,
2805               _OutputIterator1 __out_true, _OutputIterator2 __out_false,
2806               _Predicate __pred)
2807{
2808    for (; __first != __last; ++__first)
2809    {
2810        if (__pred(*__first))
2811        {
2812            *__out_true = *__first;
2813            ++__out_true;
2814        }
2815        else
2816        {
2817            *__out_false = *__first;
2818            ++__out_false;
2819        }
2820    }
2821    return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
2822}
2823
2824// partition_point
2825
2826template<class _ForwardIterator, class _Predicate>
2827_ForwardIterator
2828partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2829{
2830    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
2831    difference_type __len = _STD::distance(__first, __last);
2832    while (__len != 0)
2833    {
2834        difference_type __l2 = __len / 2;
2835        _ForwardIterator __m = __first;
2836        _STD::advance(__m, __l2);
2837        if (__pred(*__m))
2838        {
2839            __first = ++__m;
2840            __len -= __l2 + 1;
2841        }
2842        else
2843            __len = __l2;
2844    }
2845    return __first;
2846}
2847
2848// stable_partition
2849
2850template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
2851_ForwardIterator
2852__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
2853                   _Distance __len, _Pair __p, forward_iterator_tag __fit)
2854{
2855    // *__first is known to be false
2856    // __len >= 1
2857    if (__len == 1)
2858        return __first;
2859    if (__len == 2)
2860    {
2861        _ForwardIterator __m = __first;
2862        if (__pred(*++__m))
2863        {
2864            swap(*__first, *__m);
2865            return __m;
2866        }
2867        return __first;
2868    }
2869    if (__len <= __p.second)
2870    {   // The buffer is big enough to use
2871        typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2872        __destruct_n __d(0);
2873        unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
2874        // Move the falses into the temporary buffer, and the trues to the front of the line
2875        // Update __first to always point to the end of the trues
2876        value_type* __t = __p.first;
2877        ::new(__t) value_type(_STD::move(*__first));
2878        __d.__incr((value_type*)0);
2879        ++__t;
2880        _ForwardIterator __i = __first;
2881        while (++__i != __last)
2882        {
2883            if (__pred(*__i))
2884            {
2885                *__first = _STD::move(*__i);
2886                ++__first;
2887            }
2888            else
2889            {
2890                ::new(__t) value_type(_STD::move(*__i));
2891                __d.__incr((value_type*)0);
2892                ++__t;
2893            }
2894        }
2895        // All trues now at start of range, all falses in buffer
2896        // Move falses back into range, but don't mess up __first which points to first false
2897        __i = __first;
2898        for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
2899            *__i = _STD::move(*__t2);
2900        // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
2901        return __first;
2902    }
2903    // Else not enough buffer, do in place
2904    // __len >= 3
2905    _ForwardIterator __m = __first;
2906    _Distance __len2 = __len / 2;  // __len2 >= 2
2907    _STD::advance(__m, __len2);
2908    // recurse on [__first, __m), *__first know to be false
2909    // F?????????????????
2910    // f       m         l
2911    typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
2912    _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
2913    // TTTFFFFF??????????
2914    // f  ff   m         l
2915    // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
2916    _ForwardIterator __m1 = __m;
2917    _ForwardIterator __second_false = __last;
2918    _Distance __len_half = __len - __len2;
2919    while (__pred(*__m1))
2920    {
2921        if (++__m1 == __last)
2922            goto __second_half_done;
2923        --__len_half;
2924    }
2925    // TTTFFFFFTTTF??????
2926    // f  ff   m  m1     l
2927    __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
2928__second_half_done:
2929    // TTTFFFFFTTTTTFFFFF
2930    // f  ff   m    sf   l
2931    return _STD::rotate(__first_false, __m, __second_false);
2932    // TTTTTTTTFFFFFFFFFF
2933    //         |
2934}
2935
2936struct __return_temporary_buffer
2937{
2938    template <class _Tp>
2939    _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_STD::return_temporary_buffer(__p);}
2940};
2941
2942template <class _Predicate, class _ForwardIterator>
2943_ForwardIterator
2944__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
2945                   forward_iterator_tag)
2946{
2947    const unsigned __alloc_limit = 3;  // might want to make this a function of trivial assignment
2948    // Either prove all true and return __first or point to first false
2949    while (true)
2950    {
2951        if (__first == __last)
2952            return __first;
2953        if (!__pred(*__first))
2954            break;
2955        ++__first;
2956    }
2957    // We now have a reduced range [__first, __last)
2958    // *__first is known to be false
2959    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
2960    typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2961    difference_type __len = _STD::distance(__first, __last);
2962    pair<value_type*, ptrdiff_t> __p(0, 0);
2963    unique_ptr<value_type, __return_temporary_buffer> __h;
2964    if (__len >= __alloc_limit)
2965    {
2966        __p = _STD::get_temporary_buffer<value_type>(__len);
2967        __h.reset(__p.first);
2968    }
2969    return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
2970                             (__first, __last, __pred, __len, __p, forward_iterator_tag());
2971}
2972
2973template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
2974_BidirectionalIterator
2975__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
2976                   _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
2977{
2978    // *__first is known to be false
2979    // *__last is known to be true
2980    // __len >= 2
2981    if (__len == 2)
2982    {
2983        swap(*__first, *__last);
2984        return __last;
2985    }
2986    if (__len == 3)
2987    {
2988        _BidirectionalIterator __m = __first;
2989        if (__pred(*++__m))
2990        {
2991            swap(*__first, *__m);
2992            swap(*__m, *__last);
2993            return __last;
2994        }
2995        swap(*__m, *__last);
2996        swap(*__first, *__m);
2997        return __m;
2998    }
2999    if (__len <= __p.second)
3000    {   // The buffer is big enough to use
3001        typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3002        __destruct_n __d(0);
3003        unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3004        // Move the falses into the temporary buffer, and the trues to the front of the line
3005        // Update __first to always point to the end of the trues
3006        value_type* __t = __p.first;
3007        ::new(__t) value_type(_STD::move(*__first));
3008        __d.__incr((value_type*)0);
3009        ++__t;
3010        _BidirectionalIterator __i = __first;
3011        while (++__i != __last)
3012        {
3013            if (__pred(*__i))
3014            {
3015                *__first = _STD::move(*__i);
3016                ++__first;
3017            }
3018            else
3019            {
3020                ::new(__t) value_type(_STD::move(*__i));
3021                __d.__incr((value_type*)0);
3022                ++__t;
3023            }
3024        }
3025        // move *__last, known to be true
3026        *__first = _STD::move(*__i);
3027        __i = ++__first;
3028        // All trues now at start of range, all falses in buffer
3029        // Move falses back into range, but don't mess up __first which points to first false
3030        for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3031            *__i = _STD::move(*__t2);
3032        // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3033        return __first;
3034    }
3035    // Else not enough buffer, do in place
3036    // __len >= 4
3037    _BidirectionalIterator __m = __first;
3038    _Distance __len2 = __len / 2;  // __len2 >= 2
3039    _STD::advance(__m, __len2);
3040    // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
3041    // F????????????????T
3042    // f       m        l
3043    _BidirectionalIterator __m1 = __m;
3044    _BidirectionalIterator __first_false = __first;
3045    _Distance __len_half = __len2;
3046    while (!__pred(*--__m1))
3047    {
3048        if (__m1 == __first)
3049            goto __first_half_done;
3050        --__len_half;
3051    }
3052    // F???TFFF?????????T
3053    // f   m1  m        l
3054    typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3055    __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3056__first_half_done:
3057    // TTTFFFFF?????????T
3058    // f  ff   m        l
3059    // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3060    __m1 = __m;
3061    _BidirectionalIterator __second_false = __last;
3062    ++__second_false;
3063    __len_half = __len - __len2;
3064    while (__pred(*__m1))
3065    {
3066        if (++__m1 == __last)
3067            goto __second_half_done;
3068        --__len_half;
3069    }
3070    // TTTFFFFFTTTF?????T
3071    // f  ff   m  m1    l
3072    __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
3073__second_half_done:
3074    // TTTFFFFFTTTTTFFFFF
3075    // f  ff   m    sf  l
3076    return _STD::rotate(__first_false, __m, __second_false);
3077    // TTTTTTTTFFFFFFFFFF
3078    //         |
3079}
3080
3081template <class _Predicate, class _BidirectionalIterator>
3082_BidirectionalIterator
3083__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3084                   bidirectional_iterator_tag)
3085{
3086    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3087    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3088    const difference_type __alloc_limit = 4;  // might want to make this a function of trivial assignment
3089    // Either prove all true and return __first or point to first false
3090    while (true)
3091    {
3092        if (__first == __last)
3093            return __first;
3094        if (!__pred(*__first))
3095            break;
3096        ++__first;
3097    }
3098    // __first points to first false, everything prior to __first is already set.
3099    // Either prove [__first, __last) is all false and return __first, or point __last to last true
3100    do
3101    {
3102        if (__first == --__last)
3103            return __first;
3104    } while (!__pred(*__last));
3105    // We now have a reduced range [__first, __last]
3106    // *__first is known to be false
3107    // *__last is known to be true
3108    // __len >= 2
3109    difference_type __len = _STD::distance(__first, __last) + 1;
3110    pair<value_type*, ptrdiff_t> __p(0, 0);
3111    unique_ptr<value_type, __return_temporary_buffer> __h;
3112    if (__len >= __alloc_limit)
3113    {
3114        __p = _STD::get_temporary_buffer<value_type>(__len);
3115        __h.reset(__p.first);
3116    }
3117    return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3118                             (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3119}
3120
3121template <class _ForwardIterator, class _Predicate>
3122inline _LIBCPP_INLINE_VISIBILITY
3123_ForwardIterator
3124stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3125{
3126    return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3127                             (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3128}
3129
3130// is_sorted_until
3131
3132template <class _ForwardIterator, class _Compare>
3133_ForwardIterator
3134is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3135{
3136    if (__first != __last)
3137    {
3138        _ForwardIterator __i = __first;
3139        while (++__i != __last)
3140        {
3141            if (__comp(*__i, *__first))
3142                return __i;
3143            __first = __i;
3144        }
3145    }
3146    return __last;
3147}
3148
3149template<class _ForwardIterator>
3150inline _LIBCPP_INLINE_VISIBILITY
3151_ForwardIterator
3152is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3153{
3154    return _STD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3155}
3156
3157// is_sorted
3158
3159template <class _ForwardIterator, class _Compare>
3160inline _LIBCPP_INLINE_VISIBILITY
3161bool
3162is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3163{
3164    return _STD::is_sorted_until(__first, __last, __comp) == __last;
3165}
3166
3167template<class _ForwardIterator>
3168inline _LIBCPP_INLINE_VISIBILITY
3169bool
3170is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3171{
3172    return _STD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3173}
3174
3175// sort
3176
3177// stable, 2-3 compares, 0-2 swaps
3178
3179template <class _Compare, class _ForwardIterator>
3180unsigned
3181__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
3182{
3183    unsigned __r = 0;
3184    if (!__c(*__y, *__x))          // if x <= y
3185    {
3186        if (!__c(*__z, *__y))      // if y <= z
3187            return __r;            // x <= y && y <= z
3188                                   // x <= y && y > z
3189        swap(*__y, *__z);          // x <= z && y < z
3190        __r = 1;
3191        if (__c(*__y, *__x))       // if x > y
3192        {
3193            swap(*__x, *__y);      // x < y && y <= z
3194            __r = 2;
3195        }
3196        return __r;                // x <= y && y < z
3197    }
3198    if (__c(*__z, *__y))           // x > y, if y > z
3199    {
3200        swap(*__x, *__z);          // x < y && y < z
3201        __r = 1;
3202        return __r;
3203    }
3204    swap(*__x, *__y);              // x > y && y <= z
3205    __r = 1;                       // x < y && x <= z
3206    if (__c(*__z, *__y))           // if y > z
3207    {
3208        swap(*__y, *__z);          // x <= y && y < z
3209        __r = 2;
3210    }
3211    return __r;
3212}                                  // x <= y && y <= z
3213
3214// stable, 3-6 compares, 0-5 swaps
3215
3216template <class _Compare, class _ForwardIterator>
3217unsigned
3218__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3219            _ForwardIterator __x4, _Compare __c)
3220{
3221    unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
3222    if (__c(*__x4, *__x3))
3223    {
3224        swap(*__x3, *__x4);
3225        ++__r;
3226        if (__c(*__x3, *__x2))
3227        {
3228            swap(*__x2, *__x3);
3229            ++__r;
3230            if (__c(*__x2, *__x1))
3231            {
3232                swap(*__x1, *__x2);
3233                ++__r;
3234            }
3235        }
3236    }
3237    return __r;
3238}
3239
3240// stable, 4-10 compares, 0-9 swaps
3241
3242template <class _Compare, class _ForwardIterator>
3243unsigned
3244__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3245            _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
3246{
3247    unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
3248    if (__c(*__x5, *__x4))
3249    {
3250        swap(*__x4, *__x5);
3251        ++__r;
3252        if (__c(*__x4, *__x3))
3253        {
3254            swap(*__x3, *__x4);
3255            ++__r;
3256            if (__c(*__x3, *__x2))
3257            {
3258                swap(*__x2, *__x3);
3259                ++__r;
3260                if (__c(*__x2, *__x1))
3261                {
3262                    swap(*__x1, *__x2);
3263                    ++__r;
3264                }
3265            }
3266        }
3267    }
3268    return __r;
3269}
3270
3271// Assumes size > 0
3272template <class _Compare, class _BirdirectionalIterator>
3273void
3274__selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3275{
3276    _BirdirectionalIterator __lm1 = __last;
3277    for (--__lm1; __first != __lm1; ++__first)
3278    {
3279        _BirdirectionalIterator __i = _STD::min_element<_BirdirectionalIterator,
3280                                                        typename add_lvalue_reference<_Compare>::type>
3281                                                       (__first, __last, __comp);
3282        if (__i != __first)
3283            swap(*__first, *__i);
3284    }
3285}
3286
3287template <class _Compare, class _BirdirectionalIterator>
3288void
3289__insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3290{
3291    typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3292    if (__first != __last)
3293    {
3294        _BirdirectionalIterator __i = __first;
3295        for (++__i; __i != __last; ++__i)
3296        {
3297            _BirdirectionalIterator __j = __i;
3298            value_type __t(_STD::move(*__j));
3299            for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t,  *--__k); --__j)
3300                *__j = _STD::move(*__k);
3301            *__j = _STD::move(__t);
3302        }
3303    }
3304}
3305
3306template <class _Compare, class _RandomAccessIterator>
3307void
3308__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3309{
3310    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3311    _RandomAccessIterator __j = __first+2;
3312    __sort3<_Compare>(__first, __first+1, __j, __comp);
3313    for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3314    {
3315        if (__comp(*__i, *__j))
3316        {
3317            value_type __t(_STD::move(*__i));
3318            _RandomAccessIterator __k = __j;
3319            __j = __i;
3320            do
3321            {
3322                *__j = _STD::move(*__k);
3323                __j = __k;
3324            } while (__j != __first && __comp(__t, *--__k));
3325            *__j = _STD::move(__t);
3326        }
3327        __j = __i;
3328    }
3329}
3330
3331template <class _Compare, class _RandomAccessIterator>
3332bool
3333__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3334{
3335    switch (__last - __first)
3336    {
3337    case 0:
3338    case 1:
3339        return true;
3340    case 2:
3341        if (__comp(*--__last, *__first))
3342            swap(*__first, *__last);
3343        return true;
3344    case 3:
3345        _STD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3346        return true;
3347    case 4:
3348        _STD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3349        return true;
3350    case 5:
3351        _STD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3352        return true;
3353    }
3354    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3355    _RandomAccessIterator __j = __first+2;
3356    __sort3<_Compare>(__first, __first+1, __j, __comp);
3357    const unsigned __limit = 8;
3358    unsigned __count = 0;
3359    for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3360    {
3361        if (__comp(*__i, *__j))
3362        {
3363            value_type __t(_STD::move(*__i));
3364            _RandomAccessIterator __k = __j;
3365            __j = __i;
3366            do
3367            {
3368                *__j = _STD::move(*__k);
3369                __j = __k;
3370            } while (__j != __first && __comp(__t, *--__k));
3371            *__j = _STD::move(__t);
3372            if (++__count == __limit)
3373                return ++__i == __last;
3374        }
3375        __j = __i;
3376    }
3377    return true;
3378}
3379
3380template <class _Compare, class _BirdirectionalIterator>
3381void
3382__insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
3383                      typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
3384{
3385    typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3386    if (__first1 != __last1)
3387    {
3388        __destruct_n __d(0);
3389        unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
3390        value_type* __last2 = __first2;
3391        ::new(__last2) value_type(_STD::move(*__first1));
3392        __d.__incr((value_type*)0);
3393        for (++__last2; ++__first1 != __last1; ++__last2)
3394        {
3395            value_type* __j2 = __last2;
3396            value_type* __i2 = __j2;
3397            if (__comp(*__first1, *--__i2))
3398            {
3399                ::new(__j2) value_type(_STD::move(*__i2));
3400                __d.__incr((value_type*)0);
3401                for (--__j2; __i2 != __first2 && __comp(*__first1,  *--__i2); --__j2)
3402                    *__j2 = _STD::move(*__i2);
3403                *__j2 = _STD::move(*__first1);
3404            }
3405            else
3406            {
3407                ::new(__j2) value_type(_STD::move(*__first1));
3408                __d.__incr((value_type*)0);
3409            }
3410        }
3411        __h.release();
3412    }
3413}
3414
3415template <class _Compare, class _RandomAccessIterator>
3416void
3417__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3418{
3419    // _Compare is known to be a reference type
3420    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3421    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3422    const difference_type __limit = has_trivial_copy_constructor<value_type>::value &&
3423                                    has_trivial_copy_assign<value_type>::value ? 30 : 6;
3424    while (true)
3425    {
3426    __restart:
3427        difference_type __len = __last - __first;
3428        switch (__len)
3429        {
3430        case 0:
3431        case 1:
3432            return;
3433        case 2:
3434            if (__comp(*--__last, *__first))
3435                swap(*__first, *__last);
3436            return;
3437        case 3:
3438            _STD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3439            return;
3440        case 4:
3441            _STD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3442            return;
3443        case 5:
3444            _STD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3445            return;
3446        }
3447        if (__len <= __limit)
3448        {
3449            _STD::__insertion_sort_3<_Compare>(__first, __last, __comp);
3450            return;
3451        }
3452        // __len > 5
3453        _RandomAccessIterator __m = __first;
3454        _RandomAccessIterator __lm1 = __last;
3455        --__lm1;
3456        unsigned __n_swaps;
3457        {
3458        difference_type __delta;
3459        if (__len >= 1000)
3460        {
3461            __delta = __len/2;
3462            __m += __delta;
3463            __delta /= 2;
3464            __n_swaps = _STD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
3465        }
3466        else
3467        {
3468            __delta = __len/2;
3469            __m += __delta;
3470            __n_swaps = _STD::__sort3<_Compare>(__first, __m, __lm1, __comp);
3471        }
3472        }
3473        // *__m is median
3474        // partition [__first, __m) < *__m and *__m <= [__m, __last)
3475        // (this inhibits tossing elements equivalent to __m around unnecessarily)
3476        _RandomAccessIterator __i = __first;
3477        _RandomAccessIterator __j = __lm1;
3478        // j points beyond range to be tested, *__m is known to be <= *__lm1
3479        // The search going up is known to be guarded but the search coming down isn't.
3480        // Prime the downward search with a guard.
3481        if (!__comp(*__i, *__m))  // if *__first == *__m
3482        {
3483            // *__first == *__m, *__first doesn't go in first part
3484            // manually guard downward moving __j against __i
3485            while (true)
3486            {
3487                if (__i == --__j)
3488                {
3489                    // *__first == *__m, *__m <= all other elements
3490                    // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
3491                    ++__i;  // __first + 1
3492                    __j = __last;
3493                    if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
3494                    {
3495                        while (true)
3496                        {
3497                            if (__i == __j)
3498                                return;  // [__first, __last) all equivalent elements
3499                            if (__comp(*__first, *__i))
3500                            {
3501                                swap(*__i, *__j);
3502                                ++__n_swaps;
3503                                ++__i;
3504                                break;
3505                            }
3506                            ++__i;
3507                        }
3508                    }
3509                    // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
3510                    if (__i == __j)
3511                        return;
3512                    while (true)
3513                    {
3514                        while (!__comp(*__first, *__i))
3515                            ++__i;
3516                        while (__comp(*__first, *--__j))
3517                            ;
3518                        if (__i >= __j)
3519                            break;
3520                        swap(*__i, *__j);
3521                        ++__n_swaps;
3522                        ++__i;
3523                    }
3524                    // [__first, __i) == *__first and *__first < [__i, __last)
3525                    // The first part is sorted, sort the secod part
3526                    // _STD::__sort<_Compare>(__i, __last, __comp);
3527                    __first = __i;
3528                    goto __restart;
3529                }
3530                if (__comp(*__j, *__m))
3531                {
3532                    swap(*__i, *__j);
3533                    ++__n_swaps;
3534                    break;  // found guard for downward moving __j, now use unguarded partition
3535                }
3536            }
3537        }
3538        // It is known that *__i < *__m
3539        ++__i;
3540        // j points beyond range to be tested, *__m is known to be <= *__lm1
3541        // if not yet partitioned...
3542        if (__i < __j)
3543        {
3544            // known that *(__i - 1) < *__m
3545            // known that __i <= __m
3546            while (true)
3547            {
3548                // __m still guards upward moving __i
3549                while (__comp(*__i, *__m))
3550                    ++__i;
3551                // It is now known that a guard exists for downward moving __j
3552                while (!__comp(*--__j, *__m))
3553                    ;
3554                if (__i > __j)
3555                    break;
3556                swap(*__i, *__j);
3557                ++__n_swaps;
3558                // It is known that __m != __j
3559                // If __m just moved, follow it
3560                if (__m == __i)
3561                    __m = __j;
3562                ++__i;
3563            }
3564        }
3565        // [__first, __i) < *__m and *__m <= [__i, __last)
3566        if (__i != __m && __comp(*__m, *__i))
3567        {
3568            swap(*__i, *__m);
3569            ++__n_swaps;
3570        }
3571        // [__first, __i) < *__i and *__i <= [__i+1, __last)
3572        // If we were given a perfect partition, see if insertion sort is quick...
3573        if (__n_swaps == 0)
3574        {
3575            bool __fs = _STD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
3576            if (_STD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
3577            {
3578                if (__fs)
3579                    return;
3580                __last = __i;
3581                continue;
3582            }
3583            else
3584            {
3585                if (__fs)
3586                {
3587                    __first = ++__i;
3588                    continue;
3589                }
3590            }
3591        }
3592        // sort smaller range with recursive call and larger with tail recursion elimination
3593        if (__i - __first < __last - __i)
3594        {
3595            _STD::__sort<_Compare>(__first, __i, __comp);
3596            // _STD::__sort<_Compare>(__i+1, __last, __comp);
3597            __first = ++__i;
3598        }
3599        else
3600        {
3601            _STD::__sort<_Compare>(__i+1, __last, __comp);
3602            // _STD::__sort<_Compare>(__first, __i, __comp);
3603            __last = __i;
3604        }
3605    }
3606}
3607
3608// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
3609template <class _RandomAccessIterator, class _Compare>
3610inline _LIBCPP_INLINE_VISIBILITY
3611void
3612sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3613{
3614#ifdef _LIBCPP_DEBUG
3615    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3616    __debug_less<_Compare> __c(__comp);
3617    __sort<_Comp_ref>(__first, __last, __c);
3618#else  // _LIBCPP_DEBUG
3619    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3620    __sort<_Comp_ref>(__first, __last, __comp);
3621#endif  // _LIBCPP_DEBUG
3622}
3623
3624template <class _RandomAccessIterator>
3625inline _LIBCPP_INLINE_VISIBILITY
3626void
3627sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
3628{
3629    _STD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
3630}
3631
3632template <class _Tp>
3633inline _LIBCPP_INLINE_VISIBILITY
3634void
3635sort(_Tp** __first, _Tp** __last)
3636{
3637    _STD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
3638}
3639
3640template <class _Tp>
3641inline _LIBCPP_INLINE_VISIBILITY
3642void
3643sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
3644{
3645    _STD::sort(__first.base(), __last.base());
3646}
3647
3648extern template void __sort<__less<char>&, char*>(char*, char*, __less<char>&);
3649extern template void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
3650extern template void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
3651extern template void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
3652extern template void __sort<__less<short>&, short*>(short*, short*, __less<short>&);
3653extern template void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
3654extern template void __sort<__less<int>&, int*>(int*, int*, __less<int>&);
3655extern template void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
3656extern template void __sort<__less<long>&, long*>(long*, long*, __less<long>&);
3657extern template void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
3658extern template void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
3659extern template void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
3660extern template void __sort<__less<float>&, float*>(float*, float*, __less<float>&);
3661extern template void __sort<__less<double>&, double*>(double*, double*, __less<double>&);
3662extern template void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
3663
3664extern template bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&);
3665extern template bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
3666extern template bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
3667extern template bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
3668extern template bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&);
3669extern template bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
3670extern template bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&);
3671extern template bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
3672extern template bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&);
3673extern template bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
3674extern template bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
3675extern template bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
3676extern template bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&);
3677extern template bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&);
3678extern template bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
3679
3680extern template unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&);
3681
3682// lower_bound
3683
3684template <class _Compare, class _ForwardIterator, class _Tp>
3685_ForwardIterator
3686__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3687{
3688    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3689    difference_type __len = _STD::distance(__first, __last);
3690    while (__len != 0)
3691    {
3692        difference_type __l2 = __len / 2;
3693        _ForwardIterator __m = __first;
3694        _STD::advance(__m, __l2);
3695        if (__comp(*__m, __value))
3696        {
3697            __first = ++__m;
3698            __len -= __l2 + 1;
3699        }
3700        else
3701            __len = __l2;
3702    }
3703    return __first;
3704}
3705
3706template <class _ForwardIterator, class _Tp, class _Compare>
3707inline _LIBCPP_INLINE_VISIBILITY
3708_ForwardIterator
3709lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3710{
3711#ifdef _LIBCPP_DEBUG
3712    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3713    __debug_less<_Compare> __c(__comp);
3714    return __lower_bound<_Comp_ref>(__first, __last, __value, __c);
3715#else  // _LIBCPP_DEBUG
3716    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3717    return __lower_bound<_Comp_ref>(__first, __last, __value, __comp);
3718#endif  // _LIBCPP_DEBUG
3719}
3720
3721template <class _ForwardIterator, class _Tp>
3722inline _LIBCPP_INLINE_VISIBILITY
3723_ForwardIterator
3724lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
3725{
3726    return _STD::lower_bound(__first, __last, __value,
3727                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
3728}
3729
3730// upper_bound
3731
3732template <class _Compare, class _ForwardIterator, class _Tp>
3733_ForwardIterator
3734__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3735{
3736    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3737    difference_type __len = _STD::distance(__first, __last);
3738    while (__len != 0)
3739    {
3740        difference_type __l2 = __len / 2;
3741        _ForwardIterator __m = __first;
3742        _STD::advance(__m, __l2);
3743        if (__comp(__value, *__m))
3744            __len = __l2;
3745        else
3746        {
3747            __first = ++__m;
3748            __len -= __l2 + 1;
3749        }
3750    }
3751    return __first;
3752}
3753
3754template <class _ForwardIterator, class _Tp, class _Compare>
3755inline _LIBCPP_INLINE_VISIBILITY
3756_ForwardIterator
3757upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3758{
3759#ifdef _LIBCPP_DEBUG
3760    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3761    __debug_less<_Compare> __c(__comp);
3762    return __upper_bound<_Comp_ref>(__first, __last, __value, __c);
3763#else  // _LIBCPP_DEBUG
3764    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3765    return __upper_bound<_Comp_ref>(__first, __last, __value, __comp);
3766#endif  // _LIBCPP_DEBUG
3767}
3768
3769template <class _ForwardIterator, class _Tp>
3770inline _LIBCPP_INLINE_VISIBILITY
3771_ForwardIterator
3772upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
3773{
3774    return _STD::upper_bound(__first, __last, __value,
3775                             __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
3776}
3777
3778// equal_range
3779
3780template <class _Compare, class _ForwardIterator, class _Tp>
3781pair<_ForwardIterator, _ForwardIterator>
3782__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3783{
3784    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3785    difference_type __len = _STD::distance(__first, __last);
3786    while (__len != 0)
3787    {
3788        difference_type __l2 = __len / 2;
3789        _ForwardIterator __m = __first;
3790        _STD::advance(__m, __l2);
3791        if (__comp(*__m, __value))
3792        {
3793            __first = ++__m;
3794            __len -= __l2 + 1;
3795        }
3796        else if (__comp(__value, *__m))
3797        {
3798            __last = __m;
3799            __len = __l2;
3800        }
3801        else
3802        {
3803            _ForwardIterator __mp1 = __m;
3804            return pair<_ForwardIterator, _ForwardIterator>
3805                   (
3806                      __lower_bound<_Compare>(__first, __m, __value, __comp),
3807                      __upper_bound<_Compare>(++__mp1, __last, __value, __comp)
3808                   );
3809        }
3810    }
3811    return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
3812}
3813
3814template <class _ForwardIterator, class _Tp, class _Compare>
3815inline _LIBCPP_INLINE_VISIBILITY
3816pair<_ForwardIterator, _ForwardIterator>
3817equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3818{
3819#ifdef _LIBCPP_DEBUG
3820    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3821    __debug_less<_Compare> __c(__comp);
3822    return __equal_range<_Comp_ref>(__first, __last, __value, __c);
3823#else  // _LIBCPP_DEBUG
3824    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3825    return __equal_range<_Comp_ref>(__first, __last, __value, __comp);
3826#endif  // _LIBCPP_DEBUG
3827}
3828
3829template <class _ForwardIterator, class _Tp>
3830inline _LIBCPP_INLINE_VISIBILITY
3831pair<_ForwardIterator, _ForwardIterator>
3832equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
3833{
3834    return _STD::equal_range(__first, __last, __value,
3835                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
3836}
3837
3838// binary_search
3839
3840template <class _Compare, class _ForwardIterator, class _Tp>
3841inline _LIBCPP_INLINE_VISIBILITY
3842bool
3843__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3844{
3845    __first = __lower_bound<_Compare>(__first, __last, __value, __comp);
3846    return __first != __last && !__comp(__value, *__first);
3847}
3848
3849template <class _ForwardIterator, class _Tp, class _Compare>
3850inline _LIBCPP_INLINE_VISIBILITY
3851bool
3852binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3853{
3854#ifdef _LIBCPP_DEBUG
3855    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3856    __debug_less<_Compare> __c(__comp);
3857    return __binary_search<_Comp_ref>(__first, __last, __value, __c);
3858#else  // _LIBCPP_DEBUG
3859    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3860    return __binary_search<_Comp_ref>(__first, __last, __value, __comp);
3861#endif  // _LIBCPP_DEBUG
3862}
3863
3864template <class _ForwardIterator, class _Tp>
3865inline _LIBCPP_INLINE_VISIBILITY
3866bool
3867binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
3868{
3869    return _STD::binary_search(__first, __last, __value,
3870                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
3871}
3872
3873// merge
3874
3875template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
3876_OutputIterator
3877__merge(_InputIterator1 __first1, _InputIterator1 __last1,
3878        _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
3879{
3880    for (; __first1 != __last1; ++__result)
3881    {
3882        if (__first2 == __last2)
3883            return _STD::copy(__first1, __last1, __result);
3884        if (__comp(*__first2, *__first1))
3885        {
3886            *__result = *__first2;
3887            ++__first2;
3888        }
3889        else
3890        {
3891            *__result = *__first1;
3892            ++__first1;
3893        }
3894    }
3895    return _STD::copy(__first2, __last2, __result);
3896}
3897
3898template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
3899inline _LIBCPP_INLINE_VISIBILITY
3900_OutputIterator
3901merge(_InputIterator1 __first1, _InputIterator1 __last1,
3902      _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
3903{
3904#ifdef _LIBCPP_DEBUG
3905    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3906    __debug_less<_Compare> __c(__comp);
3907    return _STD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
3908#else  // _LIBCPP_DEBUG
3909    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3910    return _STD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
3911#endif  // _LIBCPP_DEBUG
3912}
3913
3914template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
3915inline _LIBCPP_INLINE_VISIBILITY
3916_OutputIterator
3917merge(_InputIterator1 __first1, _InputIterator1 __last1,
3918      _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
3919{
3920    typedef typename iterator_traits<_InputIterator1>::value_type __v1;
3921    typedef typename iterator_traits<_InputIterator2>::value_type __v2;
3922    return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
3923}
3924
3925// inplace_merge
3926
3927template <class _Compare, class _BidirectionalIterator>
3928void
3929__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
3930                _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
3931                                 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
3932                typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
3933{
3934    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3935    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3936    typedef typename iterator_traits<_BidirectionalIterator>::pointer pointer;
3937    __destruct_n __d(0);
3938    unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
3939    if (__len1 <= __len2)
3940    {
3941        value_type* __p = __buff;
3942        for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), ++__i, ++__p)
3943            ::new(__p) value_type(_STD::move(*__i));
3944        __merge<_Compare>(move_iterator<value_type*>(__buff),
3945                          move_iterator<value_type*>(__p),
3946                          move_iterator<_BidirectionalIterator>(__middle),
3947                          move_iterator<_BidirectionalIterator>(__last),
3948                          __first, __comp);
3949    }
3950    else
3951    {
3952        value_type* __p = __buff;
3953        for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), ++__i, ++__p)
3954            ::new(__p) value_type(_STD::move(*__i));
3955        typedef reverse_iterator<_BidirectionalIterator> _RBi;
3956        typedef reverse_iterator<value_type*> _Rv;
3957        __merge(move_iterator<_RBi>(_RBi(__middle)), move_iterator<_RBi>(_RBi(__first)),
3958                move_iterator<_Rv>(_Rv(__p)), move_iterator<_Rv>(_Rv(__buff)),
3959                _RBi(__last), __negate<_Compare>(__comp));
3960    }
3961}
3962
3963template <class _Compare, class _BidirectionalIterator>
3964void
3965__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
3966                _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
3967                                 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
3968                typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
3969{
3970    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3971    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3972    while (true)
3973    {
3974        // if __middle == __last, we're done
3975        if (__len2 == 0)
3976            return;
3977        // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
3978        for (; true; ++__first, --__len1)
3979        {
3980            if (__len1 == 0)
3981                return;
3982            if (__comp(*__middle, *__first))
3983                break;
3984        }
3985        if (__len1 <= __buff_size || __len2 <= __buff_size)
3986        {
3987            __buffered_inplace_merge<_Compare>(__first, __middle, __last, __comp, __len1, __len2, __buff);
3988            return;
3989        }
3990        // __first < __middle < __last
3991        // *__first > *__middle
3992        // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
3993        //     all elements in:
3994        //         [__first, __m1)  <= [__middle, __m2)
3995        //         [__middle, __m2) <  [__m1, __middle)
3996        //         [__m1, __middle) <= [__m2, __last)
3997        //     and __m1 or __m2 is in the middle of its range
3998        _BidirectionalIterator __m1;  // "median" of [__first, __middle)
3999        _BidirectionalIterator __m2;  // "median" of [__middle, __last)
4000        difference_type __len11;      // distance(__first, __m1)
4001        difference_type __len21;      // distance(__middle, __m2)
4002        // binary search smaller range
4003        if (__len1 < __len2)
4004        {   // __len >= 1, __len2 >= 2
4005            __len21 = __len2 / 2;
4006            __m2 = __middle;
4007            _STD::advance(__m2, __len21);
4008            __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4009            __len11 = _STD::distance(__first, __m1);
4010        }
4011        else
4012        {
4013            if (__len1 == 1)
4014            {   // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
4015                // It is known *__first > *__middle
4016                swap(*__first, *__middle);
4017                return;
4018            }
4019            // __len1 >= 2, __len2 >= 1
4020            __len11 = __len1 / 2;
4021            __m1 = __first;
4022            _STD::advance(__m1, __len11);
4023            __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp);
4024            __len21 = _STD::distance(__middle, __m2);
4025        }
4026        difference_type __len12 = __len1 - __len11;  // distance(__m1, __middle)
4027        difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)
4028        // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4029        // swap middle two partitions
4030        __middle = _STD::rotate(__m1, __middle, __m2);
4031        // __len12 and __len21 now have swapped meanings
4032        // merge smaller range with recurisve call and larger with tail recursion elimination
4033        if (__len11 + __len21 < __len12 + __len22)
4034        {
4035            __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4036//          __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4037            __first = __middle;
4038            __middle = __m2;
4039            __len1 = __len12;
4040            __len2 = __len22;
4041        }
4042        else
4043        {
4044            __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4045//          __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4046            __last = __middle;
4047            __middle = __m1;
4048            __len1 = __len11;
4049            __len2 = __len21;
4050        }
4051    }
4052}
4053
4054template <class _Tp>
4055struct __inplace_merge_switch
4056{
4057    static const unsigned value = has_trivial_copy_assign<_Tp>::value;
4058};
4059
4060template <class _BidirectionalIterator, class _Compare>
4061inline _LIBCPP_INLINE_VISIBILITY
4062void
4063inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4064              _Compare __comp)
4065{
4066    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4067    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4068    difference_type __len1 = _STD::distance(__first, __middle);
4069    difference_type __len2 = _STD::distance(__middle, __last);
4070    difference_type __buf_size = _STD::min(__len1, __len2);
4071    pair<value_type*, ptrdiff_t> __buf(0, 0);
4072    unique_ptr<value_type, __return_temporary_buffer> __h;
4073    if (__inplace_merge_switch<value_type>::value && __buf_size > 8)
4074    {
4075        __buf = _STD::get_temporary_buffer<value_type>(__buf_size);
4076        __h.reset(__buf.first);
4077    }
4078#ifdef _LIBCPP_DEBUG
4079    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4080    __debug_less<_Compare> __c(__comp);
4081    return _STD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2,
4082                                            __buf.first, __buf.second);
4083#else  // _LIBCPP_DEBUG
4084    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4085    return _STD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4086                                            __buf.first, __buf.second);
4087#endif  // _LIBCPP_DEBUG
4088}
4089
4090template <class _BidirectionalIterator>
4091inline _LIBCPP_INLINE_VISIBILITY
4092void
4093inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
4094{
4095    _STD::inplace_merge(__first, __middle, __last,
4096                        __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4097}
4098
4099// stable_sort
4100
4101template <class _Compare, class _InputIterator1, class _InputIterator2>
4102void
4103__merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
4104        _InputIterator2 __first2, _InputIterator2 __last2,
4105        typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
4106{
4107    typedef typename iterator_traits<_InputIterator1>::value_type value_type;
4108    __destruct_n __d(0);
4109    unique_ptr<value_type, __destruct_n&> __h(__result, __d);
4110    for (; true; ++__result)
4111    {
4112        if (__first1 == __last1)
4113        {
4114            for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0))
4115                ::new (__result) value_type(_STD::move(*__first2));
4116            __h.release();
4117            return;
4118        }
4119        if (__first2 == __last2)
4120        {
4121            for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0))
4122                ::new (__result) value_type(_STD::move(*__first1));
4123            __h.release();
4124            return;
4125        }
4126        if (__comp(*__first2, *__first1))
4127        {
4128            ::new (__result) value_type(_STD::move(*__first2));
4129            __d.__incr((value_type*)0);
4130            ++__first2;
4131        }
4132        else
4133        {
4134            ::new (__result) value_type(_STD::move(*__first1));
4135            __d.__incr((value_type*)0);
4136            ++__first1;
4137        }
4138    }
4139}
4140
4141template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4142void
4143__merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
4144        _InputIterator2 __first2, _InputIterator2 __last2,
4145        _OutputIterator __result, _Compare __comp)
4146{
4147    for (; __first1 != __last1; ++__result)
4148    {
4149        if (__first2 == __last2)
4150        {
4151            for (; __first1 != __last1; ++__first1, ++__result)
4152                *__result = _STD::move(*__first1);
4153            return;
4154        }
4155        if (__comp(*__first2, *__first1))
4156        {
4157            *__result = _STD::move(*__first2);
4158            ++__first2;
4159        }
4160        else
4161        {
4162            *__result = _STD::move(*__first1);
4163            ++__first1;
4164        }
4165    }
4166    for (; __first2 != __last2; ++__first2, ++__result)
4167        *__result = _STD::move(*__first2);
4168}
4169
4170template <class _Compare, class _RandomAccessIterator>
4171void
4172__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4173              typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4174              typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
4175
4176template <class _Compare, class _RandomAccessIterator>
4177void
4178__stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
4179                   typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4180                   typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
4181{
4182    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4183    switch (__len)
4184    {
4185    case 0:
4186        return;
4187    case 1:
4188        ::new(__first2) value_type(_STD::move(*__first1));
4189        return;
4190    case 2:
4191       __destruct_n __d(0);
4192        unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
4193         if (__comp(*--__last1, *__first1))
4194        {
4195            ::new(__first2) value_type(_STD::move(*__last1));
4196            __d.__incr((value_type*)0);
4197            ++__first2;
4198            ::new(__first2) value_type(_STD::move(*__first1));
4199        }
4200        else
4201        {
4202            ::new(__first2) value_type(_STD::move(*__first1));
4203            __d.__incr((value_type*)0);
4204            ++__first2;
4205            ::new(__first2) value_type(_STD::move(*__last1));
4206        }
4207        __h2.release();
4208        return;
4209    }
4210    if (__len <= 8)
4211    {
4212        __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
4213        return;
4214    }
4215    typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4216    _RandomAccessIterator __m = __first1 + __l2;
4217    __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
4218    __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
4219    __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
4220}
4221
4222template <class _Tp>
4223struct __stable_sort_switch
4224{
4225    static const unsigned value = 128*has_trivial_copy_assign<_Tp>::value;
4226};
4227
4228template <class _Compare, class _RandomAccessIterator>
4229void
4230__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4231              typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4232              typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
4233{
4234    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4235    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4236    switch (__len)
4237    {
4238    case 0:
4239    case 1:
4240        return;
4241    case 2:
4242        if (__comp(*--__last, *__first))
4243            swap(*__first, *__last);
4244        return;
4245    }
4246    if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4247    {
4248        __insertion_sort<_Compare>(__first, __last, __comp);
4249        return;
4250    }
4251    typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4252    _RandomAccessIterator __m = __first + __l2;
4253    if (__len <= __buff_size)
4254    {
4255        __destruct_n __d(0);
4256        unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4257        __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4258        __d.__set(__l2, (value_type*)0);
4259        __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
4260        __d.__set(__len, (value_type*)0);
4261        __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4262//         __merge<_Compare>(move_iterator<value_type*>(__buff),
4263//                           move_iterator<value_type*>(__buff + __l2),
4264//                           move_iterator<_RandomAccessIterator>(__buff + __l2),
4265//                           move_iterator<_RandomAccessIterator>(__buff + __len),
4266//                           __first, __comp);
4267        return;
4268    }
4269    __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4270    __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
4271    __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4272}
4273
4274template <class _RandomAccessIterator, class _Compare>
4275inline _LIBCPP_INLINE_VISIBILITY
4276void
4277stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4278{
4279    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4280    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4281    difference_type __len = __last - __first;
4282    pair<value_type*, ptrdiff_t> __buf(0, 0);
4283    unique_ptr<value_type, __return_temporary_buffer> __h;
4284    if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4285    {
4286        __buf = _STD::get_temporary_buffer<value_type>(__len);
4287        __h.reset(__buf.first);
4288    }
4289#ifdef _LIBCPP_DEBUG
4290    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4291    __debug_less<_Compare> __c(__comp);
4292    __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);
4293#else  // _LIBCPP_DEBUG
4294    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4295    __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4296#endif  // _LIBCPP_DEBUG
4297}
4298
4299template <class _RandomAccessIterator>
4300inline _LIBCPP_INLINE_VISIBILITY
4301void
4302stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4303{
4304    _STD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4305}
4306
4307// is_heap_until
4308
4309template <class _RandomAccessIterator, class _Compare>
4310_RandomAccessIterator
4311is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4312{
4313    typedef typename _STD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4314    difference_type __len = __last - __first;
4315    difference_type __p = 0;
4316    difference_type __c = 1;
4317    _RandomAccessIterator __pp = __first;
4318    while (__c < __len)
4319    {
4320        _RandomAccessIterator __cp = __first + __c;
4321        if (__comp(*__pp, *__cp))
4322            return __cp;
4323        ++__c;
4324        ++__cp;
4325        if (__c == __len)
4326            return __last;
4327        if (__comp(*__pp, *__cp))
4328            return __cp;
4329        ++__p;
4330        ++__pp;
4331        __c = 2 * __p + 1;
4332    }
4333    return __last;
4334}
4335
4336template<class _RandomAccessIterator>
4337inline _LIBCPP_INLINE_VISIBILITY
4338_RandomAccessIterator
4339is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4340{
4341    return _STD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4342}
4343
4344// is_heap
4345
4346template <class _RandomAccessIterator, class _Compare>
4347inline _LIBCPP_INLINE_VISIBILITY
4348bool
4349is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4350{
4351    return _STD::is_heap_until(__first, __last, __comp) == __last;
4352}
4353
4354template<class _RandomAccessIterator>
4355inline _LIBCPP_INLINE_VISIBILITY
4356bool
4357is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4358{
4359    return _STD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4360}
4361
4362// push_heap
4363
4364template <class _Compare, class _RandomAccessIterator>
4365void
4366__push_heap_front(_RandomAccessIterator __first, _RandomAccessIterator, _Compare __comp,
4367                  typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4368{
4369    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4370    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4371    if (__len > 1)
4372    {
4373        difference_type __p = 0;
4374        _RandomAccessIterator __pp = __first;
4375        difference_type __c = 2;
4376        _RandomAccessIterator __cp = __first + __c;
4377        if (__c == __len || __comp(*__cp, *(__cp - 1)))
4378        {
4379            --__c;
4380            --__cp;
4381        }
4382        if (__comp(*__pp, *__cp))
4383        {
4384            value_type __t(_STD::move(*__pp));
4385            do
4386            {
4387                *__pp = _STD::move(*__cp);
4388                __pp = __cp;
4389                __p = __c;
4390                __c = (__p + 1) * 2;
4391                if (__c > __len)
4392                    break;
4393                __cp = __first + __c;
4394                if (__c == __len || __comp(*__cp, *(__cp - 1)))
4395                {
4396                    --__c;
4397                    --__cp;
4398                }
4399            } while (__comp(__t, *__cp));
4400            *__pp = _STD::move(__t);
4401        }
4402    }
4403}
4404
4405template <class _Compare, class _RandomAccessIterator>
4406void
4407__push_heap_back(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4408                 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4409{
4410    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4411    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4412    if (__len > 1)
4413    {
4414        __len = (__len - 2) / 2;
4415        _RandomAccessIterator __ptr = __first + __len;
4416        if (__comp(*__ptr, *--__last))
4417        {
4418            value_type __t(_STD::move(*__last));
4419            do
4420            {
4421                *__last = _STD::move(*__ptr);
4422                __last = __ptr;
4423                if (__len == 0)
4424                    break;
4425                __len = (__len - 1) / 2;
4426                __ptr = __first + __len;
4427            } while (__comp(*__ptr, __t));
4428            *__last = _STD::move(__t);
4429        }
4430    }
4431}
4432
4433template <class _RandomAccessIterator, class _Compare>
4434inline _LIBCPP_INLINE_VISIBILITY
4435void
4436push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4437{
4438#ifdef _LIBCPP_DEBUG
4439    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4440    __debug_less<_Compare> __c(__comp);
4441    __push_heap_back<_Comp_ref>(__first, __last, __c, __last - __first);
4442#else  // _LIBCPP_DEBUG
4443    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4444    __push_heap_back<_Comp_ref>(__first, __last, __comp, __last - __first);
4445#endif  // _LIBCPP_DEBUG
4446}
4447
4448template <class _RandomAccessIterator>
4449inline _LIBCPP_INLINE_VISIBILITY
4450void
4451push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4452{
4453    _STD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4454}
4455
4456// pop_heap
4457
4458template <class _Compare, class _RandomAccessIterator>
4459inline _LIBCPP_INLINE_VISIBILITY
4460void
4461__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4462           typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4463{
4464    if (__len > 1)
4465    {
4466        swap(*__first, *--__last);
4467        __push_heap_front<_Compare>(__first, __last, __comp, __len-1);
4468    }
4469}
4470
4471template <class _RandomAccessIterator, class _Compare>
4472inline _LIBCPP_INLINE_VISIBILITY
4473void
4474pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4475{
4476#ifdef _LIBCPP_DEBUG
4477    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4478    __debug_less<_Compare> __c(__comp);
4479    __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);
4480#else  // _LIBCPP_DEBUG
4481    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4482    __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
4483#endif  // _LIBCPP_DEBUG
4484}
4485
4486template <class _RandomAccessIterator>
4487inline _LIBCPP_INLINE_VISIBILITY
4488void
4489pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4490{
4491    _STD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4492}
4493
4494// make_heap
4495
4496template <class _Compare, class _RandomAccessIterator>
4497void
4498__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4499{
4500    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4501    difference_type __n = __last - __first;
4502    if (__n > 1)
4503    {
4504        __last = __first;
4505        ++__last;
4506        for (difference_type __i = 1; __i < __n;)
4507            __push_heap_back<_Compare>(__first, ++__last, __comp, ++__i);
4508    }
4509}
4510
4511template <class _RandomAccessIterator, class _Compare>
4512inline _LIBCPP_INLINE_VISIBILITY
4513void
4514make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4515{
4516#ifdef _LIBCPP_DEBUG
4517    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4518    __debug_less<_Compare> __c(__comp);
4519    __make_heap<_Comp_ref>(__first, __last, __c);
4520#else  // _LIBCPP_DEBUG
4521    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4522    __make_heap<_Comp_ref>(__first, __last, __comp);
4523#endif  // _LIBCPP_DEBUG
4524}
4525
4526template <class _RandomAccessIterator>
4527inline _LIBCPP_INLINE_VISIBILITY
4528void
4529make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4530{
4531    _STD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4532}
4533
4534// sort_heap
4535
4536template <class _Compare, class _RandomAccessIterator>
4537void
4538__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4539{
4540    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4541    for (difference_type __n = __last - __first; __n > 1; --__last, --__n)
4542        __pop_heap<_Compare>(__first, __last, __comp, __n);
4543}
4544
4545template <class _RandomAccessIterator, class _Compare>
4546inline _LIBCPP_INLINE_VISIBILITY
4547void
4548sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4549{
4550#ifdef _LIBCPP_DEBUG
4551    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4552    __debug_less<_Compare> __c(__comp);
4553    __sort_heap<_Comp_ref>(__first, __last, __c);
4554#else  // _LIBCPP_DEBUG
4555    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4556    __sort_heap<_Comp_ref>(__first, __last, __comp);
4557#endif  // _LIBCPP_DEBUG
4558}
4559
4560template <class _RandomAccessIterator>
4561inline _LIBCPP_INLINE_VISIBILITY
4562void
4563sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4564{
4565    _STD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4566}
4567
4568// partial_sort
4569
4570template <class _Compare, class _RandomAccessIterator>
4571void
4572__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
4573             _Compare __comp)
4574{
4575    __make_heap<_Compare>(__first, __middle, __comp);
4576    typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
4577    for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
4578    {
4579        if (__comp(*__i, *__first))
4580        {
4581            swap(*__i, *__first);
4582            __push_heap_front<_Compare>(__first, __middle, __comp, __len);
4583        }
4584    }
4585    __sort_heap<_Compare>(__first, __middle, __comp);
4586}
4587
4588template <class _RandomAccessIterator, class _Compare>
4589inline _LIBCPP_INLINE_VISIBILITY
4590void
4591partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
4592             _Compare __comp)
4593{
4594#ifdef _LIBCPP_DEBUG
4595    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4596    __debug_less<_Compare> __c(__comp);
4597    __partial_sort<_Comp_ref>(__first, __middle, __last, __c);
4598#else  // _LIBCPP_DEBUG
4599    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4600    __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
4601#endif  // _LIBCPP_DEBUG
4602}
4603
4604template <class _RandomAccessIterator>
4605inline _LIBCPP_INLINE_VISIBILITY
4606void
4607partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
4608{
4609    _STD::partial_sort(__first, __middle, __last,
4610                       __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4611}
4612
4613// partial_sort_copy
4614
4615template <class _Compare, class _InputIterator, class _RandomAccessIterator>
4616_RandomAccessIterator
4617__partial_sort_copy(_InputIterator __first, _InputIterator __last,
4618                    _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
4619{
4620    _RandomAccessIterator __r = __result_first;
4621    if (__r != __result_last)
4622    {
4623        typename iterator_traits<_RandomAccessIterator>::difference_type __len = 0;
4624        for (; __first != __last && __r != __result_last; ++__first, ++__r, ++__len)
4625            *__r = *__first;
4626        __make_heap<_Compare>(__result_first, __r, __comp);
4627        for (; __first != __last; ++__first)
4628            if (__comp(*__first, *__result_first))
4629            {
4630                *__result_first = *__first;
4631                __push_heap_front<_Compare>(__result_first, __r, __comp, __len);
4632            }
4633        __sort_heap<_Compare>(__result_first, __r, __comp);
4634    }
4635    return __r;
4636}
4637
4638template <class _InputIterator, class _RandomAccessIterator, class _Compare>
4639inline _LIBCPP_INLINE_VISIBILITY
4640_RandomAccessIterator
4641partial_sort_copy(_InputIterator __first, _InputIterator __last,
4642                  _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
4643{
4644#ifdef _LIBCPP_DEBUG
4645    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4646    __debug_less<_Compare> __c(__comp);
4647    return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);
4648#else  // _LIBCPP_DEBUG
4649    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4650    return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
4651#endif  // _LIBCPP_DEBUG
4652}
4653
4654template <class _InputIterator, class _RandomAccessIterator>
4655inline _LIBCPP_INLINE_VISIBILITY
4656_RandomAccessIterator
4657partial_sort_copy(_InputIterator __first, _InputIterator __last,
4658                  _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
4659{
4660    return _STD::partial_sort_copy(__first, __last, __result_first, __result_last,
4661                                   __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4662}
4663
4664// nth_element
4665
4666template <class _Compare, class _RandomAccessIterator>
4667void
4668__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
4669{
4670    // _Compare is known to be a reference type
4671    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4672    const difference_type __limit = 7;
4673    while (true)
4674    {
4675    __restart:
4676        difference_type __len = __last - __first;
4677        switch (__len)
4678        {
4679        case 0:
4680        case 1:
4681            return;
4682        case 2:
4683            if (__comp(*--__last, *__first))
4684                swap(*__first, *__last);
4685            return;
4686        case 3:
4687            {
4688            _RandomAccessIterator __m = __first;
4689            _STD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
4690            return;
4691            }
4692        }
4693        if (__len <= __limit)
4694        {
4695            __selection_sort<_Compare>(__first, __last, __comp);
4696            return;
4697        }
4698        // __len > __limit >= 3
4699        _RandomAccessIterator __m = __first + __len/2;
4700        _RandomAccessIterator __lm1 = __last;
4701        unsigned __n_swaps = _STD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
4702        // *__m is median
4703        // partition [__first, __m) < *__m and *__m <= [__m, __last)
4704        // (this inhibits tossing elements equivalent to __m around unnecessarily)
4705        _RandomAccessIterator __i = __first;
4706        _RandomAccessIterator __j = __lm1;
4707        // j points beyond range to be tested, *__lm1 is known to be <= *__m
4708        // The search going up is known to be guarded but the search coming down isn't.
4709        // Prime the downward search with a guard.
4710        if (!__comp(*__i, *__m))  // if *__first == *__m
4711        {
4712            // *__first == *__m, *__first doesn't go in first part
4713            // manually guard downward moving __j against __i
4714            while (true)
4715            {
4716                if (__i == --__j)
4717                {
4718                    // *__first == *__m, *__m <= all other elements
4719                    // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
4720                    ++__i;  // __first + 1
4721                    __j = __last;
4722                    if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
4723                    {
4724                        while (true)
4725                        {
4726                            if (__i == __j)
4727                                return;  // [__first, __last) all equivalent elements
4728                            if (__comp(*__first, *__i))
4729                            {
4730                                swap(*__i, *__j);
4731                                ++__n_swaps;
4732                                ++__i;
4733                                break;
4734                            }
4735                            ++__i;
4736                        }
4737                    }
4738                    // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
4739                    if (__i == __j)
4740                        return;
4741                    while (true)
4742                    {
4743                        while (!__comp(*__first, *__i))
4744                            ++__i;
4745                        while (__comp(*__first, *--__j))
4746                            ;
4747                        if (__i >= __j)
4748                            break;
4749                        swap(*__i, *__j);
4750                        ++__n_swaps;
4751                        ++__i;
4752                    }
4753                    // [__first, __i) == *__first and *__first < [__i, __last)
4754                    // The first part is sorted,
4755                    if (__nth < __i)
4756                        return;
4757                    // __nth_element the secod part
4758                    // __nth_element<_Compare>(__i, __nth, __last, __comp);
4759                    __first = __i;
4760                    goto __restart;
4761                }
4762                if (__comp(*__j, *__m))
4763                {
4764                    swap(*__i, *__j);
4765                    ++__n_swaps;
4766                    break;  // found guard for downward moving __j, now use unguarded partition
4767                }
4768            }
4769        }
4770        ++__i;
4771        // j points beyond range to be tested, *__lm1 is known to be <= *__m
4772        // if not yet partitioned...
4773        if (__i < __j)
4774        {
4775            // known that *(__i - 1) < *__m
4776            while (true)
4777            {
4778                // __m still guards upward moving __i
4779                while (__comp(*__i, *__m))
4780                    ++__i;
4781                // It is now known that a guard exists for downward moving __j
4782                while (!__comp(*--__j, *__m))
4783                    ;
4784                if (__i >= __j)
4785                    break;
4786                swap(*__i, *__j);
4787                ++__n_swaps;
4788                // It is known that __m != __j
4789                // If __m just moved, follow it
4790                if (__m == __i)
4791                    __m = __j;
4792                ++__i;
4793            }
4794        }
4795        // [__first, __i) < *__m and *__m <= [__i, __last)
4796        if (__i != __m && __comp(*__m, *__i))
4797        {
4798            swap(*__i, *__m);
4799            ++__n_swaps;
4800        }
4801        // [__first, __i) < *__i and *__i <= [__i+1, __last)
4802        if (__nth == __i)
4803            return;
4804        if (__n_swaps == 0)
4805        {
4806            // We were given a perfectly partitioned sequence.  Coincidence?
4807            if (__nth < __i)
4808            {
4809                // Check for [__first, __i) already sorted
4810                __j = __m = __first;
4811                while (++__j != __i)
4812                {
4813                    if (__comp(*__j, *__m))
4814                        // not yet sorted, so sort
4815                        goto not_sorted;
4816                    __m = __j;
4817                }
4818                // [__first, __i) sorted
4819                return;
4820            }
4821            else
4822            {
4823                // Check for [__i, __last) already sorted
4824                __j = __m = __i;
4825                while (++__j != __last)
4826                {
4827                    if (__comp(*__j, *__m))
4828                        // not yet sorted, so sort
4829                        goto not_sorted;
4830                    __m = __j;
4831                }
4832                // [__i, __last) sorted
4833                return;
4834            }
4835        }
4836not_sorted:
4837        // __nth_element on range containing __nth
4838        if (__nth < __i)
4839        {
4840            // __nth_element<_Compare>(__first, __nth, __i, __comp);
4841            __last = __i;
4842        }
4843        else
4844        {
4845            // __nth_element<_Compare>(__i+1, __nth, __last, __comp);
4846            __first = ++__i;
4847        }
4848    }
4849}
4850
4851template <class _RandomAccessIterator, class _Compare>
4852inline _LIBCPP_INLINE_VISIBILITY
4853void
4854nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
4855{
4856#ifdef _LIBCPP_DEBUG
4857    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4858    __debug_less<_Compare> __c(__comp);
4859    __nth_element<_Comp_ref>(__first, __nth, __last, __c);
4860#else  // _LIBCPP_DEBUG
4861    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4862    __nth_element<_Comp_ref>(__first, __nth, __last, __comp);
4863#endif  // _LIBCPP_DEBUG
4864}
4865
4866template <class _RandomAccessIterator>
4867inline _LIBCPP_INLINE_VISIBILITY
4868void
4869nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
4870{
4871    _STD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4872}
4873
4874// includes
4875
4876template <class _Compare, class _InputIterator1, class _InputIterator2>
4877bool
4878__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
4879           _Compare __comp)
4880{
4881    for (; __first2 != __last2; ++__first1)
4882    {
4883        if (__first1 == __last1 || __comp(*__first2, *__first1))
4884            return false;
4885        if (!__comp(*__first1, *__first2))
4886            ++__first2;
4887    }
4888    return true;
4889}
4890
4891template <class _InputIterator1, class _InputIterator2, class _Compare>
4892inline _LIBCPP_INLINE_VISIBILITY
4893bool
4894includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
4895         _Compare __comp)
4896{
4897#ifdef _LIBCPP_DEBUG
4898    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4899    __debug_less<_Compare> __c(__comp);
4900    return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
4901#else  // _LIBCPP_DEBUG
4902    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4903    return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
4904#endif  // _LIBCPP_DEBUG
4905}
4906
4907template <class _InputIterator1, class _InputIterator2>
4908inline _LIBCPP_INLINE_VISIBILITY
4909bool
4910includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
4911{
4912    return _STD::includes(__first1, __last1, __first2, __last2,
4913                          __less<typename iterator_traits<_InputIterator1>::value_type,
4914                                 typename iterator_traits<_InputIterator2>::value_type>());
4915}
4916
4917// set_union
4918
4919template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4920_OutputIterator
4921__set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4922            _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4923{
4924    for (; __first1 != __last1; ++__result)
4925    {
4926        if (__first2 == __last2)
4927            return _STD::copy(__first1, __last1, __result);
4928        if (__comp(*__first2, *__first1))
4929        {
4930            *__result = *__first2;
4931            ++__first2;
4932        }
4933        else
4934        {
4935            *__result = *__first1;
4936            if (!__comp(*__first1, *__first2))
4937                ++__first2;
4938            ++__first1;
4939        }
4940    }
4941    return _STD::copy(__first2, __last2, __result);
4942}
4943
4944template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4945inline _LIBCPP_INLINE_VISIBILITY
4946_OutputIterator
4947set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4948          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4949{
4950#ifdef _LIBCPP_DEBUG
4951    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4952    __debug_less<_Compare> __c(__comp);
4953    return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
4954#else  // _LIBCPP_DEBUG
4955    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4956    return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4957#endif  // _LIBCPP_DEBUG
4958}
4959
4960template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4961inline _LIBCPP_INLINE_VISIBILITY
4962_OutputIterator
4963set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4964          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4965{
4966    return _STD::set_union(__first1, __last1, __first2, __last2, __result,
4967                          __less<typename iterator_traits<_InputIterator1>::value_type,
4968                                 typename iterator_traits<_InputIterator2>::value_type>());
4969}
4970
4971// set_intersection
4972
4973template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4974_OutputIterator
4975__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
4976                   _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4977{
4978    while (__first1 != __last1 && __first2 != __last2)
4979    {
4980        if (__comp(*__first1, *__first2))
4981            ++__first1;
4982        else
4983        {
4984            if (!__comp(*__first2, *__first1))
4985            {
4986                *__result = *__first1;
4987                ++__result;
4988                ++__first1;
4989            }
4990            ++__first2;
4991        }
4992    }
4993    return __result;
4994}
4995
4996template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4997inline _LIBCPP_INLINE_VISIBILITY
4998_OutputIterator
4999set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5000                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5001{
5002#ifdef _LIBCPP_DEBUG
5003    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5004    __debug_less<_Compare> __c(__comp);
5005    return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5006#else  // _LIBCPP_DEBUG
5007    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5008    return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5009#endif  // _LIBCPP_DEBUG
5010}
5011
5012template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5013inline _LIBCPP_INLINE_VISIBILITY
5014_OutputIterator
5015set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5016                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5017{
5018    return _STD::set_intersection(__first1, __last1, __first2, __last2, __result,
5019                                  __less<typename iterator_traits<_InputIterator1>::value_type,
5020                                         typename iterator_traits<_InputIterator2>::value_type>());
5021}
5022
5023// set_difference
5024
5025template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5026_OutputIterator
5027__set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5028                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5029{
5030    while (__first1 != __last1)
5031    {
5032        if (__first2 == __last2)
5033            return _STD::copy(__first1, __last1, __result);
5034        if (__comp(*__first1, *__first2))
5035        {
5036            *__result = *__first1;
5037            ++__result;
5038            ++__first1;
5039        }
5040        else
5041        {
5042            if (!__comp(*__first2, *__first1))
5043                ++__first1;
5044            ++__first2;
5045        }
5046    }
5047    return __result;
5048}
5049
5050template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5051inline _LIBCPP_INLINE_VISIBILITY
5052_OutputIterator
5053set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5054               _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5055{
5056#ifdef _LIBCPP_DEBUG
5057    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5058    __debug_less<_Compare> __c(__comp);
5059    return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5060#else  // _LIBCPP_DEBUG
5061    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5062    return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5063#endif  // _LIBCPP_DEBUG
5064}
5065
5066template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5067inline _LIBCPP_INLINE_VISIBILITY
5068_OutputIterator
5069set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5070               _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5071{
5072    return _STD::set_difference(__first1, __last1, __first2, __last2, __result,
5073                                __less<typename iterator_traits<_InputIterator1>::value_type,
5074                                       typename iterator_traits<_InputIterator2>::value_type>());
5075}
5076
5077// set_symmetric_difference
5078
5079template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5080_OutputIterator
5081__set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5082                           _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5083{
5084    while (__first1 != __last1)
5085    {
5086        if (__first2 == __last2)
5087            return _STD::copy(__first1, __last1, __result);
5088        if (__comp(*__first1, *__first2))
5089        {
5090            *__result = *__first1;
5091            ++__result;
5092            ++__first1;
5093        }
5094        else
5095        {
5096            if (__comp(*__first2, *__first1))
5097            {
5098                *__result = *__first2;
5099                ++__result;
5100            }
5101            else
5102                ++__first1;
5103            ++__first2;
5104        }
5105    }
5106    return _STD::copy(__first2, __last2, __result);
5107}
5108
5109template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5110inline _LIBCPP_INLINE_VISIBILITY
5111_OutputIterator
5112set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5113                         _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5114{
5115#ifdef _LIBCPP_DEBUG
5116    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5117    __debug_less<_Compare> __c(__comp);
5118    return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5119#else  // _LIBCPP_DEBUG
5120    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5121    return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5122#endif  // _LIBCPP_DEBUG
5123}
5124
5125template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5126inline _LIBCPP_INLINE_VISIBILITY
5127_OutputIterator
5128set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5129                         _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5130{
5131    return _STD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
5132                                          __less<typename iterator_traits<_InputIterator1>::value_type,
5133                                                 typename iterator_traits<_InputIterator2>::value_type>());
5134}
5135
5136// lexicographical_compare
5137
5138template <class _Compare, class _InputIterator1, class _InputIterator2>
5139bool
5140__lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5141                          _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5142{
5143    for (; __first2 != __last2; ++__first1, ++__first2)
5144    {
5145        if (__first1 == __last1 || __comp(*__first1, *__first2))
5146            return true;
5147        if (__comp(*__first2, *__first1))
5148            return false;
5149    }
5150    return false;
5151}
5152
5153template <class _InputIterator1, class _InputIterator2, class _Compare>
5154inline _LIBCPP_INLINE_VISIBILITY
5155bool
5156lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5157                        _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5158{
5159#ifdef _LIBCPP_DEBUG
5160    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5161    __debug_less<_Compare> __c(__comp);
5162    return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5163#else  // _LIBCPP_DEBUG
5164    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5165    return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5166#endif  // _LIBCPP_DEBUG
5167}
5168
5169template <class _InputIterator1, class _InputIterator2>
5170inline _LIBCPP_INLINE_VISIBILITY
5171bool
5172lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5173                        _InputIterator2 __first2, _InputIterator2 __last2)
5174{
5175    return _STD::lexicographical_compare(__first1, __last1, __first2, __last2,
5176                                         __less<typename iterator_traits<_InputIterator1>::value_type,
5177                                                typename iterator_traits<_InputIterator2>::value_type>());
5178}
5179
5180// next_permutation
5181
5182template <class _Compare, class _BidirectionalIterator>
5183bool
5184__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5185{
5186    _BidirectionalIterator __i = __last;
5187    if (__first == __last || __first == --__i)
5188        return false;
5189    while (true)
5190    {
5191        _BidirectionalIterator __ip1 = __i;
5192        if (__comp(*--__i, *__ip1))
5193        {
5194            _BidirectionalIterator __j = __last;
5195            while (!__comp(*__i, *--__j))
5196                ;
5197            swap(*__i, *__j);
5198            _STD::reverse(__ip1, __last);
5199            return true;
5200        }
5201        if (__i == __first)
5202        {
5203            _STD::reverse(__first, __last);
5204            return false;
5205        }
5206    }
5207}
5208
5209template <class _BidirectionalIterator, class _Compare>
5210inline _LIBCPP_INLINE_VISIBILITY
5211bool
5212next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5213{
5214#ifdef _LIBCPP_DEBUG
5215    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5216    __debug_less<_Compare> __c(__comp);
5217    return __next_permutation<_Comp_ref>(__first, __last, __c);
5218#else  // _LIBCPP_DEBUG
5219    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5220    return __next_permutation<_Comp_ref>(__first, __last, __comp);
5221#endif  // _LIBCPP_DEBUG
5222}
5223
5224template <class _BidirectionalIterator>
5225inline _LIBCPP_INLINE_VISIBILITY
5226bool
5227next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5228{
5229    return _STD::next_permutation(__first, __last,
5230                                  __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5231}
5232
5233// prev_permutation
5234
5235template <class _Compare, class _BidirectionalIterator>
5236bool
5237__prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5238{
5239    _BidirectionalIterator __i = __last;
5240    if (__first == __last || __first == --__i)
5241        return false;
5242    while (true)
5243    {
5244        _BidirectionalIterator __ip1 = __i;
5245        if (__comp(*__ip1, *--__i))
5246        {
5247            _BidirectionalIterator __j = __last;
5248            while (!__comp(*--__j, *__i))
5249                ;
5250            swap(*__i, *__j);
5251            _STD::reverse(__ip1, __last);
5252            return true;
5253        }
5254        if (__i == __first)
5255        {
5256            _STD::reverse(__first, __last);
5257            return false;
5258        }
5259    }
5260}
5261
5262template <class _BidirectionalIterator, class _Compare>
5263inline _LIBCPP_INLINE_VISIBILITY
5264bool
5265prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5266{
5267#ifdef _LIBCPP_DEBUG
5268    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5269    __debug_less<_Compare> __c(__comp);
5270    return __prev_permutation<_Comp_ref>(__first, __last, __c);
5271#else  // _LIBCPP_DEBUG
5272    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5273    return __prev_permutation<_Comp_ref>(__first, __last, __comp);
5274#endif  // _LIBCPP_DEBUG
5275}
5276
5277template <class _BidirectionalIterator>
5278inline _LIBCPP_INLINE_VISIBILITY
5279bool
5280prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5281{
5282    return _STD::prev_permutation(__first, __last,
5283                                  __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5284}
5285
5286template <class _Tp>
5287inline _LIBCPP_INLINE_VISIBILITY
5288typename enable_if
5289<
5290    is_integral<_Tp>::value,
5291    _Tp
5292>::type
5293__rotate_left(_Tp __t, _Tp __n = 1)
5294{
5295    const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1);
5296    __n &= __bits;
5297    return static_cast<_Tp>((__t << __n) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> (__bits - __n)));
5298}
5299
5300template <class _Tp>
5301inline _LIBCPP_INLINE_VISIBILITY
5302typename enable_if
5303<
5304    is_integral<_Tp>::value,
5305    _Tp
5306>::type
5307__rotate_right(_Tp __t, _Tp __n = 1)
5308{
5309    const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1);
5310    __n &= __bits;
5311    return static_cast<_Tp>((__t << (__bits - __n)) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> __n));
5312}
5313
5314_LIBCPP_END_NAMESPACE_STD
5315
5316#endif  // _LIBCPP_ALGORITHM
5317