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