2 //===-------------------------- algorithm ---------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_ALGORITHM
12 #define _LIBCPP_ALGORITHM
17 #include <initializer_list>
22 template <class InputIterator, class Predicate>
24 all_of(InputIterator first, InputIterator last, Predicate pred);
26 template <class InputIterator, class Predicate>
28 any_of(InputIterator first, InputIterator last, Predicate pred);
30 template <class InputIterator, class Predicate>
32 none_of(InputIterator first, InputIterator last, Predicate pred);
34 template <class InputIterator, class Function>
36 for_each(InputIterator first, InputIterator last, Function f);
38 template <class InputIterator, class T>
40 find(InputIterator first, InputIterator last, const T& value);
42 template <class InputIterator, class Predicate>
44 find_if(InputIterator first, InputIterator last, Predicate pred);
46 template<class InputIterator, class Predicate>
48 find_if_not(InputIterator first, InputIterator last, Predicate pred);
50 template <class ForwardIterator1, class ForwardIterator2>
52 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
53 ForwardIterator2 first2, ForwardIterator2 last2);
55 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
57 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
58 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
60 template <class ForwardIterator1, class ForwardIterator2>
62 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
63 ForwardIterator2 first2, ForwardIterator2 last2);
65 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
67 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
68 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
70 template <class ForwardIterator>
72 adjacent_find(ForwardIterator first, ForwardIterator last);
74 template <class ForwardIterator, class BinaryPredicate>
76 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
78 template <class InputIterator, class T>
79 typename iterator_traits<InputIterator>::difference_type
80 count(InputIterator first, InputIterator last, const T& value);
82 template <class InputIterator, class Predicate>
83 typename iterator_traits<InputIterator>::difference_type
84 count_if(InputIterator first, InputIterator last, Predicate pred);
86 template <class InputIterator1, class InputIterator2>
87 pair<InputIterator1, InputIterator2>
88 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
90 template <class InputIterator1, class InputIterator2>
91 pair<InputIterator1, InputIterator2>
92 mismatch(InputIterator1 first1, InputIterator1 last1,
93 InputIterator2 first2, InputIterator2 last2); // **C++14**
95 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
96 pair<InputIterator1, InputIterator2>
97 mismatch(InputIterator1 first1, InputIterator1 last1,
98 InputIterator2 first2, BinaryPredicate pred);
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**
106 template <class InputIterator1, class InputIterator2>
108 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
110 template <class InputIterator1, class InputIterator2>
112 equal(InputIterator1 first1, InputIterator1 last1,
113 InputIterator2 first2, InputIterator2 last2); // **C++14**
115 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
117 equal(InputIterator1 first1, InputIterator1 last1,
118 InputIterator2 first2, BinaryPredicate pred);
120 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
122 equal(InputIterator1 first1, InputIterator1 last1,
123 InputIterator2 first2, InputIterator2 last2,
124 BinaryPredicate pred); // **C++14**
126 template<class ForwardIterator1, class ForwardIterator2>
128 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
129 ForwardIterator2 first2);
131 template<class ForwardIterator1, class ForwardIterator2>
133 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
134 ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**
136 template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
138 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
139 ForwardIterator2 first2, BinaryPredicate pred);
141 template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
143 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
144 ForwardIterator2 first2, ForwardIterator2 last2,
145 BinaryPredicate pred); // **C++14**
147 template <class ForwardIterator1, class ForwardIterator2>
149 search(ForwardIterator1 first1, ForwardIterator1 last1,
150 ForwardIterator2 first2, ForwardIterator2 last2);
152 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
154 search(ForwardIterator1 first1, ForwardIterator1 last1,
155 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
157 template <class ForwardIterator, class Size, class T>
159 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
161 template <class ForwardIterator, class Size, class T, class BinaryPredicate>
163 search_n(ForwardIterator first, ForwardIterator last,
164 Size count, const T& value, BinaryPredicate pred);
166 template <class InputIterator, class OutputIterator>
168 copy(InputIterator first, InputIterator last, OutputIterator result);
170 template<class InputIterator, class OutputIterator, class Predicate>
172 copy_if(InputIterator first, InputIterator last,
173 OutputIterator result, Predicate pred);
175 template<class InputIterator, class Size, class OutputIterator>
177 copy_n(InputIterator first, Size n, OutputIterator result);
179 template <class BidirectionalIterator1, class BidirectionalIterator2>
180 BidirectionalIterator2
181 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
182 BidirectionalIterator2 result);
184 template <class ForwardIterator1, class ForwardIterator2>
186 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
188 template <class ForwardIterator1, class ForwardIterator2>
190 iter_swap(ForwardIterator1 a, ForwardIterator2 b);
192 template <class InputIterator, class OutputIterator, class UnaryOperation>
194 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
196 template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
198 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
199 OutputIterator result, BinaryOperation binary_op);
201 template <class ForwardIterator, class T>
203 replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
205 template <class ForwardIterator, class Predicate, class T>
207 replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
209 template <class InputIterator, class OutputIterator, class T>
211 replace_copy(InputIterator first, InputIterator last, OutputIterator result,
212 const T& old_value, const T& new_value);
214 template <class InputIterator, class OutputIterator, class Predicate, class T>
216 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
218 template <class ForwardIterator, class T>
220 fill(ForwardIterator first, ForwardIterator last, const T& value);
222 template <class OutputIterator, class Size, class T>
224 fill_n(OutputIterator first, Size n, const T& value);
226 template <class ForwardIterator, class Generator>
228 generate(ForwardIterator first, ForwardIterator last, Generator gen);
230 template <class OutputIterator, class Size, class Generator>
232 generate_n(OutputIterator first, Size n, Generator gen);
234 template <class ForwardIterator, class T>
236 remove(ForwardIterator first, ForwardIterator last, const T& value);
238 template <class ForwardIterator, class Predicate>
240 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
242 template <class InputIterator, class OutputIterator, class T>
244 remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
246 template <class InputIterator, class OutputIterator, class Predicate>
248 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
250 template <class ForwardIterator>
252 unique(ForwardIterator first, ForwardIterator last);
254 template <class ForwardIterator, class BinaryPredicate>
256 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
258 template <class InputIterator, class OutputIterator>
260 unique_copy(InputIterator first, InputIterator last, OutputIterator result);
262 template <class InputIterator, class OutputIterator, class BinaryPredicate>
264 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
266 template <class BidirectionalIterator>
268 reverse(BidirectionalIterator first, BidirectionalIterator last);
270 template <class BidirectionalIterator, class OutputIterator>
272 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
274 template <class ForwardIterator>
276 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
278 template <class ForwardIterator, class OutputIterator>
280 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
282 template <class RandomAccessIterator>
284 random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14
286 template <class RandomAccessIterator, class RandomNumberGenerator>
288 random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
289 RandomNumberGenerator& rand); // deprecated in C++14
291 template<class RandomAccessIterator, class UniformRandomNumberGenerator>
292 void shuffle(RandomAccessIterator first, RandomAccessIterator last,
293 UniformRandomNumberGenerator&& g);
295 template <class InputIterator, class Predicate>
297 is_partitioned(InputIterator first, InputIterator last, Predicate pred);
299 template <class ForwardIterator, class Predicate>
301 partition(ForwardIterator first, ForwardIterator last, Predicate pred);
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,
310 template <class ForwardIterator, class Predicate>
312 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
314 template<class ForwardIterator, class Predicate>
316 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
318 template <class ForwardIterator>
320 is_sorted(ForwardIterator first, ForwardIterator last);
322 template <class ForwardIterator, class Compare>
324 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
326 template<class ForwardIterator>
328 is_sorted_until(ForwardIterator first, ForwardIterator last);
330 template <class ForwardIterator, class Compare>
332 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
334 template <class RandomAccessIterator>
336 sort(RandomAccessIterator first, RandomAccessIterator last);
338 template <class RandomAccessIterator, class Compare>
340 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
342 template <class RandomAccessIterator>
344 stable_sort(RandomAccessIterator first, RandomAccessIterator last);
346 template <class RandomAccessIterator, class Compare>
348 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
350 template <class RandomAccessIterator>
352 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
354 template <class RandomAccessIterator, class Compare>
356 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
358 template <class InputIterator, class RandomAccessIterator>
360 partial_sort_copy(InputIterator first, InputIterator last,
361 RandomAccessIterator result_first, RandomAccessIterator result_last);
363 template <class InputIterator, class RandomAccessIterator, class Compare>
365 partial_sort_copy(InputIterator first, InputIterator last,
366 RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
368 template <class RandomAccessIterator>
370 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
372 template <class RandomAccessIterator, class Compare>
374 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
376 template <class ForwardIterator, class T>
378 lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
380 template <class ForwardIterator, class T, class Compare>
382 lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
384 template <class ForwardIterator, class T>
386 upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
388 template <class ForwardIterator, class T, class Compare>
390 upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
392 template <class ForwardIterator, class T>
393 pair<ForwardIterator, ForwardIterator>
394 equal_range(ForwardIterator first, ForwardIterator last, const T& value);
396 template <class ForwardIterator, class T, class Compare>
397 pair<ForwardIterator, ForwardIterator>
398 equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
400 template <class ForwardIterator, class T>
402 binary_search(ForwardIterator first, ForwardIterator last, const T& value);
404 template <class ForwardIterator, class T, class Compare>
406 binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
408 template <class InputIterator1, class InputIterator2, class OutputIterator>
410 merge(InputIterator1 first1, InputIterator1 last1,
411 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
413 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
415 merge(InputIterator1 first1, InputIterator1 last1,
416 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
418 template <class BidirectionalIterator>
420 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
422 template <class BidirectionalIterator, class Compare>
424 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
426 template <class InputIterator1, class InputIterator2>
428 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
430 template <class InputIterator1, class InputIterator2, class Compare>
432 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
434 template <class InputIterator1, class InputIterator2, class OutputIterator>
436 set_union(InputIterator1 first1, InputIterator1 last1,
437 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
439 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
441 set_union(InputIterator1 first1, InputIterator1 last1,
442 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
444 template <class InputIterator1, class InputIterator2, class OutputIterator>
446 set_intersection(InputIterator1 first1, InputIterator1 last1,
447 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
449 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
451 set_intersection(InputIterator1 first1, InputIterator1 last1,
452 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
454 template <class InputIterator1, class InputIterator2, class OutputIterator>
456 set_difference(InputIterator1 first1, InputIterator1 last1,
457 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
459 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
461 set_difference(InputIterator1 first1, InputIterator1 last1,
462 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
464 template <class InputIterator1, class InputIterator2, class OutputIterator>
466 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
467 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
469 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
471 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
472 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
474 template <class RandomAccessIterator>
476 push_heap(RandomAccessIterator first, RandomAccessIterator last);
478 template <class RandomAccessIterator, class Compare>
480 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
482 template <class RandomAccessIterator>
484 pop_heap(RandomAccessIterator first, RandomAccessIterator last);
486 template <class RandomAccessIterator, class Compare>
488 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
490 template <class RandomAccessIterator>
492 make_heap(RandomAccessIterator first, RandomAccessIterator last);
494 template <class RandomAccessIterator, class Compare>
496 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
498 template <class RandomAccessIterator>
500 sort_heap(RandomAccessIterator first, RandomAccessIterator last);
502 template <class RandomAccessIterator, class Compare>
504 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
506 template <class RandomAccessIterator>
508 is_heap(RandomAccessIterator first, RandomAccessiterator last);
510 template <class RandomAccessIterator, class Compare>
512 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
514 template <class RandomAccessIterator>
516 is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
518 template <class RandomAccessIterator, class Compare>
520 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
522 template <class ForwardIterator>
524 min_element(ForwardIterator first, ForwardIterator last);
526 template <class ForwardIterator, class Compare>
528 min_element(ForwardIterator first, ForwardIterator last, Compare comp);
532 min(const T& a, const T& b); // constexpr in C++14
534 template <class T, class Compare>
536 min(const T& a, const T& b, Compare comp); // constexpr in C++14
540 min(initializer_list<T> t); // constexpr in C++14
542 template<class T, class Compare>
544 min(initializer_list<T> t, Compare comp); // constexpr in C++14
546 template <class ForwardIterator>
548 max_element(ForwardIterator first, ForwardIterator last);
550 template <class ForwardIterator, class Compare>
552 max_element(ForwardIterator first, ForwardIterator last, Compare comp);
556 max(const T& a, const T& b); // constexpr in C++14
558 template <class T, class Compare>
560 max(const T& a, const T& b, Compare comp); // constexpr in C++14
564 max(initializer_list<T> t); // constexpr in C++14
566 template<class T, class Compare>
568 max(initializer_list<T> t, Compare comp); // constexpr in C++14
570 template<class ForwardIterator>
571 pair<ForwardIterator, ForwardIterator>
572 minmax_element(ForwardIterator first, ForwardIterator last);
574 template<class ForwardIterator, class Compare>
575 pair<ForwardIterator, ForwardIterator>
576 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
579 pair<const T&, const T&>
580 minmax(const T& a, const T& b); // constexpr in C++14
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
588 minmax(initializer_list<T> t); // constexpr in C++14
590 template<class T, class Compare>
592 minmax(initializer_list<T> t, Compare comp); // constexpr in C++14
594 template <class InputIterator1, class InputIterator2>
596 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
598 template <class InputIterator1, class InputIterator2, class Compare>
600 lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
601 InputIterator2 first2, InputIterator2 last2, Compare comp);
603 template <class BidirectionalIterator>
605 next_permutation(BidirectionalIterator first, BidirectionalIterator last);
607 template <class BidirectionalIterator, class Compare>
609 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
611 template <class BidirectionalIterator>
613 prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
615 template <class BidirectionalIterator, class Compare>
617 prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
624 #include <initializer_list>
625 #include <type_traits>
632 #if defined(__IBMCPP__)
633 #include "support/ibm/support.h"
635 #if defined(_LIBCPP_MSVCRT) || defined(__MINGW32__)
636 #include "support/win32/support.h"
639 #include <__undef_min_max>
643 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
644 #pragma GCC system_header
647 _LIBCPP_BEGIN_NAMESPACE_STD
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>
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;}
662 struct __equal_to<_T1, _T1>
664 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
665 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
669 struct __equal_to<const _T1, _T1>
671 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
672 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
676 struct __equal_to<_T1, const _T1>
678 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
679 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
682 template <class _T1, class _T2 = _T1>
685 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
686 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
688 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
689 bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;}
691 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
692 bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;}
694 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
695 bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;}
699 struct __less<_T1, _T1>
701 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
702 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
706 struct __less<const _T1, _T1>
708 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
709 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
713 struct __less<_T1, const _T1>
715 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
716 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
719 template <class _Predicate>
725 _LIBCPP_INLINE_VISIBILITY __negate() {}
727 _LIBCPP_INLINE_VISIBILITY
728 explicit __negate(_Predicate __p) : __p_(__p) {}
731 _LIBCPP_INLINE_VISIBILITY
732 bool operator()(const _T1& __x) {return !__p_(__x);}
734 template <class _T1, class _T2>
735 _LIBCPP_INLINE_VISIBILITY
736 bool operator()(const _T1& __x, const _T2& __y) {return !__p_(__x, __y);}
741 template <class _Compare>
745 __debug_less(_Compare& __c) : __comp_(__c) {}
746 template <class _Tp, class _Up>
747 bool operator()(const _Tp& __x, const _Up& __y)
749 bool __r = __comp_(__x, __y);
751 _LIBCPP_ASSERT(!__comp_(__y, __x), "Comparator does not induce a strict weak ordering");
756 #endif // _LIBCPP_DEBUG
758 // Precondition: __x != 0
759 inline _LIBCPP_INLINE_VISIBILITY
763 return static_cast<unsigned>(__builtin_ctz(__x));
766 inline _LIBCPP_INLINE_VISIBILITY
768 __ctz(unsigned long __x)
770 return static_cast<unsigned long>(__builtin_ctzl(__x));
773 inline _LIBCPP_INLINE_VISIBILITY
775 __ctz(unsigned long long __x)
777 return static_cast<unsigned long long>(__builtin_ctzll(__x));
780 // Precondition: __x != 0
781 inline _LIBCPP_INLINE_VISIBILITY
785 return static_cast<unsigned>(__builtin_clz(__x));
788 inline _LIBCPP_INLINE_VISIBILITY
790 __clz(unsigned long __x)
792 return static_cast<unsigned long>(__builtin_clzl (__x));
795 inline _LIBCPP_INLINE_VISIBILITY
797 __clz(unsigned long long __x)
799 return static_cast<unsigned long long>(__builtin_clzll(__x));
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);}
808 template <class _InputIterator, class _Predicate>
809 inline _LIBCPP_INLINE_VISIBILITY
811 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
813 for (; __first != __last; ++__first)
814 if (!__pred(*__first))
821 template <class _InputIterator, class _Predicate>
822 inline _LIBCPP_INLINE_VISIBILITY
824 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
826 for (; __first != __last; ++__first)
827 if (__pred(*__first))
834 template <class _InputIterator, class _Predicate>
835 inline _LIBCPP_INLINE_VISIBILITY
837 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
839 for (; __first != __last; ++__first)
840 if (__pred(*__first))
847 template <class _InputIterator, class _Function>
848 inline _LIBCPP_INLINE_VISIBILITY
850 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
852 for (; __first != __last; ++__first)
854 return _VSTD::move(__f); // explicitly moved for (emulated) C++03
859 template <class _InputIterator, class _Tp>
860 inline _LIBCPP_INLINE_VISIBILITY
862 find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
864 for (; __first != __last; ++__first)
865 if (*__first == __value_)
872 template <class _InputIterator, class _Predicate>
873 inline _LIBCPP_INLINE_VISIBILITY
875 find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
877 for (; __first != __last; ++__first)
878 if (__pred(*__first))
885 template<class _InputIterator, class _Predicate>
886 inline _LIBCPP_INLINE_VISIBILITY
888 find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
890 for (; __first != __last; ++__first)
891 if (!__pred(*__first))
898 template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
900 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
901 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
902 forward_iterator_tag, forward_iterator_tag)
904 // modeled after search algorithm
905 _ForwardIterator1 __r = __last1; // __last1 is the "default" answer
906 if (__first2 == __last2)
912 if (__first1 == __last1) // if source exhausted return last correct answer
913 return __r; // (or __last1 if never found)
914 if (__pred(*__first1, *__first2))
918 // *__first1 matches *__first2, now match elements after here
919 _ForwardIterator1 __m1 = __first1;
920 _ForwardIterator2 __m2 = __first2;
923 if (++__m2 == __last2)
924 { // Pattern exhaused, record answer and search for another one
929 if (++__m1 == __last1) // Source exhausted, return last answer
931 if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first
935 } // else there is a match, check next elements
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)
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;
954 // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks
957 if (__first1 == __l1) // return __last1 if no element matches *__first2
959 if (__pred(*--__l1, *__l2))
962 // *__l1 matches *__l2, now match elements before here
963 _BidirectionalIterator1 __m1 = __l1;
964 _BidirectionalIterator2 __m2 = __l2;
967 if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern)
969 if (__m1 == __first1) // Otherwise if source exhaused, pattern not found
971 if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1
974 } // else there is a match, check next elements
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)
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;
989 typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;
992 const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here
993 _RandomAccessIterator1 __l1 = __last1;
994 _RandomAccessIterator2 __l2 = __last2;
1002 if (__pred(*--__l1, *__l2))
1005 _RandomAccessIterator1 __m1 = __l1;
1006 _RandomAccessIterator2 __m2 = __l2;
1009 if (__m2 == __first2)
1011 // no need to check range on __m1 because __s guarantees we have enough source
1012 if (!__pred(*--__m1, *--__m2))
1020 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1021 inline _LIBCPP_INLINE_VISIBILITY
1023 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1024 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
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());
1032 template <class _ForwardIterator1, class _ForwardIterator2>
1033 inline _LIBCPP_INLINE_VISIBILITY
1035 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1036 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
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>());
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)
1050 for (; __first1 != __last1; ++__first1)
1051 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1052 if (__pred(*__first1, *__j))
1058 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1059 inline _LIBCPP_INLINE_VISIBILITY
1061 find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1062 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1064 return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred);
1067 template <class _ForwardIterator1, class _ForwardIterator2>
1068 inline _LIBCPP_INLINE_VISIBILITY
1070 find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1071 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
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>());
1080 template <class _ForwardIterator, class _BinaryPredicate>
1081 inline _LIBCPP_INLINE_VISIBILITY
1083 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
1085 if (__first != __last)
1087 _ForwardIterator __i = __first;
1088 while (++__i != __last)
1090 if (__pred(*__first, *__i))
1098 template <class _ForwardIterator>
1099 inline _LIBCPP_INLINE_VISIBILITY
1101 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
1103 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1104 return _VSTD::adjacent_find(__first, __last, __equal_to<__v>());
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_)
1114 typename iterator_traits<_InputIterator>::difference_type __r(0);
1115 for (; __first != __last; ++__first)
1116 if (*__first == __value_)
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)
1128 typename iterator_traits<_InputIterator>::difference_type __r(0);
1129 for (; __first != __last; ++__first)
1130 if (__pred(*__first))
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)
1143 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1144 if (!__pred(*__first1, *__first2))
1146 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1149 template <class _InputIterator1, class _InputIterator2>
1150 inline _LIBCPP_INLINE_VISIBILITY
1151 pair<_InputIterator1, _InputIterator2>
1152 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
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>());
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)
1167 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1168 if (!__pred(*__first1, *__first2))
1170 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
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)
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>());
1187 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1188 inline _LIBCPP_INLINE_VISIBILITY
1190 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred)
1192 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1193 if (!__pred(*__first1, *__first2))
1198 template <class _InputIterator1, class _InputIterator2>
1199 inline _LIBCPP_INLINE_VISIBILITY
1201 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
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>());
1208 #if _LIBCPP_STD_VER > 11
1209 template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2>
1210 inline _LIBCPP_INLINE_VISIBILITY
1212 __equal(_InputIterator1 __first1, _InputIterator1 __last1,
1213 _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred,
1214 input_iterator_tag, input_iterator_tag )
1216 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1217 if (!__pred(*__first1, *__first2))
1219 return __first1 == __last1 && __first2 == __last2;
1222 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1223 inline _LIBCPP_INLINE_VISIBILITY
1225 __equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1226 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1227 random_access_iterator_tag, random_access_iterator_tag )
1229 if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
1231 return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2,
1232 typename add_lvalue_reference<_BinaryPredicate>::type>
1233 (__first1, __last1, __first2, __pred );
1236 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1237 inline _LIBCPP_INLINE_VISIBILITY
1239 equal(_InputIterator1 __first1, _InputIterator1 __last1,
1240 _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred )
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());
1248 template <class _InputIterator1, class _InputIterator2>
1249 inline _LIBCPP_INLINE_VISIBILITY
1251 equal(_InputIterator1 __first1, _InputIterator1 __last1,
1252 _InputIterator2 __first2, _InputIterator2 __last2)
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());
1264 template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1266 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1267 _ForwardIterator2 __first2, _BinaryPredicate __pred)
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))
1275 // __first1 != __last1 && *__first1 != *__first2
1276 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1277 _D1 __l1 = _VSTD::distance(__first1, __last1);
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)
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))
1290 // Count number of *__i in [f2, l2)
1292 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1293 if (__pred(*__i, *__j))
1297 // Count number of *__i in [__i, l1) (we can start with 1)
1299 for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
1300 if (__pred(*__i, *__j))
1310 template<class _ForwardIterator1, class _ForwardIterator2>
1311 inline _LIBCPP_INLINE_VISIBILITY
1313 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1314 _ForwardIterator2 __first2)
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>());
1321 #if _LIBCPP_STD_VER > 11
1322 template<class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
1324 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1325 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1326 _BinaryPredicate __pred,
1327 forward_iterator_tag, forward_iterator_tag )
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))
1333 return __first1 == __last1 && __first2 == __last2;
1335 // __first1 != __last1 && __first2 != __last2 && *__first1 != *__first2
1336 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1337 _D1 __l1 = _VSTD::distance(__first1, __last1);
1339 typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2;
1340 _D2 __l2 = _VSTD::distance(__first2, __last2);
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)
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))
1353 // Count number of *__i in [f2, l2)
1355 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1356 if (__pred(*__i, *__j))
1360 // Count number of *__i in [__i, l1) (we can start with 1)
1362 for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
1363 if (__pred(*__i, *__j))
1373 template<class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1375 __is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1,
1376 _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2,
1377 _BinaryPredicate __pred,
1378 random_access_iterator_tag, random_access_iterator_tag )
1380 if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
1382 return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2,
1383 typename add_lvalue_reference<_BinaryPredicate>::type>
1384 (__first1, __last1, __first2, __pred );
1387 template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1388 inline _LIBCPP_INLINE_VISIBILITY
1390 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1391 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1392 _BinaryPredicate __pred )
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());
1400 template<class _ForwardIterator1, class _ForwardIterator2>
1401 inline _LIBCPP_INLINE_VISIBILITY
1403 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1404 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
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());
1417 template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
1419 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1420 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
1421 forward_iterator_tag, forward_iterator_tag)
1423 if (__first2 == __last2)
1424 return __first1; // Everything matches an empty sequence
1427 // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks
1430 if (__first1 == __last1) // return __last1 if no element matches *__first2
1432 if (__pred(*__first1, *__first2))
1436 // *__first1 matches *__first2, now match elements after here
1437 _ForwardIterator1 __m1 = __first1;
1438 _ForwardIterator2 __m2 = __first2;
1441 if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern)
1443 if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found
1445 if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1
1449 } // else there is a match, check next elements
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)
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;
1466 _D1 __len1 = __last1 - __first1;
1467 if (__len1 < __len2)
1469 const _RandomAccessIterator1 __s = __last1 - (__len2 - 1); // Start of pattern match can't go beyond here
1472 #if !_LIBCPP_UNROLL_LOOPS
1475 if (__first1 == __s)
1477 if (__pred(*__first1, *__first2))
1481 #else // !_LIBCPP_UNROLL_LOOPS
1482 for (_D1 __loop_unroll = (__s - __first1) / 4; __loop_unroll > 0; --__loop_unroll)
1484 if (__pred(*__first1, *__first2))
1486 if (__pred(*++__first1, *__first2))
1488 if (__pred(*++__first1, *__first2))
1490 if (__pred(*++__first1, *__first2))
1494 switch (__s - __first1)
1497 if (__pred(*__first1, *__first2))
1501 if (__pred(*__first1, *__first2))
1505 if (__pred(*__first1, *__first2))
1511 #endif // !_LIBCPP_UNROLL_LOOPS
1512 _RandomAccessIterator1 __m1 = __first1;
1513 _RandomAccessIterator2 __m2 = __first2;
1514 #if !_LIBCPP_UNROLL_LOOPS
1517 if (++__m2 == __last2)
1519 ++__m1; // no need to check range on __m1 because __s guarantees we have enough source
1520 if (!__pred(*__m1, *__m2))
1526 #else // !_LIBCPP_UNROLL_LOOPS
1529 for (_D2 __loop_unroll = (__last2 - __m2) / 4; __loop_unroll > 0; --__loop_unroll)
1531 if (!__pred(*__m1, *__m2))
1533 if (!__pred(*++__m1, *++__m2))
1535 if (!__pred(*++__m1, *++__m2))
1537 if (!__pred(*++__m1, *++__m2))
1542 switch (__last2 - __m2)
1545 if (!__pred(*__m1, *__m2))
1550 if (!__pred(*__m1, *__m2))
1555 if (!__pred(*__m1, *__m2))
1562 #endif // !_LIBCPP_UNROLL_LOOPS
1566 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1567 inline _LIBCPP_INLINE_VISIBILITY
1569 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1570 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
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());
1578 template <class _ForwardIterator1, class _ForwardIterator2>
1579 inline _LIBCPP_INLINE_VISIBILITY
1581 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1582 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
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>());
1591 template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp>
1593 __search_n(_ForwardIterator __first, _ForwardIterator __last,
1594 _Size __count, const _Tp& __value_, _BinaryPredicate __pred, forward_iterator_tag)
1600 // Find first element in sequence that matchs __value_, with a mininum of loop checks
1603 if (__first == __last) // return __last if no element matches __value_
1605 if (__pred(*__first, __value_))
1609 // *__first matches __value_, now match elements after here
1610 _ForwardIterator __m = __first;
1614 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1616 if (++__m == __last) // Otherwise if source exhaused, pattern not found
1618 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1623 } // else there is a match, check next elements
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)
1635 _Size __len = static_cast<_Size>(__last - __first);
1636 if (__len < __count)
1638 const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here
1641 // Find first element in sequence that matchs __value_, with a mininum of loop checks
1644 if (__first >= __s) // return __last if no element matches __value_
1646 if (__pred(*__first, __value_))
1650 // *__first matches __value_, now match elements after here
1651 _RandomAccessIterator __m = __first;
1655 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
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
1663 } // else there is a match, check next elements
1668 template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
1669 inline _LIBCPP_INLINE_VISIBILITY
1671 search_n(_ForwardIterator __first, _ForwardIterator __last,
1672 _Size __count, const _Tp& __value_, _BinaryPredicate __pred)
1674 return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>
1675 (__first, __last, __count, __value_, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
1678 template <class _ForwardIterator, class _Size, class _Tp>
1679 inline _LIBCPP_INLINE_VISIBILITY
1681 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
1683 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1684 return _VSTD::search_n(__first, __last, __count, __value_, __equal_to<__v, _Tp>());
1689 template <class _Iter>
1690 struct __libcpp_is_trivial_iterator
1692 static const bool value = is_pointer<_Iter>::value;
1695 template <class _Iter>
1696 struct __libcpp_is_trivial_iterator<move_iterator<_Iter> >
1698 static const bool value = is_pointer<_Iter>::value;
1701 template <class _Iter>
1702 struct __libcpp_is_trivial_iterator<__wrap_iter<_Iter> >
1704 static const bool value = is_pointer<_Iter>::value;
1707 template <class _Iter>
1708 inline _LIBCPP_INLINE_VISIBILITY
1710 __unwrap_iter(_Iter __i)
1715 template <class _Tp>
1716 inline _LIBCPP_INLINE_VISIBILITY
1719 is_trivially_copy_assignable<_Tp>::value,
1722 __unwrap_iter(move_iterator<_Tp*> __i)
1727 #if _LIBCPP_DEBUG_LEVEL < 2
1729 template <class _Tp>
1730 inline _LIBCPP_INLINE_VISIBILITY
1733 is_trivially_copy_assignable<_Tp>::value,
1736 __unwrap_iter(__wrap_iter<_Tp*> __i)
1741 #endif // _LIBCPP_DEBUG_LEVEL < 2
1743 template <class _InputIterator, class _OutputIterator>
1744 inline _LIBCPP_INLINE_VISIBILITY
1746 __copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1748 for (; __first != __last; ++__first, (void) ++__result)
1749 *__result = *__first;
1753 template <class _Tp, class _Up>
1754 inline _LIBCPP_INLINE_VISIBILITY
1757 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1758 is_trivially_copy_assignable<_Up>::value,
1761 __copy(_Tp* __first, _Tp* __last, _Up* __result)
1763 const size_t __n = static_cast<size_t>(__last - __first);
1764 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1765 return __result + __n;
1768 template <class _InputIterator, class _OutputIterator>
1769 inline _LIBCPP_INLINE_VISIBILITY
1771 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1773 return _VSTD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1778 template <class _BidirectionalIterator, class _OutputIterator>
1779 inline _LIBCPP_INLINE_VISIBILITY
1781 __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
1783 while (__first != __last)
1784 *--__result = *--__last;
1788 template <class _Tp, class _Up>
1789 inline _LIBCPP_INLINE_VISIBILITY
1792 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1793 is_trivially_copy_assignable<_Up>::value,
1796 __copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
1798 const size_t __n = static_cast<size_t>(__last - __first);
1800 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1804 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1805 inline _LIBCPP_INLINE_VISIBILITY
1806 _BidirectionalIterator2
1807 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1808 _BidirectionalIterator2 __result)
1810 return _VSTD::__copy_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1815 template<class _InputIterator, class _OutputIterator, class _Predicate>
1816 inline _LIBCPP_INLINE_VISIBILITY
1818 copy_if(_InputIterator __first, _InputIterator __last,
1819 _OutputIterator __result, _Predicate __pred)
1821 for (; __first != __last; ++__first)
1823 if (__pred(*__first))
1825 *__result = *__first;
1834 template<class _InputIterator, class _Size, class _OutputIterator>
1835 inline _LIBCPP_INLINE_VISIBILITY
1838 __is_input_iterator<_InputIterator>::value &&
1839 !__is_random_access_iterator<_InputIterator>::value,
1842 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1846 *__result = *__first;
1848 for (--__n; __n > 0; --__n)
1851 *__result = *__first;
1858 template<class _InputIterator, class _Size, class _OutputIterator>
1859 inline _LIBCPP_INLINE_VISIBILITY
1862 __is_random_access_iterator<_InputIterator>::value,
1865 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1867 return _VSTD::copy(__first, __first + __n, __result);
1872 template <class _InputIterator, class _OutputIterator>
1873 inline _LIBCPP_INLINE_VISIBILITY
1875 __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1877 for (; __first != __last; ++__first, (void) ++__result)
1878 *__result = _VSTD::move(*__first);
1882 template <class _Tp, class _Up>
1883 inline _LIBCPP_INLINE_VISIBILITY
1886 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1887 is_trivially_copy_assignable<_Up>::value,
1890 __move(_Tp* __first, _Tp* __last, _Up* __result)
1892 const size_t __n = static_cast<size_t>(__last - __first);
1893 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1894 return __result + __n;
1897 template <class _InputIterator, class _OutputIterator>
1898 inline _LIBCPP_INLINE_VISIBILITY
1900 move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1902 return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1907 template <class _InputIterator, class _OutputIterator>
1908 inline _LIBCPP_INLINE_VISIBILITY
1910 __move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1912 while (__first != __last)
1913 *--__result = _VSTD::move(*--__last);
1917 template <class _Tp, class _Up>
1918 inline _LIBCPP_INLINE_VISIBILITY
1921 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1922 is_trivially_copy_assignable<_Up>::value,
1925 __move_backward(_Tp* __first, _Tp* __last, _Up* __result)
1927 const size_t __n = static_cast<size_t>(__last - __first);
1929 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1933 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1934 inline _LIBCPP_INLINE_VISIBILITY
1935 _BidirectionalIterator2
1936 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1937 _BidirectionalIterator2 __result)
1939 return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1944 // moved to <type_traits> for better swap / noexcept support
1948 template <class _InputIterator, class _OutputIterator, class _UnaryOperation>
1949 inline _LIBCPP_INLINE_VISIBILITY
1951 transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op)
1953 for (; __first != __last; ++__first, (void) ++__result)
1954 *__result = __op(*__first);
1958 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation>
1959 inline _LIBCPP_INLINE_VISIBILITY
1961 transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
1962 _OutputIterator __result, _BinaryOperation __binary_op)
1964 for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result)
1965 *__result = __binary_op(*__first1, *__first2);
1971 template <class _ForwardIterator, class _Tp>
1972 inline _LIBCPP_INLINE_VISIBILITY
1974 replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value)
1976 for (; __first != __last; ++__first)
1977 if (*__first == __old_value)
1978 *__first = __new_value;
1983 template <class _ForwardIterator, class _Predicate, class _Tp>
1984 inline _LIBCPP_INLINE_VISIBILITY
1986 replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value)
1988 for (; __first != __last; ++__first)
1989 if (__pred(*__first))
1990 *__first = __new_value;
1995 template <class _InputIterator, class _OutputIterator, class _Tp>
1996 inline _LIBCPP_INLINE_VISIBILITY
1998 replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1999 const _Tp& __old_value, const _Tp& __new_value)
2001 for (; __first != __last; ++__first, (void) ++__result)
2002 if (*__first == __old_value)
2003 *__result = __new_value;
2005 *__result = *__first;
2011 template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp>
2012 inline _LIBCPP_INLINE_VISIBILITY
2014 replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
2015 _Predicate __pred, const _Tp& __new_value)
2017 for (; __first != __last; ++__first, (void) ++__result)
2018 if (__pred(*__first))
2019 *__result = __new_value;
2021 *__result = *__first;
2027 template <class _OutputIterator, class _Size, class _Tp>
2028 inline _LIBCPP_INLINE_VISIBILITY
2030 __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2032 for (; __n > 0; ++__first, (void) --__n)
2033 *__first = __value_;
2037 template <class _Tp, class _Size, class _Up>
2038 inline _LIBCPP_INLINE_VISIBILITY
2041 is_integral<_Tp>::value && sizeof(_Tp) == 1 &&
2042 !is_same<_Tp, bool>::value &&
2043 is_integral<_Up>::value && sizeof(_Up) == 1,
2046 __fill_n(_Tp* __first, _Size __n,_Up __value_)
2049 _VSTD::memset(__first, (unsigned char)__value_, (size_t)(__n));
2050 return __first + __n;
2053 template <class _OutputIterator, class _Size, class _Tp>
2054 inline _LIBCPP_INLINE_VISIBILITY
2056 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2058 return _VSTD::__fill_n(__first, __n, __value_);
2063 template <class _ForwardIterator, class _Tp>
2064 inline _LIBCPP_INLINE_VISIBILITY
2066 __fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
2068 for (; __first != __last; ++__first)
2069 *__first = __value_;
2072 template <class _RandomAccessIterator, class _Tp>
2073 inline _LIBCPP_INLINE_VISIBILITY
2075 __fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag)
2077 _VSTD::fill_n(__first, __last - __first, __value_);
2080 template <class _ForwardIterator, class _Tp>
2081 inline _LIBCPP_INLINE_VISIBILITY
2083 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2085 _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category());
2090 template <class _ForwardIterator, class _Generator>
2091 inline _LIBCPP_INLINE_VISIBILITY
2093 generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
2095 for (; __first != __last; ++__first)
2101 template <class _OutputIterator, class _Size, class _Generator>
2102 inline _LIBCPP_INLINE_VISIBILITY
2104 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
2106 for (; __n > 0; ++__first, (void) --__n)
2113 template <class _ForwardIterator, class _Tp>
2115 remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2117 __first = _VSTD::find(__first, __last, __value_);
2118 if (__first != __last)
2120 _ForwardIterator __i = __first;
2121 while (++__i != __last)
2123 if (!(*__i == __value_))
2125 *__first = _VSTD::move(*__i);
2135 template <class _ForwardIterator, class _Predicate>
2137 remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2139 __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
2140 (__first, __last, __pred);
2141 if (__first != __last)
2143 _ForwardIterator __i = __first;
2144 while (++__i != __last)
2148 *__first = _VSTD::move(*__i);
2158 template <class _InputIterator, class _OutputIterator, class _Tp>
2159 inline _LIBCPP_INLINE_VISIBILITY
2161 remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_)
2163 for (; __first != __last; ++__first)
2165 if (!(*__first == __value_))
2167 *__result = *__first;
2176 template <class _InputIterator, class _OutputIterator, class _Predicate>
2177 inline _LIBCPP_INLINE_VISIBILITY
2179 remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
2181 for (; __first != __last; ++__first)
2183 if (!__pred(*__first))
2185 *__result = *__first;
2194 template <class _ForwardIterator, class _BinaryPredicate>
2196 unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
2198 __first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type>
2199 (__first, __last, __pred);
2200 if (__first != __last)
2204 _ForwardIterator __i = __first;
2205 for (++__i; ++__i != __last;)
2206 if (!__pred(*__first, *__i))
2207 *++__first = _VSTD::move(*__i);
2213 template <class _ForwardIterator>
2214 inline _LIBCPP_INLINE_VISIBILITY
2216 unique(_ForwardIterator __first, _ForwardIterator __last)
2218 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
2219 return _VSTD::unique(__first, __last, __equal_to<__v>());
2224 template <class _BinaryPredicate, class _InputIterator, class _OutputIterator>
2226 __unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2227 input_iterator_tag, output_iterator_tag)
2229 if (__first != __last)
2231 typename iterator_traits<_InputIterator>::value_type __t(*__first);
2234 while (++__first != __last)
2236 if (!__pred(__t, *__first))
2247 template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator>
2249 __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2250 forward_iterator_tag, output_iterator_tag)
2252 if (__first != __last)
2254 _ForwardIterator __i = __first;
2257 while (++__first != __last)
2259 if (!__pred(*__i, *__first))
2261 *__result = *__first;
2270 template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator>
2272 __unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred,
2273 input_iterator_tag, forward_iterator_tag)
2275 if (__first != __last)
2277 *__result = *__first;
2278 while (++__first != __last)
2279 if (!__pred(*__result, *__first))
2280 *++__result = *__first;
2286 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
2287 inline _LIBCPP_INLINE_VISIBILITY
2289 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred)
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());
2297 template <class _InputIterator, class _OutputIterator>
2298 inline _LIBCPP_INLINE_VISIBILITY
2300 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
2302 typedef typename iterator_traits<_InputIterator>::value_type __v;
2303 return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());
2308 template <class _BidirectionalIterator>
2309 inline _LIBCPP_INLINE_VISIBILITY
2311 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
2313 while (__first != __last)
2315 if (__first == --__last)
2317 swap(*__first, *__last);
2322 template <class _RandomAccessIterator>
2323 inline _LIBCPP_INLINE_VISIBILITY
2325 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
2327 if (__first != __last)
2328 for (; __first < --__last; ++__first)
2329 swap(*__first, *__last);
2332 template <class _BidirectionalIterator>
2333 inline _LIBCPP_INLINE_VISIBILITY
2335 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
2337 _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());
2342 template <class _BidirectionalIterator, class _OutputIterator>
2343 inline _LIBCPP_INLINE_VISIBILITY
2345 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
2347 for (; __first != __last; ++__result)
2348 *__result = *--__last;
2354 template <class _ForwardIterator>
2356 __rotate_left(_ForwardIterator __first, _ForwardIterator __last)
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);
2365 template <class _BidirectionalIterator>
2366 _BidirectionalIterator
2367 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
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);
2377 template <class _ForwardIterator>
2379 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2381 _ForwardIterator __i = __middle;
2384 swap(*__first, *__i);
2386 if (++__i == __last)
2388 if (__first == __middle)
2391 _ForwardIterator __r = __first;
2392 if (__first != __middle)
2397 swap(*__first, *__i);
2399 if (++__i == __last)
2401 if (__first == __middle)
2405 else if (__first == __middle)
2412 template<typename _Integral>
2413 inline _LIBCPP_INLINE_VISIBILITY
2415 __gcd(_Integral __x, _Integral __y)
2419 _Integral __t = __x % __y;
2426 template<typename _RandomAccessIterator>
2427 _RandomAccessIterator
2428 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
2430 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2431 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
2433 const difference_type __m1 = __middle - __first;
2434 const difference_type __m2 = __last - __middle;
2437 _VSTD::swap_ranges(__first, __middle, __middle);
2440 const difference_type __g = _VSTD::__gcd(__m1, __m2);
2441 for (_RandomAccessIterator __p = __first + __g; __p != __first;)
2443 value_type __t(_VSTD::move(*--__p));
2444 _RandomAccessIterator __p1 = __p;
2445 _RandomAccessIterator __p2 = __p1 + __m1;
2448 *__p1 = _VSTD::move(*__p2);
2450 const difference_type __d = __last - __p2;
2454 __p2 = __first + (__m1 - __d);
2455 } while (__p2 != __p);
2456 *__p1 = _VSTD::move(__t);
2458 return __first + __m2;
2461 template <class _ForwardIterator>
2462 inline _LIBCPP_INLINE_VISIBILITY
2464 __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
2465 _VSTD::forward_iterator_tag)
2467 typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type;
2468 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2470 if (_VSTD::next(__first) == __middle)
2471 return _VSTD::__rotate_left(__first, __last);
2473 return _VSTD::__rotate_forward(__first, __middle, __last);
2476 template <class _BidirectionalIterator>
2477 inline _LIBCPP_INLINE_VISIBILITY
2478 _BidirectionalIterator
2479 __rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
2480 _VSTD::bidirectional_iterator_tag)
2482 typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type;
2483 if (_VSTD::is_trivially_move_assignable<value_type>::value)
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);
2490 return _VSTD::__rotate_forward(__first, __middle, __last);
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)
2499 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
2500 if (_VSTD::is_trivially_move_assignable<value_type>::value)
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);
2508 return _VSTD::__rotate_forward(__first, __middle, __last);
2511 template <class _ForwardIterator>
2512 inline _LIBCPP_INLINE_VISIBILITY
2514 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2516 if (__first == __middle)
2518 if (__middle == __last)
2520 return _VSTD::__rotate(__first, __middle, __last,
2521 typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());
2526 template <class _ForwardIterator, class _OutputIterator>
2527 inline _LIBCPP_INLINE_VISIBILITY
2529 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
2531 return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));
2536 template <class _ForwardIterator, class _Compare>
2537 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2539 __min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2541 if (__first != __last)
2543 _ForwardIterator __i = __first;
2544 while (++__i != __last)
2545 if (__comp(*__i, *__first))
2551 template <class _ForwardIterator, class _Compare>
2552 inline _LIBCPP_INLINE_VISIBILITY
2554 min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2556 return __min_element(__first, __last, __comp);
2559 template <class _ForwardIterator>
2560 inline _LIBCPP_INLINE_VISIBILITY
2562 min_element(_ForwardIterator __first, _ForwardIterator __last)
2564 return __min_element(__first, __last,
2565 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2570 template <class _Tp, class _Compare>
2571 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2573 min(const _Tp& __a, const _Tp& __b, _Compare __comp)
2575 return __comp(__b, __a) ? __b : __a;
2578 template <class _Tp>
2579 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2581 min(const _Tp& __a, const _Tp& __b)
2583 return _VSTD::min(__a, __b, __less<_Tp>());
2586 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2588 template<class _Tp, class _Compare>
2589 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2591 min(initializer_list<_Tp> __t, _Compare __comp)
2593 return *__min_element(__t.begin(), __t.end(), __comp);
2597 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2599 min(initializer_list<_Tp> __t)
2601 return *__min_element(__t.begin(), __t.end(), __less<_Tp>());
2604 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2608 template <class _ForwardIterator, class _Compare>
2609 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2611 __max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2613 if (__first != __last)
2615 _ForwardIterator __i = __first;
2616 while (++__i != __last)
2617 if (__comp(*__first, *__i))
2624 template <class _ForwardIterator, class _Compare>
2625 inline _LIBCPP_INLINE_VISIBILITY
2627 max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2629 return __max_element(__first, __last, __comp);
2632 template <class _ForwardIterator>
2633 inline _LIBCPP_INLINE_VISIBILITY
2635 max_element(_ForwardIterator __first, _ForwardIterator __last)
2637 return __max_element(__first, __last,
2638 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2643 template <class _Tp, class _Compare>
2644 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2646 max(const _Tp& __a, const _Tp& __b, _Compare __comp)
2648 return __comp(__a, __b) ? __b : __a;
2651 template <class _Tp>
2652 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2654 max(const _Tp& __a, const _Tp& __b)
2656 return _VSTD::max(__a, __b, __less<_Tp>());
2659 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2661 template<class _Tp, class _Compare>
2662 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2664 max(initializer_list<_Tp> __t, _Compare __comp)
2666 return *__max_element(__t.begin(), __t.end(), __comp);
2670 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2672 max(initializer_list<_Tp> __t)
2674 return *__max_element(__t.begin(), __t.end(), __less<_Tp>());
2677 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2681 template <class _ForwardIterator, class _Compare>
2682 std::pair<_ForwardIterator, _ForwardIterator>
2683 minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2685 std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);
2686 if (__first != __last)
2688 if (++__first != __last)
2690 if (__comp(*__first, *__result.first))
2691 __result.first = __first;
2693 __result.second = __first;
2694 while (++__first != __last)
2696 _ForwardIterator __i = __first;
2697 if (++__first == __last)
2699 if (__comp(*__i, *__result.first))
2700 __result.first = __i;
2701 else if (!__comp(*__i, *__result.second))
2702 __result.second = __i;
2707 if (__comp(*__first, *__i))
2709 if (__comp(*__first, *__result.first))
2710 __result.first = __first;
2711 if (!__comp(*__i, *__result.second))
2712 __result.second = __i;
2716 if (__comp(*__i, *__result.first))
2717 __result.first = __i;
2718 if (!__comp(*__first, *__result.second))
2719 __result.second = __first;
2728 template <class _ForwardIterator>
2729 inline _LIBCPP_INLINE_VISIBILITY
2730 std::pair<_ForwardIterator, _ForwardIterator>
2731 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
2733 return _VSTD::minmax_element(__first, __last,
2734 __less<typename iterator_traits<_ForwardIterator>::value_type>());
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)
2744 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) :
2745 pair<const _Tp&, const _Tp&>(__a, __b);
2749 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2750 pair<const _Tp&, const _Tp&>
2751 minmax(const _Tp& __a, const _Tp& __b)
2753 return _VSTD::minmax(__a, __b, __less<_Tp>());
2756 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2758 template<class _Tp, class _Compare>
2759 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2761 minmax(initializer_list<_Tp> __t, _Compare __comp)
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 );
2769 if (__t.size() % 2 == 0)
2771 if (__comp(*__first, __result.first))
2772 __result.first = *__first;
2774 __result.second = *__first;
2778 while (__first != __last)
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;
2786 if (__comp(*__first, __result.first)) __result.first = *__first;
2787 if (__comp(__result.second, __prev)) __result.second = __prev;
2796 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2798 minmax(initializer_list<_Tp> __t)
2800 return _VSTD::minmax(__t, __less<_Tp>());
2803 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2807 // __independent_bits_engine
2809 template <unsigned long long _Xp, size_t _Rp>
2812 static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp
2813 : __log2_imp<_Xp, _Rp - 1>::value;
2816 template <unsigned long long _Xp>
2817 struct __log2_imp<_Xp, 0>
2819 static const size_t value = 0;
2822 template <size_t _Rp>
2823 struct __log2_imp<0, _Rp>
2825 static const size_t value = _Rp + 1;
2828 template <class _UI, _UI _Xp>
2831 static const size_t value = __log2_imp<_Xp,
2832 sizeof(_UI) * __CHAR_BIT__ - 1>::value;
2835 template<class _Engine, class _UIntType>
2836 class __independent_bits_engine
2840 typedef _UIntType result_type;
2843 typedef typename _Engine::result_type _Engine_result_type;
2844 typedef typename conditional
2846 sizeof(_Engine_result_type) <= sizeof(result_type),
2849 >::type _Working_result_type;
2856 _Working_result_type __y0_;
2857 _Working_result_type __y1_;
2858 _Engine_result_type __mask0_;
2859 _Engine_result_type __mask1_;
2861 #ifdef _LIBCPP_HAS_NO_CONSTEXPR
2862 static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
2863 + _Working_result_type(1);
2865 static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()
2866 + _Working_result_type(1);
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;
2873 // constructors and seeding functions
2874 __independent_bits_engine(_Engine& __e, size_t __w);
2876 // generating functions
2877 result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
2880 result_type __eval(false_type);
2881 result_type __eval(true_type);
2884 template<class _Engine, class _UIntType>
2885 __independent_bits_engine<_Engine, _UIntType>
2886 ::__independent_bits_engine(_Engine& __e, size_t __w)
2890 __n_ = __w_ / __m + (__w_ % __m != 0);
2891 __w0_ = __w_ / __n_;
2894 else if (__w0_ < _WDt)
2895 __y0_ = (_Rp >> __w0_) << __w0_;
2898 if (_Rp - __y0_ > __y0_ / __n_)
2901 __w0_ = __w_ / __n_;
2903 __y0_ = (_Rp >> __w0_) << __w0_;
2907 __n0_ = __n_ - __w_ % __n_;
2908 if (__w0_ < _WDt - 1)
2909 __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1);
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);
2919 template<class _Engine, class _UIntType>
2922 __independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
2924 return static_cast<result_type>(__e_() & __mask0_);
2927 template<class _Engine, class _UIntType>
2929 __independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
2931 result_type _Sp = 0;
2932 for (size_t __k = 0; __k < __n0_; ++__k)
2934 _Engine_result_type __u;
2937 __u = __e_() - _Engine::min();
2938 } while (__u >= __y0_);
2943 _Sp += __u & __mask0_;
2945 for (size_t __k = __n0_; __k < __n_; ++__k)
2947 _Engine_result_type __u;
2950 __u = __e_() - _Engine::min();
2951 } while (__u >= __y1_);
2952 if (__w0_ < _WDt - 1)
2956 _Sp += __u & __mask1_;
2961 // uniform_int_distribution
2963 template<class _IntType = int>
2964 class uniform_int_distribution
2968 typedef _IntType result_type;
2975 typedef uniform_int_distribution distribution_type;
2977 explicit param_type(result_type __a = 0,
2978 result_type __b = numeric_limits<result_type>::max())
2979 : __a_(__a), __b_(__b) {}
2981 result_type a() const {return __a_;}
2982 result_type b() const {return __b_;}
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);}
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) {}
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);
3006 // property functions
3007 result_type a() const {return __p_.a();}
3008 result_type b() const {return __p_.b();}
3010 param_type param() const {return __p_;}
3011 void param(const param_type& __p) {__p_ = __p;}
3013 result_type min() const {return a();}
3014 result_type max() const {return b();}
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);}
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)
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);
3034 const size_t _Dt = numeric_limits<_UIntType>::digits;
3035 typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
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)
3046 } while (__u >= _Rp);
3047 return static_cast<result_type>(__u + __p.a());
3050 class _LIBCPP_TYPE_VIS __rs_default;
3052 _LIBCPP_FUNC_VIS __rs_default __rs_get();
3054 class _LIBCPP_TYPE_VIS __rs_default
3056 static unsigned __c_;
3060 typedef uint_fast32_t result_type;
3062 static const result_type _Min = 0;
3063 static const result_type _Max = 0xFFFFFFFF;
3065 __rs_default(const __rs_default&);
3068 result_type operator()();
3070 static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
3071 static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
3073 friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
3076 _LIBCPP_FUNC_VIS __rs_default __rs_get();
3078 template <class _RandomAccessIterator>
3080 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
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;
3089 __rs_default __g = __rs_get();
3090 for (--__last, --__d; __first < __last; ++__first, --__d)
3092 difference_type __i = __uid(__g, _Pp(0, __d));
3093 if (__i != difference_type(0))
3094 swap(*__first, *(__first + __i));
3099 template <class _RandomAccessIterator, class _RandomNumberGenerator>
3101 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3102 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3103 _RandomNumberGenerator&& __rand)
3105 _RandomNumberGenerator& __rand)
3108 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3109 difference_type __d = __last - __first;
3112 for (--__last; __first < __last; ++__first, --__d)
3114 difference_type __i = __rand(__d);
3115 swap(*__first, *(__first + __i));
3120 template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
3121 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3122 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3123 _UniformRandomNumberGenerator&& __g)
3125 _UniformRandomNumberGenerator& __g)
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;
3135 for (--__last, --__d; __first < __last; ++__first, --__d)
3137 difference_type __i = __uid(__g, _Pp(0, __d));
3138 if (__i != difference_type(0))
3139 swap(*__first, *(__first + __i));
3144 template <class _InputIterator, class _Predicate>
3146 is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3148 for (; __first != __last; ++__first)
3149 if (!__pred(*__first))
3151 for (; __first != __last; ++__first)
3152 if (__pred(*__first))
3159 template <class _Predicate, class _ForwardIterator>
3161 __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
3165 if (__first == __last)
3167 if (!__pred(*__first))
3171 for (_ForwardIterator __p = __first; ++__p != __last;)
3175 swap(*__first, *__p);
3182 template <class _Predicate, class _BidirectionalIterator>
3183 _BidirectionalIterator
3184 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3185 bidirectional_iterator_tag)
3191 if (__first == __last)
3193 if (!__pred(*__first))
3199 if (__first == --__last)
3201 } while (!__pred(*__last));
3202 swap(*__first, *__last);
3207 template <class _ForwardIterator, class _Predicate>
3208 inline _LIBCPP_INLINE_VISIBILITY
3210 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3212 return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>
3213 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
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,
3225 for (; __first != __last; ++__first)
3227 if (__pred(*__first))
3229 *__out_true = *__first;
3234 *__out_false = *__first;
3238 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
3243 template<class _ForwardIterator, class _Predicate>
3245 partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3247 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3248 difference_type __len = _VSTD::distance(__first, __last);
3251 difference_type __l2 = __len / 2;
3252 _ForwardIterator __m = __first;
3253 _VSTD::advance(__m, __l2);
3267 template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
3269 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3270 _Distance __len, _Pair __p, forward_iterator_tag __fit)
3272 // *__first is known to be false
3278 _ForwardIterator __m = __first;
3281 swap(*__first, *__m);
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);
3297 _ForwardIterator __i = __first;
3298 while (++__i != __last)
3302 *__first = _VSTD::move(*__i);
3307 ::new(__t) value_type(_VSTD::move(*__i));
3308 __d.__incr((value_type*)0);
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
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
3320 // Else not enough buffer, do in place
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?????????????????
3328 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3329 _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
3330 // TTTFFFFF??????????
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))
3338 if (++__m1 == __last)
3339 goto __second_half_done;
3342 // TTTFFFFFTTTF??????
3344 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
3346 // TTTFFFFFTTTTTFFFFF
3348 return _VSTD::rotate(__first_false, __m, __second_false);
3349 // TTTTTTTTFFFFFFFFFF
3353 struct __return_temporary_buffer
3355 template <class _Tp>
3356 _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}
3359 template <class _Predicate, class _ForwardIterator>
3361 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3362 forward_iterator_tag)
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
3368 if (__first == __last)
3370 if (!__pred(*__first))
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)
3383 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3384 __h.reset(__p.first);
3386 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3387 (__first, __last, __pred, __len, __p, forward_iterator_tag());
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)
3395 // *__first is known to be false
3396 // *__last is known to be true
3400 swap(*__first, *__last);
3405 _BidirectionalIterator __m = __first;
3408 swap(*__first, *__m);
3409 swap(*__m, *__last);
3412 swap(*__m, *__last);
3413 swap(*__first, *__m);
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);
3427 _BidirectionalIterator __i = __first;
3428 while (++__i != __last)
3432 *__first = _VSTD::move(*__i);
3437 ::new(__t) value_type(_VSTD::move(*__i));
3438 __d.__incr((value_type*)0);
3442 // move *__last, known to be true
3443 *__first = _VSTD::move(*__i);
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
3452 // Else not enough buffer, do in place
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
3460 _BidirectionalIterator __m1 = __m;
3461 _BidirectionalIterator __first_false = __first;
3462 _Distance __len_half = __len2;
3463 while (!__pred(*--__m1))
3465 if (__m1 == __first)
3466 goto __first_half_done;
3469 // F???TFFF?????????T
3471 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3472 __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3474 // TTTFFFFF?????????T
3476 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3478 _BidirectionalIterator __second_false = __last;
3480 __len_half = __len - __len2;
3481 while (__pred(*__m1))
3483 if (++__m1 == __last)
3484 goto __second_half_done;
3487 // TTTFFFFFTTTF?????T
3489 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
3491 // TTTFFFFFTTTTTFFFFF
3493 return _VSTD::rotate(__first_false, __m, __second_false);
3494 // TTTTTTTTFFFFFFFFFF
3498 template <class _Predicate, class _BidirectionalIterator>
3499 _BidirectionalIterator
3500 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3501 bidirectional_iterator_tag)
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
3509 if (__first == __last)
3511 if (!__pred(*__first))
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
3519 if (__first == --__last)
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
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)
3531 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3532 __h.reset(__p.first);
3534 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3535 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3538 template <class _ForwardIterator, class _Predicate>
3539 inline _LIBCPP_INLINE_VISIBILITY
3541 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3543 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3544 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3549 template <class _ForwardIterator, class _Compare>
3551 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3553 if (__first != __last)
3555 _ForwardIterator __i = __first;
3556 while (++__i != __last)
3558 if (__comp(*__i, *__first))
3566 template<class _ForwardIterator>
3567 inline _LIBCPP_INLINE_VISIBILITY
3569 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3571 return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3576 template <class _ForwardIterator, class _Compare>
3577 inline _LIBCPP_INLINE_VISIBILITY
3579 is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3581 return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
3584 template<class _ForwardIterator>
3585 inline _LIBCPP_INLINE_VISIBILITY
3587 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3589 return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3594 // stable, 2-3 compares, 0-2 swaps
3596 template <class _Compare, class _ForwardIterator>
3598 __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
3601 if (!__c(*__y, *__x)) // if x <= y
3603 if (!__c(*__z, *__y)) // if y <= z
3604 return __r; // x <= y && y <= z
3606 swap(*__y, *__z); // x <= z && y < z
3608 if (__c(*__y, *__x)) // if x > y
3610 swap(*__x, *__y); // x < y && y <= z
3613 return __r; // x <= y && y < z
3615 if (__c(*__z, *__y)) // x > y, if y > z
3617 swap(*__x, *__z); // x < y && y < z
3621 swap(*__x, *__y); // x > y && y <= z
3622 __r = 1; // x < y && x <= z
3623 if (__c(*__z, *__y)) // if y > z
3625 swap(*__y, *__z); // x <= y && y < z
3629 } // x <= y && y <= z
3631 // stable, 3-6 compares, 0-5 swaps
3633 template <class _Compare, class _ForwardIterator>
3635 __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3636 _ForwardIterator __x4, _Compare __c)
3638 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
3639 if (__c(*__x4, *__x3))
3643 if (__c(*__x3, *__x2))
3647 if (__c(*__x2, *__x1))
3657 // stable, 4-10 compares, 0-9 swaps
3659 template <class _Compare, class _ForwardIterator>
3661 __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3662 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
3664 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
3665 if (__c(*__x5, *__x4))
3669 if (__c(*__x4, *__x3))
3673 if (__c(*__x3, *__x2))
3677 if (__c(*__x2, *__x1))
3689 template <class _Compare, class _BirdirectionalIterator>
3691 __selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3693 _BirdirectionalIterator __lm1 = __last;
3694 for (--__lm1; __first != __lm1; ++__first)
3696 _BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator,
3697 typename add_lvalue_reference<_Compare>::type>
3698 (__first, __last, __comp);
3700 swap(*__first, *__i);
3704 template <class _Compare, class _BirdirectionalIterator>
3706 __insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3708 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3709 if (__first != __last)
3711 _BirdirectionalIterator __i = __first;
3712 for (++__i; __i != __last; ++__i)
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);
3723 template <class _Compare, class _RandomAccessIterator>
3725 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
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)
3732 if (__comp(*__i, *__j))
3734 value_type __t(_VSTD::move(*__i));
3735 _RandomAccessIterator __k = __j;
3739 *__j = _VSTD::move(*__k);
3741 } while (__j != __first && __comp(__t, *--__k));
3742 *__j = _VSTD::move(__t);
3748 template <class _Compare, class _RandomAccessIterator>
3750 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3752 switch (__last - __first)
3758 if (__comp(*--__last, *__first))
3759 swap(*__first, *__last);
3762 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3765 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3768 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
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)
3778 if (__comp(*__i, *__j))
3780 value_type __t(_VSTD::move(*__i));
3781 _RandomAccessIterator __k = __j;
3785 *__j = _VSTD::move(*__k);
3787 } while (__j != __first && __comp(__t, *--__k));
3788 *__j = _VSTD::move(__t);
3789 if (++__count == __limit)
3790 return ++__i == __last;
3797 template <class _Compare, class _BirdirectionalIterator>
3799 __insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
3800 typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
3802 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3803 if (__first1 != __last1)
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)
3812 value_type* __j2 = __last2;
3813 value_type* __i2 = __j2;
3814 if (__comp(*__first1, *--__i2))
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);
3824 ::new(__j2) value_type(_VSTD::move(*__first1));
3825 __d.__incr((value_type*)0);
3832 template <class _Compare, class _RandomAccessIterator>
3834 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
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;
3844 difference_type __len = __last - __first;
3851 if (__comp(*--__last, *__first))
3852 swap(*__first, *__last);
3855 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3858 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3861 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3864 if (__len <= __limit)
3866 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
3870 _RandomAccessIterator __m = __first;
3871 _RandomAccessIterator __lm1 = __last;
3875 difference_type __delta;
3881 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
3887 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
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
3900 // *__first == *__m, *__first doesn't go in first part
3901 // manually guard downward moving __j against __i
3906 // *__first == *__m, *__m <= all other elements
3907 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
3908 ++__i; // __first + 1
3910 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
3915 return; // [__first, __last) all equivalent elements
3916 if (__comp(*__first, *__i))
3926 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
3931 while (!__comp(*__first, *__i))
3933 while (__comp(*__first, *--__j))
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);
3947 if (__comp(*__j, *__m))
3951 break; // found guard for downward moving __j, now use unguarded partition
3955 // It is known that *__i < *__m
3957 // j points beyond range to be tested, *__m is known to be <= *__lm1
3958 // if not yet partitioned...
3961 // known that *(__i - 1) < *__m
3962 // known that __i <= __m
3965 // __m still guards upward moving __i
3966 while (__comp(*__i, *__m))
3968 // It is now known that a guard exists for downward moving __j
3969 while (!__comp(*--__j, *__m))
3975 // It is known that __m != __j
3976 // If __m just moved, follow it
3982 // [__first, __i) < *__m and *__m <= [__i, __last)
3983 if (__i != __m && __comp(*__m, *__i))
3988 // [__first, __i) < *__i and *__i <= [__i+1, __last)
3989 // If we were given a perfect partition, see if insertion sort is quick...
3992 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
3993 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
4009 // sort smaller range with recursive call and larger with tail recursion elimination
4010 if (__i - __first < __last - __i)
4012 _VSTD::__sort<_Compare>(__first, __i, __comp);
4013 // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4018 _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4019 // _VSTD::__sort<_Compare>(__first, __i, __comp);
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
4029 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
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
4041 template <class _RandomAccessIterator>
4042 inline _LIBCPP_INLINE_VISIBILITY
4044 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4046 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4049 template <class _Tp>
4050 inline _LIBCPP_INLINE_VISIBILITY
4052 sort(_Tp** __first, _Tp** __last)
4054 _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
4057 template <class _Tp>
4058 inline _LIBCPP_INLINE_VISIBILITY
4060 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
4062 _VSTD::sort(__first.base(), __last.base());
4065 template <class _Tp, class _Compare>
4066 inline _LIBCPP_INLINE_VISIBILITY
4068 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
4070 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4071 _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
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>&))
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>&))
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>&))
4112 #pragma warning( pop )
4113 #endif // _LIBCPP_MSVC
4117 template <class _Compare, class _ForwardIterator, class _Tp>
4119 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4121 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4122 difference_type __len = _VSTD::distance(__first, __last);
4125 difference_type __l2 = __len / 2;
4126 _ForwardIterator __m = __first;
4127 _VSTD::advance(__m, __l2);
4128 if (__comp(*__m, __value_))
4139 template <class _ForwardIterator, class _Tp, class _Compare>
4140 inline _LIBCPP_INLINE_VISIBILITY
4142 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
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
4154 template <class _ForwardIterator, class _Tp>
4155 inline _LIBCPP_INLINE_VISIBILITY
4157 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4159 return _VSTD::lower_bound(__first, __last, __value_,
4160 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4165 template <class _Compare, class _ForwardIterator, class _Tp>
4167 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4169 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4170 difference_type __len = _VSTD::distance(__first, __last);
4173 difference_type __l2 = __len / 2;
4174 _ForwardIterator __m = __first;
4175 _VSTD::advance(__m, __l2);
4176 if (__comp(__value_, *__m))
4187 template <class _ForwardIterator, class _Tp, class _Compare>
4188 inline _LIBCPP_INLINE_VISIBILITY
4190 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
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
4202 template <class _ForwardIterator, class _Tp>
4203 inline _LIBCPP_INLINE_VISIBILITY
4205 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4207 return _VSTD::upper_bound(__first, __last, __value_,
4208 __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
4213 template <class _Compare, class _ForwardIterator, class _Tp>
4214 pair<_ForwardIterator, _ForwardIterator>
4215 __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4217 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4218 difference_type __len = _VSTD::distance(__first, __last);
4221 difference_type __l2 = __len / 2;
4222 _ForwardIterator __m = __first;
4223 _VSTD::advance(__m, __l2);
4224 if (__comp(*__m, __value_))
4229 else if (__comp(__value_, *__m))
4236 _ForwardIterator __mp1 = __m;
4237 return pair<_ForwardIterator, _ForwardIterator>
4239 __lower_bound<_Compare>(__first, __m, __value_, __comp),
4240 __upper_bound<_Compare>(++__mp1, __last, __value_, __comp)
4244 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
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)
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
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_)
4267 return _VSTD::equal_range(__first, __last, __value_,
4268 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4273 template <class _Compare, class _ForwardIterator, class _Tp>
4274 inline _LIBCPP_INLINE_VISIBILITY
4276 __binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4278 __first = __lower_bound<_Compare>(__first, __last, __value_, __comp);
4279 return __first != __last && !__comp(__value_, *__first);
4282 template <class _ForwardIterator, class _Tp, class _Compare>
4283 inline _LIBCPP_INLINE_VISIBILITY
4285 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
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
4297 template <class _ForwardIterator, class _Tp>
4298 inline _LIBCPP_INLINE_VISIBILITY
4300 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4302 return _VSTD::binary_search(__first, __last, __value_,
4303 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4308 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4310 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4311 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4313 for (; __first1 != __last1; ++__result)
4315 if (__first2 == __last2)
4316 return _VSTD::copy(__first1, __last1, __result);
4317 if (__comp(*__first2, *__first1))
4319 *__result = *__first2;
4324 *__result = *__first1;
4328 return _VSTD::copy(__first2, __last2, __result);
4331 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4332 inline _LIBCPP_INLINE_VISIBILITY
4334 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4335 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
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
4347 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4348 inline _LIBCPP_INLINE_VISIBILITY
4350 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4351 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
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>());
4360 template <class _Compare, class _BidirectionalIterator>
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)
4367 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4368 __destruct_n __d(0);
4369 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4370 if (__len1 <= __len2)
4372 value_type* __p = __buff;
4373 for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4374 ::new(__p) value_type(_VSTD::move(*__i));
4375 __merge<_Compare>(move_iterator<value_type*>(__buff),
4376 move_iterator<value_type*>(__p),
4377 move_iterator<_BidirectionalIterator>(__middle),
4378 move_iterator<_BidirectionalIterator>(__last),
4383 value_type* __p = __buff;
4384 for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4385 ::new(__p) value_type(_VSTD::move(*__i));
4386 typedef reverse_iterator<_BidirectionalIterator> _RBi;
4387 typedef reverse_iterator<value_type*> _Rv;
4388 __merge(move_iterator<_RBi>(_RBi(__middle)), move_iterator<_RBi>(_RBi(__first)),
4389 move_iterator<_Rv>(_Rv(__p)), move_iterator<_Rv>(_Rv(__buff)),
4390 _RBi(__last), __negate<_Compare>(__comp));
4394 template <class _Compare, class _BidirectionalIterator>
4396 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4397 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4398 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4399 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
4401 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4404 // if __middle == __last, we're done
4407 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
4408 for (; true; ++__first, (void) --__len1)
4412 if (__comp(*__middle, *__first))
4415 if (__len1 <= __buff_size || __len2 <= __buff_size)
4417 __buffered_inplace_merge<_Compare>(__first, __middle, __last, __comp, __len1, __len2, __buff);
4420 // __first < __middle < __last
4421 // *__first > *__middle
4422 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4424 // [__first, __m1) <= [__middle, __m2)
4425 // [__middle, __m2) < [__m1, __middle)
4426 // [__m1, __middle) <= [__m2, __last)
4427 // and __m1 or __m2 is in the middle of its range
4428 _BidirectionalIterator __m1; // "median" of [__first, __middle)
4429 _BidirectionalIterator __m2; // "median" of [__middle, __last)
4430 difference_type __len11; // distance(__first, __m1)
4431 difference_type __len21; // distance(__middle, __m2)
4432 // binary search smaller range
4433 if (__len1 < __len2)
4434 { // __len >= 1, __len2 >= 2
4435 __len21 = __len2 / 2;
4437 _VSTD::advance(__m2, __len21);
4438 __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4439 __len11 = _VSTD::distance(__first, __m1);
4444 { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
4445 // It is known *__first > *__middle
4446 swap(*__first, *__middle);
4449 // __len1 >= 2, __len2 >= 1
4450 __len11 = __len1 / 2;
4452 _VSTD::advance(__m1, __len11);
4453 __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp);
4454 __len21 = _VSTD::distance(__middle, __m2);
4456 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle)
4457 difference_type __len22 = __len2 - __len21; // distance(__m2, __last)
4458 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4459 // swap middle two partitions
4460 __middle = _VSTD::rotate(__m1, __middle, __m2);
4461 // __len12 and __len21 now have swapped meanings
4462 // merge smaller range with recurisve call and larger with tail recursion elimination
4463 if (__len11 + __len21 < __len12 + __len22)
4465 __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4466 // __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4474 __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4475 // __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4484 template <class _Tp>
4485 struct __inplace_merge_switch
4487 static const unsigned value = is_trivially_copy_assignable<_Tp>::value;
4490 template <class _BidirectionalIterator, class _Compare>
4491 inline _LIBCPP_INLINE_VISIBILITY
4493 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4496 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4497 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4498 difference_type __len1 = _VSTD::distance(__first, __middle);
4499 difference_type __len2 = _VSTD::distance(__middle, __last);
4500 difference_type __buf_size = _VSTD::min(__len1, __len2);
4501 pair<value_type*, ptrdiff_t> __buf(0, 0);
4502 unique_ptr<value_type, __return_temporary_buffer> __h;
4503 if (__inplace_merge_switch<value_type>::value && __buf_size > 8)
4505 __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
4506 __h.reset(__buf.first);
4508 #ifdef _LIBCPP_DEBUG
4509 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4510 __debug_less<_Compare> __c(__comp);
4511 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2,
4512 __buf.first, __buf.second);
4513 #else // _LIBCPP_DEBUG
4514 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4515 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4516 __buf.first, __buf.second);
4517 #endif // _LIBCPP_DEBUG
4520 template <class _BidirectionalIterator>
4521 inline _LIBCPP_INLINE_VISIBILITY
4523 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
4525 _VSTD::inplace_merge(__first, __middle, __last,
4526 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4531 template <class _Compare, class _InputIterator1, class _InputIterator2>
4533 __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
4534 _InputIterator2 __first2, _InputIterator2 __last2,
4535 typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
4537 typedef typename iterator_traits<_InputIterator1>::value_type value_type;
4538 __destruct_n __d(0);
4539 unique_ptr<value_type, __destruct_n&> __h(__result, __d);
4540 for (; true; ++__result)
4542 if (__first1 == __last1)
4544 for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0))
4545 ::new (__result) value_type(_VSTD::move(*__first2));
4549 if (__first2 == __last2)
4551 for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0))
4552 ::new (__result) value_type(_VSTD::move(*__first1));
4556 if (__comp(*__first2, *__first1))
4558 ::new (__result) value_type(_VSTD::move(*__first2));
4559 __d.__incr((value_type*)0);
4564 ::new (__result) value_type(_VSTD::move(*__first1));
4565 __d.__incr((value_type*)0);
4571 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4573 __merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
4574 _InputIterator2 __first2, _InputIterator2 __last2,
4575 _OutputIterator __result, _Compare __comp)
4577 for (; __first1 != __last1; ++__result)
4579 if (__first2 == __last2)
4581 for (; __first1 != __last1; ++__first1, ++__result)
4582 *__result = _VSTD::move(*__first1);
4585 if (__comp(*__first2, *__first1))
4587 *__result = _VSTD::move(*__first2);
4592 *__result = _VSTD::move(*__first1);
4596 for (; __first2 != __last2; ++__first2, ++__result)
4597 *__result = _VSTD::move(*__first2);
4600 template <class _Compare, class _RandomAccessIterator>
4602 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4603 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4604 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
4606 template <class _Compare, class _RandomAccessIterator>
4608 __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
4609 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4610 typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
4612 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4618 ::new(__first2) value_type(_VSTD::move(*__first1));
4621 __destruct_n __d(0);
4622 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
4623 if (__comp(*--__last1, *__first1))
4625 ::new(__first2) value_type(_VSTD::move(*__last1));
4626 __d.__incr((value_type*)0);
4628 ::new(__first2) value_type(_VSTD::move(*__first1));
4632 ::new(__first2) value_type(_VSTD::move(*__first1));
4633 __d.__incr((value_type*)0);
4635 ::new(__first2) value_type(_VSTD::move(*__last1));
4642 __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
4645 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4646 _RandomAccessIterator __m = __first1 + __l2;
4647 __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
4648 __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
4649 __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
4652 template <class _Tp>
4653 struct __stable_sort_switch
4655 static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
4658 template <class _Compare, class _RandomAccessIterator>
4660 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4661 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4662 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
4664 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4665 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4672 if (__comp(*--__last, *__first))
4673 swap(*__first, *__last);
4676 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4678 __insertion_sort<_Compare>(__first, __last, __comp);
4681 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4682 _RandomAccessIterator __m = __first + __l2;
4683 if (__len <= __buff_size)
4685 __destruct_n __d(0);
4686 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4687 __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4688 __d.__set(__l2, (value_type*)0);
4689 __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
4690 __d.__set(__len, (value_type*)0);
4691 __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4692 // __merge<_Compare>(move_iterator<value_type*>(__buff),
4693 // move_iterator<value_type*>(__buff + __l2),
4694 // move_iterator<_RandomAccessIterator>(__buff + __l2),
4695 // move_iterator<_RandomAccessIterator>(__buff + __len),
4696 // __first, __comp);
4699 __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4700 __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
4701 __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4704 template <class _RandomAccessIterator, class _Compare>
4705 inline _LIBCPP_INLINE_VISIBILITY
4707 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4709 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4710 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4711 difference_type __len = __last - __first;
4712 pair<value_type*, ptrdiff_t> __buf(0, 0);
4713 unique_ptr<value_type, __return_temporary_buffer> __h;
4714 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4716 __buf = _VSTD::get_temporary_buffer<value_type>(__len);
4717 __h.reset(__buf.first);
4719 #ifdef _LIBCPP_DEBUG
4720 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4721 __debug_less<_Compare> __c(__comp);
4722 __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);
4723 #else // _LIBCPP_DEBUG
4724 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4725 __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4726 #endif // _LIBCPP_DEBUG
4729 template <class _RandomAccessIterator>
4730 inline _LIBCPP_INLINE_VISIBILITY
4732 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4734 _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4739 template <class _RandomAccessIterator, class _Compare>
4740 _RandomAccessIterator
4741 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4743 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4744 difference_type __len = __last - __first;
4745 difference_type __p = 0;
4746 difference_type __c = 1;
4747 _RandomAccessIterator __pp = __first;
4750 _RandomAccessIterator __cp = __first + __c;
4751 if (__comp(*__pp, *__cp))
4757 if (__comp(*__pp, *__cp))
4766 template<class _RandomAccessIterator>
4767 inline _LIBCPP_INLINE_VISIBILITY
4768 _RandomAccessIterator
4769 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4771 return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4776 template <class _RandomAccessIterator, class _Compare>
4777 inline _LIBCPP_INLINE_VISIBILITY
4779 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4781 return _VSTD::is_heap_until(__first, __last, __comp) == __last;
4784 template<class _RandomAccessIterator>
4785 inline _LIBCPP_INLINE_VISIBILITY
4787 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4789 return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4794 template <class _Compare, class _RandomAccessIterator>
4796 __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4797 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4799 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4802 __len = (__len - 2) / 2;
4803 _RandomAccessIterator __ptr = __first + __len;
4804 if (__comp(*__ptr, *--__last))
4806 value_type __t(_VSTD::move(*__last));
4809 *__last = _VSTD::move(*__ptr);
4813 __len = (__len - 1) / 2;
4814 __ptr = __first + __len;
4815 } while (__comp(*__ptr, __t));
4816 *__last = _VSTD::move(__t);
4821 template <class _RandomAccessIterator, class _Compare>
4822 inline _LIBCPP_INLINE_VISIBILITY
4824 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4826 #ifdef _LIBCPP_DEBUG
4827 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4828 __debug_less<_Compare> __c(__comp);
4829 __sift_up<_Comp_ref>(__first, __last, __c, __last - __first);
4830 #else // _LIBCPP_DEBUG
4831 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4832 __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
4833 #endif // _LIBCPP_DEBUG
4836 template <class _RandomAccessIterator>
4837 inline _LIBCPP_INLINE_VISIBILITY
4839 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4841 _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4846 template <class _Compare, class _RandomAccessIterator>
4848 __sift_down(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4849 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4850 _RandomAccessIterator __start)
4852 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4853 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4854 // left-child of __start is at 2 * __start + 1
4855 // right-child of __start is at 2 * __start + 2
4856 difference_type __child = __start - __first;
4858 if (__len < 2 || (__len - 2) / 2 < __child)
4861 __child = 2 * __child + 1;
4862 _RandomAccessIterator __child_i = __first + __child;
4864 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4865 // right-child exists and is greater than left-child
4870 // check if we are in heap-order
4871 if (__comp(*__child_i, *__start))
4872 // we are, __start is larger than it's largest child
4875 value_type __top(_VSTD::move(*__start));
4878 // we are not in heap-order, swap the parent with it's largest child
4879 *__start = _VSTD::move(*__child_i);
4880 __start = __child_i;
4882 if ((__len - 2) / 2 < __child)
4885 // recompute the child based off of the updated parent
4886 __child = 2 * __child + 1;
4887 __child_i = __first + __child;
4889 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4890 // right-child exists and is greater than left-child
4895 // check if we are in heap-order
4896 } while (!__comp(*__child_i, __top));
4897 *__start = _VSTD::move(__top);
4900 template <class _Compare, class _RandomAccessIterator>
4901 inline _LIBCPP_INLINE_VISIBILITY
4903 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4904 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4908 swap(*__first, *--__last);
4909 __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);
4913 template <class _RandomAccessIterator, class _Compare>
4914 inline _LIBCPP_INLINE_VISIBILITY
4916 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4918 #ifdef _LIBCPP_DEBUG
4919 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4920 __debug_less<_Compare> __c(__comp);
4921 __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);
4922 #else // _LIBCPP_DEBUG
4923 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4924 __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
4925 #endif // _LIBCPP_DEBUG
4928 template <class _RandomAccessIterator>
4929 inline _LIBCPP_INLINE_VISIBILITY
4931 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4933 _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4938 template <class _Compare, class _RandomAccessIterator>
4940 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4942 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4943 difference_type __n = __last - __first;
4946 // start from the first parent, there is no need to consider children
4947 for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start)
4949 __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start);
4954 template <class _RandomAccessIterator, class _Compare>
4955 inline _LIBCPP_INLINE_VISIBILITY
4957 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4959 #ifdef _LIBCPP_DEBUG
4960 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4961 __debug_less<_Compare> __c(__comp);
4962 __make_heap<_Comp_ref>(__first, __last, __c);
4963 #else // _LIBCPP_DEBUG
4964 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4965 __make_heap<_Comp_ref>(__first, __last, __comp);
4966 #endif // _LIBCPP_DEBUG
4969 template <class _RandomAccessIterator>
4970 inline _LIBCPP_INLINE_VISIBILITY
4972 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4974 _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4979 template <class _Compare, class _RandomAccessIterator>
4981 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4983 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4984 for (difference_type __n = __last - __first; __n > 1; --__last, --__n)
4985 __pop_heap<_Compare>(__first, __last, __comp, __n);
4988 template <class _RandomAccessIterator, class _Compare>
4989 inline _LIBCPP_INLINE_VISIBILITY
4991 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4993 #ifdef _LIBCPP_DEBUG
4994 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4995 __debug_less<_Compare> __c(__comp);
4996 __sort_heap<_Comp_ref>(__first, __last, __c);
4997 #else // _LIBCPP_DEBUG
4998 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4999 __sort_heap<_Comp_ref>(__first, __last, __comp);
5000 #endif // _LIBCPP_DEBUG
5003 template <class _RandomAccessIterator>
5004 inline _LIBCPP_INLINE_VISIBILITY
5006 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5008 _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5013 template <class _Compare, class _RandomAccessIterator>
5015 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5018 __make_heap<_Compare>(__first, __middle, __comp);
5019 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
5020 for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
5022 if (__comp(*__i, *__first))
5024 swap(*__i, *__first);
5025 __sift_down<_Compare>(__first, __middle, __comp, __len, __first);
5028 __sort_heap<_Compare>(__first, __middle, __comp);
5031 template <class _RandomAccessIterator, class _Compare>
5032 inline _LIBCPP_INLINE_VISIBILITY
5034 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5037 #ifdef _LIBCPP_DEBUG
5038 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5039 __debug_less<_Compare> __c(__comp);
5040 __partial_sort<_Comp_ref>(__first, __middle, __last, __c);
5041 #else // _LIBCPP_DEBUG
5042 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5043 __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
5044 #endif // _LIBCPP_DEBUG
5047 template <class _RandomAccessIterator>
5048 inline _LIBCPP_INLINE_VISIBILITY
5050 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
5052 _VSTD::partial_sort(__first, __middle, __last,
5053 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5056 // partial_sort_copy
5058 template <class _Compare, class _InputIterator, class _RandomAccessIterator>
5059 _RandomAccessIterator
5060 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
5061 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5063 _RandomAccessIterator __r = __result_first;
5064 if (__r != __result_last)
5066 for (; __first != __last && __r != __result_last; (void) ++__first, ++__r)
5068 __make_heap<_Compare>(__result_first, __r, __comp);
5069 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
5070 for (; __first != __last; ++__first)
5071 if (__comp(*__first, *__result_first))
5073 *__result_first = *__first;
5074 __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first);
5076 __sort_heap<_Compare>(__result_first, __r, __comp);
5081 template <class _InputIterator, class _RandomAccessIterator, class _Compare>
5082 inline _LIBCPP_INLINE_VISIBILITY
5083 _RandomAccessIterator
5084 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5085 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5087 #ifdef _LIBCPP_DEBUG
5088 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5089 __debug_less<_Compare> __c(__comp);
5090 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);
5091 #else // _LIBCPP_DEBUG
5092 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5093 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
5094 #endif // _LIBCPP_DEBUG
5097 template <class _InputIterator, class _RandomAccessIterator>
5098 inline _LIBCPP_INLINE_VISIBILITY
5099 _RandomAccessIterator
5100 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5101 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
5103 return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
5104 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5109 template <class _Compare, class _RandomAccessIterator>
5111 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5113 // _Compare is known to be a reference type
5114 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5115 const difference_type __limit = 7;
5119 if (__nth == __last)
5121 difference_type __len = __last - __first;
5128 if (__comp(*--__last, *__first))
5129 swap(*__first, *__last);
5133 _RandomAccessIterator __m = __first;
5134 _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
5138 if (__len <= __limit)
5140 __selection_sort<_Compare>(__first, __last, __comp);
5143 // __len > __limit >= 3
5144 _RandomAccessIterator __m = __first + __len/2;
5145 _RandomAccessIterator __lm1 = __last;
5146 unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
5148 // partition [__first, __m) < *__m and *__m <= [__m, __last)
5149 // (this inhibits tossing elements equivalent to __m around unnecessarily)
5150 _RandomAccessIterator __i = __first;
5151 _RandomAccessIterator __j = __lm1;
5152 // j points beyond range to be tested, *__lm1 is known to be <= *__m
5153 // The search going up is known to be guarded but the search coming down isn't.
5154 // Prime the downward search with a guard.
5155 if (!__comp(*__i, *__m)) // if *__first == *__m
5157 // *__first == *__m, *__first doesn't go in first part
5158 // manually guard downward moving __j against __i
5163 // *__first == *__m, *__m <= all other elements
5164 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
5165 ++__i; // __first + 1
5167 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
5172 return; // [__first, __last) all equivalent elements
5173 if (__comp(*__first, *__i))
5183 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
5188 while (!__comp(*__first, *__i))
5190 while (__comp(*__first, *--__j))
5198 // [__first, __i) == *__first and *__first < [__i, __last)
5199 // The first part is sorted,
5202 // __nth_element the secod part
5203 // __nth_element<_Compare>(__i, __nth, __last, __comp);
5207 if (__comp(*__j, *__m))
5211 break; // found guard for downward moving __j, now use unguarded partition
5216 // j points beyond range to be tested, *__lm1 is known to be <= *__m
5217 // if not yet partitioned...
5220 // known that *(__i - 1) < *__m
5223 // __m still guards upward moving __i
5224 while (__comp(*__i, *__m))
5226 // It is now known that a guard exists for downward moving __j
5227 while (!__comp(*--__j, *__m))
5233 // It is known that __m != __j
5234 // If __m just moved, follow it
5240 // [__first, __i) < *__m and *__m <= [__i, __last)
5241 if (__i != __m && __comp(*__m, *__i))
5246 // [__first, __i) < *__i and *__i <= [__i+1, __last)
5251 // We were given a perfectly partitioned sequence. Coincidence?
5254 // Check for [__first, __i) already sorted
5255 __j = __m = __first;
5256 while (++__j != __i)
5258 if (__comp(*__j, *__m))
5259 // not yet sorted, so sort
5263 // [__first, __i) sorted
5268 // Check for [__i, __last) already sorted
5270 while (++__j != __last)
5272 if (__comp(*__j, *__m))
5273 // not yet sorted, so sort
5277 // [__i, __last) sorted
5282 // __nth_element on range containing __nth
5285 // __nth_element<_Compare>(__first, __nth, __i, __comp);
5290 // __nth_element<_Compare>(__i+1, __nth, __last, __comp);
5296 template <class _RandomAccessIterator, class _Compare>
5297 inline _LIBCPP_INLINE_VISIBILITY
5299 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5301 #ifdef _LIBCPP_DEBUG
5302 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5303 __debug_less<_Compare> __c(__comp);
5304 __nth_element<_Comp_ref>(__first, __nth, __last, __c);
5305 #else // _LIBCPP_DEBUG
5306 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5307 __nth_element<_Comp_ref>(__first, __nth, __last, __comp);
5308 #endif // _LIBCPP_DEBUG
5311 template <class _RandomAccessIterator>
5312 inline _LIBCPP_INLINE_VISIBILITY
5314 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
5316 _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5321 template <class _Compare, class _InputIterator1, class _InputIterator2>
5323 __includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5326 for (; __first2 != __last2; ++__first1)
5328 if (__first1 == __last1 || __comp(*__first2, *__first1))
5330 if (!__comp(*__first1, *__first2))
5336 template <class _InputIterator1, class _InputIterator2, class _Compare>
5337 inline _LIBCPP_INLINE_VISIBILITY
5339 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5342 #ifdef _LIBCPP_DEBUG
5343 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5344 __debug_less<_Compare> __c(__comp);
5345 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5346 #else // _LIBCPP_DEBUG
5347 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5348 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5349 #endif // _LIBCPP_DEBUG
5352 template <class _InputIterator1, class _InputIterator2>
5353 inline _LIBCPP_INLINE_VISIBILITY
5355 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
5357 return _VSTD::includes(__first1, __last1, __first2, __last2,
5358 __less<typename iterator_traits<_InputIterator1>::value_type,
5359 typename iterator_traits<_InputIterator2>::value_type>());
5364 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5366 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5367 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5369 for (; __first1 != __last1; ++__result)
5371 if (__first2 == __last2)
5372 return _VSTD::copy(__first1, __last1, __result);
5373 if (__comp(*__first2, *__first1))
5375 *__result = *__first2;
5380 *__result = *__first1;
5381 if (!__comp(*__first1, *__first2))
5386 return _VSTD::copy(__first2, __last2, __result);
5389 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5390 inline _LIBCPP_INLINE_VISIBILITY
5392 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5393 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5395 #ifdef _LIBCPP_DEBUG
5396 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5397 __debug_less<_Compare> __c(__comp);
5398 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5399 #else // _LIBCPP_DEBUG
5400 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5401 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5402 #endif // _LIBCPP_DEBUG
5405 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5406 inline _LIBCPP_INLINE_VISIBILITY
5408 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5409 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5411 return _VSTD::set_union(__first1, __last1, __first2, __last2, __result,
5412 __less<typename iterator_traits<_InputIterator1>::value_type,
5413 typename iterator_traits<_InputIterator2>::value_type>());
5418 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5420 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5421 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5423 while (__first1 != __last1 && __first2 != __last2)
5425 if (__comp(*__first1, *__first2))
5429 if (!__comp(*__first2, *__first1))
5431 *__result = *__first1;
5441 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5442 inline _LIBCPP_INLINE_VISIBILITY
5444 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5445 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5447 #ifdef _LIBCPP_DEBUG
5448 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5449 __debug_less<_Compare> __c(__comp);
5450 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5451 #else // _LIBCPP_DEBUG
5452 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5453 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5454 #endif // _LIBCPP_DEBUG
5457 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5458 inline _LIBCPP_INLINE_VISIBILITY
5460 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5461 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5463 return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result,
5464 __less<typename iterator_traits<_InputIterator1>::value_type,
5465 typename iterator_traits<_InputIterator2>::value_type>());
5470 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5472 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5473 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5475 while (__first1 != __last1)
5477 if (__first2 == __last2)
5478 return _VSTD::copy(__first1, __last1, __result);
5479 if (__comp(*__first1, *__first2))
5481 *__result = *__first1;
5487 if (!__comp(*__first2, *__first1))
5495 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5496 inline _LIBCPP_INLINE_VISIBILITY
5498 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5499 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5501 #ifdef _LIBCPP_DEBUG
5502 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5503 __debug_less<_Compare> __c(__comp);
5504 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5505 #else // _LIBCPP_DEBUG
5506 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5507 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5508 #endif // _LIBCPP_DEBUG
5511 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5512 inline _LIBCPP_INLINE_VISIBILITY
5514 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5515 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5517 return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result,
5518 __less<typename iterator_traits<_InputIterator1>::value_type,
5519 typename iterator_traits<_InputIterator2>::value_type>());
5522 // set_symmetric_difference
5524 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5526 __set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5527 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5529 while (__first1 != __last1)
5531 if (__first2 == __last2)
5532 return _VSTD::copy(__first1, __last1, __result);
5533 if (__comp(*__first1, *__first2))
5535 *__result = *__first1;
5541 if (__comp(*__first2, *__first1))
5543 *__result = *__first2;
5551 return _VSTD::copy(__first2, __last2, __result);
5554 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5555 inline _LIBCPP_INLINE_VISIBILITY
5557 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5558 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5560 #ifdef _LIBCPP_DEBUG
5561 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5562 __debug_less<_Compare> __c(__comp);
5563 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5564 #else // _LIBCPP_DEBUG
5565 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5566 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5567 #endif // _LIBCPP_DEBUG
5570 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5571 inline _LIBCPP_INLINE_VISIBILITY
5573 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5574 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5576 return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
5577 __less<typename iterator_traits<_InputIterator1>::value_type,
5578 typename iterator_traits<_InputIterator2>::value_type>());
5581 // lexicographical_compare
5583 template <class _Compare, class _InputIterator1, class _InputIterator2>
5585 __lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5586 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5588 for (; __first2 != __last2; ++__first1, (void) ++__first2)
5590 if (__first1 == __last1 || __comp(*__first1, *__first2))
5592 if (__comp(*__first2, *__first1))
5598 template <class _InputIterator1, class _InputIterator2, class _Compare>
5599 inline _LIBCPP_INLINE_VISIBILITY
5601 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5602 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5604 #ifdef _LIBCPP_DEBUG
5605 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5606 __debug_less<_Compare> __c(__comp);
5607 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5608 #else // _LIBCPP_DEBUG
5609 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5610 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5611 #endif // _LIBCPP_DEBUG
5614 template <class _InputIterator1, class _InputIterator2>
5615 inline _LIBCPP_INLINE_VISIBILITY
5617 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5618 _InputIterator2 __first2, _InputIterator2 __last2)
5620 return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,
5621 __less<typename iterator_traits<_InputIterator1>::value_type,
5622 typename iterator_traits<_InputIterator2>::value_type>());
5627 template <class _Compare, class _BidirectionalIterator>
5629 __next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5631 _BidirectionalIterator __i = __last;
5632 if (__first == __last || __first == --__i)
5636 _BidirectionalIterator __ip1 = __i;
5637 if (__comp(*--__i, *__ip1))
5639 _BidirectionalIterator __j = __last;
5640 while (!__comp(*__i, *--__j))
5643 _VSTD::reverse(__ip1, __last);
5648 _VSTD::reverse(__first, __last);
5654 template <class _BidirectionalIterator, class _Compare>
5655 inline _LIBCPP_INLINE_VISIBILITY
5657 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5659 #ifdef _LIBCPP_DEBUG
5660 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5661 __debug_less<_Compare> __c(__comp);
5662 return __next_permutation<_Comp_ref>(__first, __last, __c);
5663 #else // _LIBCPP_DEBUG
5664 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5665 return __next_permutation<_Comp_ref>(__first, __last, __comp);
5666 #endif // _LIBCPP_DEBUG
5669 template <class _BidirectionalIterator>
5670 inline _LIBCPP_INLINE_VISIBILITY
5672 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5674 return _VSTD::next_permutation(__first, __last,
5675 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5680 template <class _Compare, class _BidirectionalIterator>
5682 __prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5684 _BidirectionalIterator __i = __last;
5685 if (__first == __last || __first == --__i)
5689 _BidirectionalIterator __ip1 = __i;
5690 if (__comp(*__ip1, *--__i))
5692 _BidirectionalIterator __j = __last;
5693 while (!__comp(*--__j, *__i))
5696 _VSTD::reverse(__ip1, __last);
5701 _VSTD::reverse(__first, __last);
5707 template <class _BidirectionalIterator, class _Compare>
5708 inline _LIBCPP_INLINE_VISIBILITY
5710 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5712 #ifdef _LIBCPP_DEBUG
5713 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5714 __debug_less<_Compare> __c(__comp);
5715 return __prev_permutation<_Comp_ref>(__first, __last, __c);
5716 #else // _LIBCPP_DEBUG
5717 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5718 return __prev_permutation<_Comp_ref>(__first, __last, __comp);
5719 #endif // _LIBCPP_DEBUG
5722 template <class _BidirectionalIterator>
5723 inline _LIBCPP_INLINE_VISIBILITY
5725 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5727 return _VSTD::prev_permutation(__first, __last,
5728 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5731 template <class _Tp>
5732 inline _LIBCPP_INLINE_VISIBILITY
5735 is_integral<_Tp>::value,
5738 __rotate_left(_Tp __t, _Tp __n = 1)
5740 const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1);
5742 return static_cast<_Tp>((__t << __n) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> (__bits - __n)));
5745 template <class _Tp>
5746 inline _LIBCPP_INLINE_VISIBILITY
5749 is_integral<_Tp>::value,
5752 __rotate_right(_Tp __t, _Tp __n = 1)
5754 const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1);
5756 return static_cast<_Tp>((__t << (__bits - __n)) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> __n));
5759 _LIBCPP_END_NAMESPACE_STD
5761 #endif // _LIBCPP_ALGORITHM