1// -*- C++ -*-
2//===-------------------------- algorithm ---------------------------------===//
3//
4//                     The LLVM Compiler Infrastructure
5//
6// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_ALGORITHM
12#define _LIBCPP_ALGORITHM
13
14/*
15    algorithm synopsis
16
17#include <initializer_list>
18
19namespace std
20{
21
22template <class InputIterator, class Predicate>
23    bool
24    all_of(InputIterator first, InputIterator last, Predicate pred);
25
26template <class InputIterator, class Predicate>
27    bool
28    any_of(InputIterator first, InputIterator last, Predicate pred);
29
30template <class InputIterator, class Predicate>
31    bool
32    none_of(InputIterator first, InputIterator last, Predicate pred);
33
34template <class InputIterator, class Function>
35    Function
36    for_each(InputIterator first, InputIterator last, Function f);
37
38template <class InputIterator, class T>
39    InputIterator
40    find(InputIterator first, InputIterator last, const T& value);
41
42template <class InputIterator, class Predicate>
43    InputIterator
44    find_if(InputIterator first, InputIterator last, Predicate pred);
45
46template<class InputIterator, class Predicate>
47    InputIterator
48    find_if_not(InputIterator first, InputIterator last, Predicate pred);
49
50template <class ForwardIterator1, class ForwardIterator2>
51    ForwardIterator1
52    find_end(ForwardIterator1 first1, ForwardIterator1 last1,
53             ForwardIterator2 first2, ForwardIterator2 last2);
54
55template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
56    ForwardIterator1
57    find_end(ForwardIterator1 first1, ForwardIterator1 last1,
58             ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
59
60template <class ForwardIterator1, class ForwardIterator2>
61    ForwardIterator1
62    find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
63                  ForwardIterator2 first2, ForwardIterator2 last2);
64
65template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
66    ForwardIterator1
67    find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
68                  ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
69
70template <class ForwardIterator>
71    ForwardIterator
72    adjacent_find(ForwardIterator first, ForwardIterator last);
73
74template <class ForwardIterator, class BinaryPredicate>
75    ForwardIterator
76    adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
77
78template <class InputIterator, class T>
79    typename iterator_traits<InputIterator>::difference_type
80    count(InputIterator first, InputIterator last, const T& value);
81
82template <class InputIterator, class Predicate>
83    typename iterator_traits<InputIterator>::difference_type
84    count_if(InputIterator first, InputIterator last, Predicate pred);
85
86template <class InputIterator1, class InputIterator2>
87    pair<InputIterator1, InputIterator2>
88    mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
89
90template <class InputIterator1, class InputIterator2, class BinaryPredicate>
91    pair<InputIterator1, InputIterator2>
92    mismatch(InputIterator1 first1, InputIterator1 last1,
93             InputIterator2 first2, BinaryPredicate pred);
94
95template <class InputIterator1, class InputIterator2>
96    bool
97    equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
98
99template <class InputIterator1, class InputIterator2, class BinaryPredicate>
100    bool
101    equal(InputIterator1 first1, InputIterator1 last1,
102          InputIterator2 first2, BinaryPredicate pred);
103
104template<class ForwardIterator1, class ForwardIterator2>
105    bool
106    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
107                   ForwardIterator2 first2);
108
109template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
110    bool
111    is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
112                   ForwardIterator2 first2, BinaryPredicate pred);
113
114template <class ForwardIterator1, class ForwardIterator2>
115    ForwardIterator1
116    search(ForwardIterator1 first1, ForwardIterator1 last1,
117           ForwardIterator2 first2, ForwardIterator2 last2);
118
119template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
120    ForwardIterator1
121    search(ForwardIterator1 first1, ForwardIterator1 last1,
122           ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
123
124template <class ForwardIterator, class Size, class T>
125    ForwardIterator
126    search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
127
128template <class ForwardIterator, class Size, class T, class BinaryPredicate>
129    ForwardIterator
130    search_n(ForwardIterator first, ForwardIterator last,
131             Size count, const T& value, BinaryPredicate pred);
132
133template <class InputIterator, class OutputIterator>
134    OutputIterator
135    copy(InputIterator first, InputIterator last, OutputIterator result);
136
137template<class InputIterator, class OutputIterator, class Predicate>
138    OutputIterator
139    copy_if(InputIterator first, InputIterator last,
140            OutputIterator result, Predicate pred);
141
142template<class InputIterator, class Size, class OutputIterator>
143    OutputIterator
144    copy_n(InputIterator first, Size n, OutputIterator result);
145
146template <class BidirectionalIterator1, class BidirectionalIterator2>
147    BidirectionalIterator2
148    copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
149                  BidirectionalIterator2 result);
150
151template <class ForwardIterator1, class ForwardIterator2>
152    ForwardIterator2
153    swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
154
155template <class ForwardIterator1, class ForwardIterator2>
156    void
157    iter_swap(ForwardIterator1 a, ForwardIterator2 b);
158
159template <class InputIterator, class OutputIterator, class UnaryOperation>
160    OutputIterator
161    transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
162
163template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
164    OutputIterator
165    transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
166              OutputIterator result, BinaryOperation binary_op);
167
168template <class ForwardIterator, class T>
169    void
170    replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
171
172template <class ForwardIterator, class Predicate, class T>
173    void
174    replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
175
176template <class InputIterator, class OutputIterator, class T>
177    OutputIterator
178    replace_copy(InputIterator first, InputIterator last, OutputIterator result,
179                 const T& old_value, const T& new_value);
180
181template <class InputIterator, class OutputIterator, class Predicate, class T>
182    OutputIterator
183    replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
184
185template <class ForwardIterator, class T>
186    void
187    fill(ForwardIterator first, ForwardIterator last, const T& value);
188
189template <class OutputIterator, class Size, class T>
190    OutputIterator
191    fill_n(OutputIterator first, Size n, const T& value);
192
193template <class ForwardIterator, class Generator>
194    void
195    generate(ForwardIterator first, ForwardIterator last, Generator gen);
196
197template <class OutputIterator, class Size, class Generator>
198    OutputIterator
199    generate_n(OutputIterator first, Size n, Generator gen);
200
201template <class ForwardIterator, class T>
202    ForwardIterator
203    remove(ForwardIterator first, ForwardIterator last, const T& value);
204
205template <class ForwardIterator, class Predicate>
206    ForwardIterator
207    remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
208
209template <class InputIterator, class OutputIterator, class T>
210    OutputIterator
211    remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
212
213template <class InputIterator, class OutputIterator, class Predicate>
214    OutputIterator
215    remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
216
217template <class ForwardIterator>
218    ForwardIterator
219    unique(ForwardIterator first, ForwardIterator last);
220
221template <class ForwardIterator, class BinaryPredicate>
222    ForwardIterator
223    unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
224
225template <class InputIterator, class OutputIterator>
226    OutputIterator
227    unique_copy(InputIterator first, InputIterator last, OutputIterator result);
228
229template <class InputIterator, class OutputIterator, class BinaryPredicate>
230    OutputIterator
231    unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
232
233template <class BidirectionalIterator>
234    void
235    reverse(BidirectionalIterator first, BidirectionalIterator last);
236
237template <class BidirectionalIterator, class OutputIterator>
238    OutputIterator
239    reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
240
241template <class ForwardIterator>
242    ForwardIterator
243    rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
244
245template <class ForwardIterator, class OutputIterator>
246    OutputIterator
247    rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
248
249template <class RandomAccessIterator>
250    void
251    random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
252
253template <class RandomAccessIterator, class RandomNumberGenerator>
254    void
255    random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand);
256
257template<class RandomAccessIterator, class UniformRandomNumberGenerator>
258    void shuffle(RandomAccessIterator first, RandomAccessIterator last,
259                 UniformRandomNumberGenerator&& g);
260
261template <class InputIterator, class Predicate>
262    bool
263    is_partitioned(InputIterator first, InputIterator last, Predicate pred);
264
265template <class ForwardIterator, class Predicate>
266    ForwardIterator
267    partition(ForwardIterator first, ForwardIterator last, Predicate pred);
268
269template <class InputIterator, class OutputIterator1,
270          class OutputIterator2, class Predicate>
271    pair<OutputIterator1, OutputIterator2>
272    partition_copy(InputIterator first, InputIterator last,
273                   OutputIterator1 out_true, OutputIterator2 out_false,
274                   Predicate pred);
275
276template <class ForwardIterator, class Predicate>
277    ForwardIterator
278    stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
279
280template<class ForwardIterator, class Predicate>
281    ForwardIterator
282    partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
283
284template <class ForwardIterator>
285    bool
286    is_sorted(ForwardIterator first, ForwardIterator last);
287
288template <class ForwardIterator, class Compare>
289    bool
290    is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
291
292template<class ForwardIterator>
293    ForwardIterator
294    is_sorted_until(ForwardIterator first, ForwardIterator last);
295
296template <class ForwardIterator, class Compare>
297    ForwardIterator
298    is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
299
300template <class RandomAccessIterator>
301    void
302    sort(RandomAccessIterator first, RandomAccessIterator last);
303
304template <class RandomAccessIterator, class Compare>
305    void
306    sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
307
308template <class RandomAccessIterator>
309    void
310    stable_sort(RandomAccessIterator first, RandomAccessIterator last);
311
312template <class RandomAccessIterator, class Compare>
313    void
314    stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
315
316template <class RandomAccessIterator>
317    void
318    partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
319
320template <class RandomAccessIterator, class Compare>
321    void
322    partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
323
324template <class InputIterator, class RandomAccessIterator>
325    RandomAccessIterator
326    partial_sort_copy(InputIterator first, InputIterator last,
327                      RandomAccessIterator result_first, RandomAccessIterator result_last);
328
329template <class InputIterator, class RandomAccessIterator, class Compare>
330    RandomAccessIterator
331    partial_sort_copy(InputIterator first, InputIterator last,
332                      RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
333
334template <class RandomAccessIterator>
335    void
336    nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
337
338template <class RandomAccessIterator, class Compare>
339    void
340    nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
341
342template <class ForwardIterator, class T>
343    ForwardIterator
344    lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
345
346template <class ForwardIterator, class T, class Compare>
347    ForwardIterator
348    lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
349
350template <class ForwardIterator, class T>
351    ForwardIterator
352    upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
353
354template <class ForwardIterator, class T, class Compare>
355    ForwardIterator
356    upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
357
358template <class ForwardIterator, class T>
359    pair<ForwardIterator, ForwardIterator>
360    equal_range(ForwardIterator first, ForwardIterator last, const T& value);
361
362template <class ForwardIterator, class T, class Compare>
363    pair<ForwardIterator, ForwardIterator>
364    equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
365
366template <class ForwardIterator, class T>
367    bool
368    binary_search(ForwardIterator first, ForwardIterator last, const T& value);
369
370template <class ForwardIterator, class T, class Compare>
371    bool
372    binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
373
374template <class InputIterator1, class InputIterator2, class OutputIterator>
375    OutputIterator
376    merge(InputIterator1 first1, InputIterator1 last1,
377          InputIterator2 first2, InputIterator2 last2, OutputIterator result);
378
379template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
380    OutputIterator
381    merge(InputIterator1 first1, InputIterator1 last1,
382          InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
383
384template <class BidirectionalIterator>
385    void
386    inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
387
388template <class BidirectionalIterator, class Compare>
389    void
390    inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
391
392template <class InputIterator1, class InputIterator2>
393    bool
394    includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
395
396template <class InputIterator1, class InputIterator2, class Compare>
397    bool
398    includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
399
400template <class InputIterator1, class InputIterator2, class OutputIterator>
401    OutputIterator
402    set_union(InputIterator1 first1, InputIterator1 last1,
403              InputIterator2 first2, InputIterator2 last2, OutputIterator result);
404
405template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
406    OutputIterator
407    set_union(InputIterator1 first1, InputIterator1 last1,
408              InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
409
410template <class InputIterator1, class InputIterator2, class OutputIterator>
411    OutputIterator
412    set_intersection(InputIterator1 first1, InputIterator1 last1,
413                     InputIterator2 first2, InputIterator2 last2, OutputIterator result);
414
415template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
416    OutputIterator
417    set_intersection(InputIterator1 first1, InputIterator1 last1,
418                     InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
419
420template <class InputIterator1, class InputIterator2, class OutputIterator>
421    OutputIterator
422    set_difference(InputIterator1 first1, InputIterator1 last1,
423                   InputIterator2 first2, InputIterator2 last2, OutputIterator result);
424
425template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
426    OutputIterator
427    set_difference(InputIterator1 first1, InputIterator1 last1,
428                   InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
429
430template <class InputIterator1, class InputIterator2, class OutputIterator>
431    OutputIterator
432    set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
433                             InputIterator2 first2, InputIterator2 last2, OutputIterator result);
434
435template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
436    OutputIterator
437    set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
438                             InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
439
440template <class RandomAccessIterator>
441    void
442    push_heap(RandomAccessIterator first, RandomAccessIterator last);
443
444template <class RandomAccessIterator, class Compare>
445    void
446    push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
447
448template <class RandomAccessIterator>
449    void
450    pop_heap(RandomAccessIterator first, RandomAccessIterator last);
451
452template <class RandomAccessIterator, class Compare>
453    void
454    pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
455
456template <class RandomAccessIterator>
457    void
458    make_heap(RandomAccessIterator first, RandomAccessIterator last);
459
460template <class RandomAccessIterator, class Compare>
461    void
462    make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
463
464template <class RandomAccessIterator>
465    void
466    sort_heap(RandomAccessIterator first, RandomAccessIterator last);
467
468template <class RandomAccessIterator, class Compare>
469    void
470    sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
471
472template <class RandomAccessIterator>
473    bool
474    is_heap(RandomAccessIterator first, RandomAccessiterator last);
475
476template <class RandomAccessIterator, class Compare>
477    bool
478    is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
479
480template <class RandomAccessIterator>
481    RandomAccessIterator
482    is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
483
484template <class RandomAccessIterator, class Compare>
485    RandomAccessIterator
486    is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
487
488template <class ForwardIterator>
489    ForwardIterator
490    min_element(ForwardIterator first, ForwardIterator last);
491
492template <class ForwardIterator, class Compare>
493    ForwardIterator
494    min_element(ForwardIterator first, ForwardIterator last, Compare comp);
495
496template <class T>
497    const T&
498    min(const T& a, const T& b);
499
500template <class T, class Compare>
501    const T&
502    min(const T& a, const T& b, Compare comp);
503
504template<class T>
505    T
506    min(initializer_list<T> t);
507
508template<class T, class Compare>
509    T
510    min(initializer_list<T> t, Compare comp);
511
512template <class ForwardIterator>
513    ForwardIterator
514    max_element(ForwardIterator first, ForwardIterator last);
515
516template <class ForwardIterator, class Compare>
517    ForwardIterator
518    max_element(ForwardIterator first, ForwardIterator last, Compare comp);
519
520template <class T>
521    const T&
522    max(const T& a, const T& b);
523
524template <class T, class Compare>
525    const T&
526    max(const T& a, const T& b, Compare comp);
527
528template<class T>
529    T
530    max(initializer_list<T> t);
531
532template<class T, class Compare>
533    T
534    max(initializer_list<T> t, Compare comp);
535
536template<class ForwardIterator>
537    pair<ForwardIterator, ForwardIterator>
538    minmax_element(ForwardIterator first, ForwardIterator last);
539
540template<class ForwardIterator, class Compare>
541    pair<ForwardIterator, ForwardIterator>
542    minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
543
544template<class T>
545    pair<const T&, const T&>
546    minmax(const T& a, const T& b);
547
548template<class T, class Compare>
549    pair<const T&, const T&>
550    minmax(const T& a, const T& b, Compare comp);
551
552template<class T>
553    pair<T, T>
554    minmax(initializer_list<T> t);
555
556template<class T, class Compare>
557    pair<T, T>
558    minmax(initializer_list<T> t, Compare comp);
559
560template <class InputIterator1, class InputIterator2>
561    bool
562    lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
563
564template <class InputIterator1, class InputIterator2, class Compare>
565    bool
566    lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
567                            InputIterator2 first2, InputIterator2 last2, Compare comp);
568
569template <class BidirectionalIterator>
570    bool
571    next_permutation(BidirectionalIterator first, BidirectionalIterator last);
572
573template <class BidirectionalIterator, class Compare>
574    bool
575    next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
576
577template <class BidirectionalIterator>
578    bool
579    prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
580
581template <class BidirectionalIterator, class Compare>
582    bool
583    prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
584
585}  // std
586
587*/
588
589#include <__config>
590#include <initializer_list>
591#include <type_traits>
592#include <cstring>
593#include <utility>
594#include <memory>
595#include <iterator>
596#ifdef _LIBCPP_DEBUG
597#include <cassert>
598#endif
599#include <cstdlib>
600
601#pragma GCC system_header
602
603_LIBCPP_BEGIN_NAMESPACE_STD
604
605template <class _T1, class _T2 = _T1>
606struct __equal_to
607{
608    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
609    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;}
610    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;}
611    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;}
612};
613
614template <class _T1>
615struct __equal_to<_T1, _T1>
616{
617    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
618};
619
620template <class _T1>
621struct __equal_to<const _T1, _T1>
622{
623    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
624};
625
626template <class _T1>
627struct __equal_to<_T1, const _T1>
628{
629    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
630};
631
632template <class _T1, class _T2 = _T1>
633struct __less
634{
635    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
636    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;}
637    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;}
638    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;}
639};
640
641template <class _T1>
642struct __less<_T1, _T1>
643{
644    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
645};
646
647template <class _T1>
648struct __less<const _T1, _T1>
649{
650    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
651};
652
653template <class _T1>
654struct __less<_T1, const _T1>
655{
656    _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
657};
658
659template <class _Predicate>
660class __negate
661{
662private:
663    _Predicate __p_;
664public:
665    _LIBCPP_INLINE_VISIBILITY __negate() {}
666
667    _LIBCPP_INLINE_VISIBILITY
668    explicit __negate(_Predicate __p) : __p_(__p) {}
669
670    template <class _T1>
671    _LIBCPP_INLINE_VISIBILITY
672    bool operator()(const _T1& __x) {return !__p_(__x);}
673
674    template <class _T1, class _T2>
675    _LIBCPP_INLINE_VISIBILITY
676    bool operator()(const _T1& __x, const _T2& __y) {return !__p_(__x, __y);}
677};
678
679#ifdef _LIBCPP_DEBUG
680
681template <class _Compare>
682struct __debug_less
683{
684    _Compare __comp_;
685    __debug_less(_Compare& __c) : __comp_(__c) {}
686    template <class _Tp, class _Up>
687    bool operator()(const _Tp& __x, const _Up& __y)
688    {
689        bool __r = __comp_(__x, __y);
690        if (__r)
691            assert(!__comp_(__y, __x));
692        return __r;
693    }
694};
695
696#endif  // _LIBCPP_DEBUG
697
698// Precondition:  __x != 0
699inline _LIBCPP_INLINE_VISIBILITY unsigned           __ctz(unsigned           __x) {return __builtin_ctz  (__x);}
700inline _LIBCPP_INLINE_VISIBILITY unsigned      long __ctz(unsigned      long __x) {return __builtin_ctzl (__x);}
701inline _LIBCPP_INLINE_VISIBILITY unsigned long long __ctz(unsigned long long __x) {return __builtin_ctzll(__x);}
702
703// Precondition:  __x != 0
704inline _LIBCPP_INLINE_VISIBILITY unsigned           __clz(unsigned           __x) {return __builtin_clz  (__x);}
705inline _LIBCPP_INLINE_VISIBILITY unsigned      long __clz(unsigned      long __x) {return __builtin_clzl (__x);}
706inline _LIBCPP_INLINE_VISIBILITY unsigned long long __clz(unsigned long long __x) {return __builtin_clzll(__x);}
707
708inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned           __x) {return __builtin_popcount  (__x);}
709inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned      long __x) {return __builtin_popcountl (__x);}
710inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long long __x) {return __builtin_popcountll(__x);}
711
712// all_of
713
714template <class _InputIterator, class _Predicate>
715inline _LIBCPP_INLINE_VISIBILITY
716bool
717all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
718{
719    for (; __first != __last; ++__first)
720        if (!__pred(*__first))
721            return false;
722    return true;
723}
724
725// any_of
726
727template <class _InputIterator, class _Predicate>
728inline _LIBCPP_INLINE_VISIBILITY
729bool
730any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
731{
732    for (; __first != __last; ++__first)
733        if (__pred(*__first))
734            return true;
735    return false;
736}
737
738// none_of
739
740template <class _InputIterator, class _Predicate>
741inline _LIBCPP_INLINE_VISIBILITY
742bool
743none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
744{
745    for (; __first != __last; ++__first)
746        if (__pred(*__first))
747            return false;
748    return true;
749}
750
751// for_each
752
753template <class _InputIterator, class _Function>
754inline _LIBCPP_INLINE_VISIBILITY
755_Function
756for_each(_InputIterator __first, _InputIterator __last, _Function __f)
757{
758    for (; __first != __last; ++__first)
759        __f(*__first);
760    return _STD::move(__f);
761}
762
763// find
764
765template <class _InputIterator, class _Tp>
766inline _LIBCPP_INLINE_VISIBILITY
767_InputIterator
768find(_InputIterator __first, _InputIterator __last, const _Tp& __value)
769{
770    for (; __first != __last; ++__first)
771        if (*__first == __value)
772            break;
773    return __first;
774}
775
776// find_if
777
778template <class _InputIterator, class _Predicate>
779inline _LIBCPP_INLINE_VISIBILITY
780_InputIterator
781find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
782{
783    for (; __first != __last; ++__first)
784        if (__pred(*__first))
785            break;
786    return __first;
787}
788
789// find_if_not
790
791template<class _InputIterator, class _Predicate>
792inline _LIBCPP_INLINE_VISIBILITY
793_InputIterator
794find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
795{
796    for (; __first != __last; ++__first)
797        if (!__pred(*__first))
798            break;
799    return __first;
800}
801
802// find_end
803
804template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
805_ForwardIterator1
806__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
807           _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
808           forward_iterator_tag, forward_iterator_tag)
809{
810    // modeled after search algorithm
811    _ForwardIterator1 __r = __last1;  // __last1 is the "default" answer
812    if (__first2 == __last2)
813        return __r;
814    while (true)
815    {
816        while (true)
817        {
818            if (__first1 == __last1)         // if source exhausted return last correct answer
819                return __r;                  //    (or __last1 if never found)
820            if (__pred(*__first1, *__first2))
821                break;
822            ++__first1;
823        }
824        // *__first1 matches *__first2, now match elements after here
825        _ForwardIterator1 __m1 = __first1;
826        _ForwardIterator2 __m2 = __first2;
827        while (true)
828        {
829            if (++__m2 == __last2)
830            {                         // Pattern exhaused, record answer and search for another one
831                __r = __first1;
832                ++__first1;
833                break;
834            }
835            if (++__m1 == __last1)     // Source exhausted, return last answer
836                return __r;
837            if (!__pred(*__m1, *__m2))  // mismatch, restart with a new __first
838            {
839                ++__first1;
840                break;
841            }  // else there is a match, check next elements
842        }
843    }
844}
845
846template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2>
847_BidirectionalIterator1
848__find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,
849           _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred,
850           bidirectional_iterator_tag, bidirectional_iterator_tag)
851{
852    // modeled after search algorithm (in reverse)
853    if (__first2 == __last2)
854        return __last1;  // Everything matches an empty sequence
855    _BidirectionalIterator1 __l1 = __last1;
856    _BidirectionalIterator2 __l2 = __last2;
857    --__l2;
858    while (true)
859    {
860        // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks
861        while (true)
862        {
863            if (__first1 == __l1)  // return __last1 if no element matches *__first2
864                return __last1;
865            if (__pred(*--__l1, *__l2))
866                break;
867        }
868        // *__l1 matches *__l2, now match elements before here
869        _BidirectionalIterator1 __m1 = __l1;
870        _BidirectionalIterator2 __m2 = __l2;
871        while (true)
872        {
873            if (__m2 == __first2)  // If pattern exhausted, __m1 is the answer (works for 1 element pattern)
874                return __m1;
875            if (__m1 == __first1)  // Otherwise if source exhaused, pattern not found
876                return __last1;
877            if (!__pred(*--__m1, *--__m2))  // if there is a mismatch, restart with a new __l1
878            {
879                break;
880            }  // else there is a match, check next elements
881        }
882    }
883}
884
885template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
886_RandomAccessIterator1
887__find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
888           _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
889           random_access_iterator_tag, random_access_iterator_tag)
890{
891    // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
892    typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;
893    if (__len2 == 0)
894        return __last1;
895    typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;
896    if (__len1 < __len2)
897        return __last1;
898    const _RandomAccessIterator1 __s = __first1 + (__len2 - 1);  // End of pattern match can't go before here
899    _RandomAccessIterator1 __l1 = __last1;
900    _RandomAccessIterator2 __l2 = __last2;
901    --__l2;
902    while (true)
903    {
904        while (true)
905        {
906            if (__s == __l1)
907                return __last1;
908            if (__pred(*--__l1, *__l2))
909                break;
910        }
911        _RandomAccessIterator1 __m1 = __l1;
912        _RandomAccessIterator2 __m2 = __l2;
913        while (true)
914        {
915            if (__m2 == __first2)
916                return __m1;
917                                 // no need to check range on __m1 because __s guarantees we have enough source
918            if (!__pred(*--__m1, *--__m2))
919            {
920                break;
921            }
922        }
923    }
924}
925
926template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
927inline _LIBCPP_INLINE_VISIBILITY
928_ForwardIterator1
929find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
930         _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
931{
932    return _STD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type>
933                         (__first1, __last1, __first2, __last2, __pred,
934                          typename iterator_traits<_ForwardIterator1>::iterator_category(),
935                          typename iterator_traits<_ForwardIterator2>::iterator_category());
936}
937
938template <class _ForwardIterator1, class _ForwardIterator2>
939inline _LIBCPP_INLINE_VISIBILITY
940_ForwardIterator1
941find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
942         _ForwardIterator2 __first2, _ForwardIterator2 __last2)
943{
944    typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
945    typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
946    return _STD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
947}
948
949// find_first_of
950
951template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
952_ForwardIterator1
953find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
954              _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
955{
956    for (; __first1 != __last1; ++__first1)
957        for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
958            if (__pred(*__first1, *__j))
959                return __first1;
960    return __last1;
961}
962
963template <class _ForwardIterator1, class _ForwardIterator2>
964inline _LIBCPP_INLINE_VISIBILITY
965_ForwardIterator1
966find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
967              _ForwardIterator2 __first2, _ForwardIterator2 __last2)
968{
969    typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
970    typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
971    return _STD::find_first_of(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
972}
973
974// adjacent_find
975
976template <class _ForwardIterator, class _BinaryPredicate>
977inline _LIBCPP_INLINE_VISIBILITY
978_ForwardIterator
979adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
980{
981    if (__first != __last)
982    {
983        _ForwardIterator __i = __first;
984        while (++__i != __last)
985        {
986            if (__pred(*__first, *__i))
987                return __first;
988            __first = __i;
989        }
990    }
991    return __last;
992}
993
994template <class _ForwardIterator>
995inline _LIBCPP_INLINE_VISIBILITY
996_ForwardIterator
997adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
998{
999    typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1000    return _STD::adjacent_find(__first, __last, __equal_to<__v>());
1001}
1002
1003// count
1004
1005template <class _InputIterator, class _Tp>
1006inline _LIBCPP_INLINE_VISIBILITY
1007typename iterator_traits<_InputIterator>::difference_type
1008count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
1009{
1010    typename iterator_traits<_InputIterator>::difference_type __r(0);
1011    for (; __first != __last; ++__first)
1012        if (*__first == __value)
1013            ++__r;
1014    return __r;
1015}
1016
1017// count_if
1018
1019template <class _InputIterator, class _Predicate>
1020inline _LIBCPP_INLINE_VISIBILITY
1021typename iterator_traits<_InputIterator>::difference_type
1022count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
1023{
1024    typename iterator_traits<_InputIterator>::difference_type __r(0);
1025    for (; __first != __last; ++__first)
1026        if (__pred(*__first))
1027            ++__r;
1028    return __r;
1029}
1030
1031// mismatch
1032
1033template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1034inline _LIBCPP_INLINE_VISIBILITY
1035pair<_InputIterator1, _InputIterator2>
1036mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1037         _InputIterator2 __first2, _BinaryPredicate __pred)
1038{
1039    for (; __first1 != __last1; ++__first1, ++__first2)
1040        if (!__pred(*__first1, *__first2))
1041            break;
1042    return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1043}
1044
1045template <class _InputIterator1, class _InputIterator2>
1046inline _LIBCPP_INLINE_VISIBILITY
1047pair<_InputIterator1, _InputIterator2>
1048mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1049{
1050    typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1051    typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1052    return _STD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1053}
1054
1055// equal
1056
1057template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1058inline _LIBCPP_INLINE_VISIBILITY
1059bool
1060equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred)
1061{
1062    for (; __first1 != __last1; ++__first1, ++__first2)
1063        if (!__pred(*__first1, *__first2))
1064            return false;
1065    return true;
1066}
1067
1068template <class _InputIterator1, class _InputIterator2>
1069inline _LIBCPP_INLINE_VISIBILITY
1070bool
1071equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1072{
1073    typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1074    typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1075    return _STD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1076}
1077
1078// is_permutation
1079
1080template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1081bool
1082is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1083               _ForwardIterator2 __first2, _BinaryPredicate __pred)
1084{
1085    // shorten sequences as much as possible by lopping of any equal parts
1086    for (; __first1 != __last1; ++__first1, ++__first2)
1087        if (!__pred(*__first1, *__first2))
1088            goto __not_done;
1089    return true;
1090__not_done:
1091    // __first1 != __last1 && *__first1 != *__first2
1092    typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1093    _D1 __l1 = _STD::distance(__first1, __last1);
1094    if (__l1 == _D1(1))
1095        return false;
1096    _ForwardIterator2 __last2 = _STD::next(__first2, __l1);
1097    // For each element in [f1, l1) see if there are the same number of
1098    //    equal elements in [f2, l2)
1099    for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
1100    {
1101        // Have we already counted the number of *__i in [f1, l1)?
1102        for (_ForwardIterator1 __j = __first1; __j != __i; ++__j)
1103            if (__pred(*__j, *__i))
1104                goto __next_iter;
1105        {
1106            // Count number of *__i in [f2, l2)
1107            _D1 __c2 = 0;
1108            for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1109                if (__pred(*__i, *__j))
1110                    ++__c2;
1111            if (__c2 == 0)
1112                return false;
1113            // Count number of *__i in [__i, l1) (we can start with 1)
1114            _D1 __c1 = 1;
1115            for (_ForwardIterator1 __j = _STD::next(__i); __j != __last1; ++__j)
1116                if (__pred(*__i, *__j))
1117                    ++__c1;
1118            if (__c1 != __c2)
1119                return false;
1120        }
1121__next_iter:;
1122    }
1123    return true;
1124}
1125
1126template<class _ForwardIterator1, class _ForwardIterator2>
1127inline _LIBCPP_INLINE_VISIBILITY
1128bool
1129is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1130               _ForwardIterator2 __first2)
1131{
1132    typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1133    typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1134    return _STD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1135}
1136
1137// search
1138
1139template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
1140_ForwardIterator1
1141__search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1142         _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
1143         forward_iterator_tag, forward_iterator_tag)
1144{
1145    if (__first2 == __last2)
1146        return __first1;  // Everything matches an empty sequence
1147    while (true)
1148    {
1149        // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks
1150        while (true)
1151        {
1152            if (__first1 == __last1)  // return __last1 if no element matches *__first2
1153                return __last1;
1154            if (__pred(*__first1, *__first2))
1155                break;
1156            ++__first1;
1157        }
1158        // *__first1 matches *__first2, now match elements after here
1159        _ForwardIterator1 __m1 = __first1;
1160        _ForwardIterator2 __m2 = __first2;
1161        while (true)
1162        {
1163            if (++__m2 == __last2)  // If pattern exhausted, __first1 is the answer (works for 1 element pattern)
1164                return __first1;
1165            if (++__m1 == __last1)  // Otherwise if source exhaused, pattern not found
1166                return __last1;
1167            if (!__pred(*__m1, *__m2))  // if there is a mismatch, restart with a new __first1
1168            {
1169                ++__first1;
1170                break;
1171            }  // else there is a match, check next elements
1172        }
1173    }
1174}
1175
1176template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1177_RandomAccessIterator1
1178__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1179           _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1180           random_access_iterator_tag, random_access_iterator_tag)
1181{
1182    typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _D1;
1183    typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _D2;
1184    // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
1185    _D2 __len2 = __last2 - __first2;
1186    if (__len2 == 0)
1187        return __first1;
1188    _D1 __len1 = __last1 - __first1;
1189    if (__len1 < __len2)
1190        return __last1;
1191    const _RandomAccessIterator1 __s = __last1 - (__len2 - 1);  // Start of pattern match can't go beyond here
1192    while (true)
1193    {
1194#if !_LIBCPP_UNROLL_LOOPS
1195        while (true)
1196        {
1197            if (__first1 == __s)
1198                return __last1;
1199            if (__pred(*__first1, *__first2))
1200                break;
1201            ++__first1;
1202        }
1203#else  // !_LIBCPP_UNROLL_LOOPS
1204        for (_D1 __loop_unroll = (__s - __first1) / 4; __loop_unroll > 0; --__loop_unroll)
1205        {
1206            if (__pred(*__first1, *__first2))
1207                goto __phase2;
1208            if (__pred(*++__first1, *__first2))
1209                goto __phase2;
1210            if (__pred(*++__first1, *__first2))
1211                goto __phase2;
1212            if (__pred(*++__first1, *__first2))
1213                goto __phase2;
1214            ++__first1;
1215        }
1216        switch (__s - __first1)
1217        {
1218        case 3:
1219            if (__pred(*__first1, *__first2))
1220                break;
1221            ++__first1;
1222        case 2:
1223            if (__pred(*__first1, *__first2))
1224                break;
1225            ++__first1;
1226        case 1:
1227            if (__pred(*__first1, *__first2))
1228                break;
1229        case 0:
1230            return __last1;
1231        }
1232    __phase2:
1233#endif  // !_LIBCPP_UNROLL_LOOPS
1234        _RandomAccessIterator1 __m1 = __first1;
1235        _RandomAccessIterator2 __m2 = __first2;
1236#if !_LIBCPP_UNROLL_LOOPS
1237         while (true)
1238         {
1239             if (++__m2 == __last2)
1240                 return __first1;
1241             ++__m1;          // no need to check range on __m1 because __s guarantees we have enough source
1242             if (!__pred(*__m1, *__m2))
1243             {
1244                 ++__first1;
1245                 break;
1246             }
1247         }
1248#else  // !_LIBCPP_UNROLL_LOOPS
1249        ++__m2;
1250        ++__m1;
1251        for (_D2 __loop_unroll = (__last2 - __m2) / 4; __loop_unroll > 0; --__loop_unroll)
1252        {
1253            if (!__pred(*__m1, *__m2))
1254                goto __continue;
1255            if (!__pred(*++__m1, *++__m2))
1256                goto __continue;
1257            if (!__pred(*++__m1, *++__m2))
1258                goto __continue;
1259            if (!__pred(*++__m1, *++__m2))
1260                goto __continue;
1261            ++__m1;
1262            ++__m2;
1263        }
1264        switch (__last2 - __m2)
1265        {
1266        case 3:
1267            if (!__pred(*__m1, *__m2))
1268                break;
1269            ++__m1;
1270            ++__m2;
1271        case 2:
1272            if (!__pred(*__m1, *__m2))
1273                break;
1274            ++__m1;
1275            ++__m2;
1276        case 1:
1277            if (!__pred(*__m1, *__m2))
1278                break;
1279        case 0:
1280            return __first1;
1281        }
1282    __continue:
1283        ++__first1;
1284#endif  // !_LIBCPP_UNROLL_LOOPS
1285    }
1286}
1287
1288template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1289inline _LIBCPP_INLINE_VISIBILITY
1290_ForwardIterator1
1291search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1292       _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1293{
1294    return _STD::__search<typename add_lvalue_reference<_BinaryPredicate>::type>
1295                         (__first1, __last1, __first2, __last2, __pred,
1296                          typename std::iterator_traits<_ForwardIterator1>::iterator_category(),
1297                          typename std::iterator_traits<_ForwardIterator2>::iterator_category());
1298}
1299
1300template <class _ForwardIterator1, class _ForwardIterator2>
1301inline _LIBCPP_INLINE_VISIBILITY
1302_ForwardIterator1
1303search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1304       _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1305{
1306    typedef typename std::iterator_traits<_ForwardIterator1>::value_type __v1;
1307    typedef typename std::iterator_traits<_ForwardIterator2>::value_type __v2;
1308    return _STD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1309}
1310
1311// search_n
1312
1313template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp>
1314_ForwardIterator
1315__search_n(_ForwardIterator __first, _ForwardIterator __last,
1316           _Size __count, const _Tp& __value, _BinaryPredicate __pred, forward_iterator_tag)
1317{
1318    if (__count <= 0)
1319        return __first;
1320    while (true)
1321    {
1322        // Find first element in sequence that matchs __value, with a mininum of loop checks
1323        while (true)
1324        {
1325            if (__first == __last)  // return __last if no element matches __value
1326                return __last;
1327            if (__pred(*__first, __value))
1328                break;
1329            ++__first;
1330        }
1331        // *__first matches __value, now match elements after here
1332        _ForwardIterator __m = __first;
1333        _Size __c(0);
1334        while (true)
1335        {
1336            if (++__c == __count)  // If pattern exhausted, __first is the answer (works for 1 element pattern)
1337                return __first;
1338            if (++__m == __last)  // Otherwise if source exhaused, pattern not found
1339                return __last;
1340            if (!__pred(*__m, __value))  // if there is a mismatch, restart with a new __first
1341            {
1342                __first = __m;
1343                ++__first;
1344                break;
1345            }  // else there is a match, check next elements
1346        }
1347    }
1348}
1349
1350template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp>
1351_RandomAccessIterator
1352__search_n(_RandomAccessIterator __first, _RandomAccessIterator __last,
1353           _Size __count, const _Tp& __value, _BinaryPredicate __pred, random_access_iterator_tag)
1354{
1355    if (__count <= 0)
1356        return __first;
1357    _Size __len = static_cast<_Size>(__last - __first);
1358    if (__len < __count)
1359        return __last;
1360    const _RandomAccessIterator __s = __last - (__count - 1);  // Start of pattern match can't go beyond here
1361    while (true)
1362    {
1363        // Find first element in sequence that matchs __value, with a mininum of loop checks
1364        while (true)
1365        {
1366            if (__first == __s)  // return __last if no element matches __value
1367                return __last;
1368            if (__pred(*__first, __value))
1369                break;
1370            ++__first;
1371        }
1372        // *__first matches __value, now match elements after here
1373        _RandomAccessIterator __m = __first;
1374        _Size __c(0);
1375        while (true)
1376        {
1377            if (++__c == __count)  // If pattern exhausted, __first is the answer (works for 1 element pattern)
1378                return __first;
1379             ++__m;          // no need to check range on __m because __s guarantees we have enough source
1380            if (!__pred(*__m, __value))  // if there is a mismatch, restart with a new __first
1381            {
1382                __first = __m;
1383                ++__first;
1384                break;
1385            }  // else there is a match, check next elements
1386        }
1387    }
1388}
1389
1390template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
1391inline _LIBCPP_INLINE_VISIBILITY
1392_ForwardIterator
1393search_n(_ForwardIterator __first, _ForwardIterator __last,
1394         _Size __count, const _Tp& __value, _BinaryPredicate __pred)
1395{
1396    return _STD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>
1397           (__first, __last, __count, __value, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
1398}
1399
1400template <class _ForwardIterator, class _Size, class _Tp>
1401inline _LIBCPP_INLINE_VISIBILITY
1402_ForwardIterator
1403search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value)
1404{
1405    typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1406    return _STD::search_n(__first, __last, __count, __value, __equal_to<__v, _Tp>());
1407}
1408
1409// copy
1410
1411template <class _Iter>
1412struct __libcpp_is_trivial_iterator
1413{
1414    static const bool value = is_pointer<_Iter>::value;
1415};
1416
1417template <class _Iter>
1418struct __libcpp_is_trivial_iterator<move_iterator<_Iter> >
1419{
1420    static const bool value = is_pointer<_Iter>::value;
1421};
1422
1423template <class _Iter>
1424struct __libcpp_is_trivial_iterator<__wrap_iter<_Iter> >
1425{
1426    static const bool value = is_pointer<_Iter>::value;
1427};
1428
1429template <class _Iter>
1430inline _LIBCPP_INLINE_VISIBILITY
1431_Iter
1432__unwrap_iter(_Iter __i)
1433{
1434    return __i;
1435}
1436
1437template <class _Tp>
1438inline _LIBCPP_INLINE_VISIBILITY
1439typename enable_if
1440<
1441    is_trivially_copy_assignable<_Tp>::value,
1442    _Tp*
1443>::type
1444__unwrap_iter(move_iterator<_Tp*> __i)
1445{
1446    return __i.base();
1447}
1448
1449template <class _Tp>
1450inline _LIBCPP_INLINE_VISIBILITY
1451typename enable_if
1452<
1453    is_trivially_copy_assignable<_Tp>::value,
1454    _Tp*
1455>::type
1456__unwrap_iter(__wrap_iter<_Tp*> __i)
1457{
1458    return __i.base();
1459}
1460
1461template <class _InputIterator, class _OutputIterator>
1462inline _LIBCPP_INLINE_VISIBILITY
1463_OutputIterator
1464__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1465{
1466    for (; __first != __last; ++__first, ++__result)
1467        *__result = *__first;
1468    return __result;
1469}
1470
1471template <class _Tp, class _Up>
1472inline _LIBCPP_INLINE_VISIBILITY
1473typename enable_if
1474<
1475    is_same<typename remove_const<_Tp>::type, _Up>::value &&
1476    is_trivially_copy_assignable<_Up>::value,
1477    _Up*
1478>::type
1479__copy(_Tp* __first, _Tp* __last, _Up* __result)
1480{
1481    const size_t __n = static_cast<size_t>(__last - __first);
1482    _STD::memmove(__result, __first, __n * sizeof(_Up));
1483    return __result + __n;
1484}
1485
1486template <class _InputIterator, class _OutputIterator>
1487inline _LIBCPP_INLINE_VISIBILITY
1488_OutputIterator
1489copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1490{
1491    return _STD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1492}
1493
1494// copy_backward
1495
1496template <class _InputIterator, class _OutputIterator>
1497inline _LIBCPP_INLINE_VISIBILITY
1498_OutputIterator
1499__copy_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1500{
1501    while (__first != __last)
1502        *--__result = *--__last;
1503    return __result;
1504}
1505
1506template <class _Tp, class _Up>
1507inline _LIBCPP_INLINE_VISIBILITY
1508typename enable_if
1509<
1510    is_same<typename remove_const<_Tp>::type, _Up>::value &&
1511    is_trivially_copy_assignable<_Up>::value,
1512    _Up*
1513>::type
1514__copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
1515{
1516    const size_t __n = static_cast<size_t>(__last - __first);
1517    __result -= __n;
1518    _STD::memmove(__result, __first, __n * sizeof(_Up));
1519    return __result;
1520}
1521
1522template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1523inline _LIBCPP_INLINE_VISIBILITY
1524_BidirectionalIterator2
1525copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1526              _BidirectionalIterator2 __result)
1527{
1528    return _STD::__copy_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1529}
1530
1531// copy_if
1532
1533template<class _InputIterator, class _OutputIterator, class _Predicate>
1534inline _LIBCPP_INLINE_VISIBILITY
1535_OutputIterator
1536copy_if(_InputIterator __first, _InputIterator __last,
1537        _OutputIterator __result, _Predicate __pred)
1538{
1539    for (; __first != __last; ++__first)
1540    {
1541        if (__pred(*__first))
1542        {
1543            *__result = *__first;
1544            ++__result;
1545        }
1546    }
1547    return __result;
1548}
1549
1550// copy_n
1551
1552template<class _InputIterator, class _Size, class _OutputIterator>
1553inline _LIBCPP_INLINE_VISIBILITY
1554typename enable_if
1555<
1556    __is_input_iterator<_InputIterator>::value &&
1557   !__is_random_access_iterator<_InputIterator>::value,
1558    _OutputIterator
1559>::type
1560copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1561{
1562    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    is_trivially_copy_assignable<_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    is_trivially_copy_assignable<_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                                              is_trivially_copy_assignable<_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                               is_trivially_copy_assignable
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        {
2690            difference_type __i = __uid(__g, _P(0, __d));
2691            if (__i != difference_type(0))
2692                swap(*__first, *(__first + __i));
2693        }
2694    }
2695}
2696
2697template <class _RandomAccessIterator, class _RandomNumberGenerator>
2698void
2699random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
2700#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2701               _RandomNumberGenerator&& __rand)
2702#else
2703               _RandomNumberGenerator& __rand)
2704#endif
2705{
2706    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2707    difference_type __d = __last - __first;
2708    if (__d > 1)
2709    {
2710        for (--__last; __first < __last; ++__first, --__d)
2711        {
2712            difference_type __i = __rand(__d);
2713            swap(*__first, *(__first + __i));
2714        }
2715    }
2716}
2717
2718template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
2719    void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
2720#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2721                 _UniformRandomNumberGenerator&& __g)
2722#else
2723                 _UniformRandomNumberGenerator& __g)
2724#endif
2725{
2726    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2727    typedef uniform_int_distribution<ptrdiff_t> _D;
2728    typedef typename _D::param_type _P;
2729    difference_type __d = __last - __first;
2730    if (__d > 1)
2731    {
2732        _D __uid;
2733        for (--__last, --__d; __first < __last; ++__first, --__d)
2734        {
2735            difference_type __i = __uid(__g, _P(0, __d));
2736            if (__i != difference_type(0))
2737                swap(*__first, *(__first + __i));
2738        }
2739    }
2740}
2741
2742template <class _InputIterator, class _Predicate>
2743bool
2744is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2745{
2746    for (; __first != __last; ++__first)
2747        if (!__pred(*__first))
2748            break;
2749    for (; __first != __last; ++__first)
2750        if (__pred(*__first))
2751            return false;
2752    return true;
2753}
2754
2755// partition
2756
2757template <class _Predicate, class _ForwardIterator>
2758_ForwardIterator
2759__partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
2760{
2761    while (true)
2762    {
2763        if (__first == __last)
2764            return __first;
2765        if (!__pred(*__first))
2766            break;
2767        ++__first;
2768    }
2769    for (_ForwardIterator __p = __first; ++__p != __last;)
2770    {
2771        if (__pred(*__p))
2772        {
2773            swap(*__first, *__p);
2774            ++__first;
2775        }
2776    }
2777    return __first;
2778}
2779
2780template <class _Predicate, class _BidirectionalIterator>
2781_BidirectionalIterator
2782__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
2783            bidirectional_iterator_tag)
2784{
2785    while (true)
2786    {
2787        while (true)
2788        {
2789            if (__first == __last)
2790                return __first;
2791            if (!__pred(*__first))
2792                break;
2793            ++__first;
2794        }
2795        do
2796        {
2797            if (__first == --__last)
2798                return __first;
2799        } while (!__pred(*__last));
2800        swap(*__first, *__last);
2801        ++__first;
2802    }
2803}
2804
2805template <class _ForwardIterator, class _Predicate>
2806inline _LIBCPP_INLINE_VISIBILITY
2807_ForwardIterator
2808partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2809{
2810    return _STD::__partition<typename add_lvalue_reference<_Predicate>::type>
2811                            (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
2812}
2813
2814// partition_copy
2815
2816template <class _InputIterator, class _OutputIterator1,
2817          class _OutputIterator2, class _Predicate>
2818pair<_OutputIterator1, _OutputIterator2>
2819partition_copy(_InputIterator __first, _InputIterator __last,
2820               _OutputIterator1 __out_true, _OutputIterator2 __out_false,
2821               _Predicate __pred)
2822{
2823    for (; __first != __last; ++__first)
2824    {
2825        if (__pred(*__first))
2826        {
2827            *__out_true = *__first;
2828            ++__out_true;
2829        }
2830        else
2831        {
2832            *__out_false = *__first;
2833            ++__out_false;
2834        }
2835    }
2836    return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
2837}
2838
2839// partition_point
2840
2841template<class _ForwardIterator, class _Predicate>
2842_ForwardIterator
2843partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2844{
2845    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
2846    difference_type __len = _STD::distance(__first, __last);
2847    while (__len != 0)
2848    {
2849        difference_type __l2 = __len / 2;
2850        _ForwardIterator __m = __first;
2851        _STD::advance(__m, __l2);
2852        if (__pred(*__m))
2853        {
2854            __first = ++__m;
2855            __len -= __l2 + 1;
2856        }
2857        else
2858            __len = __l2;
2859    }
2860    return __first;
2861}
2862
2863// stable_partition
2864
2865template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
2866_ForwardIterator
2867__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
2868                   _Distance __len, _Pair __p, forward_iterator_tag __fit)
2869{
2870    // *__first is known to be false
2871    // __len >= 1
2872    if (__len == 1)
2873        return __first;
2874    if (__len == 2)
2875    {
2876        _ForwardIterator __m = __first;
2877        if (__pred(*++__m))
2878        {
2879            swap(*__first, *__m);
2880            return __m;
2881        }
2882        return __first;
2883    }
2884    if (__len <= __p.second)
2885    {   // The buffer is big enough to use
2886        typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2887        __destruct_n __d(0);
2888        unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
2889        // Move the falses into the temporary buffer, and the trues to the front of the line
2890        // Update __first to always point to the end of the trues
2891        value_type* __t = __p.first;
2892        ::new(__t) value_type(_STD::move(*__first));
2893        __d.__incr((value_type*)0);
2894        ++__t;
2895        _ForwardIterator __i = __first;
2896        while (++__i != __last)
2897        {
2898            if (__pred(*__i))
2899            {
2900                *__first = _STD::move(*__i);
2901                ++__first;
2902            }
2903            else
2904            {
2905                ::new(__t) value_type(_STD::move(*__i));
2906                __d.__incr((value_type*)0);
2907                ++__t;
2908            }
2909        }
2910        // All trues now at start of range, all falses in buffer
2911        // Move falses back into range, but don't mess up __first which points to first false
2912        __i = __first;
2913        for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
2914            *__i = _STD::move(*__t2);
2915        // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
2916        return __first;
2917    }
2918    // Else not enough buffer, do in place
2919    // __len >= 3
2920    _ForwardIterator __m = __first;
2921    _Distance __len2 = __len / 2;  // __len2 >= 2
2922    _STD::advance(__m, __len2);
2923    // recurse on [__first, __m), *__first know to be false
2924    // F?????????????????
2925    // f       m         l
2926    typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
2927    _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
2928    // TTTFFFFF??????????
2929    // f  ff   m         l
2930    // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
2931    _ForwardIterator __m1 = __m;
2932    _ForwardIterator __second_false = __last;
2933    _Distance __len_half = __len - __len2;
2934    while (__pred(*__m1))
2935    {
2936        if (++__m1 == __last)
2937            goto __second_half_done;
2938        --__len_half;
2939    }
2940    // TTTFFFFFTTTF??????
2941    // f  ff   m  m1     l
2942    __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
2943__second_half_done:
2944    // TTTFFFFFTTTTTFFFFF
2945    // f  ff   m    sf   l
2946    return _STD::rotate(__first_false, __m, __second_false);
2947    // TTTTTTTTFFFFFFFFFF
2948    //         |
2949}
2950
2951struct __return_temporary_buffer
2952{
2953    template <class _Tp>
2954    _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_STD::return_temporary_buffer(__p);}
2955};
2956
2957template <class _Predicate, class _ForwardIterator>
2958_ForwardIterator
2959__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
2960                   forward_iterator_tag)
2961{
2962    const unsigned __alloc_limit = 3;  // might want to make this a function of trivial assignment
2963    // Either prove all true and return __first or point to first false
2964    while (true)
2965    {
2966        if (__first == __last)
2967            return __first;
2968        if (!__pred(*__first))
2969            break;
2970        ++__first;
2971    }
2972    // We now have a reduced range [__first, __last)
2973    // *__first is known to be false
2974    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
2975    typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2976    difference_type __len = _STD::distance(__first, __last);
2977    pair<value_type*, ptrdiff_t> __p(0, 0);
2978    unique_ptr<value_type, __return_temporary_buffer> __h;
2979    if (__len >= __alloc_limit)
2980    {
2981        __p = _STD::get_temporary_buffer<value_type>(__len);
2982        __h.reset(__p.first);
2983    }
2984    return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
2985                             (__first, __last, __pred, __len, __p, forward_iterator_tag());
2986}
2987
2988template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
2989_BidirectionalIterator
2990__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
2991                   _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
2992{
2993    // *__first is known to be false
2994    // *__last is known to be true
2995    // __len >= 2
2996    if (__len == 2)
2997    {
2998        swap(*__first, *__last);
2999        return __last;
3000    }
3001    if (__len == 3)
3002    {
3003        _BidirectionalIterator __m = __first;
3004        if (__pred(*++__m))
3005        {
3006            swap(*__first, *__m);
3007            swap(*__m, *__last);
3008            return __last;
3009        }
3010        swap(*__m, *__last);
3011        swap(*__first, *__m);
3012        return __m;
3013    }
3014    if (__len <= __p.second)
3015    {   // The buffer is big enough to use
3016        typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3017        __destruct_n __d(0);
3018        unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3019        // Move the falses into the temporary buffer, and the trues to the front of the line
3020        // Update __first to always point to the end of the trues
3021        value_type* __t = __p.first;
3022        ::new(__t) value_type(_STD::move(*__first));
3023        __d.__incr((value_type*)0);
3024        ++__t;
3025        _BidirectionalIterator __i = __first;
3026        while (++__i != __last)
3027        {
3028            if (__pred(*__i))
3029            {
3030                *__first = _STD::move(*__i);
3031                ++__first;
3032            }
3033            else
3034            {
3035                ::new(__t) value_type(_STD::move(*__i));
3036                __d.__incr((value_type*)0);
3037                ++__t;
3038            }
3039        }
3040        // move *__last, known to be true
3041        *__first = _STD::move(*__i);
3042        __i = ++__first;
3043        // All trues now at start of range, all falses in buffer
3044        // Move falses back into range, but don't mess up __first which points to first false
3045        for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3046            *__i = _STD::move(*__t2);
3047        // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3048        return __first;
3049    }
3050    // Else not enough buffer, do in place
3051    // __len >= 4
3052    _BidirectionalIterator __m = __first;
3053    _Distance __len2 = __len / 2;  // __len2 >= 2
3054    _STD::advance(__m, __len2);
3055    // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
3056    // F????????????????T
3057    // f       m        l
3058    _BidirectionalIterator __m1 = __m;
3059    _BidirectionalIterator __first_false = __first;
3060    _Distance __len_half = __len2;
3061    while (!__pred(*--__m1))
3062    {
3063        if (__m1 == __first)
3064            goto __first_half_done;
3065        --__len_half;
3066    }
3067    // F???TFFF?????????T
3068    // f   m1  m        l
3069    typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3070    __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3071__first_half_done:
3072    // TTTFFFFF?????????T
3073    // f  ff   m        l
3074    // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3075    __m1 = __m;
3076    _BidirectionalIterator __second_false = __last;
3077    ++__second_false;
3078    __len_half = __len - __len2;
3079    while (__pred(*__m1))
3080    {
3081        if (++__m1 == __last)
3082            goto __second_half_done;
3083        --__len_half;
3084    }
3085    // TTTFFFFFTTTF?????T
3086    // f  ff   m  m1    l
3087    __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
3088__second_half_done:
3089    // TTTFFFFFTTTTTFFFFF
3090    // f  ff   m    sf  l
3091    return _STD::rotate(__first_false, __m, __second_false);
3092    // TTTTTTTTFFFFFFFFFF
3093    //         |
3094}
3095
3096template <class _Predicate, class _BidirectionalIterator>
3097_BidirectionalIterator
3098__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3099                   bidirectional_iterator_tag)
3100{
3101    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3102    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3103    const difference_type __alloc_limit = 4;  // might want to make this a function of trivial assignment
3104    // Either prove all true and return __first or point to first false
3105    while (true)
3106    {
3107        if (__first == __last)
3108            return __first;
3109        if (!__pred(*__first))
3110            break;
3111        ++__first;
3112    }
3113    // __first points to first false, everything prior to __first is already set.
3114    // Either prove [__first, __last) is all false and return __first, or point __last to last true
3115    do
3116    {
3117        if (__first == --__last)
3118            return __first;
3119    } while (!__pred(*__last));
3120    // We now have a reduced range [__first, __last]
3121    // *__first is known to be false
3122    // *__last is known to be true
3123    // __len >= 2
3124    difference_type __len = _STD::distance(__first, __last) + 1;
3125    pair<value_type*, ptrdiff_t> __p(0, 0);
3126    unique_ptr<value_type, __return_temporary_buffer> __h;
3127    if (__len >= __alloc_limit)
3128    {
3129        __p = _STD::get_temporary_buffer<value_type>(__len);
3130        __h.reset(__p.first);
3131    }
3132    return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3133                             (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3134}
3135
3136template <class _ForwardIterator, class _Predicate>
3137inline _LIBCPP_INLINE_VISIBILITY
3138_ForwardIterator
3139stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3140{
3141    return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3142                             (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3143}
3144
3145// is_sorted_until
3146
3147template <class _ForwardIterator, class _Compare>
3148_ForwardIterator
3149is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3150{
3151    if (__first != __last)
3152    {
3153        _ForwardIterator __i = __first;
3154        while (++__i != __last)
3155        {
3156            if (__comp(*__i, *__first))
3157                return __i;
3158            __first = __i;
3159        }
3160    }
3161    return __last;
3162}
3163
3164template<class _ForwardIterator>
3165inline _LIBCPP_INLINE_VISIBILITY
3166_ForwardIterator
3167is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3168{
3169    return _STD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3170}
3171
3172// is_sorted
3173
3174template <class _ForwardIterator, class _Compare>
3175inline _LIBCPP_INLINE_VISIBILITY
3176bool
3177is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3178{
3179    return _STD::is_sorted_until(__first, __last, __comp) == __last;
3180}
3181
3182template<class _ForwardIterator>
3183inline _LIBCPP_INLINE_VISIBILITY
3184bool
3185is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3186{
3187    return _STD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3188}
3189
3190// sort
3191
3192// stable, 2-3 compares, 0-2 swaps
3193
3194template <class _Compare, class _ForwardIterator>
3195unsigned
3196__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
3197{
3198    unsigned __r = 0;
3199    if (!__c(*__y, *__x))          // if x <= y
3200    {
3201        if (!__c(*__z, *__y))      // if y <= z
3202            return __r;            // x <= y && y <= z
3203                                   // x <= y && y > z
3204        swap(*__y, *__z);          // x <= z && y < z
3205        __r = 1;
3206        if (__c(*__y, *__x))       // if x > y
3207        {
3208            swap(*__x, *__y);      // x < y && y <= z
3209            __r = 2;
3210        }
3211        return __r;                // x <= y && y < z
3212    }
3213    if (__c(*__z, *__y))           // x > y, if y > z
3214    {
3215        swap(*__x, *__z);          // x < y && y < z
3216        __r = 1;
3217        return __r;
3218    }
3219    swap(*__x, *__y);              // x > y && y <= z
3220    __r = 1;                       // x < y && x <= z
3221    if (__c(*__z, *__y))           // if y > z
3222    {
3223        swap(*__y, *__z);          // x <= y && y < z
3224        __r = 2;
3225    }
3226    return __r;
3227}                                  // x <= y && y <= z
3228
3229// stable, 3-6 compares, 0-5 swaps
3230
3231template <class _Compare, class _ForwardIterator>
3232unsigned
3233__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3234            _ForwardIterator __x4, _Compare __c)
3235{
3236    unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
3237    if (__c(*__x4, *__x3))
3238    {
3239        swap(*__x3, *__x4);
3240        ++__r;
3241        if (__c(*__x3, *__x2))
3242        {
3243            swap(*__x2, *__x3);
3244            ++__r;
3245            if (__c(*__x2, *__x1))
3246            {
3247                swap(*__x1, *__x2);
3248                ++__r;
3249            }
3250        }
3251    }
3252    return __r;
3253}
3254
3255// stable, 4-10 compares, 0-9 swaps
3256
3257template <class _Compare, class _ForwardIterator>
3258unsigned
3259__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3260            _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
3261{
3262    unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
3263    if (__c(*__x5, *__x4))
3264    {
3265        swap(*__x4, *__x5);
3266        ++__r;
3267        if (__c(*__x4, *__x3))
3268        {
3269            swap(*__x3, *__x4);
3270            ++__r;
3271            if (__c(*__x3, *__x2))
3272            {
3273                swap(*__x2, *__x3);
3274                ++__r;
3275                if (__c(*__x2, *__x1))
3276                {
3277                    swap(*__x1, *__x2);
3278                    ++__r;
3279                }
3280            }
3281        }
3282    }
3283    return __r;
3284}
3285
3286// Assumes size > 0
3287template <class _Compare, class _BirdirectionalIterator>
3288void
3289__selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3290{
3291    _BirdirectionalIterator __lm1 = __last;
3292    for (--__lm1; __first != __lm1; ++__first)
3293    {
3294        _BirdirectionalIterator __i = _STD::min_element<_BirdirectionalIterator,
3295                                                        typename add_lvalue_reference<_Compare>::type>
3296                                                       (__first, __last, __comp);
3297        if (__i != __first)
3298            swap(*__first, *__i);
3299    }
3300}
3301
3302template <class _Compare, class _BirdirectionalIterator>
3303void
3304__insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3305{
3306    typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3307    if (__first != __last)
3308    {
3309        _BirdirectionalIterator __i = __first;
3310        for (++__i; __i != __last; ++__i)
3311        {
3312            _BirdirectionalIterator __j = __i;
3313            value_type __t(_STD::move(*__j));
3314            for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t,  *--__k); --__j)
3315                *__j = _STD::move(*__k);
3316            *__j = _STD::move(__t);
3317        }
3318    }
3319}
3320
3321template <class _Compare, class _RandomAccessIterator>
3322void
3323__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3324{
3325    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3326    _RandomAccessIterator __j = __first+2;
3327    __sort3<_Compare>(__first, __first+1, __j, __comp);
3328    for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3329    {
3330        if (__comp(*__i, *__j))
3331        {
3332            value_type __t(_STD::move(*__i));
3333            _RandomAccessIterator __k = __j;
3334            __j = __i;
3335            do
3336            {
3337                *__j = _STD::move(*__k);
3338                __j = __k;
3339            } while (__j != __first && __comp(__t, *--__k));
3340            *__j = _STD::move(__t);
3341        }
3342        __j = __i;
3343    }
3344}
3345
3346template <class _Compare, class _RandomAccessIterator>
3347bool
3348__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3349{
3350    switch (__last - __first)
3351    {
3352    case 0:
3353    case 1:
3354        return true;
3355    case 2:
3356        if (__comp(*--__last, *__first))
3357            swap(*__first, *__last);
3358        return true;
3359    case 3:
3360        _STD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3361        return true;
3362    case 4:
3363        _STD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3364        return true;
3365    case 5:
3366        _STD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3367        return true;
3368    }
3369    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3370    _RandomAccessIterator __j = __first+2;
3371    __sort3<_Compare>(__first, __first+1, __j, __comp);
3372    const unsigned __limit = 8;
3373    unsigned __count = 0;
3374    for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3375    {
3376        if (__comp(*__i, *__j))
3377        {
3378            value_type __t(_STD::move(*__i));
3379            _RandomAccessIterator __k = __j;
3380            __j = __i;
3381            do
3382            {
3383                *__j = _STD::move(*__k);
3384                __j = __k;
3385            } while (__j != __first && __comp(__t, *--__k));
3386            *__j = _STD::move(__t);
3387            if (++__count == __limit)
3388                return ++__i == __last;
3389        }
3390        __j = __i;
3391    }
3392    return true;
3393}
3394
3395template <class _Compare, class _BirdirectionalIterator>
3396void
3397__insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
3398                      typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
3399{
3400    typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3401    if (__first1 != __last1)
3402    {
3403        __destruct_n __d(0);
3404        unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
3405        value_type* __last2 = __first2;
3406        ::new(__last2) value_type(_STD::move(*__first1));
3407        __d.__incr((value_type*)0);
3408        for (++__last2; ++__first1 != __last1; ++__last2)
3409        {
3410            value_type* __j2 = __last2;
3411            value_type* __i2 = __j2;
3412            if (__comp(*__first1, *--__i2))
3413            {
3414                ::new(__j2) value_type(_STD::move(*__i2));
3415                __d.__incr((value_type*)0);
3416                for (--__j2; __i2 != __first2 && __comp(*__first1,  *--__i2); --__j2)
3417                    *__j2 = _STD::move(*__i2);
3418                *__j2 = _STD::move(*__first1);
3419            }
3420            else
3421            {
3422                ::new(__j2) value_type(_STD::move(*__first1));
3423                __d.__incr((value_type*)0);
3424            }
3425        }
3426        __h.release();
3427    }
3428}
3429
3430template <class _Compare, class _RandomAccessIterator>
3431void
3432__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3433{
3434    // _Compare is known to be a reference type
3435    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3436    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3437    const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
3438                                    is_trivially_copy_assignable<value_type>::value ? 30 : 6;
3439    while (true)
3440    {
3441    __restart:
3442        difference_type __len = __last - __first;
3443        switch (__len)
3444        {
3445        case 0:
3446        case 1:
3447            return;
3448        case 2:
3449            if (__comp(*--__last, *__first))
3450                swap(*__first, *__last);
3451            return;
3452        case 3:
3453            _STD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3454            return;
3455        case 4:
3456            _STD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3457            return;
3458        case 5:
3459            _STD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3460            return;
3461        }
3462        if (__len <= __limit)
3463        {
3464            _STD::__insertion_sort_3<_Compare>(__first, __last, __comp);
3465            return;
3466        }
3467        // __len > 5
3468        _RandomAccessIterator __m = __first;
3469        _RandomAccessIterator __lm1 = __last;
3470        --__lm1;
3471        unsigned __n_swaps;
3472        {
3473        difference_type __delta;
3474        if (__len >= 1000)
3475        {
3476            __delta = __len/2;
3477            __m += __delta;
3478            __delta /= 2;
3479            __n_swaps = _STD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
3480        }
3481        else
3482        {
3483            __delta = __len/2;
3484            __m += __delta;
3485            __n_swaps = _STD::__sort3<_Compare>(__first, __m, __lm1, __comp);
3486        }
3487        }
3488        // *__m is median
3489        // partition [__first, __m) < *__m and *__m <= [__m, __last)
3490        // (this inhibits tossing elements equivalent to __m around unnecessarily)
3491        _RandomAccessIterator __i = __first;
3492        _RandomAccessIterator __j = __lm1;
3493        // j points beyond range to be tested, *__m is known to be <= *__lm1
3494        // The search going up is known to be guarded but the search coming down isn't.
3495        // Prime the downward search with a guard.
3496        if (!__comp(*__i, *__m))  // if *__first == *__m
3497        {
3498            // *__first == *__m, *__first doesn't go in first part
3499            // manually guard downward moving __j against __i
3500            while (true)
3501            {
3502                if (__i == --__j)
3503                {
3504                    // *__first == *__m, *__m <= all other elements
3505                    // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
3506                    ++__i;  // __first + 1
3507                    __j = __last;
3508                    if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
3509                    {
3510                        while (true)
3511                        {
3512                            if (__i == __j)
3513                                return;  // [__first, __last) all equivalent elements
3514                            if (__comp(*__first, *__i))
3515                            {
3516                                swap(*__i, *__j);
3517                                ++__n_swaps;
3518                                ++__i;
3519                                break;
3520                            }
3521                            ++__i;
3522                        }
3523                    }
3524                    // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
3525                    if (__i == __j)
3526                        return;
3527                    while (true)
3528                    {
3529                        while (!__comp(*__first, *__i))
3530                            ++__i;
3531                        while (__comp(*__first, *--__j))
3532                            ;
3533                        if (__i >= __j)
3534                            break;
3535                        swap(*__i, *__j);
3536                        ++__n_swaps;
3537                        ++__i;
3538                    }
3539                    // [__first, __i) == *__first and *__first < [__i, __last)
3540                    // The first part is sorted, sort the secod part
3541                    // _STD::__sort<_Compare>(__i, __last, __comp);
3542                    __first = __i;
3543                    goto __restart;
3544                }
3545                if (__comp(*__j, *__m))
3546                {
3547                    swap(*__i, *__j);
3548                    ++__n_swaps;
3549                    break;  // found guard for downward moving __j, now use unguarded partition
3550                }
3551            }
3552        }
3553        // It is known that *__i < *__m
3554        ++__i;
3555        // j points beyond range to be tested, *__m is known to be <= *__lm1
3556        // if not yet partitioned...
3557        if (__i < __j)
3558        {
3559            // known that *(__i - 1) < *__m
3560            // known that __i <= __m
3561            while (true)
3562            {
3563                // __m still guards upward moving __i
3564                while (__comp(*__i, *__m))
3565                    ++__i;
3566                // It is now known that a guard exists for downward moving __j
3567                while (!__comp(*--__j, *__m))
3568                    ;
3569                if (__i > __j)
3570                    break;
3571                swap(*__i, *__j);
3572                ++__n_swaps;
3573                // It is known that __m != __j
3574                // If __m just moved, follow it
3575                if (__m == __i)
3576                    __m = __j;
3577                ++__i;
3578            }
3579        }
3580        // [__first, __i) < *__m and *__m <= [__i, __last)
3581        if (__i != __m && __comp(*__m, *__i))
3582        {
3583            swap(*__i, *__m);
3584            ++__n_swaps;
3585        }
3586        // [__first, __i) < *__i and *__i <= [__i+1, __last)
3587        // If we were given a perfect partition, see if insertion sort is quick...
3588        if (__n_swaps == 0)
3589        {
3590            bool __fs = _STD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
3591            if (_STD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
3592            {
3593                if (__fs)
3594                    return;
3595                __last = __i;
3596                continue;
3597            }
3598            else
3599            {
3600                if (__fs)
3601                {
3602                    __first = ++__i;
3603                    continue;
3604                }
3605            }
3606        }
3607        // sort smaller range with recursive call and larger with tail recursion elimination
3608        if (__i - __first < __last - __i)
3609        {
3610            _STD::__sort<_Compare>(__first, __i, __comp);
3611            // _STD::__sort<_Compare>(__i+1, __last, __comp);
3612            __first = ++__i;
3613        }
3614        else
3615        {
3616            _STD::__sort<_Compare>(__i+1, __last, __comp);
3617            // _STD::__sort<_Compare>(__first, __i, __comp);
3618            __last = __i;
3619        }
3620    }
3621}
3622
3623// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
3624template <class _RandomAccessIterator, class _Compare>
3625inline _LIBCPP_INLINE_VISIBILITY
3626void
3627sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3628{
3629#ifdef _LIBCPP_DEBUG
3630    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3631    __debug_less<_Compare> __c(__comp);
3632    __sort<_Comp_ref>(__first, __last, __c);
3633#else  // _LIBCPP_DEBUG
3634    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3635    __sort<_Comp_ref>(__first, __last, __comp);
3636#endif  // _LIBCPP_DEBUG
3637}
3638
3639template <class _RandomAccessIterator>
3640inline _LIBCPP_INLINE_VISIBILITY
3641void
3642sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
3643{
3644    _STD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
3645}
3646
3647template <class _Tp>
3648inline _LIBCPP_INLINE_VISIBILITY
3649void
3650sort(_Tp** __first, _Tp** __last)
3651{
3652    _STD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
3653}
3654
3655template <class _Tp>
3656inline _LIBCPP_INLINE_VISIBILITY
3657void
3658sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
3659{
3660    _STD::sort(__first.base(), __last.base());
3661}
3662
3663extern template void __sort<__less<char>&, char*>(char*, char*, __less<char>&);
3664extern template void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
3665extern template void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
3666extern template void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
3667extern template void __sort<__less<short>&, short*>(short*, short*, __less<short>&);
3668extern template void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
3669extern template void __sort<__less<int>&, int*>(int*, int*, __less<int>&);
3670extern template void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
3671extern template void __sort<__less<long>&, long*>(long*, long*, __less<long>&);
3672extern template void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
3673extern template void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
3674extern template void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
3675extern template void __sort<__less<float>&, float*>(float*, float*, __less<float>&);
3676extern template void __sort<__less<double>&, double*>(double*, double*, __less<double>&);
3677extern template void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
3678
3679extern template bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&);
3680extern template bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
3681extern template bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
3682extern template bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
3683extern template bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&);
3684extern template bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
3685extern template bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&);
3686extern template bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
3687extern template bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&);
3688extern template bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
3689extern template bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
3690extern template bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
3691extern template bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&);
3692extern template bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&);
3693extern template bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
3694
3695extern template unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&);
3696
3697// lower_bound
3698
3699template <class _Compare, class _ForwardIterator, class _Tp>
3700_ForwardIterator
3701__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3702{
3703    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3704    difference_type __len = _STD::distance(__first, __last);
3705    while (__len != 0)
3706    {
3707        difference_type __l2 = __len / 2;
3708        _ForwardIterator __m = __first;
3709        _STD::advance(__m, __l2);
3710        if (__comp(*__m, __value))
3711        {
3712            __first = ++__m;
3713            __len -= __l2 + 1;
3714        }
3715        else
3716            __len = __l2;
3717    }
3718    return __first;
3719}
3720
3721template <class _ForwardIterator, class _Tp, class _Compare>
3722inline _LIBCPP_INLINE_VISIBILITY
3723_ForwardIterator
3724lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3725{
3726#ifdef _LIBCPP_DEBUG
3727    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3728    __debug_less<_Compare> __c(__comp);
3729    return __lower_bound<_Comp_ref>(__first, __last, __value, __c);
3730#else  // _LIBCPP_DEBUG
3731    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3732    return __lower_bound<_Comp_ref>(__first, __last, __value, __comp);
3733#endif  // _LIBCPP_DEBUG
3734}
3735
3736template <class _ForwardIterator, class _Tp>
3737inline _LIBCPP_INLINE_VISIBILITY
3738_ForwardIterator
3739lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
3740{
3741    return _STD::lower_bound(__first, __last, __value,
3742                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
3743}
3744
3745// upper_bound
3746
3747template <class _Compare, class _ForwardIterator, class _Tp>
3748_ForwardIterator
3749__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3750{
3751    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3752    difference_type __len = _STD::distance(__first, __last);
3753    while (__len != 0)
3754    {
3755        difference_type __l2 = __len / 2;
3756        _ForwardIterator __m = __first;
3757        _STD::advance(__m, __l2);
3758        if (__comp(__value, *__m))
3759            __len = __l2;
3760        else
3761        {
3762            __first = ++__m;
3763            __len -= __l2 + 1;
3764        }
3765    }
3766    return __first;
3767}
3768
3769template <class _ForwardIterator, class _Tp, class _Compare>
3770inline _LIBCPP_INLINE_VISIBILITY
3771_ForwardIterator
3772upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3773{
3774#ifdef _LIBCPP_DEBUG
3775    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3776    __debug_less<_Compare> __c(__comp);
3777    return __upper_bound<_Comp_ref>(__first, __last, __value, __c);
3778#else  // _LIBCPP_DEBUG
3779    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3780    return __upper_bound<_Comp_ref>(__first, __last, __value, __comp);
3781#endif  // _LIBCPP_DEBUG
3782}
3783
3784template <class _ForwardIterator, class _Tp>
3785inline _LIBCPP_INLINE_VISIBILITY
3786_ForwardIterator
3787upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
3788{
3789    return _STD::upper_bound(__first, __last, __value,
3790                             __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
3791}
3792
3793// equal_range
3794
3795template <class _Compare, class _ForwardIterator, class _Tp>
3796pair<_ForwardIterator, _ForwardIterator>
3797__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3798{
3799    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3800    difference_type __len = _STD::distance(__first, __last);
3801    while (__len != 0)
3802    {
3803        difference_type __l2 = __len / 2;
3804        _ForwardIterator __m = __first;
3805        _STD::advance(__m, __l2);
3806        if (__comp(*__m, __value))
3807        {
3808            __first = ++__m;
3809            __len -= __l2 + 1;
3810        }
3811        else if (__comp(__value, *__m))
3812        {
3813            __last = __m;
3814            __len = __l2;
3815        }
3816        else
3817        {
3818            _ForwardIterator __mp1 = __m;
3819            return pair<_ForwardIterator, _ForwardIterator>
3820                   (
3821                      __lower_bound<_Compare>(__first, __m, __value, __comp),
3822                      __upper_bound<_Compare>(++__mp1, __last, __value, __comp)
3823                   );
3824        }
3825    }
3826    return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
3827}
3828
3829template <class _ForwardIterator, class _Tp, class _Compare>
3830inline _LIBCPP_INLINE_VISIBILITY
3831pair<_ForwardIterator, _ForwardIterator>
3832equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3833{
3834#ifdef _LIBCPP_DEBUG
3835    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3836    __debug_less<_Compare> __c(__comp);
3837    return __equal_range<_Comp_ref>(__first, __last, __value, __c);
3838#else  // _LIBCPP_DEBUG
3839    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3840    return __equal_range<_Comp_ref>(__first, __last, __value, __comp);
3841#endif  // _LIBCPP_DEBUG
3842}
3843
3844template <class _ForwardIterator, class _Tp>
3845inline _LIBCPP_INLINE_VISIBILITY
3846pair<_ForwardIterator, _ForwardIterator>
3847equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
3848{
3849    return _STD::equal_range(__first, __last, __value,
3850                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
3851}
3852
3853// binary_search
3854
3855template <class _Compare, class _ForwardIterator, class _Tp>
3856inline _LIBCPP_INLINE_VISIBILITY
3857bool
3858__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3859{
3860    __first = __lower_bound<_Compare>(__first, __last, __value, __comp);
3861    return __first != __last && !__comp(__value, *__first);
3862}
3863
3864template <class _ForwardIterator, class _Tp, class _Compare>
3865inline _LIBCPP_INLINE_VISIBILITY
3866bool
3867binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
3868{
3869#ifdef _LIBCPP_DEBUG
3870    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3871    __debug_less<_Compare> __c(__comp);
3872    return __binary_search<_Comp_ref>(__first, __last, __value, __c);
3873#else  // _LIBCPP_DEBUG
3874    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3875    return __binary_search<_Comp_ref>(__first, __last, __value, __comp);
3876#endif  // _LIBCPP_DEBUG
3877}
3878
3879template <class _ForwardIterator, class _Tp>
3880inline _LIBCPP_INLINE_VISIBILITY
3881bool
3882binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
3883{
3884    return _STD::binary_search(__first, __last, __value,
3885                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
3886}
3887
3888// merge
3889
3890template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
3891_OutputIterator
3892__merge(_InputIterator1 __first1, _InputIterator1 __last1,
3893        _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
3894{
3895    for (; __first1 != __last1; ++__result)
3896    {
3897        if (__first2 == __last2)
3898            return _STD::copy(__first1, __last1, __result);
3899        if (__comp(*__first2, *__first1))
3900        {
3901            *__result = *__first2;
3902            ++__first2;
3903        }
3904        else
3905        {
3906            *__result = *__first1;
3907            ++__first1;
3908        }
3909    }
3910    return _STD::copy(__first2, __last2, __result);
3911}
3912
3913template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
3914inline _LIBCPP_INLINE_VISIBILITY
3915_OutputIterator
3916merge(_InputIterator1 __first1, _InputIterator1 __last1,
3917      _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
3918{
3919#ifdef _LIBCPP_DEBUG
3920    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3921    __debug_less<_Compare> __c(__comp);
3922    return _STD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
3923#else  // _LIBCPP_DEBUG
3924    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3925    return _STD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
3926#endif  // _LIBCPP_DEBUG
3927}
3928
3929template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
3930inline _LIBCPP_INLINE_VISIBILITY
3931_OutputIterator
3932merge(_InputIterator1 __first1, _InputIterator1 __last1,
3933      _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
3934{
3935    typedef typename iterator_traits<_InputIterator1>::value_type __v1;
3936    typedef typename iterator_traits<_InputIterator2>::value_type __v2;
3937    return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
3938}
3939
3940// inplace_merge
3941
3942template <class _Compare, class _BidirectionalIterator>
3943void
3944__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
3945                _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
3946                                 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
3947                typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
3948{
3949    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3950    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3951    typedef typename iterator_traits<_BidirectionalIterator>::pointer pointer;
3952    __destruct_n __d(0);
3953    unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
3954    if (__len1 <= __len2)
3955    {
3956        value_type* __p = __buff;
3957        for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), ++__i, ++__p)
3958            ::new(__p) value_type(_STD::move(*__i));
3959        __merge<_Compare>(move_iterator<value_type*>(__buff),
3960                          move_iterator<value_type*>(__p),
3961                          move_iterator<_BidirectionalIterator>(__middle),
3962                          move_iterator<_BidirectionalIterator>(__last),
3963                          __first, __comp);
3964    }
3965    else
3966    {
3967        value_type* __p = __buff;
3968        for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), ++__i, ++__p)
3969            ::new(__p) value_type(_STD::move(*__i));
3970        typedef reverse_iterator<_BidirectionalIterator> _RBi;
3971        typedef reverse_iterator<value_type*> _Rv;
3972        __merge(move_iterator<_RBi>(_RBi(__middle)), move_iterator<_RBi>(_RBi(__first)),
3973                move_iterator<_Rv>(_Rv(__p)), move_iterator<_Rv>(_Rv(__buff)),
3974                _RBi(__last), __negate<_Compare>(__comp));
3975    }
3976}
3977
3978template <class _Compare, class _BidirectionalIterator>
3979void
3980__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
3981                _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
3982                                 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
3983                typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
3984{
3985    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3986    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3987    while (true)
3988    {
3989        // if __middle == __last, we're done
3990        if (__len2 == 0)
3991            return;
3992        // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
3993        for (; true; ++__first, --__len1)
3994        {
3995            if (__len1 == 0)
3996                return;
3997            if (__comp(*__middle, *__first))
3998                break;
3999        }
4000        if (__len1 <= __buff_size || __len2 <= __buff_size)
4001        {
4002            __buffered_inplace_merge<_Compare>(__first, __middle, __last, __comp, __len1, __len2, __buff);
4003            return;
4004        }
4005        // __first < __middle < __last
4006        // *__first > *__middle
4007        // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4008        //     all elements in:
4009        //         [__first, __m1)  <= [__middle, __m2)
4010        //         [__middle, __m2) <  [__m1, __middle)
4011        //         [__m1, __middle) <= [__m2, __last)
4012        //     and __m1 or __m2 is in the middle of its range
4013        _BidirectionalIterator __m1;  // "median" of [__first, __middle)
4014        _BidirectionalIterator __m2;  // "median" of [__middle, __last)
4015        difference_type __len11;      // distance(__first, __m1)
4016        difference_type __len21;      // distance(__middle, __m2)
4017        // binary search smaller range
4018        if (__len1 < __len2)
4019        {   // __len >= 1, __len2 >= 2
4020            __len21 = __len2 / 2;
4021            __m2 = __middle;
4022            _STD::advance(__m2, __len21);
4023            __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4024            __len11 = _STD::distance(__first, __m1);
4025        }
4026        else
4027        {
4028            if (__len1 == 1)
4029            {   // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
4030                // It is known *__first > *__middle
4031                swap(*__first, *__middle);
4032                return;
4033            }
4034            // __len1 >= 2, __len2 >= 1
4035            __len11 = __len1 / 2;
4036            __m1 = __first;
4037            _STD::advance(__m1, __len11);
4038            __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp);
4039            __len21 = _STD::distance(__middle, __m2);
4040        }
4041        difference_type __len12 = __len1 - __len11;  // distance(__m1, __middle)
4042        difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)
4043        // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4044        // swap middle two partitions
4045        __middle = _STD::rotate(__m1, __middle, __m2);
4046        // __len12 and __len21 now have swapped meanings
4047        // merge smaller range with recurisve call and larger with tail recursion elimination
4048        if (__len11 + __len21 < __len12 + __len22)
4049        {
4050            __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4051//          __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4052            __first = __middle;
4053            __middle = __m2;
4054            __len1 = __len12;
4055            __len2 = __len22;
4056        }
4057        else
4058        {
4059            __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4060//          __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4061            __last = __middle;
4062            __middle = __m1;
4063            __len1 = __len11;
4064            __len2 = __len21;
4065        }
4066    }
4067}
4068
4069template <class _Tp>
4070struct __inplace_merge_switch
4071{
4072    static const unsigned value = is_trivially_copy_assignable<_Tp>::value;
4073};
4074
4075template <class _BidirectionalIterator, class _Compare>
4076inline _LIBCPP_INLINE_VISIBILITY
4077void
4078inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4079              _Compare __comp)
4080{
4081    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4082    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4083    difference_type __len1 = _STD::distance(__first, __middle);
4084    difference_type __len2 = _STD::distance(__middle, __last);
4085    difference_type __buf_size = _STD::min(__len1, __len2);
4086    pair<value_type*, ptrdiff_t> __buf(0, 0);
4087    unique_ptr<value_type, __return_temporary_buffer> __h;
4088    if (__inplace_merge_switch<value_type>::value && __buf_size > 8)
4089    {
4090        __buf = _STD::get_temporary_buffer<value_type>(__buf_size);
4091        __h.reset(__buf.first);
4092    }
4093#ifdef _LIBCPP_DEBUG
4094    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4095    __debug_less<_Compare> __c(__comp);
4096    return _STD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2,
4097                                            __buf.first, __buf.second);
4098#else  // _LIBCPP_DEBUG
4099    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4100    return _STD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4101                                            __buf.first, __buf.second);
4102#endif  // _LIBCPP_DEBUG
4103}
4104
4105template <class _BidirectionalIterator>
4106inline _LIBCPP_INLINE_VISIBILITY
4107void
4108inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
4109{
4110    _STD::inplace_merge(__first, __middle, __last,
4111                        __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4112}
4113
4114// stable_sort
4115
4116template <class _Compare, class _InputIterator1, class _InputIterator2>
4117void
4118__merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
4119        _InputIterator2 __first2, _InputIterator2 __last2,
4120        typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
4121{
4122    typedef typename iterator_traits<_InputIterator1>::value_type value_type;
4123    __destruct_n __d(0);
4124    unique_ptr<value_type, __destruct_n&> __h(__result, __d);
4125    for (; true; ++__result)
4126    {
4127        if (__first1 == __last1)
4128        {
4129            for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0))
4130                ::new (__result) value_type(_STD::move(*__first2));
4131            __h.release();
4132            return;
4133        }
4134        if (__first2 == __last2)
4135        {
4136            for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0))
4137                ::new (__result) value_type(_STD::move(*__first1));
4138            __h.release();
4139            return;
4140        }
4141        if (__comp(*__first2, *__first1))
4142        {
4143            ::new (__result) value_type(_STD::move(*__first2));
4144            __d.__incr((value_type*)0);
4145            ++__first2;
4146        }
4147        else
4148        {
4149            ::new (__result) value_type(_STD::move(*__first1));
4150            __d.__incr((value_type*)0);
4151            ++__first1;
4152        }
4153    }
4154}
4155
4156template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4157void
4158__merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
4159        _InputIterator2 __first2, _InputIterator2 __last2,
4160        _OutputIterator __result, _Compare __comp)
4161{
4162    for (; __first1 != __last1; ++__result)
4163    {
4164        if (__first2 == __last2)
4165        {
4166            for (; __first1 != __last1; ++__first1, ++__result)
4167                *__result = _STD::move(*__first1);
4168            return;
4169        }
4170        if (__comp(*__first2, *__first1))
4171        {
4172            *__result = _STD::move(*__first2);
4173            ++__first2;
4174        }
4175        else
4176        {
4177            *__result = _STD::move(*__first1);
4178            ++__first1;
4179        }
4180    }
4181    for (; __first2 != __last2; ++__first2, ++__result)
4182        *__result = _STD::move(*__first2);
4183}
4184
4185template <class _Compare, class _RandomAccessIterator>
4186void
4187__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4188              typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4189              typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
4190
4191template <class _Compare, class _RandomAccessIterator>
4192void
4193__stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
4194                   typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4195                   typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
4196{
4197    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4198    switch (__len)
4199    {
4200    case 0:
4201        return;
4202    case 1:
4203        ::new(__first2) value_type(_STD::move(*__first1));
4204        return;
4205    case 2:
4206       __destruct_n __d(0);
4207        unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
4208         if (__comp(*--__last1, *__first1))
4209        {
4210            ::new(__first2) value_type(_STD::move(*__last1));
4211            __d.__incr((value_type*)0);
4212            ++__first2;
4213            ::new(__first2) value_type(_STD::move(*__first1));
4214        }
4215        else
4216        {
4217            ::new(__first2) value_type(_STD::move(*__first1));
4218            __d.__incr((value_type*)0);
4219            ++__first2;
4220            ::new(__first2) value_type(_STD::move(*__last1));
4221        }
4222        __h2.release();
4223        return;
4224    }
4225    if (__len <= 8)
4226    {
4227        __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
4228        return;
4229    }
4230    typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4231    _RandomAccessIterator __m = __first1 + __l2;
4232    __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
4233    __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
4234    __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
4235}
4236
4237template <class _Tp>
4238struct __stable_sort_switch
4239{
4240    static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
4241};
4242
4243template <class _Compare, class _RandomAccessIterator>
4244void
4245__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4246              typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4247              typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
4248{
4249    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4250    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4251    switch (__len)
4252    {
4253    case 0:
4254    case 1:
4255        return;
4256    case 2:
4257        if (__comp(*--__last, *__first))
4258            swap(*__first, *__last);
4259        return;
4260    }
4261    if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4262    {
4263        __insertion_sort<_Compare>(__first, __last, __comp);
4264        return;
4265    }
4266    typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4267    _RandomAccessIterator __m = __first + __l2;
4268    if (__len <= __buff_size)
4269    {
4270        __destruct_n __d(0);
4271        unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4272        __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4273        __d.__set(__l2, (value_type*)0);
4274        __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
4275        __d.__set(__len, (value_type*)0);
4276        __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4277//         __merge<_Compare>(move_iterator<value_type*>(__buff),
4278//                           move_iterator<value_type*>(__buff + __l2),
4279//                           move_iterator<_RandomAccessIterator>(__buff + __l2),
4280//                           move_iterator<_RandomAccessIterator>(__buff + __len),
4281//                           __first, __comp);
4282        return;
4283    }
4284    __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4285    __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
4286    __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4287}
4288
4289template <class _RandomAccessIterator, class _Compare>
4290inline _LIBCPP_INLINE_VISIBILITY
4291void
4292stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4293{
4294    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4295    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4296    difference_type __len = __last - __first;
4297    pair<value_type*, ptrdiff_t> __buf(0, 0);
4298    unique_ptr<value_type, __return_temporary_buffer> __h;
4299    if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4300    {
4301        __buf = _STD::get_temporary_buffer<value_type>(__len);
4302        __h.reset(__buf.first);
4303    }
4304#ifdef _LIBCPP_DEBUG
4305    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4306    __debug_less<_Compare> __c(__comp);
4307    __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);
4308#else  // _LIBCPP_DEBUG
4309    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4310    __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4311#endif  // _LIBCPP_DEBUG
4312}
4313
4314template <class _RandomAccessIterator>
4315inline _LIBCPP_INLINE_VISIBILITY
4316void
4317stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4318{
4319    _STD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4320}
4321
4322// is_heap_until
4323
4324template <class _RandomAccessIterator, class _Compare>
4325_RandomAccessIterator
4326is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4327{
4328    typedef typename _STD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4329    difference_type __len = __last - __first;
4330    difference_type __p = 0;
4331    difference_type __c = 1;
4332    _RandomAccessIterator __pp = __first;
4333    while (__c < __len)
4334    {
4335        _RandomAccessIterator __cp = __first + __c;
4336        if (__comp(*__pp, *__cp))
4337            return __cp;
4338        ++__c;
4339        ++__cp;
4340        if (__c == __len)
4341            return __last;
4342        if (__comp(*__pp, *__cp))
4343            return __cp;
4344        ++__p;
4345        ++__pp;
4346        __c = 2 * __p + 1;
4347    }
4348    return __last;
4349}
4350
4351template<class _RandomAccessIterator>
4352inline _LIBCPP_INLINE_VISIBILITY
4353_RandomAccessIterator
4354is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4355{
4356    return _STD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4357}
4358
4359// is_heap
4360
4361template <class _RandomAccessIterator, class _Compare>
4362inline _LIBCPP_INLINE_VISIBILITY
4363bool
4364is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4365{
4366    return _STD::is_heap_until(__first, __last, __comp) == __last;
4367}
4368
4369template<class _RandomAccessIterator>
4370inline _LIBCPP_INLINE_VISIBILITY
4371bool
4372is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4373{
4374    return _STD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4375}
4376
4377// push_heap
4378
4379template <class _Compare, class _RandomAccessIterator>
4380void
4381__push_heap_front(_RandomAccessIterator __first, _RandomAccessIterator, _Compare __comp,
4382                  typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4383{
4384    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4385    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4386    if (__len > 1)
4387    {
4388        difference_type __p = 0;
4389        _RandomAccessIterator __pp = __first;
4390        difference_type __c = 2;
4391        _RandomAccessIterator __cp = __first + __c;
4392        if (__c == __len || __comp(*__cp, *(__cp - 1)))
4393        {
4394            --__c;
4395            --__cp;
4396        }
4397        if (__comp(*__pp, *__cp))
4398        {
4399            value_type __t(_STD::move(*__pp));
4400            do
4401            {
4402                *__pp = _STD::move(*__cp);
4403                __pp = __cp;
4404                __p = __c;
4405                __c = (__p + 1) * 2;
4406                if (__c > __len)
4407                    break;
4408                __cp = __first + __c;
4409                if (__c == __len || __comp(*__cp, *(__cp - 1)))
4410                {
4411                    --__c;
4412                    --__cp;
4413                }
4414            } while (__comp(__t, *__cp));
4415            *__pp = _STD::move(__t);
4416        }
4417    }
4418}
4419
4420template <class _Compare, class _RandomAccessIterator>
4421void
4422__push_heap_back(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4423                 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4424{
4425    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4426    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4427    if (__len > 1)
4428    {
4429        __len = (__len - 2) / 2;
4430        _RandomAccessIterator __ptr = __first + __len;
4431        if (__comp(*__ptr, *--__last))
4432        {
4433            value_type __t(_STD::move(*__last));
4434            do
4435            {
4436                *__last = _STD::move(*__ptr);
4437                __last = __ptr;
4438                if (__len == 0)
4439                    break;
4440                __len = (__len - 1) / 2;
4441                __ptr = __first + __len;
4442            } while (__comp(*__ptr, __t));
4443            *__last = _STD::move(__t);
4444        }
4445    }
4446}
4447
4448template <class _RandomAccessIterator, class _Compare>
4449inline _LIBCPP_INLINE_VISIBILITY
4450void
4451push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4452{
4453#ifdef _LIBCPP_DEBUG
4454    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4455    __debug_less<_Compare> __c(__comp);
4456    __push_heap_back<_Comp_ref>(__first, __last, __c, __last - __first);
4457#else  // _LIBCPP_DEBUG
4458    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4459    __push_heap_back<_Comp_ref>(__first, __last, __comp, __last - __first);
4460#endif  // _LIBCPP_DEBUG
4461}
4462
4463template <class _RandomAccessIterator>
4464inline _LIBCPP_INLINE_VISIBILITY
4465void
4466push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4467{
4468    _STD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4469}
4470
4471// pop_heap
4472
4473template <class _Compare, class _RandomAccessIterator>
4474inline _LIBCPP_INLINE_VISIBILITY
4475void
4476__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4477           typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4478{
4479    if (__len > 1)
4480    {
4481        swap(*__first, *--__last);
4482        __push_heap_front<_Compare>(__first, __last, __comp, __len-1);
4483    }
4484}
4485
4486template <class _RandomAccessIterator, class _Compare>
4487inline _LIBCPP_INLINE_VISIBILITY
4488void
4489pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4490{
4491#ifdef _LIBCPP_DEBUG
4492    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4493    __debug_less<_Compare> __c(__comp);
4494    __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);
4495#else  // _LIBCPP_DEBUG
4496    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4497    __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
4498#endif  // _LIBCPP_DEBUG
4499}
4500
4501template <class _RandomAccessIterator>
4502inline _LIBCPP_INLINE_VISIBILITY
4503void
4504pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4505{
4506    _STD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4507}
4508
4509// make_heap
4510
4511template <class _Compare, class _RandomAccessIterator>
4512void
4513__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4514{
4515    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4516    difference_type __n = __last - __first;
4517    if (__n > 1)
4518    {
4519        __last = __first;
4520        ++__last;
4521        for (difference_type __i = 1; __i < __n;)
4522            __push_heap_back<_Compare>(__first, ++__last, __comp, ++__i);
4523    }
4524}
4525
4526template <class _RandomAccessIterator, class _Compare>
4527inline _LIBCPP_INLINE_VISIBILITY
4528void
4529make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4530{
4531#ifdef _LIBCPP_DEBUG
4532    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4533    __debug_less<_Compare> __c(__comp);
4534    __make_heap<_Comp_ref>(__first, __last, __c);
4535#else  // _LIBCPP_DEBUG
4536    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4537    __make_heap<_Comp_ref>(__first, __last, __comp);
4538#endif  // _LIBCPP_DEBUG
4539}
4540
4541template <class _RandomAccessIterator>
4542inline _LIBCPP_INLINE_VISIBILITY
4543void
4544make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4545{
4546    _STD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4547}
4548
4549// sort_heap
4550
4551template <class _Compare, class _RandomAccessIterator>
4552void
4553__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4554{
4555    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4556    for (difference_type __n = __last - __first; __n > 1; --__last, --__n)
4557        __pop_heap<_Compare>(__first, __last, __comp, __n);
4558}
4559
4560template <class _RandomAccessIterator, class _Compare>
4561inline _LIBCPP_INLINE_VISIBILITY
4562void
4563sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4564{
4565#ifdef _LIBCPP_DEBUG
4566    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4567    __debug_less<_Compare> __c(__comp);
4568    __sort_heap<_Comp_ref>(__first, __last, __c);
4569#else  // _LIBCPP_DEBUG
4570    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4571    __sort_heap<_Comp_ref>(__first, __last, __comp);
4572#endif  // _LIBCPP_DEBUG
4573}
4574
4575template <class _RandomAccessIterator>
4576inline _LIBCPP_INLINE_VISIBILITY
4577void
4578sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4579{
4580    _STD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4581}
4582
4583// partial_sort
4584
4585template <class _Compare, class _RandomAccessIterator>
4586void
4587__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
4588             _Compare __comp)
4589{
4590    __make_heap<_Compare>(__first, __middle, __comp);
4591    typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
4592    for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
4593    {
4594        if (__comp(*__i, *__first))
4595        {
4596            swap(*__i, *__first);
4597            __push_heap_front<_Compare>(__first, __middle, __comp, __len);
4598        }
4599    }
4600    __sort_heap<_Compare>(__first, __middle, __comp);
4601}
4602
4603template <class _RandomAccessIterator, class _Compare>
4604inline _LIBCPP_INLINE_VISIBILITY
4605void
4606partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
4607             _Compare __comp)
4608{
4609#ifdef _LIBCPP_DEBUG
4610    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4611    __debug_less<_Compare> __c(__comp);
4612    __partial_sort<_Comp_ref>(__first, __middle, __last, __c);
4613#else  // _LIBCPP_DEBUG
4614    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4615    __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
4616#endif  // _LIBCPP_DEBUG
4617}
4618
4619template <class _RandomAccessIterator>
4620inline _LIBCPP_INLINE_VISIBILITY
4621void
4622partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
4623{
4624    _STD::partial_sort(__first, __middle, __last,
4625                       __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4626}
4627
4628// partial_sort_copy
4629
4630template <class _Compare, class _InputIterator, class _RandomAccessIterator>
4631_RandomAccessIterator
4632__partial_sort_copy(_InputIterator __first, _InputIterator __last,
4633                    _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
4634{
4635    _RandomAccessIterator __r = __result_first;
4636    if (__r != __result_last)
4637    {
4638        typename iterator_traits<_RandomAccessIterator>::difference_type __len = 0;
4639        for (; __first != __last && __r != __result_last; ++__first, ++__r, ++__len)
4640            *__r = *__first;
4641        __make_heap<_Compare>(__result_first, __r, __comp);
4642        for (; __first != __last; ++__first)
4643            if (__comp(*__first, *__result_first))
4644            {
4645                *__result_first = *__first;
4646                __push_heap_front<_Compare>(__result_first, __r, __comp, __len);
4647            }
4648        __sort_heap<_Compare>(__result_first, __r, __comp);
4649    }
4650    return __r;
4651}
4652
4653template <class _InputIterator, class _RandomAccessIterator, class _Compare>
4654inline _LIBCPP_INLINE_VISIBILITY
4655_RandomAccessIterator
4656partial_sort_copy(_InputIterator __first, _InputIterator __last,
4657                  _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
4658{
4659#ifdef _LIBCPP_DEBUG
4660    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4661    __debug_less<_Compare> __c(__comp);
4662    return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);
4663#else  // _LIBCPP_DEBUG
4664    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4665    return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
4666#endif  // _LIBCPP_DEBUG
4667}
4668
4669template <class _InputIterator, class _RandomAccessIterator>
4670inline _LIBCPP_INLINE_VISIBILITY
4671_RandomAccessIterator
4672partial_sort_copy(_InputIterator __first, _InputIterator __last,
4673                  _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
4674{
4675    return _STD::partial_sort_copy(__first, __last, __result_first, __result_last,
4676                                   __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4677}
4678
4679// nth_element
4680
4681template <class _Compare, class _RandomAccessIterator>
4682void
4683__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
4684{
4685    // _Compare is known to be a reference type
4686    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4687    const difference_type __limit = 7;
4688    while (true)
4689    {
4690    __restart:
4691        difference_type __len = __last - __first;
4692        switch (__len)
4693        {
4694        case 0:
4695        case 1:
4696            return;
4697        case 2:
4698            if (__comp(*--__last, *__first))
4699                swap(*__first, *__last);
4700            return;
4701        case 3:
4702            {
4703            _RandomAccessIterator __m = __first;
4704            _STD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
4705            return;
4706            }
4707        }
4708        if (__len <= __limit)
4709        {
4710            __selection_sort<_Compare>(__first, __last, __comp);
4711            return;
4712        }
4713        // __len > __limit >= 3
4714        _RandomAccessIterator __m = __first + __len/2;
4715        _RandomAccessIterator __lm1 = __last;
4716        unsigned __n_swaps = _STD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
4717        // *__m is median
4718        // partition [__first, __m) < *__m and *__m <= [__m, __last)
4719        // (this inhibits tossing elements equivalent to __m around unnecessarily)
4720        _RandomAccessIterator __i = __first;
4721        _RandomAccessIterator __j = __lm1;
4722        // j points beyond range to be tested, *__lm1 is known to be <= *__m
4723        // The search going up is known to be guarded but the search coming down isn't.
4724        // Prime the downward search with a guard.
4725        if (!__comp(*__i, *__m))  // if *__first == *__m
4726        {
4727            // *__first == *__m, *__first doesn't go in first part
4728            // manually guard downward moving __j against __i
4729            while (true)
4730            {
4731                if (__i == --__j)
4732                {
4733                    // *__first == *__m, *__m <= all other elements
4734                    // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
4735                    ++__i;  // __first + 1
4736                    __j = __last;
4737                    if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
4738                    {
4739                        while (true)
4740                        {
4741                            if (__i == __j)
4742                                return;  // [__first, __last) all equivalent elements
4743                            if (__comp(*__first, *__i))
4744                            {
4745                                swap(*__i, *__j);
4746                                ++__n_swaps;
4747                                ++__i;
4748                                break;
4749                            }
4750                            ++__i;
4751                        }
4752                    }
4753                    // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
4754                    if (__i == __j)
4755                        return;
4756                    while (true)
4757                    {
4758                        while (!__comp(*__first, *__i))
4759                            ++__i;
4760                        while (__comp(*__first, *--__j))
4761                            ;
4762                        if (__i >= __j)
4763                            break;
4764                        swap(*__i, *__j);
4765                        ++__n_swaps;
4766                        ++__i;
4767                    }
4768                    // [__first, __i) == *__first and *__first < [__i, __last)
4769                    // The first part is sorted,
4770                    if (__nth < __i)
4771                        return;
4772                    // __nth_element the secod part
4773                    // __nth_element<_Compare>(__i, __nth, __last, __comp);
4774                    __first = __i;
4775                    goto __restart;
4776                }
4777                if (__comp(*__j, *__m))
4778                {
4779                    swap(*__i, *__j);
4780                    ++__n_swaps;
4781                    break;  // found guard for downward moving __j, now use unguarded partition
4782                }
4783            }
4784        }
4785        ++__i;
4786        // j points beyond range to be tested, *__lm1 is known to be <= *__m
4787        // if not yet partitioned...
4788        if (__i < __j)
4789        {
4790            // known that *(__i - 1) < *__m
4791            while (true)
4792            {
4793                // __m still guards upward moving __i
4794                while (__comp(*__i, *__m))
4795                    ++__i;
4796                // It is now known that a guard exists for downward moving __j
4797                while (!__comp(*--__j, *__m))
4798                    ;
4799                if (__i >= __j)
4800                    break;
4801                swap(*__i, *__j);
4802                ++__n_swaps;
4803                // It is known that __m != __j
4804                // If __m just moved, follow it
4805                if (__m == __i)
4806                    __m = __j;
4807                ++__i;
4808            }
4809        }
4810        // [__first, __i) < *__m and *__m <= [__i, __last)
4811        if (__i != __m && __comp(*__m, *__i))
4812        {
4813            swap(*__i, *__m);
4814            ++__n_swaps;
4815        }
4816        // [__first, __i) < *__i and *__i <= [__i+1, __last)
4817        if (__nth == __i)
4818            return;
4819        if (__n_swaps == 0)
4820        {
4821            // We were given a perfectly partitioned sequence.  Coincidence?
4822            if (__nth < __i)
4823            {
4824                // Check for [__first, __i) already sorted
4825                __j = __m = __first;
4826                while (++__j != __i)
4827                {
4828                    if (__comp(*__j, *__m))
4829                        // not yet sorted, so sort
4830                        goto not_sorted;
4831                    __m = __j;
4832                }
4833                // [__first, __i) sorted
4834                return;
4835            }
4836            else
4837            {
4838                // Check for [__i, __last) already sorted
4839                __j = __m = __i;
4840                while (++__j != __last)
4841                {
4842                    if (__comp(*__j, *__m))
4843                        // not yet sorted, so sort
4844                        goto not_sorted;
4845                    __m = __j;
4846                }
4847                // [__i, __last) sorted
4848                return;
4849            }
4850        }
4851not_sorted:
4852        // __nth_element on range containing __nth
4853        if (__nth < __i)
4854        {
4855            // __nth_element<_Compare>(__first, __nth, __i, __comp);
4856            __last = __i;
4857        }
4858        else
4859        {
4860            // __nth_element<_Compare>(__i+1, __nth, __last, __comp);
4861            __first = ++__i;
4862        }
4863    }
4864}
4865
4866template <class _RandomAccessIterator, class _Compare>
4867inline _LIBCPP_INLINE_VISIBILITY
4868void
4869nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
4870{
4871#ifdef _LIBCPP_DEBUG
4872    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4873    __debug_less<_Compare> __c(__comp);
4874    __nth_element<_Comp_ref>(__first, __nth, __last, __c);
4875#else  // _LIBCPP_DEBUG
4876    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4877    __nth_element<_Comp_ref>(__first, __nth, __last, __comp);
4878#endif  // _LIBCPP_DEBUG
4879}
4880
4881template <class _RandomAccessIterator>
4882inline _LIBCPP_INLINE_VISIBILITY
4883void
4884nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
4885{
4886    _STD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4887}
4888
4889// includes
4890
4891template <class _Compare, class _InputIterator1, class _InputIterator2>
4892bool
4893__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
4894           _Compare __comp)
4895{
4896    for (; __first2 != __last2; ++__first1)
4897    {
4898        if (__first1 == __last1 || __comp(*__first2, *__first1))
4899            return false;
4900        if (!__comp(*__first1, *__first2))
4901            ++__first2;
4902    }
4903    return true;
4904}
4905
4906template <class _InputIterator1, class _InputIterator2, class _Compare>
4907inline _LIBCPP_INLINE_VISIBILITY
4908bool
4909includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
4910         _Compare __comp)
4911{
4912#ifdef _LIBCPP_DEBUG
4913    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4914    __debug_less<_Compare> __c(__comp);
4915    return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
4916#else  // _LIBCPP_DEBUG
4917    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4918    return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
4919#endif  // _LIBCPP_DEBUG
4920}
4921
4922template <class _InputIterator1, class _InputIterator2>
4923inline _LIBCPP_INLINE_VISIBILITY
4924bool
4925includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
4926{
4927    return _STD::includes(__first1, __last1, __first2, __last2,
4928                          __less<typename iterator_traits<_InputIterator1>::value_type,
4929                                 typename iterator_traits<_InputIterator2>::value_type>());
4930}
4931
4932// set_union
4933
4934template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4935_OutputIterator
4936__set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4937            _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4938{
4939    for (; __first1 != __last1; ++__result)
4940    {
4941        if (__first2 == __last2)
4942            return _STD::copy(__first1, __last1, __result);
4943        if (__comp(*__first2, *__first1))
4944        {
4945            *__result = *__first2;
4946            ++__first2;
4947        }
4948        else
4949        {
4950            *__result = *__first1;
4951            if (!__comp(*__first1, *__first2))
4952                ++__first2;
4953            ++__first1;
4954        }
4955    }
4956    return _STD::copy(__first2, __last2, __result);
4957}
4958
4959template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4960inline _LIBCPP_INLINE_VISIBILITY
4961_OutputIterator
4962set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4963          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4964{
4965#ifdef _LIBCPP_DEBUG
4966    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4967    __debug_less<_Compare> __c(__comp);
4968    return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
4969#else  // _LIBCPP_DEBUG
4970    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4971    return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4972#endif  // _LIBCPP_DEBUG
4973}
4974
4975template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4976inline _LIBCPP_INLINE_VISIBILITY
4977_OutputIterator
4978set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4979          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4980{
4981    return _STD::set_union(__first1, __last1, __first2, __last2, __result,
4982                          __less<typename iterator_traits<_InputIterator1>::value_type,
4983                                 typename iterator_traits<_InputIterator2>::value_type>());
4984}
4985
4986// set_intersection
4987
4988template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4989_OutputIterator
4990__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
4991                   _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4992{
4993    while (__first1 != __last1 && __first2 != __last2)
4994    {
4995        if (__comp(*__first1, *__first2))
4996            ++__first1;
4997        else
4998        {
4999            if (!__comp(*__first2, *__first1))
5000            {
5001                *__result = *__first1;
5002                ++__result;
5003                ++__first1;
5004            }
5005            ++__first2;
5006        }
5007    }
5008    return __result;
5009}
5010
5011template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5012inline _LIBCPP_INLINE_VISIBILITY
5013_OutputIterator
5014set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5015                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5016{
5017#ifdef _LIBCPP_DEBUG
5018    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5019    __debug_less<_Compare> __c(__comp);
5020    return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5021#else  // _LIBCPP_DEBUG
5022    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5023    return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5024#endif  // _LIBCPP_DEBUG
5025}
5026
5027template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5028inline _LIBCPP_INLINE_VISIBILITY
5029_OutputIterator
5030set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5031                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5032{
5033    return _STD::set_intersection(__first1, __last1, __first2, __last2, __result,
5034                                  __less<typename iterator_traits<_InputIterator1>::value_type,
5035                                         typename iterator_traits<_InputIterator2>::value_type>());
5036}
5037
5038// set_difference
5039
5040template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5041_OutputIterator
5042__set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5043                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5044{
5045    while (__first1 != __last1)
5046    {
5047        if (__first2 == __last2)
5048            return _STD::copy(__first1, __last1, __result);
5049        if (__comp(*__first1, *__first2))
5050        {
5051            *__result = *__first1;
5052            ++__result;
5053            ++__first1;
5054        }
5055        else
5056        {
5057            if (!__comp(*__first2, *__first1))
5058                ++__first1;
5059            ++__first2;
5060        }
5061    }
5062    return __result;
5063}
5064
5065template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5066inline _LIBCPP_INLINE_VISIBILITY
5067_OutputIterator
5068set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5069               _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5070{
5071#ifdef _LIBCPP_DEBUG
5072    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5073    __debug_less<_Compare> __c(__comp);
5074    return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5075#else  // _LIBCPP_DEBUG
5076    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5077    return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5078#endif  // _LIBCPP_DEBUG
5079}
5080
5081template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5082inline _LIBCPP_INLINE_VISIBILITY
5083_OutputIterator
5084set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5085               _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5086{
5087    return _STD::set_difference(__first1, __last1, __first2, __last2, __result,
5088                                __less<typename iterator_traits<_InputIterator1>::value_type,
5089                                       typename iterator_traits<_InputIterator2>::value_type>());
5090}
5091
5092// set_symmetric_difference
5093
5094template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5095_OutputIterator
5096__set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5097                           _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5098{
5099    while (__first1 != __last1)
5100    {
5101        if (__first2 == __last2)
5102            return _STD::copy(__first1, __last1, __result);
5103        if (__comp(*__first1, *__first2))
5104        {
5105            *__result = *__first1;
5106            ++__result;
5107            ++__first1;
5108        }
5109        else
5110        {
5111            if (__comp(*__first2, *__first1))
5112            {
5113                *__result = *__first2;
5114                ++__result;
5115            }
5116            else
5117                ++__first1;
5118            ++__first2;
5119        }
5120    }
5121    return _STD::copy(__first2, __last2, __result);
5122}
5123
5124template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5125inline _LIBCPP_INLINE_VISIBILITY
5126_OutputIterator
5127set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5128                         _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5129{
5130#ifdef _LIBCPP_DEBUG
5131    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5132    __debug_less<_Compare> __c(__comp);
5133    return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5134#else  // _LIBCPP_DEBUG
5135    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5136    return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5137#endif  // _LIBCPP_DEBUG
5138}
5139
5140template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5141inline _LIBCPP_INLINE_VISIBILITY
5142_OutputIterator
5143set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5144                         _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5145{
5146    return _STD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
5147                                          __less<typename iterator_traits<_InputIterator1>::value_type,
5148                                                 typename iterator_traits<_InputIterator2>::value_type>());
5149}
5150
5151// lexicographical_compare
5152
5153template <class _Compare, class _InputIterator1, class _InputIterator2>
5154bool
5155__lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5156                          _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5157{
5158    for (; __first2 != __last2; ++__first1, ++__first2)
5159    {
5160        if (__first1 == __last1 || __comp(*__first1, *__first2))
5161            return true;
5162        if (__comp(*__first2, *__first1))
5163            return false;
5164    }
5165    return false;
5166}
5167
5168template <class _InputIterator1, class _InputIterator2, class _Compare>
5169inline _LIBCPP_INLINE_VISIBILITY
5170bool
5171lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5172                        _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5173{
5174#ifdef _LIBCPP_DEBUG
5175    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5176    __debug_less<_Compare> __c(__comp);
5177    return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5178#else  // _LIBCPP_DEBUG
5179    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5180    return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5181#endif  // _LIBCPP_DEBUG
5182}
5183
5184template <class _InputIterator1, class _InputIterator2>
5185inline _LIBCPP_INLINE_VISIBILITY
5186bool
5187lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5188                        _InputIterator2 __first2, _InputIterator2 __last2)
5189{
5190    return _STD::lexicographical_compare(__first1, __last1, __first2, __last2,
5191                                         __less<typename iterator_traits<_InputIterator1>::value_type,
5192                                                typename iterator_traits<_InputIterator2>::value_type>());
5193}
5194
5195// next_permutation
5196
5197template <class _Compare, class _BidirectionalIterator>
5198bool
5199__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5200{
5201    _BidirectionalIterator __i = __last;
5202    if (__first == __last || __first == --__i)
5203        return false;
5204    while (true)
5205    {
5206        _BidirectionalIterator __ip1 = __i;
5207        if (__comp(*--__i, *__ip1))
5208        {
5209            _BidirectionalIterator __j = __last;
5210            while (!__comp(*__i, *--__j))
5211                ;
5212            swap(*__i, *__j);
5213            _STD::reverse(__ip1, __last);
5214            return true;
5215        }
5216        if (__i == __first)
5217        {
5218            _STD::reverse(__first, __last);
5219            return false;
5220        }
5221    }
5222}
5223
5224template <class _BidirectionalIterator, class _Compare>
5225inline _LIBCPP_INLINE_VISIBILITY
5226bool
5227next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5228{
5229#ifdef _LIBCPP_DEBUG
5230    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5231    __debug_less<_Compare> __c(__comp);
5232    return __next_permutation<_Comp_ref>(__first, __last, __c);
5233#else  // _LIBCPP_DEBUG
5234    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5235    return __next_permutation<_Comp_ref>(__first, __last, __comp);
5236#endif  // _LIBCPP_DEBUG
5237}
5238
5239template <class _BidirectionalIterator>
5240inline _LIBCPP_INLINE_VISIBILITY
5241bool
5242next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5243{
5244    return _STD::next_permutation(__first, __last,
5245                                  __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5246}
5247
5248// prev_permutation
5249
5250template <class _Compare, class _BidirectionalIterator>
5251bool
5252__prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5253{
5254    _BidirectionalIterator __i = __last;
5255    if (__first == __last || __first == --__i)
5256        return false;
5257    while (true)
5258    {
5259        _BidirectionalIterator __ip1 = __i;
5260        if (__comp(*__ip1, *--__i))
5261        {
5262            _BidirectionalIterator __j = __last;
5263            while (!__comp(*--__j, *__i))
5264                ;
5265            swap(*__i, *__j);
5266            _STD::reverse(__ip1, __last);
5267            return true;
5268        }
5269        if (__i == __first)
5270        {
5271            _STD::reverse(__first, __last);
5272            return false;
5273        }
5274    }
5275}
5276
5277template <class _BidirectionalIterator, class _Compare>
5278inline _LIBCPP_INLINE_VISIBILITY
5279bool
5280prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5281{
5282#ifdef _LIBCPP_DEBUG
5283    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5284    __debug_less<_Compare> __c(__comp);
5285    return __prev_permutation<_Comp_ref>(__first, __last, __c);
5286#else  // _LIBCPP_DEBUG
5287    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5288    return __prev_permutation<_Comp_ref>(__first, __last, __comp);
5289#endif  // _LIBCPP_DEBUG
5290}
5291
5292template <class _BidirectionalIterator>
5293inline _LIBCPP_INLINE_VISIBILITY
5294bool
5295prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5296{
5297    return _STD::prev_permutation(__first, __last,
5298                                  __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5299}
5300
5301template <class _Tp>
5302inline _LIBCPP_INLINE_VISIBILITY
5303typename enable_if
5304<
5305    is_integral<_Tp>::value,
5306    _Tp
5307>::type
5308__rotate_left(_Tp __t, _Tp __n = 1)
5309{
5310    const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1);
5311    __n &= __bits;
5312    return static_cast<_Tp>((__t << __n) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> (__bits - __n)));
5313}
5314
5315template <class _Tp>
5316inline _LIBCPP_INLINE_VISIBILITY
5317typename enable_if
5318<
5319    is_integral<_Tp>::value,
5320    _Tp
5321>::type
5322__rotate_right(_Tp __t, _Tp __n = 1)
5323{
5324    const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1);
5325    __n &= __bits;
5326    return static_cast<_Tp>((__t << (__bits - __n)) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> __n));
5327}
5328
5329_LIBCPP_END_NAMESPACE_STD
5330
5331#endif  // _LIBCPP_ALGORITHM
5332