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