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
547 constexpr const T& clamp( const T& v, const T& lo, const T& hi ); // C++17
549 template<class T, class Compare>
550 constexpr const T& clamp( const T& v, const T& lo, const T& hi, Compare comp ); // C++17
552 template <class ForwardIterator>
554 max_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14
556 template <class ForwardIterator, class Compare>
558 max_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14
562 max(const T& a, const T& b); // constexpr in C++14
564 template <class T, class Compare>
566 max(const T& a, const T& b, Compare comp); // constexpr in C++14
570 max(initializer_list<T> t); // constexpr in C++14
572 template<class T, class Compare>
574 max(initializer_list<T> t, Compare comp); // constexpr in C++14
576 template<class ForwardIterator>
577 pair<ForwardIterator, ForwardIterator>
578 minmax_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14
580 template<class ForwardIterator, class Compare>
581 pair<ForwardIterator, ForwardIterator>
582 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14
585 pair<const T&, const T&>
586 minmax(const T& a, const T& b); // constexpr in C++14
588 template<class T, class Compare>
589 pair<const T&, const T&>
590 minmax(const T& a, const T& b, Compare comp); // constexpr in C++14
594 minmax(initializer_list<T> t); // constexpr in C++14
596 template<class T, class Compare>
598 minmax(initializer_list<T> t, Compare comp); // constexpr in C++14
600 template <class InputIterator1, class InputIterator2>
602 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
604 template <class InputIterator1, class InputIterator2, class Compare>
606 lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
607 InputIterator2 first2, InputIterator2 last2, Compare comp);
609 template <class BidirectionalIterator>
611 next_permutation(BidirectionalIterator first, BidirectionalIterator last);
613 template <class BidirectionalIterator, class Compare>
615 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
617 template <class BidirectionalIterator>
619 prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
621 template <class BidirectionalIterator, class Compare>
623 prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
630 #include <initializer_list>
631 #include <type_traits>
633 #include <utility> // needed to provide swap_ranges.
638 #if defined(__IBMCPP__)
639 #include "support/ibm/support.h"
641 #if defined(_LIBCPP_MSVCRT) || defined(__MINGW32__)
642 #include "support/win32/support.h"
645 #include <__undef_min_max>
649 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
650 #pragma GCC system_header
653 _LIBCPP_BEGIN_NAMESPACE_STD
655 // I'd like to replace these with _VSTD::equal_to<void>, but can't because:
656 // * That only works with C++14 and later, and
657 // * We haven't included <functional> here.
658 template <class _T1, class _T2 = _T1>
661 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
662 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;}
663 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;}
664 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;}
668 struct __equal_to<_T1, _T1>
670 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
671 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
675 struct __equal_to<const _T1, _T1>
677 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
678 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
682 struct __equal_to<_T1, const _T1>
684 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
685 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
688 template <class _T1, class _T2 = _T1>
691 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
692 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
694 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
695 bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;}
697 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
698 bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;}
700 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
701 bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;}
705 struct __less<_T1, _T1>
707 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
708 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
712 struct __less<const _T1, _T1>
714 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
715 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
719 struct __less<_T1, const _T1>
721 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
722 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
725 template <class _Predicate>
731 _LIBCPP_INLINE_VISIBILITY __negate() {}
733 _LIBCPP_INLINE_VISIBILITY
734 explicit __negate(_Predicate __p) : __p_(__p) {}
737 _LIBCPP_INLINE_VISIBILITY
738 bool operator()(const _T1& __x) {return !__p_(__x);}
740 template <class _T1, class _T2>
741 _LIBCPP_INLINE_VISIBILITY
742 bool operator()(const _T1& __x, const _T2& __y) {return !__p_(__x, __y);}
747 template <class _Compare>
751 __debug_less(_Compare& __c) : __comp_(__c) {}
752 template <class _Tp, class _Up>
753 bool operator()(const _Tp& __x, const _Up& __y)
755 bool __r = __comp_(__x, __y);
757 _LIBCPP_ASSERT(!__comp_(__y, __x), "Comparator does not induce a strict weak ordering");
762 #endif // _LIBCPP_DEBUG
764 // Precondition: __x != 0
765 inline _LIBCPP_INLINE_VISIBILITY
769 return static_cast<unsigned>(__builtin_ctz(__x));
772 inline _LIBCPP_INLINE_VISIBILITY
774 __ctz(unsigned long __x)
776 return static_cast<unsigned long>(__builtin_ctzl(__x));
779 inline _LIBCPP_INLINE_VISIBILITY
781 __ctz(unsigned long long __x)
783 return static_cast<unsigned long long>(__builtin_ctzll(__x));
786 // Precondition: __x != 0
787 inline _LIBCPP_INLINE_VISIBILITY
791 return static_cast<unsigned>(__builtin_clz(__x));
794 inline _LIBCPP_INLINE_VISIBILITY
796 __clz(unsigned long __x)
798 return static_cast<unsigned long>(__builtin_clzl (__x));
801 inline _LIBCPP_INLINE_VISIBILITY
803 __clz(unsigned long long __x)
805 return static_cast<unsigned long long>(__builtin_clzll(__x));
808 inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned __x) {return __builtin_popcount (__x);}
809 inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long __x) {return __builtin_popcountl (__x);}
810 inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long long __x) {return __builtin_popcountll(__x);}
814 template <class _InputIterator, class _Predicate>
815 inline _LIBCPP_INLINE_VISIBILITY
817 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
819 for (; __first != __last; ++__first)
820 if (!__pred(*__first))
827 template <class _InputIterator, class _Predicate>
828 inline _LIBCPP_INLINE_VISIBILITY
830 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
832 for (; __first != __last; ++__first)
833 if (__pred(*__first))
840 template <class _InputIterator, class _Predicate>
841 inline _LIBCPP_INLINE_VISIBILITY
843 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
845 for (; __first != __last; ++__first)
846 if (__pred(*__first))
853 template <class _InputIterator, class _Function>
854 inline _LIBCPP_INLINE_VISIBILITY
856 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
858 for (; __first != __last; ++__first)
860 return _LIBCPP_EXPLICIT_MOVE(__f); // explicitly moved for (emulated) C++03
865 template <class _InputIterator, class _Tp>
866 inline _LIBCPP_INLINE_VISIBILITY
868 find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
870 for (; __first != __last; ++__first)
871 if (*__first == __value_)
878 template <class _InputIterator, class _Predicate>
879 inline _LIBCPP_INLINE_VISIBILITY
881 find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
883 for (; __first != __last; ++__first)
884 if (__pred(*__first))
891 template<class _InputIterator, class _Predicate>
892 inline _LIBCPP_INLINE_VISIBILITY
894 find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
896 for (; __first != __last; ++__first)
897 if (!__pred(*__first))
904 template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
906 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
907 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
908 forward_iterator_tag, forward_iterator_tag)
910 // modeled after search algorithm
911 _ForwardIterator1 __r = __last1; // __last1 is the "default" answer
912 if (__first2 == __last2)
918 if (__first1 == __last1) // if source exhausted return last correct answer
919 return __r; // (or __last1 if never found)
920 if (__pred(*__first1, *__first2))
924 // *__first1 matches *__first2, now match elements after here
925 _ForwardIterator1 __m1 = __first1;
926 _ForwardIterator2 __m2 = __first2;
929 if (++__m2 == __last2)
930 { // Pattern exhaused, record answer and search for another one
935 if (++__m1 == __last1) // Source exhausted, return last answer
937 if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first
941 } // else there is a match, check next elements
946 template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2>
947 _BidirectionalIterator1
948 __find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,
949 _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred,
950 bidirectional_iterator_tag, bidirectional_iterator_tag)
952 // modeled after search algorithm (in reverse)
953 if (__first2 == __last2)
954 return __last1; // Everything matches an empty sequence
955 _BidirectionalIterator1 __l1 = __last1;
956 _BidirectionalIterator2 __l2 = __last2;
960 // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks
963 if (__first1 == __l1) // return __last1 if no element matches *__first2
965 if (__pred(*--__l1, *__l2))
968 // *__l1 matches *__l2, now match elements before here
969 _BidirectionalIterator1 __m1 = __l1;
970 _BidirectionalIterator2 __m2 = __l2;
973 if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern)
975 if (__m1 == __first1) // Otherwise if source exhaused, pattern not found
977 if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1
980 } // else there is a match, check next elements
985 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
986 _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1
987 __find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
988 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
989 random_access_iterator_tag, random_access_iterator_tag)
991 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern
992 typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;
995 typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;
998 const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here
999 _RandomAccessIterator1 __l1 = __last1;
1000 _RandomAccessIterator2 __l2 = __last2;
1008 if (__pred(*--__l1, *__l2))
1011 _RandomAccessIterator1 __m1 = __l1;
1012 _RandomAccessIterator2 __m2 = __l2;
1015 if (__m2 == __first2)
1017 // no need to check range on __m1 because __s guarantees we have enough source
1018 if (!__pred(*--__m1, *--__m2))
1026 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1027 inline _LIBCPP_INLINE_VISIBILITY
1029 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1030 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1032 return _VSTD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type>
1033 (__first1, __last1, __first2, __last2, __pred,
1034 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1035 typename iterator_traits<_ForwardIterator2>::iterator_category());
1038 template <class _ForwardIterator1, class _ForwardIterator2>
1039 inline _LIBCPP_INLINE_VISIBILITY
1041 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1042 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1044 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1045 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1046 return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1051 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1052 _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator1
1053 __find_first_of_ce(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1054 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1056 for (; __first1 != __last1; ++__first1)
1057 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1058 if (__pred(*__first1, *__j))
1064 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1065 inline _LIBCPP_INLINE_VISIBILITY
1067 find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1068 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1070 return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred);
1073 template <class _ForwardIterator1, class _ForwardIterator2>
1074 inline _LIBCPP_INLINE_VISIBILITY
1076 find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1077 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1079 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1080 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1081 return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1086 template <class _ForwardIterator, class _BinaryPredicate>
1087 inline _LIBCPP_INLINE_VISIBILITY
1089 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
1091 if (__first != __last)
1093 _ForwardIterator __i = __first;
1094 while (++__i != __last)
1096 if (__pred(*__first, *__i))
1104 template <class _ForwardIterator>
1105 inline _LIBCPP_INLINE_VISIBILITY
1107 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
1109 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1110 return _VSTD::adjacent_find(__first, __last, __equal_to<__v>());
1115 template <class _InputIterator, class _Tp>
1116 inline _LIBCPP_INLINE_VISIBILITY
1117 typename iterator_traits<_InputIterator>::difference_type
1118 count(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
1120 typename iterator_traits<_InputIterator>::difference_type __r(0);
1121 for (; __first != __last; ++__first)
1122 if (*__first == __value_)
1129 template <class _InputIterator, class _Predicate>
1130 inline _LIBCPP_INLINE_VISIBILITY
1131 typename iterator_traits<_InputIterator>::difference_type
1132 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
1134 typename iterator_traits<_InputIterator>::difference_type __r(0);
1135 for (; __first != __last; ++__first)
1136 if (__pred(*__first))
1143 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1144 inline _LIBCPP_INLINE_VISIBILITY
1145 pair<_InputIterator1, _InputIterator2>
1146 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1147 _InputIterator2 __first2, _BinaryPredicate __pred)
1149 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1150 if (!__pred(*__first1, *__first2))
1152 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1155 template <class _InputIterator1, class _InputIterator2>
1156 inline _LIBCPP_INLINE_VISIBILITY
1157 pair<_InputIterator1, _InputIterator2>
1158 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1160 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1161 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1162 return _VSTD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1165 #if _LIBCPP_STD_VER > 11
1166 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1167 inline _LIBCPP_INLINE_VISIBILITY
1168 pair<_InputIterator1, _InputIterator2>
1169 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1170 _InputIterator2 __first2, _InputIterator2 __last2,
1171 _BinaryPredicate __pred)
1173 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1174 if (!__pred(*__first1, *__first2))
1176 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1179 template <class _InputIterator1, class _InputIterator2>
1180 inline _LIBCPP_INLINE_VISIBILITY
1181 pair<_InputIterator1, _InputIterator2>
1182 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1183 _InputIterator2 __first2, _InputIterator2 __last2)
1185 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1186 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1187 return _VSTD::mismatch(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1193 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1194 inline _LIBCPP_INLINE_VISIBILITY
1196 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred)
1198 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1199 if (!__pred(*__first1, *__first2))
1204 template <class _InputIterator1, class _InputIterator2>
1205 inline _LIBCPP_INLINE_VISIBILITY
1207 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1209 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1210 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1211 return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1214 #if _LIBCPP_STD_VER > 11
1215 template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2>
1216 inline _LIBCPP_INLINE_VISIBILITY
1218 __equal(_InputIterator1 __first1, _InputIterator1 __last1,
1219 _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred,
1220 input_iterator_tag, input_iterator_tag )
1222 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1223 if (!__pred(*__first1, *__first2))
1225 return __first1 == __last1 && __first2 == __last2;
1228 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1229 inline _LIBCPP_INLINE_VISIBILITY
1231 __equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1232 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1233 random_access_iterator_tag, random_access_iterator_tag )
1235 if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
1237 return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2,
1238 typename add_lvalue_reference<_BinaryPredicate>::type>
1239 (__first1, __last1, __first2, __pred );
1242 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1243 inline _LIBCPP_INLINE_VISIBILITY
1245 equal(_InputIterator1 __first1, _InputIterator1 __last1,
1246 _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred )
1248 return _VSTD::__equal<typename add_lvalue_reference<_BinaryPredicate>::type>
1249 (__first1, __last1, __first2, __last2, __pred,
1250 typename iterator_traits<_InputIterator1>::iterator_category(),
1251 typename iterator_traits<_InputIterator2>::iterator_category());
1254 template <class _InputIterator1, class _InputIterator2>
1255 inline _LIBCPP_INLINE_VISIBILITY
1257 equal(_InputIterator1 __first1, _InputIterator1 __last1,
1258 _InputIterator2 __first2, _InputIterator2 __last2)
1260 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1261 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1262 return _VSTD::__equal(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(),
1263 typename iterator_traits<_InputIterator1>::iterator_category(),
1264 typename iterator_traits<_InputIterator2>::iterator_category());
1270 template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1272 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1273 _ForwardIterator2 __first2, _BinaryPredicate __pred)
1275 // shorten sequences as much as possible by lopping of any equal parts
1276 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1277 if (!__pred(*__first1, *__first2))
1281 // __first1 != __last1 && *__first1 != *__first2
1282 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1283 _D1 __l1 = _VSTD::distance(__first1, __last1);
1286 _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1);
1287 // For each element in [f1, l1) see if there are the same number of
1288 // equal elements in [f2, l2)
1289 for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
1291 // Have we already counted the number of *__i in [f1, l1)?
1292 for (_ForwardIterator1 __j = __first1; __j != __i; ++__j)
1293 if (__pred(*__j, *__i))
1296 // Count number of *__i in [f2, l2)
1298 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1299 if (__pred(*__i, *__j))
1303 // Count number of *__i in [__i, l1) (we can start with 1)
1305 for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
1306 if (__pred(*__i, *__j))
1316 template<class _ForwardIterator1, class _ForwardIterator2>
1317 inline _LIBCPP_INLINE_VISIBILITY
1319 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1320 _ForwardIterator2 __first2)
1322 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1323 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1324 return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1327 #if _LIBCPP_STD_VER > 11
1328 template<class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
1330 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1331 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1332 _BinaryPredicate __pred,
1333 forward_iterator_tag, forward_iterator_tag )
1335 // shorten sequences as much as possible by lopping of any equal parts
1336 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1337 if (!__pred(*__first1, *__first2))
1339 return __first1 == __last1 && __first2 == __last2;
1341 // __first1 != __last1 && __first2 != __last2 && *__first1 != *__first2
1342 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1343 _D1 __l1 = _VSTD::distance(__first1, __last1);
1345 typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2;
1346 _D2 __l2 = _VSTD::distance(__first2, __last2);
1350 // For each element in [f1, l1) see if there are the same number of
1351 // equal elements in [f2, l2)
1352 for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
1354 // Have we already counted the number of *__i in [f1, l1)?
1355 for (_ForwardIterator1 __j = __first1; __j != __i; ++__j)
1356 if (__pred(*__j, *__i))
1359 // Count number of *__i in [f2, l2)
1361 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1362 if (__pred(*__i, *__j))
1366 // Count number of *__i in [__i, l1) (we can start with 1)
1368 for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
1369 if (__pred(*__i, *__j))
1379 template<class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1381 __is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1,
1382 _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2,
1383 _BinaryPredicate __pred,
1384 random_access_iterator_tag, random_access_iterator_tag )
1386 if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
1388 return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2,
1389 typename add_lvalue_reference<_BinaryPredicate>::type>
1390 (__first1, __last1, __first2, __pred );
1393 template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1394 inline _LIBCPP_INLINE_VISIBILITY
1396 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1397 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1398 _BinaryPredicate __pred )
1400 return _VSTD::__is_permutation<typename add_lvalue_reference<_BinaryPredicate>::type>
1401 (__first1, __last1, __first2, __last2, __pred,
1402 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1403 typename iterator_traits<_ForwardIterator2>::iterator_category());
1406 template<class _ForwardIterator1, class _ForwardIterator2>
1407 inline _LIBCPP_INLINE_VISIBILITY
1409 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1410 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1412 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1413 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1414 return _VSTD::__is_permutation(__first1, __last1, __first2, __last2,
1415 __equal_to<__v1, __v2>(),
1416 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1417 typename iterator_traits<_ForwardIterator2>::iterator_category());
1423 template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
1424 pair<_ForwardIterator1, _ForwardIterator1>
1425 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1426 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
1427 forward_iterator_tag, forward_iterator_tag)
1429 if (__first2 == __last2)
1430 return make_pair(__first1, __first1); // Everything matches an empty sequence
1433 // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks
1436 if (__first1 == __last1) // return __last1 if no element matches *__first2
1437 return make_pair(__last1, __last1);
1438 if (__pred(*__first1, *__first2))
1442 // *__first1 matches *__first2, now match elements after here
1443 _ForwardIterator1 __m1 = __first1;
1444 _ForwardIterator2 __m2 = __first2;
1447 if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern)
1448 return make_pair(__first1, __m1);
1449 if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found
1450 return make_pair(__last1, __last1);
1451 if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1
1455 } // else there is a match, check next elements
1460 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1461 _LIBCPP_CONSTEXPR_AFTER_CXX11
1462 pair<_RandomAccessIterator1, _RandomAccessIterator1>
1463 __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1464 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1465 random_access_iterator_tag, random_access_iterator_tag)
1467 typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1;
1468 typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2;
1469 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern
1470 const _D2 __len2 = __last2 - __first2;
1472 return make_pair(__first1, __first1);
1473 const _D1 __len1 = __last1 - __first1;
1474 if (__len1 < __len2)
1475 return make_pair(__last1, __last1);
1476 const _RandomAccessIterator1 __s = __last1 - (__len2 - 1); // Start of pattern match can't go beyond here
1479 #if !_LIBCPP_UNROLL_LOOPS
1482 if (__first1 == __s)
1483 return make_pair(__last1, __last1);
1484 if (__pred(*__first1, *__first2))
1488 #else // !_LIBCPP_UNROLL_LOOPS
1489 for (_D1 __loop_unroll = (__s - __first1) / 4; __loop_unroll > 0; --__loop_unroll)
1491 if (__pred(*__first1, *__first2))
1493 if (__pred(*++__first1, *__first2))
1495 if (__pred(*++__first1, *__first2))
1497 if (__pred(*++__first1, *__first2))
1501 switch (__s - __first1)
1504 if (__pred(*__first1, *__first2))
1508 if (__pred(*__first1, *__first2))
1512 if (__pred(*__first1, *__first2))
1515 return make_pair(__last1, __last1);
1518 #endif // !_LIBCPP_UNROLL_LOOPS
1519 _RandomAccessIterator1 __m1 = __first1;
1520 _RandomAccessIterator2 __m2 = __first2;
1521 #if !_LIBCPP_UNROLL_LOOPS
1524 if (++__m2 == __last2)
1525 return make_pair(__first1, __first1 + __len2);
1526 ++__m1; // no need to check range on __m1 because __s guarantees we have enough source
1527 if (!__pred(*__m1, *__m2))
1533 #else // !_LIBCPP_UNROLL_LOOPS
1536 for (_D2 __loop_unroll = (__last2 - __m2) / 4; __loop_unroll > 0; --__loop_unroll)
1538 if (!__pred(*__m1, *__m2))
1540 if (!__pred(*++__m1, *++__m2))
1542 if (!__pred(*++__m1, *++__m2))
1544 if (!__pred(*++__m1, *++__m2))
1549 switch (__last2 - __m2)
1552 if (!__pred(*__m1, *__m2))
1557 if (!__pred(*__m1, *__m2))
1562 if (!__pred(*__m1, *__m2))
1565 return make_pair(__first1, __first1 + __len2);
1569 #endif // !_LIBCPP_UNROLL_LOOPS
1573 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1574 inline _LIBCPP_INLINE_VISIBILITY
1576 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1577 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1579 return _VSTD::__search<typename add_lvalue_reference<_BinaryPredicate>::type>
1580 (__first1, __last1, __first2, __last2, __pred,
1581 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1582 typename iterator_traits<_ForwardIterator2>::iterator_category())
1586 template <class _ForwardIterator1, class _ForwardIterator2>
1587 inline _LIBCPP_INLINE_VISIBILITY
1589 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1590 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1592 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1593 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1594 return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1599 template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp>
1601 __search_n(_ForwardIterator __first, _ForwardIterator __last,
1602 _Size __count, const _Tp& __value_, _BinaryPredicate __pred, forward_iterator_tag)
1608 // Find first element in sequence that matchs __value_, with a mininum of loop checks
1611 if (__first == __last) // return __last if no element matches __value_
1613 if (__pred(*__first, __value_))
1617 // *__first matches __value_, now match elements after here
1618 _ForwardIterator __m = __first;
1622 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1624 if (++__m == __last) // Otherwise if source exhaused, pattern not found
1626 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1631 } // else there is a match, check next elements
1636 template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp>
1637 _RandomAccessIterator
1638 __search_n(_RandomAccessIterator __first, _RandomAccessIterator __last,
1639 _Size __count, const _Tp& __value_, _BinaryPredicate __pred, random_access_iterator_tag)
1643 _Size __len = static_cast<_Size>(__last - __first);
1644 if (__len < __count)
1646 const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here
1649 // Find first element in sequence that matchs __value_, with a mininum of loop checks
1652 if (__first >= __s) // return __last if no element matches __value_
1654 if (__pred(*__first, __value_))
1658 // *__first matches __value_, now match elements after here
1659 _RandomAccessIterator __m = __first;
1663 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1665 ++__m; // no need to check range on __m because __s guarantees we have enough source
1666 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1671 } // else there is a match, check next elements
1676 template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
1677 inline _LIBCPP_INLINE_VISIBILITY
1679 search_n(_ForwardIterator __first, _ForwardIterator __last,
1680 _Size __count, const _Tp& __value_, _BinaryPredicate __pred)
1682 return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>
1683 (__first, __last, __convert_to_integral(__count), __value_, __pred,
1684 typename iterator_traits<_ForwardIterator>::iterator_category());
1687 template <class _ForwardIterator, class _Size, class _Tp>
1688 inline _LIBCPP_INLINE_VISIBILITY
1690 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
1692 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1693 return _VSTD::search_n(__first, __last, __convert_to_integral(__count),
1694 __value_, __equal_to<__v, _Tp>());
1698 template <class _Iter>
1699 inline _LIBCPP_INLINE_VISIBILITY
1701 __unwrap_iter(_Iter __i)
1706 template <class _Tp>
1707 inline _LIBCPP_INLINE_VISIBILITY
1710 is_trivially_copy_assignable<_Tp>::value,
1713 __unwrap_iter(move_iterator<_Tp*> __i)
1718 #if _LIBCPP_DEBUG_LEVEL < 2
1720 template <class _Tp>
1721 inline _LIBCPP_INLINE_VISIBILITY
1724 is_trivially_copy_assignable<_Tp>::value,
1727 __unwrap_iter(__wrap_iter<_Tp*> __i)
1732 #endif // _LIBCPP_DEBUG_LEVEL < 2
1734 template <class _InputIterator, class _OutputIterator>
1735 inline _LIBCPP_INLINE_VISIBILITY
1737 __copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1739 for (; __first != __last; ++__first, (void) ++__result)
1740 *__result = *__first;
1744 template <class _Tp, class _Up>
1745 inline _LIBCPP_INLINE_VISIBILITY
1748 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1749 is_trivially_copy_assignable<_Up>::value,
1752 __copy(_Tp* __first, _Tp* __last, _Up* __result)
1754 const size_t __n = static_cast<size_t>(__last - __first);
1756 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1757 return __result + __n;
1760 template <class _InputIterator, class _OutputIterator>
1761 inline _LIBCPP_INLINE_VISIBILITY
1763 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1765 return _VSTD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1770 template <class _BidirectionalIterator, class _OutputIterator>
1771 inline _LIBCPP_INLINE_VISIBILITY
1773 __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
1775 while (__first != __last)
1776 *--__result = *--__last;
1780 template <class _Tp, class _Up>
1781 inline _LIBCPP_INLINE_VISIBILITY
1784 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1785 is_trivially_copy_assignable<_Up>::value,
1788 __copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
1790 const size_t __n = static_cast<size_t>(__last - __first);
1794 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1799 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1800 inline _LIBCPP_INLINE_VISIBILITY
1801 _BidirectionalIterator2
1802 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1803 _BidirectionalIterator2 __result)
1805 return _VSTD::__copy_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1810 template<class _InputIterator, class _OutputIterator, class _Predicate>
1811 inline _LIBCPP_INLINE_VISIBILITY
1813 copy_if(_InputIterator __first, _InputIterator __last,
1814 _OutputIterator __result, _Predicate __pred)
1816 for (; __first != __last; ++__first)
1818 if (__pred(*__first))
1820 *__result = *__first;
1829 template<class _InputIterator, class _Size, class _OutputIterator>
1830 inline _LIBCPP_INLINE_VISIBILITY
1833 __is_input_iterator<_InputIterator>::value &&
1834 !__is_random_access_iterator<_InputIterator>::value,
1837 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1839 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
1840 _IntegralSize __n = __orig_n;
1843 *__result = *__first;
1845 for (--__n; __n > 0; --__n)
1848 *__result = *__first;
1855 template<class _InputIterator, class _Size, class _OutputIterator>
1856 inline _LIBCPP_INLINE_VISIBILITY
1859 __is_random_access_iterator<_InputIterator>::value,
1862 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1864 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
1865 _IntegralSize __n = __orig_n;
1866 return _VSTD::copy(__first, __first + __n, __result);
1871 template <class _InputIterator, class _OutputIterator>
1872 inline _LIBCPP_INLINE_VISIBILITY
1874 __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1876 for (; __first != __last; ++__first, (void) ++__result)
1877 *__result = _VSTD::move(*__first);
1881 template <class _Tp, class _Up>
1882 inline _LIBCPP_INLINE_VISIBILITY
1885 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1886 is_trivially_copy_assignable<_Up>::value,
1889 __move(_Tp* __first, _Tp* __last, _Up* __result)
1891 const size_t __n = static_cast<size_t>(__last - __first);
1893 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1894 return __result + __n;
1897 template <class _InputIterator, class _OutputIterator>
1898 inline _LIBCPP_INLINE_VISIBILITY
1900 move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1902 return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1907 template <class _InputIterator, class _OutputIterator>
1908 inline _LIBCPP_INLINE_VISIBILITY
1910 __move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1912 while (__first != __last)
1913 *--__result = _VSTD::move(*--__last);
1917 template <class _Tp, class _Up>
1918 inline _LIBCPP_INLINE_VISIBILITY
1921 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1922 is_trivially_copy_assignable<_Up>::value,
1925 __move_backward(_Tp* __first, _Tp* __last, _Up* __result)
1927 const size_t __n = static_cast<size_t>(__last - __first);
1931 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1936 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1937 inline _LIBCPP_INLINE_VISIBILITY
1938 _BidirectionalIterator2
1939 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1940 _BidirectionalIterator2 __result)
1942 return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1947 // moved to <type_traits> for better swap / noexcept support
1951 template <class _InputIterator, class _OutputIterator, class _UnaryOperation>
1952 inline _LIBCPP_INLINE_VISIBILITY
1954 transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op)
1956 for (; __first != __last; ++__first, (void) ++__result)
1957 *__result = __op(*__first);
1961 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation>
1962 inline _LIBCPP_INLINE_VISIBILITY
1964 transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
1965 _OutputIterator __result, _BinaryOperation __binary_op)
1967 for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result)
1968 *__result = __binary_op(*__first1, *__first2);
1974 template <class _ForwardIterator, class _Tp>
1975 inline _LIBCPP_INLINE_VISIBILITY
1977 replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value)
1979 for (; __first != __last; ++__first)
1980 if (*__first == __old_value)
1981 *__first = __new_value;
1986 template <class _ForwardIterator, class _Predicate, class _Tp>
1987 inline _LIBCPP_INLINE_VISIBILITY
1989 replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value)
1991 for (; __first != __last; ++__first)
1992 if (__pred(*__first))
1993 *__first = __new_value;
1998 template <class _InputIterator, class _OutputIterator, class _Tp>
1999 inline _LIBCPP_INLINE_VISIBILITY
2001 replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
2002 const _Tp& __old_value, const _Tp& __new_value)
2004 for (; __first != __last; ++__first, (void) ++__result)
2005 if (*__first == __old_value)
2006 *__result = __new_value;
2008 *__result = *__first;
2014 template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp>
2015 inline _LIBCPP_INLINE_VISIBILITY
2017 replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
2018 _Predicate __pred, const _Tp& __new_value)
2020 for (; __first != __last; ++__first, (void) ++__result)
2021 if (__pred(*__first))
2022 *__result = __new_value;
2024 *__result = *__first;
2030 template <class _OutputIterator, class _Size, class _Tp>
2031 inline _LIBCPP_INLINE_VISIBILITY
2033 __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2035 for (; __n > 0; ++__first, (void) --__n)
2036 *__first = __value_;
2040 template <class _Tp, class _Size, class _Up>
2041 inline _LIBCPP_INLINE_VISIBILITY
2044 is_integral<_Tp>::value && sizeof(_Tp) == 1 &&
2045 !is_same<_Tp, bool>::value &&
2046 is_integral<_Up>::value && sizeof(_Up) == 1,
2049 __fill_n(_Tp* __first, _Size __n,_Up __value_)
2052 _VSTD::memset(__first, (unsigned char)__value_, (size_t)(__n));
2053 return __first + __n;
2056 template <class _OutputIterator, class _Size, class _Tp>
2057 inline _LIBCPP_INLINE_VISIBILITY
2059 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2061 return _VSTD::__fill_n(__first, __convert_to_integral(__n), __value_);
2066 template <class _ForwardIterator, class _Tp>
2067 inline _LIBCPP_INLINE_VISIBILITY
2069 __fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
2071 for (; __first != __last; ++__first)
2072 *__first = __value_;
2075 template <class _RandomAccessIterator, class _Tp>
2076 inline _LIBCPP_INLINE_VISIBILITY
2078 __fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag)
2080 _VSTD::fill_n(__first, __last - __first, __value_);
2083 template <class _ForwardIterator, class _Tp>
2084 inline _LIBCPP_INLINE_VISIBILITY
2086 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2088 _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category());
2093 template <class _ForwardIterator, class _Generator>
2094 inline _LIBCPP_INLINE_VISIBILITY
2096 generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
2098 for (; __first != __last; ++__first)
2104 template <class _OutputIterator, class _Size, class _Generator>
2105 inline _LIBCPP_INLINE_VISIBILITY
2107 generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen)
2109 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
2110 _IntegralSize __n = __orig_n;
2111 for (; __n > 0; ++__first, (void) --__n)
2118 template <class _ForwardIterator, class _Tp>
2120 remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2122 __first = _VSTD::find(__first, __last, __value_);
2123 if (__first != __last)
2125 _ForwardIterator __i = __first;
2126 while (++__i != __last)
2128 if (!(*__i == __value_))
2130 *__first = _VSTD::move(*__i);
2140 template <class _ForwardIterator, class _Predicate>
2142 remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2144 __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
2145 (__first, __last, __pred);
2146 if (__first != __last)
2148 _ForwardIterator __i = __first;
2149 while (++__i != __last)
2153 *__first = _VSTD::move(*__i);
2163 template <class _InputIterator, class _OutputIterator, class _Tp>
2164 inline _LIBCPP_INLINE_VISIBILITY
2166 remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_)
2168 for (; __first != __last; ++__first)
2170 if (!(*__first == __value_))
2172 *__result = *__first;
2181 template <class _InputIterator, class _OutputIterator, class _Predicate>
2182 inline _LIBCPP_INLINE_VISIBILITY
2184 remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
2186 for (; __first != __last; ++__first)
2188 if (!__pred(*__first))
2190 *__result = *__first;
2199 template <class _ForwardIterator, class _BinaryPredicate>
2201 unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
2203 __first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type>
2204 (__first, __last, __pred);
2205 if (__first != __last)
2209 _ForwardIterator __i = __first;
2210 for (++__i; ++__i != __last;)
2211 if (!__pred(*__first, *__i))
2212 *++__first = _VSTD::move(*__i);
2218 template <class _ForwardIterator>
2219 inline _LIBCPP_INLINE_VISIBILITY
2221 unique(_ForwardIterator __first, _ForwardIterator __last)
2223 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
2224 return _VSTD::unique(__first, __last, __equal_to<__v>());
2229 template <class _BinaryPredicate, class _InputIterator, class _OutputIterator>
2231 __unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2232 input_iterator_tag, output_iterator_tag)
2234 if (__first != __last)
2236 typename iterator_traits<_InputIterator>::value_type __t(*__first);
2239 while (++__first != __last)
2241 if (!__pred(__t, *__first))
2252 template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator>
2254 __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2255 forward_iterator_tag, output_iterator_tag)
2257 if (__first != __last)
2259 _ForwardIterator __i = __first;
2262 while (++__first != __last)
2264 if (!__pred(*__i, *__first))
2266 *__result = *__first;
2275 template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator>
2277 __unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred,
2278 input_iterator_tag, forward_iterator_tag)
2280 if (__first != __last)
2282 *__result = *__first;
2283 while (++__first != __last)
2284 if (!__pred(*__result, *__first))
2285 *++__result = *__first;
2291 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
2292 inline _LIBCPP_INLINE_VISIBILITY
2294 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred)
2296 return _VSTD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type>
2297 (__first, __last, __result, __pred,
2298 typename iterator_traits<_InputIterator>::iterator_category(),
2299 typename iterator_traits<_OutputIterator>::iterator_category());
2302 template <class _InputIterator, class _OutputIterator>
2303 inline _LIBCPP_INLINE_VISIBILITY
2305 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
2307 typedef typename iterator_traits<_InputIterator>::value_type __v;
2308 return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());
2313 template <class _BidirectionalIterator>
2314 inline _LIBCPP_INLINE_VISIBILITY
2316 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
2318 while (__first != __last)
2320 if (__first == --__last)
2322 _VSTD::iter_swap(__first, __last);
2327 template <class _RandomAccessIterator>
2328 inline _LIBCPP_INLINE_VISIBILITY
2330 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
2332 if (__first != __last)
2333 for (; __first < --__last; ++__first)
2334 _VSTD::iter_swap(__first, __last);
2337 template <class _BidirectionalIterator>
2338 inline _LIBCPP_INLINE_VISIBILITY
2340 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
2342 _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());
2347 template <class _BidirectionalIterator, class _OutputIterator>
2348 inline _LIBCPP_INLINE_VISIBILITY
2350 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
2352 for (; __first != __last; ++__result)
2353 *__result = *--__last;
2359 template <class _ForwardIterator>
2361 __rotate_left(_ForwardIterator __first, _ForwardIterator __last)
2363 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2364 value_type __tmp = _VSTD::move(*__first);
2365 _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
2366 *__lm1 = _VSTD::move(__tmp);
2370 template <class _BidirectionalIterator>
2371 _BidirectionalIterator
2372 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
2374 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
2375 _BidirectionalIterator __lm1 = _VSTD::prev(__last);
2376 value_type __tmp = _VSTD::move(*__lm1);
2377 _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
2378 *__first = _VSTD::move(__tmp);
2382 template <class _ForwardIterator>
2384 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2386 _ForwardIterator __i = __middle;
2389 swap(*__first, *__i);
2391 if (++__i == __last)
2393 if (__first == __middle)
2396 _ForwardIterator __r = __first;
2397 if (__first != __middle)
2402 swap(*__first, *__i);
2404 if (++__i == __last)
2406 if (__first == __middle)
2410 else if (__first == __middle)
2417 template<typename _Integral>
2418 inline _LIBCPP_INLINE_VISIBILITY
2420 __gcd(_Integral __x, _Integral __y)
2424 _Integral __t = __x % __y;
2431 template<typename _RandomAccessIterator>
2432 _RandomAccessIterator
2433 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
2435 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2436 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
2438 const difference_type __m1 = __middle - __first;
2439 const difference_type __m2 = __last - __middle;
2442 _VSTD::swap_ranges(__first, __middle, __middle);
2445 const difference_type __g = _VSTD::__gcd(__m1, __m2);
2446 for (_RandomAccessIterator __p = __first + __g; __p != __first;)
2448 value_type __t(_VSTD::move(*--__p));
2449 _RandomAccessIterator __p1 = __p;
2450 _RandomAccessIterator __p2 = __p1 + __m1;
2453 *__p1 = _VSTD::move(*__p2);
2455 const difference_type __d = __last - __p2;
2459 __p2 = __first + (__m1 - __d);
2460 } while (__p2 != __p);
2461 *__p1 = _VSTD::move(__t);
2463 return __first + __m2;
2466 template <class _ForwardIterator>
2467 inline _LIBCPP_INLINE_VISIBILITY
2469 __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
2470 _VSTD::forward_iterator_tag)
2472 typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type;
2473 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2475 if (_VSTD::next(__first) == __middle)
2476 return _VSTD::__rotate_left(__first, __last);
2478 return _VSTD::__rotate_forward(__first, __middle, __last);
2481 template <class _BidirectionalIterator>
2482 inline _LIBCPP_INLINE_VISIBILITY
2483 _BidirectionalIterator
2484 __rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
2485 _VSTD::bidirectional_iterator_tag)
2487 typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type;
2488 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2490 if (_VSTD::next(__first) == __middle)
2491 return _VSTD::__rotate_left(__first, __last);
2492 if (_VSTD::next(__middle) == __last)
2493 return _VSTD::__rotate_right(__first, __last);
2495 return _VSTD::__rotate_forward(__first, __middle, __last);
2498 template <class _RandomAccessIterator>
2499 inline _LIBCPP_INLINE_VISIBILITY
2500 _RandomAccessIterator
2501 __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
2502 _VSTD::random_access_iterator_tag)
2504 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
2505 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2507 if (_VSTD::next(__first) == __middle)
2508 return _VSTD::__rotate_left(__first, __last);
2509 if (_VSTD::next(__middle) == __last)
2510 return _VSTD::__rotate_right(__first, __last);
2511 return _VSTD::__rotate_gcd(__first, __middle, __last);
2513 return _VSTD::__rotate_forward(__first, __middle, __last);
2516 template <class _ForwardIterator>
2517 inline _LIBCPP_INLINE_VISIBILITY
2519 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2521 if (__first == __middle)
2523 if (__middle == __last)
2525 return _VSTD::__rotate(__first, __middle, __last,
2526 typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());
2531 template <class _ForwardIterator, class _OutputIterator>
2532 inline _LIBCPP_INLINE_VISIBILITY
2534 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
2536 return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));
2541 template <class _ForwardIterator, class _Compare>
2542 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2544 min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2546 if (__first != __last)
2548 _ForwardIterator __i = __first;
2549 while (++__i != __last)
2550 if (__comp(*__i, *__first))
2556 template <class _ForwardIterator>
2557 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2559 min_element(_ForwardIterator __first, _ForwardIterator __last)
2561 return _VSTD::min_element(__first, __last,
2562 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2567 template <class _Tp, class _Compare>
2568 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2570 min(const _Tp& __a, const _Tp& __b, _Compare __comp)
2572 return __comp(__b, __a) ? __b : __a;
2575 template <class _Tp>
2576 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2578 min(const _Tp& __a, const _Tp& __b)
2580 return _VSTD::min(__a, __b, __less<_Tp>());
2583 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2585 template<class _Tp, class _Compare>
2586 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2588 min(initializer_list<_Tp> __t, _Compare __comp)
2590 return *_VSTD::min_element(__t.begin(), __t.end(), __comp);
2594 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2596 min(initializer_list<_Tp> __t)
2598 return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>());
2601 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2605 template <class _ForwardIterator, class _Compare>
2606 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2608 max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2610 if (__first != __last)
2612 _ForwardIterator __i = __first;
2613 while (++__i != __last)
2614 if (__comp(*__first, *__i))
2621 template <class _ForwardIterator>
2622 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2624 max_element(_ForwardIterator __first, _ForwardIterator __last)
2626 return _VSTD::max_element(__first, __last,
2627 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2632 template <class _Tp, class _Compare>
2633 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2635 max(const _Tp& __a, const _Tp& __b, _Compare __comp)
2637 return __comp(__a, __b) ? __b : __a;
2640 template <class _Tp>
2641 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2643 max(const _Tp& __a, const _Tp& __b)
2645 return _VSTD::max(__a, __b, __less<_Tp>());
2648 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2650 template<class _Tp, class _Compare>
2651 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2653 max(initializer_list<_Tp> __t, _Compare __comp)
2655 return *_VSTD::max_element(__t.begin(), __t.end(), __comp);
2659 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2661 max(initializer_list<_Tp> __t)
2663 return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>());
2666 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2668 #if _LIBCPP_STD_VER > 14
2670 template<class _Tp, class _Compare>
2671 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
2673 clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
2675 _LIBCPP_ASSERT(!__comp(__hi, __lo), "Bad bounds passed to std::clamp");
2676 return __comp(__v, __lo) ? __lo : __comp(__hi, __v) ? __hi : __v;
2681 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
2683 clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi)
2685 return _VSTD::clamp(__v, __lo, __hi, __less<_Tp>());
2691 template <class _ForwardIterator, class _Compare>
2692 _LIBCPP_CONSTEXPR_AFTER_CXX11
2693 std::pair<_ForwardIterator, _ForwardIterator>
2694 minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2696 std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);
2697 if (__first != __last)
2699 if (++__first != __last)
2701 if (__comp(*__first, *__result.first))
2702 __result.first = __first;
2704 __result.second = __first;
2705 while (++__first != __last)
2707 _ForwardIterator __i = __first;
2708 if (++__first == __last)
2710 if (__comp(*__i, *__result.first))
2711 __result.first = __i;
2712 else if (!__comp(*__i, *__result.second))
2713 __result.second = __i;
2718 if (__comp(*__first, *__i))
2720 if (__comp(*__first, *__result.first))
2721 __result.first = __first;
2722 if (!__comp(*__i, *__result.second))
2723 __result.second = __i;
2727 if (__comp(*__i, *__result.first))
2728 __result.first = __i;
2729 if (!__comp(*__first, *__result.second))
2730 __result.second = __first;
2739 template <class _ForwardIterator>
2740 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2741 std::pair<_ForwardIterator, _ForwardIterator>
2742 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
2744 return _VSTD::minmax_element(__first, __last,
2745 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2750 template<class _Tp, class _Compare>
2751 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2752 pair<const _Tp&, const _Tp&>
2753 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
2755 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) :
2756 pair<const _Tp&, const _Tp&>(__a, __b);
2760 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2761 pair<const _Tp&, const _Tp&>
2762 minmax(const _Tp& __a, const _Tp& __b)
2764 return _VSTD::minmax(__a, __b, __less<_Tp>());
2767 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2769 template<class _Tp, class _Compare>
2770 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2772 minmax(initializer_list<_Tp> __t, _Compare __comp)
2774 typedef typename initializer_list<_Tp>::const_iterator _Iter;
2775 _Iter __first = __t.begin();
2776 _Iter __last = __t.end();
2777 std::pair<_Tp, _Tp> __result(*__first, *__first);
2780 if (__t.size() % 2 == 0)
2782 if (__comp(*__first, __result.first))
2783 __result.first = *__first;
2785 __result.second = *__first;
2789 while (__first != __last)
2791 _Tp __prev = *__first++;
2792 if (__comp(*__first, __prev)) {
2793 if ( __comp(*__first, __result.first)) __result.first = *__first;
2794 if (!__comp(__prev, __result.second)) __result.second = __prev;
2797 if ( __comp(__prev, __result.first)) __result.first = __prev;
2798 if (!__comp(*__first, __result.second)) __result.second = *__first;
2807 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2809 minmax(initializer_list<_Tp> __t)
2811 return _VSTD::minmax(__t, __less<_Tp>());
2814 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2818 // __independent_bits_engine
2820 template <unsigned long long _Xp, size_t _Rp>
2823 static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp
2824 : __log2_imp<_Xp, _Rp - 1>::value;
2827 template <unsigned long long _Xp>
2828 struct __log2_imp<_Xp, 0>
2830 static const size_t value = 0;
2833 template <size_t _Rp>
2834 struct __log2_imp<0, _Rp>
2836 static const size_t value = _Rp + 1;
2839 template <class _UI, _UI _Xp>
2842 static const size_t value = __log2_imp<_Xp,
2843 sizeof(_UI) * __CHAR_BIT__ - 1>::value;
2846 template<class _Engine, class _UIntType>
2847 class __independent_bits_engine
2851 typedef _UIntType result_type;
2854 typedef typename _Engine::result_type _Engine_result_type;
2855 typedef typename conditional
2857 sizeof(_Engine_result_type) <= sizeof(result_type),
2860 >::type _Working_result_type;
2867 _Working_result_type __y0_;
2868 _Working_result_type __y1_;
2869 _Engine_result_type __mask0_;
2870 _Engine_result_type __mask1_;
2872 #ifdef _LIBCPP_HAS_NO_CONSTEXPR
2873 static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
2874 + _Working_result_type(1);
2876 static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()
2877 + _Working_result_type(1);
2879 static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value;
2880 static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits;
2881 static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
2884 // constructors and seeding functions
2885 __independent_bits_engine(_Engine& __e, size_t __w);
2887 // generating functions
2888 result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
2891 result_type __eval(false_type);
2892 result_type __eval(true_type);
2895 template<class _Engine, class _UIntType>
2896 __independent_bits_engine<_Engine, _UIntType>
2897 ::__independent_bits_engine(_Engine& __e, size_t __w)
2901 __n_ = __w_ / __m + (__w_ % __m != 0);
2902 __w0_ = __w_ / __n_;
2905 else if (__w0_ < _WDt)
2906 __y0_ = (_Rp >> __w0_) << __w0_;
2909 if (_Rp - __y0_ > __y0_ / __n_)
2912 __w0_ = __w_ / __n_;
2914 __y0_ = (_Rp >> __w0_) << __w0_;
2918 __n0_ = __n_ - __w_ % __n_;
2919 if (__w0_ < _WDt - 1)
2920 __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1);
2923 __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :
2924 _Engine_result_type(0);
2925 __mask1_ = __w0_ < _EDt - 1 ?
2926 _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :
2927 _Engine_result_type(~0);
2930 template<class _Engine, class _UIntType>
2933 __independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
2935 return static_cast<result_type>(__e_() & __mask0_);
2938 template<class _Engine, class _UIntType>
2940 __independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
2942 result_type _Sp = 0;
2943 for (size_t __k = 0; __k < __n0_; ++__k)
2945 _Engine_result_type __u;
2948 __u = __e_() - _Engine::min();
2949 } while (__u >= __y0_);
2954 _Sp += __u & __mask0_;
2956 for (size_t __k = __n0_; __k < __n_; ++__k)
2958 _Engine_result_type __u;
2961 __u = __e_() - _Engine::min();
2962 } while (__u >= __y1_);
2963 if (__w0_ < _WDt - 1)
2967 _Sp += __u & __mask1_;
2972 // uniform_int_distribution
2974 template<class _IntType = int>
2975 class uniform_int_distribution
2979 typedef _IntType result_type;
2986 typedef uniform_int_distribution distribution_type;
2988 explicit param_type(result_type __a = 0,
2989 result_type __b = numeric_limits<result_type>::max())
2990 : __a_(__a), __b_(__b) {}
2992 result_type a() const {return __a_;}
2993 result_type b() const {return __b_;}
2995 friend bool operator==(const param_type& __x, const param_type& __y)
2996 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
2997 friend bool operator!=(const param_type& __x, const param_type& __y)
2998 {return !(__x == __y);}
3005 // constructors and reset functions
3006 explicit uniform_int_distribution(result_type __a = 0,
3007 result_type __b = numeric_limits<result_type>::max())
3008 : __p_(param_type(__a, __b)) {}
3009 explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
3012 // generating functions
3013 template<class _URNG> result_type operator()(_URNG& __g)
3014 {return (*this)(__g, __p_);}
3015 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3017 // property functions
3018 result_type a() const {return __p_.a();}
3019 result_type b() const {return __p_.b();}
3021 param_type param() const {return __p_;}
3022 void param(const param_type& __p) {__p_ = __p;}
3024 result_type min() const {return a();}
3025 result_type max() const {return b();}
3027 friend bool operator==(const uniform_int_distribution& __x,
3028 const uniform_int_distribution& __y)
3029 {return __x.__p_ == __y.__p_;}
3030 friend bool operator!=(const uniform_int_distribution& __x,
3031 const uniform_int_distribution& __y)
3032 {return !(__x == __y);}
3035 template<class _IntType>
3036 template<class _URNG>
3037 typename uniform_int_distribution<_IntType>::result_type
3038 uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
3040 typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
3041 uint32_t, uint64_t>::type _UIntType;
3042 const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1);
3045 const size_t _Dt = numeric_limits<_UIntType>::digits;
3046 typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
3048 return static_cast<result_type>(_Eng(__g, _Dt)());
3049 size_t __w = _Dt - __clz(_Rp) - 1;
3050 if ((_Rp & (std::numeric_limits<_UIntType>::max() >> (_Dt - __w))) != 0)
3057 } while (__u >= _Rp);
3058 return static_cast<result_type>(__u + __p.a());
3061 class _LIBCPP_TYPE_VIS __rs_default;
3063 _LIBCPP_FUNC_VIS __rs_default __rs_get();
3065 class _LIBCPP_TYPE_VIS __rs_default
3067 static unsigned __c_;
3071 typedef uint_fast32_t result_type;
3073 static const result_type _Min = 0;
3074 static const result_type _Max = 0xFFFFFFFF;
3076 __rs_default(const __rs_default&);
3079 result_type operator()();
3081 static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
3082 static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
3084 friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
3087 _LIBCPP_FUNC_VIS __rs_default __rs_get();
3089 template <class _RandomAccessIterator>
3091 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
3093 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3094 typedef uniform_int_distribution<ptrdiff_t> _Dp;
3095 typedef typename _Dp::param_type _Pp;
3096 difference_type __d = __last - __first;
3100 __rs_default __g = __rs_get();
3101 for (--__last, --__d; __first < __last; ++__first, --__d)
3103 difference_type __i = __uid(__g, _Pp(0, __d));
3104 if (__i != difference_type(0))
3105 swap(*__first, *(__first + __i));
3110 template <class _RandomAccessIterator, class _RandomNumberGenerator>
3112 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3113 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3114 _RandomNumberGenerator&& __rand)
3116 _RandomNumberGenerator& __rand)
3119 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3120 difference_type __d = __last - __first;
3123 for (--__last; __first < __last; ++__first, --__d)
3125 difference_type __i = __rand(__d);
3126 swap(*__first, *(__first + __i));
3131 template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
3132 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3133 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3134 _UniformRandomNumberGenerator&& __g)
3136 _UniformRandomNumberGenerator& __g)
3139 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3140 typedef uniform_int_distribution<ptrdiff_t> _Dp;
3141 typedef typename _Dp::param_type _Pp;
3142 difference_type __d = __last - __first;
3146 for (--__last, --__d; __first < __last; ++__first, --__d)
3148 difference_type __i = __uid(__g, _Pp(0, __d));
3149 if (__i != difference_type(0))
3150 swap(*__first, *(__first + __i));
3155 template <class _InputIterator, class _Predicate>
3157 is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3159 for (; __first != __last; ++__first)
3160 if (!__pred(*__first))
3162 if ( __first == __last )
3165 for (; __first != __last; ++__first)
3166 if (__pred(*__first))
3173 template <class _Predicate, class _ForwardIterator>
3175 __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
3179 if (__first == __last)
3181 if (!__pred(*__first))
3185 for (_ForwardIterator __p = __first; ++__p != __last;)
3189 swap(*__first, *__p);
3196 template <class _Predicate, class _BidirectionalIterator>
3197 _BidirectionalIterator
3198 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3199 bidirectional_iterator_tag)
3205 if (__first == __last)
3207 if (!__pred(*__first))
3213 if (__first == --__last)
3215 } while (!__pred(*__last));
3216 swap(*__first, *__last);
3221 template <class _ForwardIterator, class _Predicate>
3222 inline _LIBCPP_INLINE_VISIBILITY
3224 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3226 return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>
3227 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3232 template <class _InputIterator, class _OutputIterator1,
3233 class _OutputIterator2, class _Predicate>
3234 pair<_OutputIterator1, _OutputIterator2>
3235 partition_copy(_InputIterator __first, _InputIterator __last,
3236 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
3239 for (; __first != __last; ++__first)
3241 if (__pred(*__first))
3243 *__out_true = *__first;
3248 *__out_false = *__first;
3252 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
3257 template<class _ForwardIterator, class _Predicate>
3259 partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3261 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3262 difference_type __len = _VSTD::distance(__first, __last);
3265 difference_type __l2 = __len / 2;
3266 _ForwardIterator __m = __first;
3267 _VSTD::advance(__m, __l2);
3281 template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
3283 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3284 _Distance __len, _Pair __p, forward_iterator_tag __fit)
3286 // *__first is known to be false
3292 _ForwardIterator __m = __first;
3295 swap(*__first, *__m);
3300 if (__len <= __p.second)
3301 { // The buffer is big enough to use
3302 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3303 __destruct_n __d(0);
3304 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3305 // Move the falses into the temporary buffer, and the trues to the front of the line
3306 // Update __first to always point to the end of the trues
3307 value_type* __t = __p.first;
3308 ::new(__t) value_type(_VSTD::move(*__first));
3309 __d.__incr((value_type*)0);
3311 _ForwardIterator __i = __first;
3312 while (++__i != __last)
3316 *__first = _VSTD::move(*__i);
3321 ::new(__t) value_type(_VSTD::move(*__i));
3322 __d.__incr((value_type*)0);
3326 // All trues now at start of range, all falses in buffer
3327 // Move falses back into range, but don't mess up __first which points to first false
3329 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3330 *__i = _VSTD::move(*__t2);
3331 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3334 // Else not enough buffer, do in place
3336 _ForwardIterator __m = __first;
3337 _Distance __len2 = __len / 2; // __len2 >= 2
3338 _VSTD::advance(__m, __len2);
3339 // recurse on [__first, __m), *__first know to be false
3340 // F?????????????????
3342 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3343 _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
3344 // TTTFFFFF??????????
3346 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3347 _ForwardIterator __m1 = __m;
3348 _ForwardIterator __second_false = __last;
3349 _Distance __len_half = __len - __len2;
3350 while (__pred(*__m1))
3352 if (++__m1 == __last)
3353 goto __second_half_done;
3356 // TTTFFFFFTTTF??????
3358 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
3360 // TTTFFFFFTTTTTFFFFF
3362 return _VSTD::rotate(__first_false, __m, __second_false);
3363 // TTTTTTTTFFFFFFFFFF
3367 struct __return_temporary_buffer
3369 template <class _Tp>
3370 _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}
3373 template <class _Predicate, class _ForwardIterator>
3375 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3376 forward_iterator_tag)
3378 const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment
3379 // Either prove all true and return __first or point to first false
3382 if (__first == __last)
3384 if (!__pred(*__first))
3388 // We now have a reduced range [__first, __last)
3389 // *__first is known to be false
3390 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3391 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3392 difference_type __len = _VSTD::distance(__first, __last);
3393 pair<value_type*, ptrdiff_t> __p(0, 0);
3394 unique_ptr<value_type, __return_temporary_buffer> __h;
3395 if (__len >= __alloc_limit)
3397 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3398 __h.reset(__p.first);
3400 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3401 (__first, __last, __pred, __len, __p, forward_iterator_tag());
3404 template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
3405 _BidirectionalIterator
3406 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3407 _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
3409 // *__first is known to be false
3410 // *__last is known to be true
3414 swap(*__first, *__last);
3419 _BidirectionalIterator __m = __first;
3422 swap(*__first, *__m);
3423 swap(*__m, *__last);
3426 swap(*__m, *__last);
3427 swap(*__first, *__m);
3430 if (__len <= __p.second)
3431 { // The buffer is big enough to use
3432 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3433 __destruct_n __d(0);
3434 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3435 // Move the falses into the temporary buffer, and the trues to the front of the line
3436 // Update __first to always point to the end of the trues
3437 value_type* __t = __p.first;
3438 ::new(__t) value_type(_VSTD::move(*__first));
3439 __d.__incr((value_type*)0);
3441 _BidirectionalIterator __i = __first;
3442 while (++__i != __last)
3446 *__first = _VSTD::move(*__i);
3451 ::new(__t) value_type(_VSTD::move(*__i));
3452 __d.__incr((value_type*)0);
3456 // move *__last, known to be true
3457 *__first = _VSTD::move(*__i);
3459 // All trues now at start of range, all falses in buffer
3460 // Move falses back into range, but don't mess up __first which points to first false
3461 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3462 *__i = _VSTD::move(*__t2);
3463 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3466 // Else not enough buffer, do in place
3468 _BidirectionalIterator __m = __first;
3469 _Distance __len2 = __len / 2; // __len2 >= 2
3470 _VSTD::advance(__m, __len2);
3471 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
3472 // F????????????????T
3474 _BidirectionalIterator __m1 = __m;
3475 _BidirectionalIterator __first_false = __first;
3476 _Distance __len_half = __len2;
3477 while (!__pred(*--__m1))
3479 if (__m1 == __first)
3480 goto __first_half_done;
3483 // F???TFFF?????????T
3485 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3486 __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3488 // TTTFFFFF?????????T
3490 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3492 _BidirectionalIterator __second_false = __last;
3494 __len_half = __len - __len2;
3495 while (__pred(*__m1))
3497 if (++__m1 == __last)
3498 goto __second_half_done;
3501 // TTTFFFFFTTTF?????T
3503 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
3505 // TTTFFFFFTTTTTFFFFF
3507 return _VSTD::rotate(__first_false, __m, __second_false);
3508 // TTTTTTTTFFFFFFFFFF
3512 template <class _Predicate, class _BidirectionalIterator>
3513 _BidirectionalIterator
3514 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3515 bidirectional_iterator_tag)
3517 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3518 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3519 const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment
3520 // Either prove all true and return __first or point to first false
3523 if (__first == __last)
3525 if (!__pred(*__first))
3529 // __first points to first false, everything prior to __first is already set.
3530 // Either prove [__first, __last) is all false and return __first, or point __last to last true
3533 if (__first == --__last)
3535 } while (!__pred(*__last));
3536 // We now have a reduced range [__first, __last]
3537 // *__first is known to be false
3538 // *__last is known to be true
3540 difference_type __len = _VSTD::distance(__first, __last) + 1;
3541 pair<value_type*, ptrdiff_t> __p(0, 0);
3542 unique_ptr<value_type, __return_temporary_buffer> __h;
3543 if (__len >= __alloc_limit)
3545 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3546 __h.reset(__p.first);
3548 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3549 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3552 template <class _ForwardIterator, class _Predicate>
3553 inline _LIBCPP_INLINE_VISIBILITY
3555 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3557 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3558 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3563 template <class _ForwardIterator, class _Compare>
3565 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3567 if (__first != __last)
3569 _ForwardIterator __i = __first;
3570 while (++__i != __last)
3572 if (__comp(*__i, *__first))
3580 template<class _ForwardIterator>
3581 inline _LIBCPP_INLINE_VISIBILITY
3583 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3585 return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3590 template <class _ForwardIterator, class _Compare>
3591 inline _LIBCPP_INLINE_VISIBILITY
3593 is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3595 return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
3598 template<class _ForwardIterator>
3599 inline _LIBCPP_INLINE_VISIBILITY
3601 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3603 return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3608 // stable, 2-3 compares, 0-2 swaps
3610 template <class _Compare, class _ForwardIterator>
3612 __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
3615 if (!__c(*__y, *__x)) // if x <= y
3617 if (!__c(*__z, *__y)) // if y <= z
3618 return __r; // x <= y && y <= z
3620 swap(*__y, *__z); // x <= z && y < z
3622 if (__c(*__y, *__x)) // if x > y
3624 swap(*__x, *__y); // x < y && y <= z
3627 return __r; // x <= y && y < z
3629 if (__c(*__z, *__y)) // x > y, if y > z
3631 swap(*__x, *__z); // x < y && y < z
3635 swap(*__x, *__y); // x > y && y <= z
3636 __r = 1; // x < y && x <= z
3637 if (__c(*__z, *__y)) // if y > z
3639 swap(*__y, *__z); // x <= y && y < z
3643 } // x <= y && y <= z
3645 // stable, 3-6 compares, 0-5 swaps
3647 template <class _Compare, class _ForwardIterator>
3649 __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3650 _ForwardIterator __x4, _Compare __c)
3652 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
3653 if (__c(*__x4, *__x3))
3657 if (__c(*__x3, *__x2))
3661 if (__c(*__x2, *__x1))
3671 // stable, 4-10 compares, 0-9 swaps
3673 template <class _Compare, class _ForwardIterator>
3675 __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3676 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
3678 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
3679 if (__c(*__x5, *__x4))
3683 if (__c(*__x4, *__x3))
3687 if (__c(*__x3, *__x2))
3691 if (__c(*__x2, *__x1))
3703 template <class _Compare, class _BirdirectionalIterator>
3705 __selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3707 _BirdirectionalIterator __lm1 = __last;
3708 for (--__lm1; __first != __lm1; ++__first)
3710 _BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator,
3711 typename add_lvalue_reference<_Compare>::type>
3712 (__first, __last, __comp);
3714 swap(*__first, *__i);
3718 template <class _Compare, class _BirdirectionalIterator>
3720 __insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3722 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3723 if (__first != __last)
3725 _BirdirectionalIterator __i = __first;
3726 for (++__i; __i != __last; ++__i)
3728 _BirdirectionalIterator __j = __i;
3729 value_type __t(_VSTD::move(*__j));
3730 for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
3731 *__j = _VSTD::move(*__k);
3732 *__j = _VSTD::move(__t);
3737 template <class _Compare, class _RandomAccessIterator>
3739 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3741 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3742 _RandomAccessIterator __j = __first+2;
3743 __sort3<_Compare>(__first, __first+1, __j, __comp);
3744 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3746 if (__comp(*__i, *__j))
3748 value_type __t(_VSTD::move(*__i));
3749 _RandomAccessIterator __k = __j;
3753 *__j = _VSTD::move(*__k);
3755 } while (__j != __first && __comp(__t, *--__k));
3756 *__j = _VSTD::move(__t);
3762 template <class _Compare, class _RandomAccessIterator>
3764 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3766 switch (__last - __first)
3772 if (__comp(*--__last, *__first))
3773 swap(*__first, *__last);
3776 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3779 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3782 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3785 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3786 _RandomAccessIterator __j = __first+2;
3787 __sort3<_Compare>(__first, __first+1, __j, __comp);
3788 const unsigned __limit = 8;
3789 unsigned __count = 0;
3790 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3792 if (__comp(*__i, *__j))
3794 value_type __t(_VSTD::move(*__i));
3795 _RandomAccessIterator __k = __j;
3799 *__j = _VSTD::move(*__k);
3801 } while (__j != __first && __comp(__t, *--__k));
3802 *__j = _VSTD::move(__t);
3803 if (++__count == __limit)
3804 return ++__i == __last;
3811 template <class _Compare, class _BirdirectionalIterator>
3813 __insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
3814 typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
3816 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3817 if (__first1 != __last1)
3819 __destruct_n __d(0);
3820 unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
3821 value_type* __last2 = __first2;
3822 ::new(__last2) value_type(_VSTD::move(*__first1));
3823 __d.__incr((value_type*)0);
3824 for (++__last2; ++__first1 != __last1; ++__last2)
3826 value_type* __j2 = __last2;
3827 value_type* __i2 = __j2;
3828 if (__comp(*__first1, *--__i2))
3830 ::new(__j2) value_type(_VSTD::move(*__i2));
3831 __d.__incr((value_type*)0);
3832 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2)
3833 *__j2 = _VSTD::move(*__i2);
3834 *__j2 = _VSTD::move(*__first1);
3838 ::new(__j2) value_type(_VSTD::move(*__first1));
3839 __d.__incr((value_type*)0);
3846 template <class _Compare, class _RandomAccessIterator>
3848 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3850 // _Compare is known to be a reference type
3851 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3852 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3853 const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
3854 is_trivially_copy_assignable<value_type>::value ? 30 : 6;
3858 difference_type __len = __last - __first;
3865 if (__comp(*--__last, *__first))
3866 swap(*__first, *__last);
3869 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3872 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3875 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3878 if (__len <= __limit)
3880 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
3884 _RandomAccessIterator __m = __first;
3885 _RandomAccessIterator __lm1 = __last;
3889 difference_type __delta;
3895 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
3901 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
3905 // partition [__first, __m) < *__m and *__m <= [__m, __last)
3906 // (this inhibits tossing elements equivalent to __m around unnecessarily)
3907 _RandomAccessIterator __i = __first;
3908 _RandomAccessIterator __j = __lm1;
3909 // j points beyond range to be tested, *__m is known to be <= *__lm1
3910 // The search going up is known to be guarded but the search coming down isn't.
3911 // Prime the downward search with a guard.
3912 if (!__comp(*__i, *__m)) // if *__first == *__m
3914 // *__first == *__m, *__first doesn't go in first part
3915 // manually guard downward moving __j against __i
3920 // *__first == *__m, *__m <= all other elements
3921 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
3922 ++__i; // __first + 1
3924 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
3929 return; // [__first, __last) all equivalent elements
3930 if (__comp(*__first, *__i))
3940 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
3945 while (!__comp(*__first, *__i))
3947 while (__comp(*__first, *--__j))
3955 // [__first, __i) == *__first and *__first < [__i, __last)
3956 // The first part is sorted, sort the secod part
3957 // _VSTD::__sort<_Compare>(__i, __last, __comp);
3961 if (__comp(*__j, *__m))
3965 break; // found guard for downward moving __j, now use unguarded partition
3969 // It is known that *__i < *__m
3971 // j points beyond range to be tested, *__m is known to be <= *__lm1
3972 // if not yet partitioned...
3975 // known that *(__i - 1) < *__m
3976 // known that __i <= __m
3979 // __m still guards upward moving __i
3980 while (__comp(*__i, *__m))
3982 // It is now known that a guard exists for downward moving __j
3983 while (!__comp(*--__j, *__m))
3989 // It is known that __m != __j
3990 // If __m just moved, follow it
3996 // [__first, __i) < *__m and *__m <= [__i, __last)
3997 if (__i != __m && __comp(*__m, *__i))
4002 // [__first, __i) < *__i and *__i <= [__i+1, __last)
4003 // If we were given a perfect partition, see if insertion sort is quick...
4006 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
4007 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
4023 // sort smaller range with recursive call and larger with tail recursion elimination
4024 if (__i - __first < __last - __i)
4026 _VSTD::__sort<_Compare>(__first, __i, __comp);
4027 // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4032 _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4033 // _VSTD::__sort<_Compare>(__first, __i, __comp);
4039 // This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
4040 template <class _RandomAccessIterator, class _Compare>
4041 inline _LIBCPP_INLINE_VISIBILITY
4043 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4045 #ifdef _LIBCPP_DEBUG
4046 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4047 __debug_less<_Compare> __c(__comp);
4048 __sort<_Comp_ref>(__first, __last, __c);
4049 #else // _LIBCPP_DEBUG
4050 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4051 __sort<_Comp_ref>(__first, __last, __comp);
4052 #endif // _LIBCPP_DEBUG
4055 template <class _RandomAccessIterator>
4056 inline _LIBCPP_INLINE_VISIBILITY
4058 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4060 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4063 template <class _Tp>
4064 inline _LIBCPP_INLINE_VISIBILITY
4066 sort(_Tp** __first, _Tp** __last)
4068 _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
4071 template <class _Tp>
4072 inline _LIBCPP_INLINE_VISIBILITY
4074 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
4076 _VSTD::sort(__first.base(), __last.base());
4079 template <class _Tp, class _Compare>
4080 inline _LIBCPP_INLINE_VISIBILITY
4082 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
4084 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4085 _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
4089 #pragma warning( push )
4090 #pragma warning( disable: 4231)
4091 #endif // _LIBCPP_MSVC
4092 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
4093 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4094 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4095 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4096 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))
4097 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4098 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&))
4099 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4100 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&))
4101 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4102 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4103 _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>&))
4104 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&))
4105 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&))
4106 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4108 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))
4109 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4110 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4111 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4112 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))
4113 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4114 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&))
4115 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4116 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&))
4117 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4118 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4119 _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>&))
4120 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&))
4121 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&))
4122 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4124 _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>&))
4126 #pragma warning( pop )
4127 #endif // _LIBCPP_MSVC
4131 template <class _Compare, class _ForwardIterator, class _Tp>
4133 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4135 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4136 difference_type __len = _VSTD::distance(__first, __last);
4139 difference_type __l2 = __len / 2;
4140 _ForwardIterator __m = __first;
4141 _VSTD::advance(__m, __l2);
4142 if (__comp(*__m, __value_))
4153 template <class _ForwardIterator, class _Tp, class _Compare>
4154 inline _LIBCPP_INLINE_VISIBILITY
4156 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4158 #ifdef _LIBCPP_DEBUG
4159 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4160 __debug_less<_Compare> __c(__comp);
4161 return __lower_bound<_Comp_ref>(__first, __last, __value_, __c);
4162 #else // _LIBCPP_DEBUG
4163 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4164 return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp);
4165 #endif // _LIBCPP_DEBUG
4168 template <class _ForwardIterator, class _Tp>
4169 inline _LIBCPP_INLINE_VISIBILITY
4171 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4173 return _VSTD::lower_bound(__first, __last, __value_,
4174 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4179 template <class _Compare, class _ForwardIterator, class _Tp>
4181 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4183 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4184 difference_type __len = _VSTD::distance(__first, __last);
4187 difference_type __l2 = __len / 2;
4188 _ForwardIterator __m = __first;
4189 _VSTD::advance(__m, __l2);
4190 if (__comp(__value_, *__m))
4201 template <class _ForwardIterator, class _Tp, class _Compare>
4202 inline _LIBCPP_INLINE_VISIBILITY
4204 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4206 #ifdef _LIBCPP_DEBUG
4207 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4208 __debug_less<_Compare> __c(__comp);
4209 return __upper_bound<_Comp_ref>(__first, __last, __value_, __c);
4210 #else // _LIBCPP_DEBUG
4211 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4212 return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp);
4213 #endif // _LIBCPP_DEBUG
4216 template <class _ForwardIterator, class _Tp>
4217 inline _LIBCPP_INLINE_VISIBILITY
4219 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4221 return _VSTD::upper_bound(__first, __last, __value_,
4222 __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
4227 template <class _Compare, class _ForwardIterator, class _Tp>
4228 pair<_ForwardIterator, _ForwardIterator>
4229 __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4231 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4232 difference_type __len = _VSTD::distance(__first, __last);
4235 difference_type __l2 = __len / 2;
4236 _ForwardIterator __m = __first;
4237 _VSTD::advance(__m, __l2);
4238 if (__comp(*__m, __value_))
4243 else if (__comp(__value_, *__m))
4250 _ForwardIterator __mp1 = __m;
4251 return pair<_ForwardIterator, _ForwardIterator>
4253 __lower_bound<_Compare>(__first, __m, __value_, __comp),
4254 __upper_bound<_Compare>(++__mp1, __last, __value_, __comp)
4258 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4261 template <class _ForwardIterator, class _Tp, class _Compare>
4262 inline _LIBCPP_INLINE_VISIBILITY
4263 pair<_ForwardIterator, _ForwardIterator>
4264 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4266 #ifdef _LIBCPP_DEBUG
4267 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4268 __debug_less<_Compare> __c(__comp);
4269 return __equal_range<_Comp_ref>(__first, __last, __value_, __c);
4270 #else // _LIBCPP_DEBUG
4271 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4272 return __equal_range<_Comp_ref>(__first, __last, __value_, __comp);
4273 #endif // _LIBCPP_DEBUG
4276 template <class _ForwardIterator, class _Tp>
4277 inline _LIBCPP_INLINE_VISIBILITY
4278 pair<_ForwardIterator, _ForwardIterator>
4279 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4281 return _VSTD::equal_range(__first, __last, __value_,
4282 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4287 template <class _Compare, class _ForwardIterator, class _Tp>
4288 inline _LIBCPP_INLINE_VISIBILITY
4290 __binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4292 __first = __lower_bound<_Compare>(__first, __last, __value_, __comp);
4293 return __first != __last && !__comp(__value_, *__first);
4296 template <class _ForwardIterator, class _Tp, class _Compare>
4297 inline _LIBCPP_INLINE_VISIBILITY
4299 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4301 #ifdef _LIBCPP_DEBUG
4302 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4303 __debug_less<_Compare> __c(__comp);
4304 return __binary_search<_Comp_ref>(__first, __last, __value_, __c);
4305 #else // _LIBCPP_DEBUG
4306 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4307 return __binary_search<_Comp_ref>(__first, __last, __value_, __comp);
4308 #endif // _LIBCPP_DEBUG
4311 template <class _ForwardIterator, class _Tp>
4312 inline _LIBCPP_INLINE_VISIBILITY
4314 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4316 return _VSTD::binary_search(__first, __last, __value_,
4317 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4322 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4324 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4325 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4327 for (; __first1 != __last1; ++__result)
4329 if (__first2 == __last2)
4330 return _VSTD::copy(__first1, __last1, __result);
4331 if (__comp(*__first2, *__first1))
4333 *__result = *__first2;
4338 *__result = *__first1;
4342 return _VSTD::copy(__first2, __last2, __result);
4345 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4346 inline _LIBCPP_INLINE_VISIBILITY
4348 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4349 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4351 #ifdef _LIBCPP_DEBUG
4352 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4353 __debug_less<_Compare> __c(__comp);
4354 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
4355 #else // _LIBCPP_DEBUG
4356 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4357 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4358 #endif // _LIBCPP_DEBUG
4361 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4362 inline _LIBCPP_INLINE_VISIBILITY
4364 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4365 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4367 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
4368 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
4369 return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
4374 template <class _Compare, class _InputIterator1, class _InputIterator2,
4375 class _OutputIterator>
4376 void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
4377 _InputIterator2 __first2, _InputIterator2 __last2,
4378 _OutputIterator __result, _Compare __comp)
4380 for (; __first1 != __last1; ++__result)
4382 if (__first2 == __last2)
4384 _VSTD::move(__first1, __last1, __result);
4388 if (__comp(*__first2, *__first1))
4390 *__result = _VSTD::move(*__first2);
4395 *__result = _VSTD::move(*__first1);
4399 // __first2 through __last2 are already in the right spot.
4402 template <class _Compare, class _BidirectionalIterator>
4404 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4405 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4406 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4407 typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
4409 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4410 __destruct_n __d(0);
4411 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4412 if (__len1 <= __len2)
4414 value_type* __p = __buff;
4415 for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4416 ::new(__p) value_type(_VSTD::move(*__i));
4417 __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);
4421 value_type* __p = __buff;
4422 for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4423 ::new(__p) value_type(_VSTD::move(*__i));
4424 typedef reverse_iterator<_BidirectionalIterator> _RBi;
4425 typedef reverse_iterator<value_type*> _Rv;
4426 __half_inplace_merge(_Rv(__p), _Rv(__buff),
4427 _RBi(__middle), _RBi(__first),
4428 _RBi(__last), __negate<_Compare>(__comp));
4432 template <class _Compare, class _BidirectionalIterator>
4434 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4435 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4436 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4437 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
4439 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4442 // if __middle == __last, we're done
4445 if (__len1 <= __buff_size || __len2 <= __buff_size)
4446 return __buffered_inplace_merge<_Compare>
4447 (__first, __middle, __last, __comp, __len1, __len2, __buff);
4448 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
4449 for (; true; ++__first, (void) --__len1)
4453 if (__comp(*__middle, *__first))
4456 // __first < __middle < __last
4457 // *__first > *__middle
4458 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4460 // [__first, __m1) <= [__middle, __m2)
4461 // [__middle, __m2) < [__m1, __middle)
4462 // [__m1, __middle) <= [__m2, __last)
4463 // and __m1 or __m2 is in the middle of its range
4464 _BidirectionalIterator __m1; // "median" of [__first, __middle)
4465 _BidirectionalIterator __m2; // "median" of [__middle, __last)
4466 difference_type __len11; // distance(__first, __m1)
4467 difference_type __len21; // distance(__middle, __m2)
4468 // binary search smaller range
4469 if (__len1 < __len2)
4470 { // __len >= 1, __len2 >= 2
4471 __len21 = __len2 / 2;
4473 _VSTD::advance(__m2, __len21);
4474 __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4475 __len11 = _VSTD::distance(__first, __m1);
4480 { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
4481 // It is known *__first > *__middle
4482 swap(*__first, *__middle);
4485 // __len1 >= 2, __len2 >= 1
4486 __len11 = __len1 / 2;
4488 _VSTD::advance(__m1, __len11);
4489 __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp);
4490 __len21 = _VSTD::distance(__middle, __m2);
4492 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle)
4493 difference_type __len22 = __len2 - __len21; // distance(__m2, __last)
4494 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4495 // swap middle two partitions
4496 __middle = _VSTD::rotate(__m1, __middle, __m2);
4497 // __len12 and __len21 now have swapped meanings
4498 // merge smaller range with recurisve call and larger with tail recursion elimination
4499 if (__len11 + __len21 < __len12 + __len22)
4501 __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4502 // __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4510 __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4511 // __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4520 template <class _BidirectionalIterator, class _Compare>
4521 inline _LIBCPP_INLINE_VISIBILITY
4523 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4526 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4527 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4528 difference_type __len1 = _VSTD::distance(__first, __middle);
4529 difference_type __len2 = _VSTD::distance(__middle, __last);
4530 difference_type __buf_size = _VSTD::min(__len1, __len2);
4531 pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
4532 unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
4534 #ifdef _LIBCPP_DEBUG
4535 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4536 __debug_less<_Compare> __c(__comp);
4537 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2,
4538 __buf.first, __buf.second);
4539 #else // _LIBCPP_DEBUG
4540 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4541 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4542 __buf.first, __buf.second);
4543 #endif // _LIBCPP_DEBUG
4546 template <class _BidirectionalIterator>
4547 inline _LIBCPP_INLINE_VISIBILITY
4549 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
4551 _VSTD::inplace_merge(__first, __middle, __last,
4552 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4557 template <class _Compare, class _InputIterator1, class _InputIterator2>
4559 __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
4560 _InputIterator2 __first2, _InputIterator2 __last2,
4561 typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
4563 typedef typename iterator_traits<_InputIterator1>::value_type value_type;
4564 __destruct_n __d(0);
4565 unique_ptr<value_type, __destruct_n&> __h(__result, __d);
4566 for (; true; ++__result)
4568 if (__first1 == __last1)
4570 for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0))
4571 ::new (__result) value_type(_VSTD::move(*__first2));
4575 if (__first2 == __last2)
4577 for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0))
4578 ::new (__result) value_type(_VSTD::move(*__first1));
4582 if (__comp(*__first2, *__first1))
4584 ::new (__result) value_type(_VSTD::move(*__first2));
4585 __d.__incr((value_type*)0);
4590 ::new (__result) value_type(_VSTD::move(*__first1));
4591 __d.__incr((value_type*)0);
4597 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4599 __merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
4600 _InputIterator2 __first2, _InputIterator2 __last2,
4601 _OutputIterator __result, _Compare __comp)
4603 for (; __first1 != __last1; ++__result)
4605 if (__first2 == __last2)
4607 for (; __first1 != __last1; ++__first1, ++__result)
4608 *__result = _VSTD::move(*__first1);
4611 if (__comp(*__first2, *__first1))
4613 *__result = _VSTD::move(*__first2);
4618 *__result = _VSTD::move(*__first1);
4622 for (; __first2 != __last2; ++__first2, ++__result)
4623 *__result = _VSTD::move(*__first2);
4626 template <class _Compare, class _RandomAccessIterator>
4628 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4629 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4630 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
4632 template <class _Compare, class _RandomAccessIterator>
4634 __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
4635 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4636 typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
4638 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4644 ::new(__first2) value_type(_VSTD::move(*__first1));
4647 __destruct_n __d(0);
4648 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
4649 if (__comp(*--__last1, *__first1))
4651 ::new(__first2) value_type(_VSTD::move(*__last1));
4652 __d.__incr((value_type*)0);
4654 ::new(__first2) value_type(_VSTD::move(*__first1));
4658 ::new(__first2) value_type(_VSTD::move(*__first1));
4659 __d.__incr((value_type*)0);
4661 ::new(__first2) value_type(_VSTD::move(*__last1));
4668 __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
4671 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4672 _RandomAccessIterator __m = __first1 + __l2;
4673 __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
4674 __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
4675 __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
4678 template <class _Tp>
4679 struct __stable_sort_switch
4681 static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
4684 template <class _Compare, class _RandomAccessIterator>
4686 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4687 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4688 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
4690 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4691 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4698 if (__comp(*--__last, *__first))
4699 swap(*__first, *__last);
4702 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4704 __insertion_sort<_Compare>(__first, __last, __comp);
4707 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4708 _RandomAccessIterator __m = __first + __l2;
4709 if (__len <= __buff_size)
4711 __destruct_n __d(0);
4712 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4713 __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4714 __d.__set(__l2, (value_type*)0);
4715 __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
4716 __d.__set(__len, (value_type*)0);
4717 __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4718 // __merge<_Compare>(move_iterator<value_type*>(__buff),
4719 // move_iterator<value_type*>(__buff + __l2),
4720 // move_iterator<_RandomAccessIterator>(__buff + __l2),
4721 // move_iterator<_RandomAccessIterator>(__buff + __len),
4722 // __first, __comp);
4725 __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4726 __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
4727 __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4730 template <class _RandomAccessIterator, class _Compare>
4731 inline _LIBCPP_INLINE_VISIBILITY
4733 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4735 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4736 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4737 difference_type __len = __last - __first;
4738 pair<value_type*, ptrdiff_t> __buf(0, 0);
4739 unique_ptr<value_type, __return_temporary_buffer> __h;
4740 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4742 __buf = _VSTD::get_temporary_buffer<value_type>(__len);
4743 __h.reset(__buf.first);
4745 #ifdef _LIBCPP_DEBUG
4746 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4747 __debug_less<_Compare> __c(__comp);
4748 __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);
4749 #else // _LIBCPP_DEBUG
4750 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4751 __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4752 #endif // _LIBCPP_DEBUG
4755 template <class _RandomAccessIterator>
4756 inline _LIBCPP_INLINE_VISIBILITY
4758 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4760 _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4765 template <class _RandomAccessIterator, class _Compare>
4766 _RandomAccessIterator
4767 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4769 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4770 difference_type __len = __last - __first;
4771 difference_type __p = 0;
4772 difference_type __c = 1;
4773 _RandomAccessIterator __pp = __first;
4776 _RandomAccessIterator __cp = __first + __c;
4777 if (__comp(*__pp, *__cp))
4783 if (__comp(*__pp, *__cp))
4792 template<class _RandomAccessIterator>
4793 inline _LIBCPP_INLINE_VISIBILITY
4794 _RandomAccessIterator
4795 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4797 return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4802 template <class _RandomAccessIterator, class _Compare>
4803 inline _LIBCPP_INLINE_VISIBILITY
4805 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4807 return _VSTD::is_heap_until(__first, __last, __comp) == __last;
4810 template<class _RandomAccessIterator>
4811 inline _LIBCPP_INLINE_VISIBILITY
4813 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4815 return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4820 template <class _Compare, class _RandomAccessIterator>
4822 __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4823 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4825 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4828 __len = (__len - 2) / 2;
4829 _RandomAccessIterator __ptr = __first + __len;
4830 if (__comp(*__ptr, *--__last))
4832 value_type __t(_VSTD::move(*__last));
4835 *__last = _VSTD::move(*__ptr);
4839 __len = (__len - 1) / 2;
4840 __ptr = __first + __len;
4841 } while (__comp(*__ptr, __t));
4842 *__last = _VSTD::move(__t);
4847 template <class _RandomAccessIterator, class _Compare>
4848 inline _LIBCPP_INLINE_VISIBILITY
4850 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4852 #ifdef _LIBCPP_DEBUG
4853 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4854 __debug_less<_Compare> __c(__comp);
4855 __sift_up<_Comp_ref>(__first, __last, __c, __last - __first);
4856 #else // _LIBCPP_DEBUG
4857 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4858 __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
4859 #endif // _LIBCPP_DEBUG
4862 template <class _RandomAccessIterator>
4863 inline _LIBCPP_INLINE_VISIBILITY
4865 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4867 _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4872 template <class _Compare, class _RandomAccessIterator>
4874 __sift_down(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4875 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4876 _RandomAccessIterator __start)
4878 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4879 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4880 // left-child of __start is at 2 * __start + 1
4881 // right-child of __start is at 2 * __start + 2
4882 difference_type __child = __start - __first;
4884 if (__len < 2 || (__len - 2) / 2 < __child)
4887 __child = 2 * __child + 1;
4888 _RandomAccessIterator __child_i = __first + __child;
4890 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4891 // right-child exists and is greater than left-child
4896 // check if we are in heap-order
4897 if (__comp(*__child_i, *__start))
4898 // we are, __start is larger than it's largest child
4901 value_type __top(_VSTD::move(*__start));
4904 // we are not in heap-order, swap the parent with it's largest child
4905 *__start = _VSTD::move(*__child_i);
4906 __start = __child_i;
4908 if ((__len - 2) / 2 < __child)
4911 // recompute the child based off of the updated parent
4912 __child = 2 * __child + 1;
4913 __child_i = __first + __child;
4915 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4916 // right-child exists and is greater than left-child
4921 // check if we are in heap-order
4922 } while (!__comp(*__child_i, __top));
4923 *__start = _VSTD::move(__top);
4926 template <class _Compare, class _RandomAccessIterator>
4927 inline _LIBCPP_INLINE_VISIBILITY
4929 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4930 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4934 swap(*__first, *--__last);
4935 __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);
4939 template <class _RandomAccessIterator, class _Compare>
4940 inline _LIBCPP_INLINE_VISIBILITY
4942 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4944 #ifdef _LIBCPP_DEBUG
4945 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4946 __debug_less<_Compare> __c(__comp);
4947 __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);
4948 #else // _LIBCPP_DEBUG
4949 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4950 __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
4951 #endif // _LIBCPP_DEBUG
4954 template <class _RandomAccessIterator>
4955 inline _LIBCPP_INLINE_VISIBILITY
4957 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4959 _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4964 template <class _Compare, class _RandomAccessIterator>
4966 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4968 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4969 difference_type __n = __last - __first;
4972 // start from the first parent, there is no need to consider children
4973 for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start)
4975 __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start);
4980 template <class _RandomAccessIterator, class _Compare>
4981 inline _LIBCPP_INLINE_VISIBILITY
4983 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4985 #ifdef _LIBCPP_DEBUG
4986 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4987 __debug_less<_Compare> __c(__comp);
4988 __make_heap<_Comp_ref>(__first, __last, __c);
4989 #else // _LIBCPP_DEBUG
4990 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4991 __make_heap<_Comp_ref>(__first, __last, __comp);
4992 #endif // _LIBCPP_DEBUG
4995 template <class _RandomAccessIterator>
4996 inline _LIBCPP_INLINE_VISIBILITY
4998 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5000 _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5005 template <class _Compare, class _RandomAccessIterator>
5007 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5009 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5010 for (difference_type __n = __last - __first; __n > 1; --__last, --__n)
5011 __pop_heap<_Compare>(__first, __last, __comp, __n);
5014 template <class _RandomAccessIterator, class _Compare>
5015 inline _LIBCPP_INLINE_VISIBILITY
5017 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5019 #ifdef _LIBCPP_DEBUG
5020 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5021 __debug_less<_Compare> __c(__comp);
5022 __sort_heap<_Comp_ref>(__first, __last, __c);
5023 #else // _LIBCPP_DEBUG
5024 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5025 __sort_heap<_Comp_ref>(__first, __last, __comp);
5026 #endif // _LIBCPP_DEBUG
5029 template <class _RandomAccessIterator>
5030 inline _LIBCPP_INLINE_VISIBILITY
5032 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5034 _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5039 template <class _Compare, class _RandomAccessIterator>
5041 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5044 __make_heap<_Compare>(__first, __middle, __comp);
5045 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
5046 for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
5048 if (__comp(*__i, *__first))
5050 swap(*__i, *__first);
5051 __sift_down<_Compare>(__first, __middle, __comp, __len, __first);
5054 __sort_heap<_Compare>(__first, __middle, __comp);
5057 template <class _RandomAccessIterator, class _Compare>
5058 inline _LIBCPP_INLINE_VISIBILITY
5060 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5063 #ifdef _LIBCPP_DEBUG
5064 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5065 __debug_less<_Compare> __c(__comp);
5066 __partial_sort<_Comp_ref>(__first, __middle, __last, __c);
5067 #else // _LIBCPP_DEBUG
5068 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5069 __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
5070 #endif // _LIBCPP_DEBUG
5073 template <class _RandomAccessIterator>
5074 inline _LIBCPP_INLINE_VISIBILITY
5076 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
5078 _VSTD::partial_sort(__first, __middle, __last,
5079 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5082 // partial_sort_copy
5084 template <class _Compare, class _InputIterator, class _RandomAccessIterator>
5085 _RandomAccessIterator
5086 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
5087 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5089 _RandomAccessIterator __r = __result_first;
5090 if (__r != __result_last)
5092 for (; __first != __last && __r != __result_last; (void) ++__first, ++__r)
5094 __make_heap<_Compare>(__result_first, __r, __comp);
5095 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
5096 for (; __first != __last; ++__first)
5097 if (__comp(*__first, *__result_first))
5099 *__result_first = *__first;
5100 __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first);
5102 __sort_heap<_Compare>(__result_first, __r, __comp);
5107 template <class _InputIterator, class _RandomAccessIterator, class _Compare>
5108 inline _LIBCPP_INLINE_VISIBILITY
5109 _RandomAccessIterator
5110 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5111 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5113 #ifdef _LIBCPP_DEBUG
5114 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5115 __debug_less<_Compare> __c(__comp);
5116 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);
5117 #else // _LIBCPP_DEBUG
5118 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5119 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
5120 #endif // _LIBCPP_DEBUG
5123 template <class _InputIterator, class _RandomAccessIterator>
5124 inline _LIBCPP_INLINE_VISIBILITY
5125 _RandomAccessIterator
5126 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5127 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
5129 return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
5130 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5135 template <class _Compare, class _RandomAccessIterator>
5137 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5139 // _Compare is known to be a reference type
5140 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5141 const difference_type __limit = 7;
5145 if (__nth == __last)
5147 difference_type __len = __last - __first;
5154 if (__comp(*--__last, *__first))
5155 swap(*__first, *__last);
5159 _RandomAccessIterator __m = __first;
5160 _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
5164 if (__len <= __limit)
5166 __selection_sort<_Compare>(__first, __last, __comp);
5169 // __len > __limit >= 3
5170 _RandomAccessIterator __m = __first + __len/2;
5171 _RandomAccessIterator __lm1 = __last;
5172 unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
5174 // partition [__first, __m) < *__m and *__m <= [__m, __last)
5175 // (this inhibits tossing elements equivalent to __m around unnecessarily)
5176 _RandomAccessIterator __i = __first;
5177 _RandomAccessIterator __j = __lm1;
5178 // j points beyond range to be tested, *__lm1 is known to be <= *__m
5179 // The search going up is known to be guarded but the search coming down isn't.
5180 // Prime the downward search with a guard.
5181 if (!__comp(*__i, *__m)) // if *__first == *__m
5183 // *__first == *__m, *__first doesn't go in first part
5184 // manually guard downward moving __j against __i
5189 // *__first == *__m, *__m <= all other elements
5190 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
5191 ++__i; // __first + 1
5193 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
5198 return; // [__first, __last) all equivalent elements
5199 if (__comp(*__first, *__i))
5209 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
5214 while (!__comp(*__first, *__i))
5216 while (__comp(*__first, *--__j))
5224 // [__first, __i) == *__first and *__first < [__i, __last)
5225 // The first part is sorted,
5228 // __nth_element the secod part
5229 // __nth_element<_Compare>(__i, __nth, __last, __comp);
5233 if (__comp(*__j, *__m))
5237 break; // found guard for downward moving __j, now use unguarded partition
5242 // j points beyond range to be tested, *__lm1 is known to be <= *__m
5243 // if not yet partitioned...
5246 // known that *(__i - 1) < *__m
5249 // __m still guards upward moving __i
5250 while (__comp(*__i, *__m))
5252 // It is now known that a guard exists for downward moving __j
5253 while (!__comp(*--__j, *__m))
5259 // It is known that __m != __j
5260 // If __m just moved, follow it
5266 // [__first, __i) < *__m and *__m <= [__i, __last)
5267 if (__i != __m && __comp(*__m, *__i))
5272 // [__first, __i) < *__i and *__i <= [__i+1, __last)
5277 // We were given a perfectly partitioned sequence. Coincidence?
5280 // Check for [__first, __i) already sorted
5281 __j = __m = __first;
5282 while (++__j != __i)
5284 if (__comp(*__j, *__m))
5285 // not yet sorted, so sort
5289 // [__first, __i) sorted
5294 // Check for [__i, __last) already sorted
5296 while (++__j != __last)
5298 if (__comp(*__j, *__m))
5299 // not yet sorted, so sort
5303 // [__i, __last) sorted
5308 // __nth_element on range containing __nth
5311 // __nth_element<_Compare>(__first, __nth, __i, __comp);
5316 // __nth_element<_Compare>(__i+1, __nth, __last, __comp);
5322 template <class _RandomAccessIterator, class _Compare>
5323 inline _LIBCPP_INLINE_VISIBILITY
5325 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5327 #ifdef _LIBCPP_DEBUG
5328 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5329 __debug_less<_Compare> __c(__comp);
5330 __nth_element<_Comp_ref>(__first, __nth, __last, __c);
5331 #else // _LIBCPP_DEBUG
5332 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5333 __nth_element<_Comp_ref>(__first, __nth, __last, __comp);
5334 #endif // _LIBCPP_DEBUG
5337 template <class _RandomAccessIterator>
5338 inline _LIBCPP_INLINE_VISIBILITY
5340 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
5342 _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5347 template <class _Compare, class _InputIterator1, class _InputIterator2>
5349 __includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5352 for (; __first2 != __last2; ++__first1)
5354 if (__first1 == __last1 || __comp(*__first2, *__first1))
5356 if (!__comp(*__first1, *__first2))
5362 template <class _InputIterator1, class _InputIterator2, class _Compare>
5363 inline _LIBCPP_INLINE_VISIBILITY
5365 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5368 #ifdef _LIBCPP_DEBUG
5369 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5370 __debug_less<_Compare> __c(__comp);
5371 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5372 #else // _LIBCPP_DEBUG
5373 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5374 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5375 #endif // _LIBCPP_DEBUG
5378 template <class _InputIterator1, class _InputIterator2>
5379 inline _LIBCPP_INLINE_VISIBILITY
5381 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
5383 return _VSTD::includes(__first1, __last1, __first2, __last2,
5384 __less<typename iterator_traits<_InputIterator1>::value_type,
5385 typename iterator_traits<_InputIterator2>::value_type>());
5390 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5392 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5393 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5395 for (; __first1 != __last1; ++__result)
5397 if (__first2 == __last2)
5398 return _VSTD::copy(__first1, __last1, __result);
5399 if (__comp(*__first2, *__first1))
5401 *__result = *__first2;
5406 *__result = *__first1;
5407 if (!__comp(*__first1, *__first2))
5412 return _VSTD::copy(__first2, __last2, __result);
5415 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5416 inline _LIBCPP_INLINE_VISIBILITY
5418 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5419 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5421 #ifdef _LIBCPP_DEBUG
5422 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5423 __debug_less<_Compare> __c(__comp);
5424 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5425 #else // _LIBCPP_DEBUG
5426 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5427 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5428 #endif // _LIBCPP_DEBUG
5431 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5432 inline _LIBCPP_INLINE_VISIBILITY
5434 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5435 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5437 return _VSTD::set_union(__first1, __last1, __first2, __last2, __result,
5438 __less<typename iterator_traits<_InputIterator1>::value_type,
5439 typename iterator_traits<_InputIterator2>::value_type>());
5444 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5446 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5447 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5449 while (__first1 != __last1 && __first2 != __last2)
5451 if (__comp(*__first1, *__first2))
5455 if (!__comp(*__first2, *__first1))
5457 *__result = *__first1;
5467 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5468 inline _LIBCPP_INLINE_VISIBILITY
5470 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5471 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5473 #ifdef _LIBCPP_DEBUG
5474 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5475 __debug_less<_Compare> __c(__comp);
5476 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5477 #else // _LIBCPP_DEBUG
5478 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5479 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5480 #endif // _LIBCPP_DEBUG
5483 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5484 inline _LIBCPP_INLINE_VISIBILITY
5486 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5487 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5489 return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result,
5490 __less<typename iterator_traits<_InputIterator1>::value_type,
5491 typename iterator_traits<_InputIterator2>::value_type>());
5496 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5498 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5499 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5501 while (__first1 != __last1)
5503 if (__first2 == __last2)
5504 return _VSTD::copy(__first1, __last1, __result);
5505 if (__comp(*__first1, *__first2))
5507 *__result = *__first1;
5513 if (!__comp(*__first2, *__first1))
5521 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5522 inline _LIBCPP_INLINE_VISIBILITY
5524 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5525 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5527 #ifdef _LIBCPP_DEBUG
5528 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5529 __debug_less<_Compare> __c(__comp);
5530 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5531 #else // _LIBCPP_DEBUG
5532 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5533 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5534 #endif // _LIBCPP_DEBUG
5537 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5538 inline _LIBCPP_INLINE_VISIBILITY
5540 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5541 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5543 return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result,
5544 __less<typename iterator_traits<_InputIterator1>::value_type,
5545 typename iterator_traits<_InputIterator2>::value_type>());
5548 // set_symmetric_difference
5550 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5552 __set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5553 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5555 while (__first1 != __last1)
5557 if (__first2 == __last2)
5558 return _VSTD::copy(__first1, __last1, __result);
5559 if (__comp(*__first1, *__first2))
5561 *__result = *__first1;
5567 if (__comp(*__first2, *__first1))
5569 *__result = *__first2;
5577 return _VSTD::copy(__first2, __last2, __result);
5580 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5581 inline _LIBCPP_INLINE_VISIBILITY
5583 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5584 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5586 #ifdef _LIBCPP_DEBUG
5587 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5588 __debug_less<_Compare> __c(__comp);
5589 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5590 #else // _LIBCPP_DEBUG
5591 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5592 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5593 #endif // _LIBCPP_DEBUG
5596 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5597 inline _LIBCPP_INLINE_VISIBILITY
5599 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5600 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5602 return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
5603 __less<typename iterator_traits<_InputIterator1>::value_type,
5604 typename iterator_traits<_InputIterator2>::value_type>());
5607 // lexicographical_compare
5609 template <class _Compare, class _InputIterator1, class _InputIterator2>
5611 __lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5612 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5614 for (; __first2 != __last2; ++__first1, (void) ++__first2)
5616 if (__first1 == __last1 || __comp(*__first1, *__first2))
5618 if (__comp(*__first2, *__first1))
5624 template <class _InputIterator1, class _InputIterator2, class _Compare>
5625 inline _LIBCPP_INLINE_VISIBILITY
5627 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5628 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5630 #ifdef _LIBCPP_DEBUG
5631 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5632 __debug_less<_Compare> __c(__comp);
5633 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5634 #else // _LIBCPP_DEBUG
5635 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5636 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5637 #endif // _LIBCPP_DEBUG
5640 template <class _InputIterator1, class _InputIterator2>
5641 inline _LIBCPP_INLINE_VISIBILITY
5643 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5644 _InputIterator2 __first2, _InputIterator2 __last2)
5646 return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,
5647 __less<typename iterator_traits<_InputIterator1>::value_type,
5648 typename iterator_traits<_InputIterator2>::value_type>());
5653 template <class _Compare, class _BidirectionalIterator>
5655 __next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5657 _BidirectionalIterator __i = __last;
5658 if (__first == __last || __first == --__i)
5662 _BidirectionalIterator __ip1 = __i;
5663 if (__comp(*--__i, *__ip1))
5665 _BidirectionalIterator __j = __last;
5666 while (!__comp(*__i, *--__j))
5669 _VSTD::reverse(__ip1, __last);
5674 _VSTD::reverse(__first, __last);
5680 template <class _BidirectionalIterator, class _Compare>
5681 inline _LIBCPP_INLINE_VISIBILITY
5683 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5685 #ifdef _LIBCPP_DEBUG
5686 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5687 __debug_less<_Compare> __c(__comp);
5688 return __next_permutation<_Comp_ref>(__first, __last, __c);
5689 #else // _LIBCPP_DEBUG
5690 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5691 return __next_permutation<_Comp_ref>(__first, __last, __comp);
5692 #endif // _LIBCPP_DEBUG
5695 template <class _BidirectionalIterator>
5696 inline _LIBCPP_INLINE_VISIBILITY
5698 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5700 return _VSTD::next_permutation(__first, __last,
5701 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5706 template <class _Compare, class _BidirectionalIterator>
5708 __prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5710 _BidirectionalIterator __i = __last;
5711 if (__first == __last || __first == --__i)
5715 _BidirectionalIterator __ip1 = __i;
5716 if (__comp(*__ip1, *--__i))
5718 _BidirectionalIterator __j = __last;
5719 while (!__comp(*--__j, *__i))
5722 _VSTD::reverse(__ip1, __last);
5727 _VSTD::reverse(__first, __last);
5733 template <class _BidirectionalIterator, class _Compare>
5734 inline _LIBCPP_INLINE_VISIBILITY
5736 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5738 #ifdef _LIBCPP_DEBUG
5739 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5740 __debug_less<_Compare> __c(__comp);
5741 return __prev_permutation<_Comp_ref>(__first, __last, __c);
5742 #else // _LIBCPP_DEBUG
5743 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5744 return __prev_permutation<_Comp_ref>(__first, __last, __comp);
5745 #endif // _LIBCPP_DEBUG
5748 template <class _BidirectionalIterator>
5749 inline _LIBCPP_INLINE_VISIBILITY
5751 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5753 return _VSTD::prev_permutation(__first, __last,
5754 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5757 _LIBCPP_END_NAMESPACE_STD
5759 #endif // _LIBCPP_ALGORITHM