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