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); // constexpr in C++14
526 template <class ForwardIterator, class Compare>
528 min_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14
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); // constexpr in C++14
550 template <class ForwardIterator, class Compare>
552 max_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14
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); // constexpr in C++14
574 template<class ForwardIterator, class Compare>
575 pair<ForwardIterator, ForwardIterator>
576 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14
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 _LIBCPP_EXPLICIT_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, __convert_to_integral(__count), __value_, __pred,
1676 typename iterator_traits<_ForwardIterator>::iterator_category());
1679 template <class _ForwardIterator, class _Size, class _Tp>
1680 inline _LIBCPP_INLINE_VISIBILITY
1682 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
1684 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1685 return _VSTD::search_n(__first, __last, __convert_to_integral(__count),
1686 __value_, __equal_to<__v, _Tp>());
1690 template <class _Iter>
1691 inline _LIBCPP_INLINE_VISIBILITY
1693 __unwrap_iter(_Iter __i)
1698 template <class _Tp>
1699 inline _LIBCPP_INLINE_VISIBILITY
1702 is_trivially_copy_assignable<_Tp>::value,
1705 __unwrap_iter(move_iterator<_Tp*> __i)
1710 #if _LIBCPP_DEBUG_LEVEL < 2
1712 template <class _Tp>
1713 inline _LIBCPP_INLINE_VISIBILITY
1716 is_trivially_copy_assignable<_Tp>::value,
1719 __unwrap_iter(__wrap_iter<_Tp*> __i)
1724 #endif // _LIBCPP_DEBUG_LEVEL < 2
1726 template <class _InputIterator, class _OutputIterator>
1727 inline _LIBCPP_INLINE_VISIBILITY
1729 __copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1731 for (; __first != __last; ++__first, (void) ++__result)
1732 *__result = *__first;
1736 template <class _Tp, class _Up>
1737 inline _LIBCPP_INLINE_VISIBILITY
1740 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1741 is_trivially_copy_assignable<_Up>::value,
1744 __copy(_Tp* __first, _Tp* __last, _Up* __result)
1746 const size_t __n = static_cast<size_t>(__last - __first);
1748 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1749 return __result + __n;
1752 template <class _InputIterator, class _OutputIterator>
1753 inline _LIBCPP_INLINE_VISIBILITY
1755 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1757 return _VSTD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1762 template <class _BidirectionalIterator, class _OutputIterator>
1763 inline _LIBCPP_INLINE_VISIBILITY
1765 __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
1767 while (__first != __last)
1768 *--__result = *--__last;
1772 template <class _Tp, class _Up>
1773 inline _LIBCPP_INLINE_VISIBILITY
1776 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1777 is_trivially_copy_assignable<_Up>::value,
1780 __copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
1782 const size_t __n = static_cast<size_t>(__last - __first);
1786 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1791 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1792 inline _LIBCPP_INLINE_VISIBILITY
1793 _BidirectionalIterator2
1794 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1795 _BidirectionalIterator2 __result)
1797 return _VSTD::__copy_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1802 template<class _InputIterator, class _OutputIterator, class _Predicate>
1803 inline _LIBCPP_INLINE_VISIBILITY
1805 copy_if(_InputIterator __first, _InputIterator __last,
1806 _OutputIterator __result, _Predicate __pred)
1808 for (; __first != __last; ++__first)
1810 if (__pred(*__first))
1812 *__result = *__first;
1821 template<class _InputIterator, class _Size, class _OutputIterator>
1822 inline _LIBCPP_INLINE_VISIBILITY
1825 __is_input_iterator<_InputIterator>::value &&
1826 !__is_random_access_iterator<_InputIterator>::value,
1829 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1831 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
1832 _IntegralSize __n = __orig_n;
1835 *__result = *__first;
1837 for (--__n; __n > 0; --__n)
1840 *__result = *__first;
1847 template<class _InputIterator, class _Size, class _OutputIterator>
1848 inline _LIBCPP_INLINE_VISIBILITY
1851 __is_random_access_iterator<_InputIterator>::value,
1854 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1856 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
1857 _IntegralSize __n = __orig_n;
1858 return _VSTD::copy(__first, __first + __n, __result);
1863 template <class _InputIterator, class _OutputIterator>
1864 inline _LIBCPP_INLINE_VISIBILITY
1866 __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1868 for (; __first != __last; ++__first, (void) ++__result)
1869 *__result = _VSTD::move(*__first);
1873 template <class _Tp, class _Up>
1874 inline _LIBCPP_INLINE_VISIBILITY
1877 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1878 is_trivially_copy_assignable<_Up>::value,
1881 __move(_Tp* __first, _Tp* __last, _Up* __result)
1883 const size_t __n = static_cast<size_t>(__last - __first);
1885 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1886 return __result + __n;
1889 template <class _InputIterator, class _OutputIterator>
1890 inline _LIBCPP_INLINE_VISIBILITY
1892 move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1894 return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1899 template <class _InputIterator, class _OutputIterator>
1900 inline _LIBCPP_INLINE_VISIBILITY
1902 __move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1904 while (__first != __last)
1905 *--__result = _VSTD::move(*--__last);
1909 template <class _Tp, class _Up>
1910 inline _LIBCPP_INLINE_VISIBILITY
1913 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1914 is_trivially_copy_assignable<_Up>::value,
1917 __move_backward(_Tp* __first, _Tp* __last, _Up* __result)
1919 const size_t __n = static_cast<size_t>(__last - __first);
1923 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1928 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1929 inline _LIBCPP_INLINE_VISIBILITY
1930 _BidirectionalIterator2
1931 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1932 _BidirectionalIterator2 __result)
1934 return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1939 // moved to <type_traits> for better swap / noexcept support
1943 template <class _InputIterator, class _OutputIterator, class _UnaryOperation>
1944 inline _LIBCPP_INLINE_VISIBILITY
1946 transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op)
1948 for (; __first != __last; ++__first, (void) ++__result)
1949 *__result = __op(*__first);
1953 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation>
1954 inline _LIBCPP_INLINE_VISIBILITY
1956 transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
1957 _OutputIterator __result, _BinaryOperation __binary_op)
1959 for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result)
1960 *__result = __binary_op(*__first1, *__first2);
1966 template <class _ForwardIterator, class _Tp>
1967 inline _LIBCPP_INLINE_VISIBILITY
1969 replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value)
1971 for (; __first != __last; ++__first)
1972 if (*__first == __old_value)
1973 *__first = __new_value;
1978 template <class _ForwardIterator, class _Predicate, class _Tp>
1979 inline _LIBCPP_INLINE_VISIBILITY
1981 replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value)
1983 for (; __first != __last; ++__first)
1984 if (__pred(*__first))
1985 *__first = __new_value;
1990 template <class _InputIterator, class _OutputIterator, class _Tp>
1991 inline _LIBCPP_INLINE_VISIBILITY
1993 replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1994 const _Tp& __old_value, const _Tp& __new_value)
1996 for (; __first != __last; ++__first, (void) ++__result)
1997 if (*__first == __old_value)
1998 *__result = __new_value;
2000 *__result = *__first;
2006 template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp>
2007 inline _LIBCPP_INLINE_VISIBILITY
2009 replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
2010 _Predicate __pred, const _Tp& __new_value)
2012 for (; __first != __last; ++__first, (void) ++__result)
2013 if (__pred(*__first))
2014 *__result = __new_value;
2016 *__result = *__first;
2022 template <class _OutputIterator, class _Size, class _Tp>
2023 inline _LIBCPP_INLINE_VISIBILITY
2025 __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2027 for (; __n > 0; ++__first, (void) --__n)
2028 *__first = __value_;
2032 template <class _Tp, class _Size, class _Up>
2033 inline _LIBCPP_INLINE_VISIBILITY
2036 is_integral<_Tp>::value && sizeof(_Tp) == 1 &&
2037 !is_same<_Tp, bool>::value &&
2038 is_integral<_Up>::value && sizeof(_Up) == 1,
2041 __fill_n(_Tp* __first, _Size __n,_Up __value_)
2044 _VSTD::memset(__first, (unsigned char)__value_, (size_t)(__n));
2045 return __first + __n;
2048 template <class _OutputIterator, class _Size, class _Tp>
2049 inline _LIBCPP_INLINE_VISIBILITY
2051 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2053 return _VSTD::__fill_n(__first, __convert_to_integral(__n), __value_);
2058 template <class _ForwardIterator, class _Tp>
2059 inline _LIBCPP_INLINE_VISIBILITY
2061 __fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
2063 for (; __first != __last; ++__first)
2064 *__first = __value_;
2067 template <class _RandomAccessIterator, class _Tp>
2068 inline _LIBCPP_INLINE_VISIBILITY
2070 __fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag)
2072 _VSTD::fill_n(__first, __last - __first, __value_);
2075 template <class _ForwardIterator, class _Tp>
2076 inline _LIBCPP_INLINE_VISIBILITY
2078 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2080 _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category());
2085 template <class _ForwardIterator, class _Generator>
2086 inline _LIBCPP_INLINE_VISIBILITY
2088 generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
2090 for (; __first != __last; ++__first)
2096 template <class _OutputIterator, class _Size, class _Generator>
2097 inline _LIBCPP_INLINE_VISIBILITY
2099 generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen)
2101 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
2102 _IntegralSize __n = __orig_n;
2103 for (; __n > 0; ++__first, (void) --__n)
2110 template <class _ForwardIterator, class _Tp>
2112 remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2114 __first = _VSTD::find(__first, __last, __value_);
2115 if (__first != __last)
2117 _ForwardIterator __i = __first;
2118 while (++__i != __last)
2120 if (!(*__i == __value_))
2122 *__first = _VSTD::move(*__i);
2132 template <class _ForwardIterator, class _Predicate>
2134 remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2136 __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
2137 (__first, __last, __pred);
2138 if (__first != __last)
2140 _ForwardIterator __i = __first;
2141 while (++__i != __last)
2145 *__first = _VSTD::move(*__i);
2155 template <class _InputIterator, class _OutputIterator, class _Tp>
2156 inline _LIBCPP_INLINE_VISIBILITY
2158 remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_)
2160 for (; __first != __last; ++__first)
2162 if (!(*__first == __value_))
2164 *__result = *__first;
2173 template <class _InputIterator, class _OutputIterator, class _Predicate>
2174 inline _LIBCPP_INLINE_VISIBILITY
2176 remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
2178 for (; __first != __last; ++__first)
2180 if (!__pred(*__first))
2182 *__result = *__first;
2191 template <class _ForwardIterator, class _BinaryPredicate>
2193 unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
2195 __first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type>
2196 (__first, __last, __pred);
2197 if (__first != __last)
2201 _ForwardIterator __i = __first;
2202 for (++__i; ++__i != __last;)
2203 if (!__pred(*__first, *__i))
2204 *++__first = _VSTD::move(*__i);
2210 template <class _ForwardIterator>
2211 inline _LIBCPP_INLINE_VISIBILITY
2213 unique(_ForwardIterator __first, _ForwardIterator __last)
2215 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
2216 return _VSTD::unique(__first, __last, __equal_to<__v>());
2221 template <class _BinaryPredicate, class _InputIterator, class _OutputIterator>
2223 __unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2224 input_iterator_tag, output_iterator_tag)
2226 if (__first != __last)
2228 typename iterator_traits<_InputIterator>::value_type __t(*__first);
2231 while (++__first != __last)
2233 if (!__pred(__t, *__first))
2244 template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator>
2246 __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2247 forward_iterator_tag, output_iterator_tag)
2249 if (__first != __last)
2251 _ForwardIterator __i = __first;
2254 while (++__first != __last)
2256 if (!__pred(*__i, *__first))
2258 *__result = *__first;
2267 template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator>
2269 __unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred,
2270 input_iterator_tag, forward_iterator_tag)
2272 if (__first != __last)
2274 *__result = *__first;
2275 while (++__first != __last)
2276 if (!__pred(*__result, *__first))
2277 *++__result = *__first;
2283 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
2284 inline _LIBCPP_INLINE_VISIBILITY
2286 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred)
2288 return _VSTD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type>
2289 (__first, __last, __result, __pred,
2290 typename iterator_traits<_InputIterator>::iterator_category(),
2291 typename iterator_traits<_OutputIterator>::iterator_category());
2294 template <class _InputIterator, class _OutputIterator>
2295 inline _LIBCPP_INLINE_VISIBILITY
2297 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
2299 typedef typename iterator_traits<_InputIterator>::value_type __v;
2300 return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());
2305 template <class _BidirectionalIterator>
2306 inline _LIBCPP_INLINE_VISIBILITY
2308 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
2310 while (__first != __last)
2312 if (__first == --__last)
2314 _VSTD::iter_swap(__first, __last);
2319 template <class _RandomAccessIterator>
2320 inline _LIBCPP_INLINE_VISIBILITY
2322 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
2324 if (__first != __last)
2325 for (; __first < --__last; ++__first)
2326 _VSTD::iter_swap(__first, __last);
2329 template <class _BidirectionalIterator>
2330 inline _LIBCPP_INLINE_VISIBILITY
2332 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
2334 _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());
2339 template <class _BidirectionalIterator, class _OutputIterator>
2340 inline _LIBCPP_INLINE_VISIBILITY
2342 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
2344 for (; __first != __last; ++__result)
2345 *__result = *--__last;
2351 template <class _ForwardIterator>
2353 __rotate_left(_ForwardIterator __first, _ForwardIterator __last)
2355 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2356 value_type __tmp = _VSTD::move(*__first);
2357 _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
2358 *__lm1 = _VSTD::move(__tmp);
2362 template <class _BidirectionalIterator>
2363 _BidirectionalIterator
2364 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
2366 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
2367 _BidirectionalIterator __lm1 = _VSTD::prev(__last);
2368 value_type __tmp = _VSTD::move(*__lm1);
2369 _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
2370 *__first = _VSTD::move(__tmp);
2374 template <class _ForwardIterator>
2376 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2378 _ForwardIterator __i = __middle;
2381 swap(*__first, *__i);
2383 if (++__i == __last)
2385 if (__first == __middle)
2388 _ForwardIterator __r = __first;
2389 if (__first != __middle)
2394 swap(*__first, *__i);
2396 if (++__i == __last)
2398 if (__first == __middle)
2402 else if (__first == __middle)
2409 template<typename _Integral>
2410 inline _LIBCPP_INLINE_VISIBILITY
2412 __gcd(_Integral __x, _Integral __y)
2416 _Integral __t = __x % __y;
2423 template<typename _RandomAccessIterator>
2424 _RandomAccessIterator
2425 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
2427 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2428 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
2430 const difference_type __m1 = __middle - __first;
2431 const difference_type __m2 = __last - __middle;
2434 _VSTD::swap_ranges(__first, __middle, __middle);
2437 const difference_type __g = _VSTD::__gcd(__m1, __m2);
2438 for (_RandomAccessIterator __p = __first + __g; __p != __first;)
2440 value_type __t(_VSTD::move(*--__p));
2441 _RandomAccessIterator __p1 = __p;
2442 _RandomAccessIterator __p2 = __p1 + __m1;
2445 *__p1 = _VSTD::move(*__p2);
2447 const difference_type __d = __last - __p2;
2451 __p2 = __first + (__m1 - __d);
2452 } while (__p2 != __p);
2453 *__p1 = _VSTD::move(__t);
2455 return __first + __m2;
2458 template <class _ForwardIterator>
2459 inline _LIBCPP_INLINE_VISIBILITY
2461 __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
2462 _VSTD::forward_iterator_tag)
2464 typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type;
2465 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2467 if (_VSTD::next(__first) == __middle)
2468 return _VSTD::__rotate_left(__first, __last);
2470 return _VSTD::__rotate_forward(__first, __middle, __last);
2473 template <class _BidirectionalIterator>
2474 inline _LIBCPP_INLINE_VISIBILITY
2475 _BidirectionalIterator
2476 __rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
2477 _VSTD::bidirectional_iterator_tag)
2479 typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type;
2480 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2482 if (_VSTD::next(__first) == __middle)
2483 return _VSTD::__rotate_left(__first, __last);
2484 if (_VSTD::next(__middle) == __last)
2485 return _VSTD::__rotate_right(__first, __last);
2487 return _VSTD::__rotate_forward(__first, __middle, __last);
2490 template <class _RandomAccessIterator>
2491 inline _LIBCPP_INLINE_VISIBILITY
2492 _RandomAccessIterator
2493 __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
2494 _VSTD::random_access_iterator_tag)
2496 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
2497 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2499 if (_VSTD::next(__first) == __middle)
2500 return _VSTD::__rotate_left(__first, __last);
2501 if (_VSTD::next(__middle) == __last)
2502 return _VSTD::__rotate_right(__first, __last);
2503 return _VSTD::__rotate_gcd(__first, __middle, __last);
2505 return _VSTD::__rotate_forward(__first, __middle, __last);
2508 template <class _ForwardIterator>
2509 inline _LIBCPP_INLINE_VISIBILITY
2511 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2513 if (__first == __middle)
2515 if (__middle == __last)
2517 return _VSTD::__rotate(__first, __middle, __last,
2518 typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());
2523 template <class _ForwardIterator, class _OutputIterator>
2524 inline _LIBCPP_INLINE_VISIBILITY
2526 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
2528 return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));
2533 template <class _ForwardIterator, class _Compare>
2534 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2536 min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2538 if (__first != __last)
2540 _ForwardIterator __i = __first;
2541 while (++__i != __last)
2542 if (__comp(*__i, *__first))
2548 template <class _ForwardIterator>
2549 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2551 min_element(_ForwardIterator __first, _ForwardIterator __last)
2553 return _VSTD::min_element(__first, __last,
2554 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2559 template <class _Tp, class _Compare>
2560 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2562 min(const _Tp& __a, const _Tp& __b, _Compare __comp)
2564 return __comp(__b, __a) ? __b : __a;
2567 template <class _Tp>
2568 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2570 min(const _Tp& __a, const _Tp& __b)
2572 return _VSTD::min(__a, __b, __less<_Tp>());
2575 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2577 template<class _Tp, class _Compare>
2578 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2580 min(initializer_list<_Tp> __t, _Compare __comp)
2582 return *_VSTD::min_element(__t.begin(), __t.end(), __comp);
2586 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2588 min(initializer_list<_Tp> __t)
2590 return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>());
2593 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2597 template <class _ForwardIterator, class _Compare>
2598 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2600 max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2602 if (__first != __last)
2604 _ForwardIterator __i = __first;
2605 while (++__i != __last)
2606 if (__comp(*__first, *__i))
2613 template <class _ForwardIterator>
2614 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2616 max_element(_ForwardIterator __first, _ForwardIterator __last)
2618 return _VSTD::max_element(__first, __last,
2619 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2624 template <class _Tp, class _Compare>
2625 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2627 max(const _Tp& __a, const _Tp& __b, _Compare __comp)
2629 return __comp(__a, __b) ? __b : __a;
2632 template <class _Tp>
2633 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2635 max(const _Tp& __a, const _Tp& __b)
2637 return _VSTD::max(__a, __b, __less<_Tp>());
2640 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2642 template<class _Tp, class _Compare>
2643 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2645 max(initializer_list<_Tp> __t, _Compare __comp)
2647 return *_VSTD::max_element(__t.begin(), __t.end(), __comp);
2651 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2653 max(initializer_list<_Tp> __t)
2655 return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>());
2658 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2662 template <class _ForwardIterator, class _Compare>
2663 _LIBCPP_CONSTEXPR_AFTER_CXX11
2664 std::pair<_ForwardIterator, _ForwardIterator>
2665 minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2667 std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);
2668 if (__first != __last)
2670 if (++__first != __last)
2672 if (__comp(*__first, *__result.first))
2673 __result.first = __first;
2675 __result.second = __first;
2676 while (++__first != __last)
2678 _ForwardIterator __i = __first;
2679 if (++__first == __last)
2681 if (__comp(*__i, *__result.first))
2682 __result.first = __i;
2683 else if (!__comp(*__i, *__result.second))
2684 __result.second = __i;
2689 if (__comp(*__first, *__i))
2691 if (__comp(*__first, *__result.first))
2692 __result.first = __first;
2693 if (!__comp(*__i, *__result.second))
2694 __result.second = __i;
2698 if (__comp(*__i, *__result.first))
2699 __result.first = __i;
2700 if (!__comp(*__first, *__result.second))
2701 __result.second = __first;
2710 template <class _ForwardIterator>
2711 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2712 std::pair<_ForwardIterator, _ForwardIterator>
2713 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
2715 return _VSTD::minmax_element(__first, __last,
2716 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2721 template<class _Tp, class _Compare>
2722 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2723 pair<const _Tp&, const _Tp&>
2724 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
2726 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) :
2727 pair<const _Tp&, const _Tp&>(__a, __b);
2731 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2732 pair<const _Tp&, const _Tp&>
2733 minmax(const _Tp& __a, const _Tp& __b)
2735 return _VSTD::minmax(__a, __b, __less<_Tp>());
2738 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2740 template<class _Tp, class _Compare>
2741 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2743 minmax(initializer_list<_Tp> __t, _Compare __comp)
2745 typedef typename initializer_list<_Tp>::const_iterator _Iter;
2746 _Iter __first = __t.begin();
2747 _Iter __last = __t.end();
2748 std::pair<_Tp, _Tp> __result(*__first, *__first);
2751 if (__t.size() % 2 == 0)
2753 if (__comp(*__first, __result.first))
2754 __result.first = *__first;
2756 __result.second = *__first;
2760 while (__first != __last)
2762 _Tp __prev = *__first++;
2763 if (__comp(*__first, __prev)) {
2764 if ( __comp(*__first, __result.first)) __result.first = *__first;
2765 if (!__comp(__prev, __result.second)) __result.second = __prev;
2768 if ( __comp(__prev, __result.first)) __result.first = __prev;
2769 if (!__comp(*__first, __result.second)) __result.second = *__first;
2778 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2780 minmax(initializer_list<_Tp> __t)
2782 return _VSTD::minmax(__t, __less<_Tp>());
2785 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2789 // __independent_bits_engine
2791 template <unsigned long long _Xp, size_t _Rp>
2794 static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp
2795 : __log2_imp<_Xp, _Rp - 1>::value;
2798 template <unsigned long long _Xp>
2799 struct __log2_imp<_Xp, 0>
2801 static const size_t value = 0;
2804 template <size_t _Rp>
2805 struct __log2_imp<0, _Rp>
2807 static const size_t value = _Rp + 1;
2810 template <class _UI, _UI _Xp>
2813 static const size_t value = __log2_imp<_Xp,
2814 sizeof(_UI) * __CHAR_BIT__ - 1>::value;
2817 template<class _Engine, class _UIntType>
2818 class __independent_bits_engine
2822 typedef _UIntType result_type;
2825 typedef typename _Engine::result_type _Engine_result_type;
2826 typedef typename conditional
2828 sizeof(_Engine_result_type) <= sizeof(result_type),
2831 >::type _Working_result_type;
2838 _Working_result_type __y0_;
2839 _Working_result_type __y1_;
2840 _Engine_result_type __mask0_;
2841 _Engine_result_type __mask1_;
2843 #ifdef _LIBCPP_HAS_NO_CONSTEXPR
2844 static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
2845 + _Working_result_type(1);
2847 static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()
2848 + _Working_result_type(1);
2850 static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value;
2851 static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits;
2852 static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
2855 // constructors and seeding functions
2856 __independent_bits_engine(_Engine& __e, size_t __w);
2858 // generating functions
2859 result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
2862 result_type __eval(false_type);
2863 result_type __eval(true_type);
2866 template<class _Engine, class _UIntType>
2867 __independent_bits_engine<_Engine, _UIntType>
2868 ::__independent_bits_engine(_Engine& __e, size_t __w)
2872 __n_ = __w_ / __m + (__w_ % __m != 0);
2873 __w0_ = __w_ / __n_;
2876 else if (__w0_ < _WDt)
2877 __y0_ = (_Rp >> __w0_) << __w0_;
2880 if (_Rp - __y0_ > __y0_ / __n_)
2883 __w0_ = __w_ / __n_;
2885 __y0_ = (_Rp >> __w0_) << __w0_;
2889 __n0_ = __n_ - __w_ % __n_;
2890 if (__w0_ < _WDt - 1)
2891 __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1);
2894 __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :
2895 _Engine_result_type(0);
2896 __mask1_ = __w0_ < _EDt - 1 ?
2897 _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :
2898 _Engine_result_type(~0);
2901 template<class _Engine, class _UIntType>
2904 __independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
2906 return static_cast<result_type>(__e_() & __mask0_);
2909 template<class _Engine, class _UIntType>
2911 __independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
2913 result_type _Sp = 0;
2914 for (size_t __k = 0; __k < __n0_; ++__k)
2916 _Engine_result_type __u;
2919 __u = __e_() - _Engine::min();
2920 } while (__u >= __y0_);
2925 _Sp += __u & __mask0_;
2927 for (size_t __k = __n0_; __k < __n_; ++__k)
2929 _Engine_result_type __u;
2932 __u = __e_() - _Engine::min();
2933 } while (__u >= __y1_);
2934 if (__w0_ < _WDt - 1)
2938 _Sp += __u & __mask1_;
2943 // uniform_int_distribution
2945 template<class _IntType = int>
2946 class uniform_int_distribution
2950 typedef _IntType result_type;
2957 typedef uniform_int_distribution distribution_type;
2959 explicit param_type(result_type __a = 0,
2960 result_type __b = numeric_limits<result_type>::max())
2961 : __a_(__a), __b_(__b) {}
2963 result_type a() const {return __a_;}
2964 result_type b() const {return __b_;}
2966 friend bool operator==(const param_type& __x, const param_type& __y)
2967 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
2968 friend bool operator!=(const param_type& __x, const param_type& __y)
2969 {return !(__x == __y);}
2976 // constructors and reset functions
2977 explicit uniform_int_distribution(result_type __a = 0,
2978 result_type __b = numeric_limits<result_type>::max())
2979 : __p_(param_type(__a, __b)) {}
2980 explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
2983 // generating functions
2984 template<class _URNG> result_type operator()(_URNG& __g)
2985 {return (*this)(__g, __p_);}
2986 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
2988 // property functions
2989 result_type a() const {return __p_.a();}
2990 result_type b() const {return __p_.b();}
2992 param_type param() const {return __p_;}
2993 void param(const param_type& __p) {__p_ = __p;}
2995 result_type min() const {return a();}
2996 result_type max() const {return b();}
2998 friend bool operator==(const uniform_int_distribution& __x,
2999 const uniform_int_distribution& __y)
3000 {return __x.__p_ == __y.__p_;}
3001 friend bool operator!=(const uniform_int_distribution& __x,
3002 const uniform_int_distribution& __y)
3003 {return !(__x == __y);}
3006 template<class _IntType>
3007 template<class _URNG>
3008 typename uniform_int_distribution<_IntType>::result_type
3009 uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
3011 typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
3012 uint32_t, uint64_t>::type _UIntType;
3013 const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1);
3016 const size_t _Dt = numeric_limits<_UIntType>::digits;
3017 typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
3019 return static_cast<result_type>(_Eng(__g, _Dt)());
3020 size_t __w = _Dt - __clz(_Rp) - 1;
3021 if ((_Rp & (std::numeric_limits<_UIntType>::max() >> (_Dt - __w))) != 0)
3028 } while (__u >= _Rp);
3029 return static_cast<result_type>(__u + __p.a());
3032 class _LIBCPP_TYPE_VIS __rs_default;
3034 _LIBCPP_FUNC_VIS __rs_default __rs_get();
3036 class _LIBCPP_TYPE_VIS __rs_default
3038 static unsigned __c_;
3042 typedef uint_fast32_t result_type;
3044 static const result_type _Min = 0;
3045 static const result_type _Max = 0xFFFFFFFF;
3047 __rs_default(const __rs_default&);
3050 result_type operator()();
3052 static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
3053 static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
3055 friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
3058 _LIBCPP_FUNC_VIS __rs_default __rs_get();
3060 template <class _RandomAccessIterator>
3062 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
3064 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3065 typedef uniform_int_distribution<ptrdiff_t> _Dp;
3066 typedef typename _Dp::param_type _Pp;
3067 difference_type __d = __last - __first;
3071 __rs_default __g = __rs_get();
3072 for (--__last, --__d; __first < __last; ++__first, --__d)
3074 difference_type __i = __uid(__g, _Pp(0, __d));
3075 if (__i != difference_type(0))
3076 swap(*__first, *(__first + __i));
3081 template <class _RandomAccessIterator, class _RandomNumberGenerator>
3083 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3084 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3085 _RandomNumberGenerator&& __rand)
3087 _RandomNumberGenerator& __rand)
3090 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3091 difference_type __d = __last - __first;
3094 for (--__last; __first < __last; ++__first, --__d)
3096 difference_type __i = __rand(__d);
3097 swap(*__first, *(__first + __i));
3102 template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
3103 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3104 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3105 _UniformRandomNumberGenerator&& __g)
3107 _UniformRandomNumberGenerator& __g)
3110 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3111 typedef uniform_int_distribution<ptrdiff_t> _Dp;
3112 typedef typename _Dp::param_type _Pp;
3113 difference_type __d = __last - __first;
3117 for (--__last, --__d; __first < __last; ++__first, --__d)
3119 difference_type __i = __uid(__g, _Pp(0, __d));
3120 if (__i != difference_type(0))
3121 swap(*__first, *(__first + __i));
3126 template <class _InputIterator, class _Predicate>
3128 is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3130 for (; __first != __last; ++__first)
3131 if (!__pred(*__first))
3133 if ( __first == __last )
3136 for (; __first != __last; ++__first)
3137 if (__pred(*__first))
3144 template <class _Predicate, class _ForwardIterator>
3146 __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
3150 if (__first == __last)
3152 if (!__pred(*__first))
3156 for (_ForwardIterator __p = __first; ++__p != __last;)
3160 swap(*__first, *__p);
3167 template <class _Predicate, class _BidirectionalIterator>
3168 _BidirectionalIterator
3169 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3170 bidirectional_iterator_tag)
3176 if (__first == __last)
3178 if (!__pred(*__first))
3184 if (__first == --__last)
3186 } while (!__pred(*__last));
3187 swap(*__first, *__last);
3192 template <class _ForwardIterator, class _Predicate>
3193 inline _LIBCPP_INLINE_VISIBILITY
3195 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3197 return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>
3198 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3203 template <class _InputIterator, class _OutputIterator1,
3204 class _OutputIterator2, class _Predicate>
3205 pair<_OutputIterator1, _OutputIterator2>
3206 partition_copy(_InputIterator __first, _InputIterator __last,
3207 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
3210 for (; __first != __last; ++__first)
3212 if (__pred(*__first))
3214 *__out_true = *__first;
3219 *__out_false = *__first;
3223 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
3228 template<class _ForwardIterator, class _Predicate>
3230 partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3232 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3233 difference_type __len = _VSTD::distance(__first, __last);
3236 difference_type __l2 = __len / 2;
3237 _ForwardIterator __m = __first;
3238 _VSTD::advance(__m, __l2);
3252 template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
3254 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3255 _Distance __len, _Pair __p, forward_iterator_tag __fit)
3257 // *__first is known to be false
3263 _ForwardIterator __m = __first;
3266 swap(*__first, *__m);
3271 if (__len <= __p.second)
3272 { // The buffer is big enough to use
3273 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3274 __destruct_n __d(0);
3275 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3276 // Move the falses into the temporary buffer, and the trues to the front of the line
3277 // Update __first to always point to the end of the trues
3278 value_type* __t = __p.first;
3279 ::new(__t) value_type(_VSTD::move(*__first));
3280 __d.__incr((value_type*)0);
3282 _ForwardIterator __i = __first;
3283 while (++__i != __last)
3287 *__first = _VSTD::move(*__i);
3292 ::new(__t) value_type(_VSTD::move(*__i));
3293 __d.__incr((value_type*)0);
3297 // All trues now at start of range, all falses in buffer
3298 // Move falses back into range, but don't mess up __first which points to first false
3300 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3301 *__i = _VSTD::move(*__t2);
3302 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3305 // Else not enough buffer, do in place
3307 _ForwardIterator __m = __first;
3308 _Distance __len2 = __len / 2; // __len2 >= 2
3309 _VSTD::advance(__m, __len2);
3310 // recurse on [__first, __m), *__first know to be false
3311 // F?????????????????
3313 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3314 _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
3315 // TTTFFFFF??????????
3317 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3318 _ForwardIterator __m1 = __m;
3319 _ForwardIterator __second_false = __last;
3320 _Distance __len_half = __len - __len2;
3321 while (__pred(*__m1))
3323 if (++__m1 == __last)
3324 goto __second_half_done;
3327 // TTTFFFFFTTTF??????
3329 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
3331 // TTTFFFFFTTTTTFFFFF
3333 return _VSTD::rotate(__first_false, __m, __second_false);
3334 // TTTTTTTTFFFFFFFFFF
3338 struct __return_temporary_buffer
3340 template <class _Tp>
3341 _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}
3344 template <class _Predicate, class _ForwardIterator>
3346 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3347 forward_iterator_tag)
3349 const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment
3350 // Either prove all true and return __first or point to first false
3353 if (__first == __last)
3355 if (!__pred(*__first))
3359 // We now have a reduced range [__first, __last)
3360 // *__first is known to be false
3361 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3362 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3363 difference_type __len = _VSTD::distance(__first, __last);
3364 pair<value_type*, ptrdiff_t> __p(0, 0);
3365 unique_ptr<value_type, __return_temporary_buffer> __h;
3366 if (__len >= __alloc_limit)
3368 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3369 __h.reset(__p.first);
3371 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3372 (__first, __last, __pred, __len, __p, forward_iterator_tag());
3375 template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
3376 _BidirectionalIterator
3377 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3378 _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
3380 // *__first is known to be false
3381 // *__last is known to be true
3385 swap(*__first, *__last);
3390 _BidirectionalIterator __m = __first;
3393 swap(*__first, *__m);
3394 swap(*__m, *__last);
3397 swap(*__m, *__last);
3398 swap(*__first, *__m);
3401 if (__len <= __p.second)
3402 { // The buffer is big enough to use
3403 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3404 __destruct_n __d(0);
3405 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3406 // Move the falses into the temporary buffer, and the trues to the front of the line
3407 // Update __first to always point to the end of the trues
3408 value_type* __t = __p.first;
3409 ::new(__t) value_type(_VSTD::move(*__first));
3410 __d.__incr((value_type*)0);
3412 _BidirectionalIterator __i = __first;
3413 while (++__i != __last)
3417 *__first = _VSTD::move(*__i);
3422 ::new(__t) value_type(_VSTD::move(*__i));
3423 __d.__incr((value_type*)0);
3427 // move *__last, known to be true
3428 *__first = _VSTD::move(*__i);
3430 // All trues now at start of range, all falses in buffer
3431 // Move falses back into range, but don't mess up __first which points to first false
3432 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3433 *__i = _VSTD::move(*__t2);
3434 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3437 // Else not enough buffer, do in place
3439 _BidirectionalIterator __m = __first;
3440 _Distance __len2 = __len / 2; // __len2 >= 2
3441 _VSTD::advance(__m, __len2);
3442 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
3443 // F????????????????T
3445 _BidirectionalIterator __m1 = __m;
3446 _BidirectionalIterator __first_false = __first;
3447 _Distance __len_half = __len2;
3448 while (!__pred(*--__m1))
3450 if (__m1 == __first)
3451 goto __first_half_done;
3454 // F???TFFF?????????T
3456 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3457 __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3459 // TTTFFFFF?????????T
3461 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3463 _BidirectionalIterator __second_false = __last;
3465 __len_half = __len - __len2;
3466 while (__pred(*__m1))
3468 if (++__m1 == __last)
3469 goto __second_half_done;
3472 // TTTFFFFFTTTF?????T
3474 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
3476 // TTTFFFFFTTTTTFFFFF
3478 return _VSTD::rotate(__first_false, __m, __second_false);
3479 // TTTTTTTTFFFFFFFFFF
3483 template <class _Predicate, class _BidirectionalIterator>
3484 _BidirectionalIterator
3485 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3486 bidirectional_iterator_tag)
3488 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3489 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3490 const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment
3491 // Either prove all true and return __first or point to first false
3494 if (__first == __last)
3496 if (!__pred(*__first))
3500 // __first points to first false, everything prior to __first is already set.
3501 // Either prove [__first, __last) is all false and return __first, or point __last to last true
3504 if (__first == --__last)
3506 } while (!__pred(*__last));
3507 // We now have a reduced range [__first, __last]
3508 // *__first is known to be false
3509 // *__last is known to be true
3511 difference_type __len = _VSTD::distance(__first, __last) + 1;
3512 pair<value_type*, ptrdiff_t> __p(0, 0);
3513 unique_ptr<value_type, __return_temporary_buffer> __h;
3514 if (__len >= __alloc_limit)
3516 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3517 __h.reset(__p.first);
3519 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3520 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3523 template <class _ForwardIterator, class _Predicate>
3524 inline _LIBCPP_INLINE_VISIBILITY
3526 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3528 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3529 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3534 template <class _ForwardIterator, class _Compare>
3536 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3538 if (__first != __last)
3540 _ForwardIterator __i = __first;
3541 while (++__i != __last)
3543 if (__comp(*__i, *__first))
3551 template<class _ForwardIterator>
3552 inline _LIBCPP_INLINE_VISIBILITY
3554 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3556 return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3561 template <class _ForwardIterator, class _Compare>
3562 inline _LIBCPP_INLINE_VISIBILITY
3564 is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3566 return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
3569 template<class _ForwardIterator>
3570 inline _LIBCPP_INLINE_VISIBILITY
3572 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3574 return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3579 // stable, 2-3 compares, 0-2 swaps
3581 template <class _Compare, class _ForwardIterator>
3583 __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
3586 if (!__c(*__y, *__x)) // if x <= y
3588 if (!__c(*__z, *__y)) // if y <= z
3589 return __r; // x <= y && y <= z
3591 swap(*__y, *__z); // x <= z && y < z
3593 if (__c(*__y, *__x)) // if x > y
3595 swap(*__x, *__y); // x < y && y <= z
3598 return __r; // x <= y && y < z
3600 if (__c(*__z, *__y)) // x > y, if y > z
3602 swap(*__x, *__z); // x < y && y < z
3606 swap(*__x, *__y); // x > y && y <= z
3607 __r = 1; // x < y && x <= z
3608 if (__c(*__z, *__y)) // if y > z
3610 swap(*__y, *__z); // x <= y && y < z
3614 } // x <= y && y <= z
3616 // stable, 3-6 compares, 0-5 swaps
3618 template <class _Compare, class _ForwardIterator>
3620 __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3621 _ForwardIterator __x4, _Compare __c)
3623 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
3624 if (__c(*__x4, *__x3))
3628 if (__c(*__x3, *__x2))
3632 if (__c(*__x2, *__x1))
3642 // stable, 4-10 compares, 0-9 swaps
3644 template <class _Compare, class _ForwardIterator>
3646 __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3647 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
3649 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
3650 if (__c(*__x5, *__x4))
3654 if (__c(*__x4, *__x3))
3658 if (__c(*__x3, *__x2))
3662 if (__c(*__x2, *__x1))
3674 template <class _Compare, class _BirdirectionalIterator>
3676 __selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3678 _BirdirectionalIterator __lm1 = __last;
3679 for (--__lm1; __first != __lm1; ++__first)
3681 _BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator,
3682 typename add_lvalue_reference<_Compare>::type>
3683 (__first, __last, __comp);
3685 swap(*__first, *__i);
3689 template <class _Compare, class _BirdirectionalIterator>
3691 __insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3693 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3694 if (__first != __last)
3696 _BirdirectionalIterator __i = __first;
3697 for (++__i; __i != __last; ++__i)
3699 _BirdirectionalIterator __j = __i;
3700 value_type __t(_VSTD::move(*__j));
3701 for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
3702 *__j = _VSTD::move(*__k);
3703 *__j = _VSTD::move(__t);
3708 template <class _Compare, class _RandomAccessIterator>
3710 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3712 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3713 _RandomAccessIterator __j = __first+2;
3714 __sort3<_Compare>(__first, __first+1, __j, __comp);
3715 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3717 if (__comp(*__i, *__j))
3719 value_type __t(_VSTD::move(*__i));
3720 _RandomAccessIterator __k = __j;
3724 *__j = _VSTD::move(*__k);
3726 } while (__j != __first && __comp(__t, *--__k));
3727 *__j = _VSTD::move(__t);
3733 template <class _Compare, class _RandomAccessIterator>
3735 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3737 switch (__last - __first)
3743 if (__comp(*--__last, *__first))
3744 swap(*__first, *__last);
3747 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3750 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3753 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3756 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3757 _RandomAccessIterator __j = __first+2;
3758 __sort3<_Compare>(__first, __first+1, __j, __comp);
3759 const unsigned __limit = 8;
3760 unsigned __count = 0;
3761 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3763 if (__comp(*__i, *__j))
3765 value_type __t(_VSTD::move(*__i));
3766 _RandomAccessIterator __k = __j;
3770 *__j = _VSTD::move(*__k);
3772 } while (__j != __first && __comp(__t, *--__k));
3773 *__j = _VSTD::move(__t);
3774 if (++__count == __limit)
3775 return ++__i == __last;
3782 template <class _Compare, class _BirdirectionalIterator>
3784 __insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
3785 typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
3787 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3788 if (__first1 != __last1)
3790 __destruct_n __d(0);
3791 unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
3792 value_type* __last2 = __first2;
3793 ::new(__last2) value_type(_VSTD::move(*__first1));
3794 __d.__incr((value_type*)0);
3795 for (++__last2; ++__first1 != __last1; ++__last2)
3797 value_type* __j2 = __last2;
3798 value_type* __i2 = __j2;
3799 if (__comp(*__first1, *--__i2))
3801 ::new(__j2) value_type(_VSTD::move(*__i2));
3802 __d.__incr((value_type*)0);
3803 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2)
3804 *__j2 = _VSTD::move(*__i2);
3805 *__j2 = _VSTD::move(*__first1);
3809 ::new(__j2) value_type(_VSTD::move(*__first1));
3810 __d.__incr((value_type*)0);
3817 template <class _Compare, class _RandomAccessIterator>
3819 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3821 // _Compare is known to be a reference type
3822 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3823 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3824 const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
3825 is_trivially_copy_assignable<value_type>::value ? 30 : 6;
3829 difference_type __len = __last - __first;
3836 if (__comp(*--__last, *__first))
3837 swap(*__first, *__last);
3840 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3843 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3846 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3849 if (__len <= __limit)
3851 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
3855 _RandomAccessIterator __m = __first;
3856 _RandomAccessIterator __lm1 = __last;
3860 difference_type __delta;
3866 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
3872 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
3876 // partition [__first, __m) < *__m and *__m <= [__m, __last)
3877 // (this inhibits tossing elements equivalent to __m around unnecessarily)
3878 _RandomAccessIterator __i = __first;
3879 _RandomAccessIterator __j = __lm1;
3880 // j points beyond range to be tested, *__m is known to be <= *__lm1
3881 // The search going up is known to be guarded but the search coming down isn't.
3882 // Prime the downward search with a guard.
3883 if (!__comp(*__i, *__m)) // if *__first == *__m
3885 // *__first == *__m, *__first doesn't go in first part
3886 // manually guard downward moving __j against __i
3891 // *__first == *__m, *__m <= all other elements
3892 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
3893 ++__i; // __first + 1
3895 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
3900 return; // [__first, __last) all equivalent elements
3901 if (__comp(*__first, *__i))
3911 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
3916 while (!__comp(*__first, *__i))
3918 while (__comp(*__first, *--__j))
3926 // [__first, __i) == *__first and *__first < [__i, __last)
3927 // The first part is sorted, sort the secod part
3928 // _VSTD::__sort<_Compare>(__i, __last, __comp);
3932 if (__comp(*__j, *__m))
3936 break; // found guard for downward moving __j, now use unguarded partition
3940 // It is known that *__i < *__m
3942 // j points beyond range to be tested, *__m is known to be <= *__lm1
3943 // if not yet partitioned...
3946 // known that *(__i - 1) < *__m
3947 // known that __i <= __m
3950 // __m still guards upward moving __i
3951 while (__comp(*__i, *__m))
3953 // It is now known that a guard exists for downward moving __j
3954 while (!__comp(*--__j, *__m))
3960 // It is known that __m != __j
3961 // If __m just moved, follow it
3967 // [__first, __i) < *__m and *__m <= [__i, __last)
3968 if (__i != __m && __comp(*__m, *__i))
3973 // [__first, __i) < *__i and *__i <= [__i+1, __last)
3974 // If we were given a perfect partition, see if insertion sort is quick...
3977 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
3978 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
3994 // sort smaller range with recursive call and larger with tail recursion elimination
3995 if (__i - __first < __last - __i)
3997 _VSTD::__sort<_Compare>(__first, __i, __comp);
3998 // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4003 _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4004 // _VSTD::__sort<_Compare>(__first, __i, __comp);
4010 // This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
4011 template <class _RandomAccessIterator, class _Compare>
4012 inline _LIBCPP_INLINE_VISIBILITY
4014 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4016 #ifdef _LIBCPP_DEBUG
4017 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4018 __debug_less<_Compare> __c(__comp);
4019 __sort<_Comp_ref>(__first, __last, __c);
4020 #else // _LIBCPP_DEBUG
4021 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4022 __sort<_Comp_ref>(__first, __last, __comp);
4023 #endif // _LIBCPP_DEBUG
4026 template <class _RandomAccessIterator>
4027 inline _LIBCPP_INLINE_VISIBILITY
4029 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4031 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4034 template <class _Tp>
4035 inline _LIBCPP_INLINE_VISIBILITY
4037 sort(_Tp** __first, _Tp** __last)
4039 _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
4042 template <class _Tp>
4043 inline _LIBCPP_INLINE_VISIBILITY
4045 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
4047 _VSTD::sort(__first.base(), __last.base());
4050 template <class _Tp, class _Compare>
4051 inline _LIBCPP_INLINE_VISIBILITY
4053 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
4055 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4056 _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
4060 #pragma warning( push )
4061 #pragma warning( disable: 4231)
4062 #endif // _LIBCPP_MSVC
4063 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
4064 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4065 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4066 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4067 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))
4068 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4069 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&))
4070 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4071 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&))
4072 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4073 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4074 _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>&))
4075 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&))
4076 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&))
4077 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4079 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))
4080 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4081 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4082 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4083 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))
4084 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4085 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&))
4086 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4087 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&))
4088 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4089 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4090 _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>&))
4091 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&))
4092 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&))
4093 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4095 _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>&))
4097 #pragma warning( pop )
4098 #endif // _LIBCPP_MSVC
4102 template <class _Compare, class _ForwardIterator, class _Tp>
4104 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4106 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4107 difference_type __len = _VSTD::distance(__first, __last);
4110 difference_type __l2 = __len / 2;
4111 _ForwardIterator __m = __first;
4112 _VSTD::advance(__m, __l2);
4113 if (__comp(*__m, __value_))
4124 template <class _ForwardIterator, class _Tp, class _Compare>
4125 inline _LIBCPP_INLINE_VISIBILITY
4127 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4129 #ifdef _LIBCPP_DEBUG
4130 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4131 __debug_less<_Compare> __c(__comp);
4132 return __lower_bound<_Comp_ref>(__first, __last, __value_, __c);
4133 #else // _LIBCPP_DEBUG
4134 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4135 return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp);
4136 #endif // _LIBCPP_DEBUG
4139 template <class _ForwardIterator, class _Tp>
4140 inline _LIBCPP_INLINE_VISIBILITY
4142 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4144 return _VSTD::lower_bound(__first, __last, __value_,
4145 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4150 template <class _Compare, class _ForwardIterator, class _Tp>
4152 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4154 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4155 difference_type __len = _VSTD::distance(__first, __last);
4158 difference_type __l2 = __len / 2;
4159 _ForwardIterator __m = __first;
4160 _VSTD::advance(__m, __l2);
4161 if (__comp(__value_, *__m))
4172 template <class _ForwardIterator, class _Tp, class _Compare>
4173 inline _LIBCPP_INLINE_VISIBILITY
4175 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4177 #ifdef _LIBCPP_DEBUG
4178 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4179 __debug_less<_Compare> __c(__comp);
4180 return __upper_bound<_Comp_ref>(__first, __last, __value_, __c);
4181 #else // _LIBCPP_DEBUG
4182 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4183 return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp);
4184 #endif // _LIBCPP_DEBUG
4187 template <class _ForwardIterator, class _Tp>
4188 inline _LIBCPP_INLINE_VISIBILITY
4190 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4192 return _VSTD::upper_bound(__first, __last, __value_,
4193 __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
4198 template <class _Compare, class _ForwardIterator, class _Tp>
4199 pair<_ForwardIterator, _ForwardIterator>
4200 __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4202 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4203 difference_type __len = _VSTD::distance(__first, __last);
4206 difference_type __l2 = __len / 2;
4207 _ForwardIterator __m = __first;
4208 _VSTD::advance(__m, __l2);
4209 if (__comp(*__m, __value_))
4214 else if (__comp(__value_, *__m))
4221 _ForwardIterator __mp1 = __m;
4222 return pair<_ForwardIterator, _ForwardIterator>
4224 __lower_bound<_Compare>(__first, __m, __value_, __comp),
4225 __upper_bound<_Compare>(++__mp1, __last, __value_, __comp)
4229 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4232 template <class _ForwardIterator, class _Tp, class _Compare>
4233 inline _LIBCPP_INLINE_VISIBILITY
4234 pair<_ForwardIterator, _ForwardIterator>
4235 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4237 #ifdef _LIBCPP_DEBUG
4238 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4239 __debug_less<_Compare> __c(__comp);
4240 return __equal_range<_Comp_ref>(__first, __last, __value_, __c);
4241 #else // _LIBCPP_DEBUG
4242 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4243 return __equal_range<_Comp_ref>(__first, __last, __value_, __comp);
4244 #endif // _LIBCPP_DEBUG
4247 template <class _ForwardIterator, class _Tp>
4248 inline _LIBCPP_INLINE_VISIBILITY
4249 pair<_ForwardIterator, _ForwardIterator>
4250 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4252 return _VSTD::equal_range(__first, __last, __value_,
4253 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4258 template <class _Compare, class _ForwardIterator, class _Tp>
4259 inline _LIBCPP_INLINE_VISIBILITY
4261 __binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4263 __first = __lower_bound<_Compare>(__first, __last, __value_, __comp);
4264 return __first != __last && !__comp(__value_, *__first);
4267 template <class _ForwardIterator, class _Tp, class _Compare>
4268 inline _LIBCPP_INLINE_VISIBILITY
4270 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4272 #ifdef _LIBCPP_DEBUG
4273 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4274 __debug_less<_Compare> __c(__comp);
4275 return __binary_search<_Comp_ref>(__first, __last, __value_, __c);
4276 #else // _LIBCPP_DEBUG
4277 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4278 return __binary_search<_Comp_ref>(__first, __last, __value_, __comp);
4279 #endif // _LIBCPP_DEBUG
4282 template <class _ForwardIterator, class _Tp>
4283 inline _LIBCPP_INLINE_VISIBILITY
4285 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4287 return _VSTD::binary_search(__first, __last, __value_,
4288 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4293 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4295 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4296 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4298 for (; __first1 != __last1; ++__result)
4300 if (__first2 == __last2)
4301 return _VSTD::copy(__first1, __last1, __result);
4302 if (__comp(*__first2, *__first1))
4304 *__result = *__first2;
4309 *__result = *__first1;
4313 return _VSTD::copy(__first2, __last2, __result);
4316 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4317 inline _LIBCPP_INLINE_VISIBILITY
4319 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4320 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4322 #ifdef _LIBCPP_DEBUG
4323 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4324 __debug_less<_Compare> __c(__comp);
4325 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
4326 #else // _LIBCPP_DEBUG
4327 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4328 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4329 #endif // _LIBCPP_DEBUG
4332 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4333 inline _LIBCPP_INLINE_VISIBILITY
4335 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4336 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4338 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
4339 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
4340 return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
4345 template <class _Compare, class _InputIterator1, class _InputIterator2,
4346 class _OutputIterator>
4347 void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
4348 _InputIterator2 __first2, _InputIterator2 __last2,
4349 _OutputIterator __result, _Compare __comp)
4351 for (; __first1 != __last1; ++__result)
4353 if (__first2 == __last2)
4355 _VSTD::move(__first1, __last1, __result);
4359 if (__comp(*__first2, *__first1))
4361 *__result = _VSTD::move(*__first2);
4366 *__result = _VSTD::move(*__first1);
4370 // __first2 through __last2 are already in the right spot.
4373 template <class _Compare, class _BidirectionalIterator>
4375 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4376 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4377 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4378 typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
4380 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4381 __destruct_n __d(0);
4382 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4383 if (__len1 <= __len2)
4385 value_type* __p = __buff;
4386 for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4387 ::new(__p) value_type(_VSTD::move(*__i));
4388 __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);
4392 value_type* __p = __buff;
4393 for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4394 ::new(__p) value_type(_VSTD::move(*__i));
4395 typedef reverse_iterator<_BidirectionalIterator> _RBi;
4396 typedef reverse_iterator<value_type*> _Rv;
4397 __half_inplace_merge(_Rv(__p), _Rv(__buff),
4398 _RBi(__middle), _RBi(__first),
4399 _RBi(__last), __negate<_Compare>(__comp));
4403 template <class _Compare, class _BidirectionalIterator>
4405 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4406 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4407 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4408 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
4410 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4413 // if __middle == __last, we're done
4416 if (__len1 <= __buff_size || __len2 <= __buff_size)
4417 return __buffered_inplace_merge<_Compare>
4418 (__first, __middle, __last, __comp, __len1, __len2, __buff);
4419 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
4420 for (; true; ++__first, (void) --__len1)
4424 if (__comp(*__middle, *__first))
4427 // __first < __middle < __last
4428 // *__first > *__middle
4429 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4431 // [__first, __m1) <= [__middle, __m2)
4432 // [__middle, __m2) < [__m1, __middle)
4433 // [__m1, __middle) <= [__m2, __last)
4434 // and __m1 or __m2 is in the middle of its range
4435 _BidirectionalIterator __m1; // "median" of [__first, __middle)
4436 _BidirectionalIterator __m2; // "median" of [__middle, __last)
4437 difference_type __len11; // distance(__first, __m1)
4438 difference_type __len21; // distance(__middle, __m2)
4439 // binary search smaller range
4440 if (__len1 < __len2)
4441 { // __len >= 1, __len2 >= 2
4442 __len21 = __len2 / 2;
4444 _VSTD::advance(__m2, __len21);
4445 __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4446 __len11 = _VSTD::distance(__first, __m1);
4451 { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
4452 // It is known *__first > *__middle
4453 swap(*__first, *__middle);
4456 // __len1 >= 2, __len2 >= 1
4457 __len11 = __len1 / 2;
4459 _VSTD::advance(__m1, __len11);
4460 __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp);
4461 __len21 = _VSTD::distance(__middle, __m2);
4463 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle)
4464 difference_type __len22 = __len2 - __len21; // distance(__m2, __last)
4465 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4466 // swap middle two partitions
4467 __middle = _VSTD::rotate(__m1, __middle, __m2);
4468 // __len12 and __len21 now have swapped meanings
4469 // merge smaller range with recurisve call and larger with tail recursion elimination
4470 if (__len11 + __len21 < __len12 + __len22)
4472 __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4473 // __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4481 __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4482 // __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4491 template <class _BidirectionalIterator, class _Compare>
4492 inline _LIBCPP_INLINE_VISIBILITY
4494 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4497 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4498 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4499 difference_type __len1 = _VSTD::distance(__first, __middle);
4500 difference_type __len2 = _VSTD::distance(__middle, __last);
4501 difference_type __buf_size = _VSTD::min(__len1, __len2);
4502 pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
4503 unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
4505 #ifdef _LIBCPP_DEBUG
4506 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4507 __debug_less<_Compare> __c(__comp);
4508 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2,
4509 __buf.first, __buf.second);
4510 #else // _LIBCPP_DEBUG
4511 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4512 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4513 __buf.first, __buf.second);
4514 #endif // _LIBCPP_DEBUG
4517 template <class _BidirectionalIterator>
4518 inline _LIBCPP_INLINE_VISIBILITY
4520 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
4522 _VSTD::inplace_merge(__first, __middle, __last,
4523 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4528 template <class _Compare, class _InputIterator1, class _InputIterator2>
4530 __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
4531 _InputIterator2 __first2, _InputIterator2 __last2,
4532 typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
4534 typedef typename iterator_traits<_InputIterator1>::value_type value_type;
4535 __destruct_n __d(0);
4536 unique_ptr<value_type, __destruct_n&> __h(__result, __d);
4537 for (; true; ++__result)
4539 if (__first1 == __last1)
4541 for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0))
4542 ::new (__result) value_type(_VSTD::move(*__first2));
4546 if (__first2 == __last2)
4548 for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0))
4549 ::new (__result) value_type(_VSTD::move(*__first1));
4553 if (__comp(*__first2, *__first1))
4555 ::new (__result) value_type(_VSTD::move(*__first2));
4556 __d.__incr((value_type*)0);
4561 ::new (__result) value_type(_VSTD::move(*__first1));
4562 __d.__incr((value_type*)0);
4568 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4570 __merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
4571 _InputIterator2 __first2, _InputIterator2 __last2,
4572 _OutputIterator __result, _Compare __comp)
4574 for (; __first1 != __last1; ++__result)
4576 if (__first2 == __last2)
4578 for (; __first1 != __last1; ++__first1, ++__result)
4579 *__result = _VSTD::move(*__first1);
4582 if (__comp(*__first2, *__first1))
4584 *__result = _VSTD::move(*__first2);
4589 *__result = _VSTD::move(*__first1);
4593 for (; __first2 != __last2; ++__first2, ++__result)
4594 *__result = _VSTD::move(*__first2);
4597 template <class _Compare, class _RandomAccessIterator>
4599 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4600 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4601 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
4603 template <class _Compare, class _RandomAccessIterator>
4605 __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
4606 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4607 typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
4609 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4615 ::new(__first2) value_type(_VSTD::move(*__first1));
4618 __destruct_n __d(0);
4619 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
4620 if (__comp(*--__last1, *__first1))
4622 ::new(__first2) value_type(_VSTD::move(*__last1));
4623 __d.__incr((value_type*)0);
4625 ::new(__first2) value_type(_VSTD::move(*__first1));
4629 ::new(__first2) value_type(_VSTD::move(*__first1));
4630 __d.__incr((value_type*)0);
4632 ::new(__first2) value_type(_VSTD::move(*__last1));
4639 __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
4642 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4643 _RandomAccessIterator __m = __first1 + __l2;
4644 __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
4645 __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
4646 __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
4649 template <class _Tp>
4650 struct __stable_sort_switch
4652 static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
4655 template <class _Compare, class _RandomAccessIterator>
4657 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4658 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4659 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
4661 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4662 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4669 if (__comp(*--__last, *__first))
4670 swap(*__first, *__last);
4673 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4675 __insertion_sort<_Compare>(__first, __last, __comp);
4678 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4679 _RandomAccessIterator __m = __first + __l2;
4680 if (__len <= __buff_size)
4682 __destruct_n __d(0);
4683 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4684 __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4685 __d.__set(__l2, (value_type*)0);
4686 __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
4687 __d.__set(__len, (value_type*)0);
4688 __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4689 // __merge<_Compare>(move_iterator<value_type*>(__buff),
4690 // move_iterator<value_type*>(__buff + __l2),
4691 // move_iterator<_RandomAccessIterator>(__buff + __l2),
4692 // move_iterator<_RandomAccessIterator>(__buff + __len),
4693 // __first, __comp);
4696 __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4697 __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
4698 __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4701 template <class _RandomAccessIterator, class _Compare>
4702 inline _LIBCPP_INLINE_VISIBILITY
4704 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4706 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4707 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4708 difference_type __len = __last - __first;
4709 pair<value_type*, ptrdiff_t> __buf(0, 0);
4710 unique_ptr<value_type, __return_temporary_buffer> __h;
4711 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4713 __buf = _VSTD::get_temporary_buffer<value_type>(__len);
4714 __h.reset(__buf.first);
4716 #ifdef _LIBCPP_DEBUG
4717 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4718 __debug_less<_Compare> __c(__comp);
4719 __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);
4720 #else // _LIBCPP_DEBUG
4721 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4722 __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4723 #endif // _LIBCPP_DEBUG
4726 template <class _RandomAccessIterator>
4727 inline _LIBCPP_INLINE_VISIBILITY
4729 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4731 _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4736 template <class _RandomAccessIterator, class _Compare>
4737 _RandomAccessIterator
4738 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4740 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4741 difference_type __len = __last - __first;
4742 difference_type __p = 0;
4743 difference_type __c = 1;
4744 _RandomAccessIterator __pp = __first;
4747 _RandomAccessIterator __cp = __first + __c;
4748 if (__comp(*__pp, *__cp))
4754 if (__comp(*__pp, *__cp))
4763 template<class _RandomAccessIterator>
4764 inline _LIBCPP_INLINE_VISIBILITY
4765 _RandomAccessIterator
4766 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4768 return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4773 template <class _RandomAccessIterator, class _Compare>
4774 inline _LIBCPP_INLINE_VISIBILITY
4776 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4778 return _VSTD::is_heap_until(__first, __last, __comp) == __last;
4781 template<class _RandomAccessIterator>
4782 inline _LIBCPP_INLINE_VISIBILITY
4784 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4786 return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4791 template <class _Compare, class _RandomAccessIterator>
4793 __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4794 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4796 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4799 __len = (__len - 2) / 2;
4800 _RandomAccessIterator __ptr = __first + __len;
4801 if (__comp(*__ptr, *--__last))
4803 value_type __t(_VSTD::move(*__last));
4806 *__last = _VSTD::move(*__ptr);
4810 __len = (__len - 1) / 2;
4811 __ptr = __first + __len;
4812 } while (__comp(*__ptr, __t));
4813 *__last = _VSTD::move(__t);
4818 template <class _RandomAccessIterator, class _Compare>
4819 inline _LIBCPP_INLINE_VISIBILITY
4821 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4823 #ifdef _LIBCPP_DEBUG
4824 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4825 __debug_less<_Compare> __c(__comp);
4826 __sift_up<_Comp_ref>(__first, __last, __c, __last - __first);
4827 #else // _LIBCPP_DEBUG
4828 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4829 __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
4830 #endif // _LIBCPP_DEBUG
4833 template <class _RandomAccessIterator>
4834 inline _LIBCPP_INLINE_VISIBILITY
4836 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4838 _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4843 template <class _Compare, class _RandomAccessIterator>
4845 __sift_down(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4846 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4847 _RandomAccessIterator __start)
4849 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4850 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4851 // left-child of __start is at 2 * __start + 1
4852 // right-child of __start is at 2 * __start + 2
4853 difference_type __child = __start - __first;
4855 if (__len < 2 || (__len - 2) / 2 < __child)
4858 __child = 2 * __child + 1;
4859 _RandomAccessIterator __child_i = __first + __child;
4861 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4862 // right-child exists and is greater than left-child
4867 // check if we are in heap-order
4868 if (__comp(*__child_i, *__start))
4869 // we are, __start is larger than it's largest child
4872 value_type __top(_VSTD::move(*__start));
4875 // we are not in heap-order, swap the parent with it's largest child
4876 *__start = _VSTD::move(*__child_i);
4877 __start = __child_i;
4879 if ((__len - 2) / 2 < __child)
4882 // recompute the child based off of the updated parent
4883 __child = 2 * __child + 1;
4884 __child_i = __first + __child;
4886 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4887 // right-child exists and is greater than left-child
4892 // check if we are in heap-order
4893 } while (!__comp(*__child_i, __top));
4894 *__start = _VSTD::move(__top);
4897 template <class _Compare, class _RandomAccessIterator>
4898 inline _LIBCPP_INLINE_VISIBILITY
4900 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4901 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4905 swap(*__first, *--__last);
4906 __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);
4910 template <class _RandomAccessIterator, class _Compare>
4911 inline _LIBCPP_INLINE_VISIBILITY
4913 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4915 #ifdef _LIBCPP_DEBUG
4916 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4917 __debug_less<_Compare> __c(__comp);
4918 __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);
4919 #else // _LIBCPP_DEBUG
4920 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4921 __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
4922 #endif // _LIBCPP_DEBUG
4925 template <class _RandomAccessIterator>
4926 inline _LIBCPP_INLINE_VISIBILITY
4928 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4930 _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4935 template <class _Compare, class _RandomAccessIterator>
4937 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4939 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4940 difference_type __n = __last - __first;
4943 // start from the first parent, there is no need to consider children
4944 for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start)
4946 __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start);
4951 template <class _RandomAccessIterator, class _Compare>
4952 inline _LIBCPP_INLINE_VISIBILITY
4954 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4956 #ifdef _LIBCPP_DEBUG
4957 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4958 __debug_less<_Compare> __c(__comp);
4959 __make_heap<_Comp_ref>(__first, __last, __c);
4960 #else // _LIBCPP_DEBUG
4961 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4962 __make_heap<_Comp_ref>(__first, __last, __comp);
4963 #endif // _LIBCPP_DEBUG
4966 template <class _RandomAccessIterator>
4967 inline _LIBCPP_INLINE_VISIBILITY
4969 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4971 _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4976 template <class _Compare, class _RandomAccessIterator>
4978 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4980 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4981 for (difference_type __n = __last - __first; __n > 1; --__last, --__n)
4982 __pop_heap<_Compare>(__first, __last, __comp, __n);
4985 template <class _RandomAccessIterator, class _Compare>
4986 inline _LIBCPP_INLINE_VISIBILITY
4988 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4990 #ifdef _LIBCPP_DEBUG
4991 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4992 __debug_less<_Compare> __c(__comp);
4993 __sort_heap<_Comp_ref>(__first, __last, __c);
4994 #else // _LIBCPP_DEBUG
4995 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4996 __sort_heap<_Comp_ref>(__first, __last, __comp);
4997 #endif // _LIBCPP_DEBUG
5000 template <class _RandomAccessIterator>
5001 inline _LIBCPP_INLINE_VISIBILITY
5003 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5005 _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5010 template <class _Compare, class _RandomAccessIterator>
5012 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5015 __make_heap<_Compare>(__first, __middle, __comp);
5016 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
5017 for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
5019 if (__comp(*__i, *__first))
5021 swap(*__i, *__first);
5022 __sift_down<_Compare>(__first, __middle, __comp, __len, __first);
5025 __sort_heap<_Compare>(__first, __middle, __comp);
5028 template <class _RandomAccessIterator, class _Compare>
5029 inline _LIBCPP_INLINE_VISIBILITY
5031 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5034 #ifdef _LIBCPP_DEBUG
5035 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5036 __debug_less<_Compare> __c(__comp);
5037 __partial_sort<_Comp_ref>(__first, __middle, __last, __c);
5038 #else // _LIBCPP_DEBUG
5039 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5040 __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
5041 #endif // _LIBCPP_DEBUG
5044 template <class _RandomAccessIterator>
5045 inline _LIBCPP_INLINE_VISIBILITY
5047 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
5049 _VSTD::partial_sort(__first, __middle, __last,
5050 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5053 // partial_sort_copy
5055 template <class _Compare, class _InputIterator, class _RandomAccessIterator>
5056 _RandomAccessIterator
5057 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
5058 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5060 _RandomAccessIterator __r = __result_first;
5061 if (__r != __result_last)
5063 for (; __first != __last && __r != __result_last; (void) ++__first, ++__r)
5065 __make_heap<_Compare>(__result_first, __r, __comp);
5066 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
5067 for (; __first != __last; ++__first)
5068 if (__comp(*__first, *__result_first))
5070 *__result_first = *__first;
5071 __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first);
5073 __sort_heap<_Compare>(__result_first, __r, __comp);
5078 template <class _InputIterator, class _RandomAccessIterator, class _Compare>
5079 inline _LIBCPP_INLINE_VISIBILITY
5080 _RandomAccessIterator
5081 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5082 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5084 #ifdef _LIBCPP_DEBUG
5085 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5086 __debug_less<_Compare> __c(__comp);
5087 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);
5088 #else // _LIBCPP_DEBUG
5089 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5090 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
5091 #endif // _LIBCPP_DEBUG
5094 template <class _InputIterator, class _RandomAccessIterator>
5095 inline _LIBCPP_INLINE_VISIBILITY
5096 _RandomAccessIterator
5097 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5098 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
5100 return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
5101 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5106 template <class _Compare, class _RandomAccessIterator>
5108 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5110 // _Compare is known to be a reference type
5111 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5112 const difference_type __limit = 7;
5116 if (__nth == __last)
5118 difference_type __len = __last - __first;
5125 if (__comp(*--__last, *__first))
5126 swap(*__first, *__last);
5130 _RandomAccessIterator __m = __first;
5131 _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
5135 if (__len <= __limit)
5137 __selection_sort<_Compare>(__first, __last, __comp);
5140 // __len > __limit >= 3
5141 _RandomAccessIterator __m = __first + __len/2;
5142 _RandomAccessIterator __lm1 = __last;
5143 unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
5145 // partition [__first, __m) < *__m and *__m <= [__m, __last)
5146 // (this inhibits tossing elements equivalent to __m around unnecessarily)
5147 _RandomAccessIterator __i = __first;
5148 _RandomAccessIterator __j = __lm1;
5149 // j points beyond range to be tested, *__lm1 is known to be <= *__m
5150 // The search going up is known to be guarded but the search coming down isn't.
5151 // Prime the downward search with a guard.
5152 if (!__comp(*__i, *__m)) // if *__first == *__m
5154 // *__first == *__m, *__first doesn't go in first part
5155 // manually guard downward moving __j against __i
5160 // *__first == *__m, *__m <= all other elements
5161 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
5162 ++__i; // __first + 1
5164 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
5169 return; // [__first, __last) all equivalent elements
5170 if (__comp(*__first, *__i))
5180 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
5185 while (!__comp(*__first, *__i))
5187 while (__comp(*__first, *--__j))
5195 // [__first, __i) == *__first and *__first < [__i, __last)
5196 // The first part is sorted,
5199 // __nth_element the secod part
5200 // __nth_element<_Compare>(__i, __nth, __last, __comp);
5204 if (__comp(*__j, *__m))
5208 break; // found guard for downward moving __j, now use unguarded partition
5213 // j points beyond range to be tested, *__lm1 is known to be <= *__m
5214 // if not yet partitioned...
5217 // known that *(__i - 1) < *__m
5220 // __m still guards upward moving __i
5221 while (__comp(*__i, *__m))
5223 // It is now known that a guard exists for downward moving __j
5224 while (!__comp(*--__j, *__m))
5230 // It is known that __m != __j
5231 // If __m just moved, follow it
5237 // [__first, __i) < *__m and *__m <= [__i, __last)
5238 if (__i != __m && __comp(*__m, *__i))
5243 // [__first, __i) < *__i and *__i <= [__i+1, __last)
5248 // We were given a perfectly partitioned sequence. Coincidence?
5251 // Check for [__first, __i) already sorted
5252 __j = __m = __first;
5253 while (++__j != __i)
5255 if (__comp(*__j, *__m))
5256 // not yet sorted, so sort
5260 // [__first, __i) sorted
5265 // Check for [__i, __last) already sorted
5267 while (++__j != __last)
5269 if (__comp(*__j, *__m))
5270 // not yet sorted, so sort
5274 // [__i, __last) sorted
5279 // __nth_element on range containing __nth
5282 // __nth_element<_Compare>(__first, __nth, __i, __comp);
5287 // __nth_element<_Compare>(__i+1, __nth, __last, __comp);
5293 template <class _RandomAccessIterator, class _Compare>
5294 inline _LIBCPP_INLINE_VISIBILITY
5296 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5298 #ifdef _LIBCPP_DEBUG
5299 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5300 __debug_less<_Compare> __c(__comp);
5301 __nth_element<_Comp_ref>(__first, __nth, __last, __c);
5302 #else // _LIBCPP_DEBUG
5303 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5304 __nth_element<_Comp_ref>(__first, __nth, __last, __comp);
5305 #endif // _LIBCPP_DEBUG
5308 template <class _RandomAccessIterator>
5309 inline _LIBCPP_INLINE_VISIBILITY
5311 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
5313 _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5318 template <class _Compare, class _InputIterator1, class _InputIterator2>
5320 __includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5323 for (; __first2 != __last2; ++__first1)
5325 if (__first1 == __last1 || __comp(*__first2, *__first1))
5327 if (!__comp(*__first1, *__first2))
5333 template <class _InputIterator1, class _InputIterator2, class _Compare>
5334 inline _LIBCPP_INLINE_VISIBILITY
5336 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5339 #ifdef _LIBCPP_DEBUG
5340 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5341 __debug_less<_Compare> __c(__comp);
5342 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5343 #else // _LIBCPP_DEBUG
5344 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5345 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5346 #endif // _LIBCPP_DEBUG
5349 template <class _InputIterator1, class _InputIterator2>
5350 inline _LIBCPP_INLINE_VISIBILITY
5352 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
5354 return _VSTD::includes(__first1, __last1, __first2, __last2,
5355 __less<typename iterator_traits<_InputIterator1>::value_type,
5356 typename iterator_traits<_InputIterator2>::value_type>());
5361 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5363 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5364 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5366 for (; __first1 != __last1; ++__result)
5368 if (__first2 == __last2)
5369 return _VSTD::copy(__first1, __last1, __result);
5370 if (__comp(*__first2, *__first1))
5372 *__result = *__first2;
5377 *__result = *__first1;
5378 if (!__comp(*__first1, *__first2))
5383 return _VSTD::copy(__first2, __last2, __result);
5386 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5387 inline _LIBCPP_INLINE_VISIBILITY
5389 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5390 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5392 #ifdef _LIBCPP_DEBUG
5393 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5394 __debug_less<_Compare> __c(__comp);
5395 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5396 #else // _LIBCPP_DEBUG
5397 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5398 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5399 #endif // _LIBCPP_DEBUG
5402 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5403 inline _LIBCPP_INLINE_VISIBILITY
5405 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5406 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5408 return _VSTD::set_union(__first1, __last1, __first2, __last2, __result,
5409 __less<typename iterator_traits<_InputIterator1>::value_type,
5410 typename iterator_traits<_InputIterator2>::value_type>());
5415 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5417 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5418 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5420 while (__first1 != __last1 && __first2 != __last2)
5422 if (__comp(*__first1, *__first2))
5426 if (!__comp(*__first2, *__first1))
5428 *__result = *__first1;
5438 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5439 inline _LIBCPP_INLINE_VISIBILITY
5441 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5442 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5444 #ifdef _LIBCPP_DEBUG
5445 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5446 __debug_less<_Compare> __c(__comp);
5447 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5448 #else // _LIBCPP_DEBUG
5449 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5450 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5451 #endif // _LIBCPP_DEBUG
5454 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5455 inline _LIBCPP_INLINE_VISIBILITY
5457 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5458 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5460 return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result,
5461 __less<typename iterator_traits<_InputIterator1>::value_type,
5462 typename iterator_traits<_InputIterator2>::value_type>());
5467 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5469 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5470 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5472 while (__first1 != __last1)
5474 if (__first2 == __last2)
5475 return _VSTD::copy(__first1, __last1, __result);
5476 if (__comp(*__first1, *__first2))
5478 *__result = *__first1;
5484 if (!__comp(*__first2, *__first1))
5492 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5493 inline _LIBCPP_INLINE_VISIBILITY
5495 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5496 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5498 #ifdef _LIBCPP_DEBUG
5499 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5500 __debug_less<_Compare> __c(__comp);
5501 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5502 #else // _LIBCPP_DEBUG
5503 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5504 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5505 #endif // _LIBCPP_DEBUG
5508 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5509 inline _LIBCPP_INLINE_VISIBILITY
5511 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5512 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5514 return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result,
5515 __less<typename iterator_traits<_InputIterator1>::value_type,
5516 typename iterator_traits<_InputIterator2>::value_type>());
5519 // set_symmetric_difference
5521 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5523 __set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5524 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5526 while (__first1 != __last1)
5528 if (__first2 == __last2)
5529 return _VSTD::copy(__first1, __last1, __result);
5530 if (__comp(*__first1, *__first2))
5532 *__result = *__first1;
5538 if (__comp(*__first2, *__first1))
5540 *__result = *__first2;
5548 return _VSTD::copy(__first2, __last2, __result);
5551 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5552 inline _LIBCPP_INLINE_VISIBILITY
5554 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5555 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5557 #ifdef _LIBCPP_DEBUG
5558 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5559 __debug_less<_Compare> __c(__comp);
5560 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5561 #else // _LIBCPP_DEBUG
5562 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5563 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5564 #endif // _LIBCPP_DEBUG
5567 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5568 inline _LIBCPP_INLINE_VISIBILITY
5570 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5571 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5573 return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
5574 __less<typename iterator_traits<_InputIterator1>::value_type,
5575 typename iterator_traits<_InputIterator2>::value_type>());
5578 // lexicographical_compare
5580 template <class _Compare, class _InputIterator1, class _InputIterator2>
5582 __lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5583 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5585 for (; __first2 != __last2; ++__first1, (void) ++__first2)
5587 if (__first1 == __last1 || __comp(*__first1, *__first2))
5589 if (__comp(*__first2, *__first1))
5595 template <class _InputIterator1, class _InputIterator2, class _Compare>
5596 inline _LIBCPP_INLINE_VISIBILITY
5598 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5599 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5601 #ifdef _LIBCPP_DEBUG
5602 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5603 __debug_less<_Compare> __c(__comp);
5604 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5605 #else // _LIBCPP_DEBUG
5606 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5607 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5608 #endif // _LIBCPP_DEBUG
5611 template <class _InputIterator1, class _InputIterator2>
5612 inline _LIBCPP_INLINE_VISIBILITY
5614 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5615 _InputIterator2 __first2, _InputIterator2 __last2)
5617 return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,
5618 __less<typename iterator_traits<_InputIterator1>::value_type,
5619 typename iterator_traits<_InputIterator2>::value_type>());
5624 template <class _Compare, class _BidirectionalIterator>
5626 __next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5628 _BidirectionalIterator __i = __last;
5629 if (__first == __last || __first == --__i)
5633 _BidirectionalIterator __ip1 = __i;
5634 if (__comp(*--__i, *__ip1))
5636 _BidirectionalIterator __j = __last;
5637 while (!__comp(*__i, *--__j))
5640 _VSTD::reverse(__ip1, __last);
5645 _VSTD::reverse(__first, __last);
5651 template <class _BidirectionalIterator, class _Compare>
5652 inline _LIBCPP_INLINE_VISIBILITY
5654 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5656 #ifdef _LIBCPP_DEBUG
5657 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5658 __debug_less<_Compare> __c(__comp);
5659 return __next_permutation<_Comp_ref>(__first, __last, __c);
5660 #else // _LIBCPP_DEBUG
5661 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5662 return __next_permutation<_Comp_ref>(__first, __last, __comp);
5663 #endif // _LIBCPP_DEBUG
5666 template <class _BidirectionalIterator>
5667 inline _LIBCPP_INLINE_VISIBILITY
5669 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5671 return _VSTD::next_permutation(__first, __last,
5672 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5677 template <class _Compare, class _BidirectionalIterator>
5679 __prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5681 _BidirectionalIterator __i = __last;
5682 if (__first == __last || __first == --__i)
5686 _BidirectionalIterator __ip1 = __i;
5687 if (__comp(*__ip1, *--__i))
5689 _BidirectionalIterator __j = __last;
5690 while (!__comp(*--__j, *__i))
5693 _VSTD::reverse(__ip1, __last);
5698 _VSTD::reverse(__first, __last);
5704 template <class _BidirectionalIterator, class _Compare>
5705 inline _LIBCPP_INLINE_VISIBILITY
5707 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5709 #ifdef _LIBCPP_DEBUG
5710 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5711 __debug_less<_Compare> __c(__comp);
5712 return __prev_permutation<_Comp_ref>(__first, __last, __c);
5713 #else // _LIBCPP_DEBUG
5714 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5715 return __prev_permutation<_Comp_ref>(__first, __last, __comp);
5716 #endif // _LIBCPP_DEBUG
5719 template <class _BidirectionalIterator>
5720 inline _LIBCPP_INLINE_VISIBILITY
5722 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5724 return _VSTD::prev_permutation(__first, __last,
5725 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5728 template <class _Tp>
5729 inline _LIBCPP_INLINE_VISIBILITY
5732 is_integral<_Tp>::value,
5735 __rotate_left(_Tp __t, _Tp __n = 1)
5737 const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1);
5739 return static_cast<_Tp>((__t << __n) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> (__bits - __n)));
5742 template <class _Tp>
5743 inline _LIBCPP_INLINE_VISIBILITY
5746 is_integral<_Tp>::value,
5749 __rotate_right(_Tp __t, _Tp __n = 1)
5751 const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1);
5753 return static_cast<_Tp>((__t << (__bits - __n)) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> __n));
5756 _LIBCPP_END_NAMESPACE_STD
5758 #endif // _LIBCPP_ALGORITHM