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, class BinaryPredicate>
91 pair<InputIterator1, InputIterator2>
92 mismatch(InputIterator1 first1, InputIterator1 last1,
93 InputIterator2 first2, BinaryPredicate pred);
95 template <class InputIterator1, class InputIterator2>
97 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
99 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
101 equal(InputIterator1 first1, InputIterator1 last1,
102 InputIterator2 first2, BinaryPredicate pred);
104 template<class ForwardIterator1, class ForwardIterator2>
106 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
107 ForwardIterator2 first2);
109 template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
111 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
112 ForwardIterator2 first2, BinaryPredicate pred);
114 template <class ForwardIterator1, class ForwardIterator2>
116 search(ForwardIterator1 first1, ForwardIterator1 last1,
117 ForwardIterator2 first2, ForwardIterator2 last2);
119 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
121 search(ForwardIterator1 first1, ForwardIterator1 last1,
122 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
124 template <class ForwardIterator, class Size, class T>
126 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
128 template <class ForwardIterator, class Size, class T, class BinaryPredicate>
130 search_n(ForwardIterator first, ForwardIterator last,
131 Size count, const T& value, BinaryPredicate pred);
133 template <class InputIterator, class OutputIterator>
135 copy(InputIterator first, InputIterator last, OutputIterator result);
137 template<class InputIterator, class OutputIterator, class Predicate>
139 copy_if(InputIterator first, InputIterator last,
140 OutputIterator result, Predicate pred);
142 template<class InputIterator, class Size, class OutputIterator>
144 copy_n(InputIterator first, Size n, OutputIterator result);
146 template <class BidirectionalIterator1, class BidirectionalIterator2>
147 BidirectionalIterator2
148 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
149 BidirectionalIterator2 result);
151 template <class ForwardIterator1, class ForwardIterator2>
153 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
155 template <class ForwardIterator1, class ForwardIterator2>
157 iter_swap(ForwardIterator1 a, ForwardIterator2 b);
159 template <class InputIterator, class OutputIterator, class UnaryOperation>
161 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
163 template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
165 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
166 OutputIterator result, BinaryOperation binary_op);
168 template <class ForwardIterator, class T>
170 replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
172 template <class ForwardIterator, class Predicate, class T>
174 replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
176 template <class InputIterator, class OutputIterator, class T>
178 replace_copy(InputIterator first, InputIterator last, OutputIterator result,
179 const T& old_value, const T& new_value);
181 template <class InputIterator, class OutputIterator, class Predicate, class T>
183 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
185 template <class ForwardIterator, class T>
187 fill(ForwardIterator first, ForwardIterator last, const T& value);
189 template <class OutputIterator, class Size, class T>
191 fill_n(OutputIterator first, Size n, const T& value);
193 template <class ForwardIterator, class Generator>
195 generate(ForwardIterator first, ForwardIterator last, Generator gen);
197 template <class OutputIterator, class Size, class Generator>
199 generate_n(OutputIterator first, Size n, Generator gen);
201 template <class ForwardIterator, class T>
203 remove(ForwardIterator first, ForwardIterator last, const T& value);
205 template <class ForwardIterator, class Predicate>
207 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
209 template <class InputIterator, class OutputIterator, class T>
211 remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
213 template <class InputIterator, class OutputIterator, class Predicate>
215 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
217 template <class ForwardIterator>
219 unique(ForwardIterator first, ForwardIterator last);
221 template <class ForwardIterator, class BinaryPredicate>
223 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
225 template <class InputIterator, class OutputIterator>
227 unique_copy(InputIterator first, InputIterator last, OutputIterator result);
229 template <class InputIterator, class OutputIterator, class BinaryPredicate>
231 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
233 template <class BidirectionalIterator>
235 reverse(BidirectionalIterator first, BidirectionalIterator last);
237 template <class BidirectionalIterator, class OutputIterator>
239 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
241 template <class ForwardIterator>
243 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
245 template <class ForwardIterator, class OutputIterator>
247 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
249 template <class RandomAccessIterator>
251 random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
253 template <class RandomAccessIterator, class RandomNumberGenerator>
255 random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand);
257 template<class RandomAccessIterator, class UniformRandomNumberGenerator>
258 void shuffle(RandomAccessIterator first, RandomAccessIterator last,
259 UniformRandomNumberGenerator&& g);
261 template <class InputIterator, class Predicate>
263 is_partitioned(InputIterator first, InputIterator last, Predicate pred);
265 template <class ForwardIterator, class Predicate>
267 partition(ForwardIterator first, ForwardIterator last, Predicate pred);
269 template <class InputIterator, class OutputIterator1,
270 class OutputIterator2, class Predicate>
271 pair<OutputIterator1, OutputIterator2>
272 partition_copy(InputIterator first, InputIterator last,
273 OutputIterator1 out_true, OutputIterator2 out_false,
276 template <class ForwardIterator, class Predicate>
278 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
280 template<class ForwardIterator, class Predicate>
282 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
284 template <class ForwardIterator>
286 is_sorted(ForwardIterator first, ForwardIterator last);
288 template <class ForwardIterator, class Compare>
290 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
292 template<class ForwardIterator>
294 is_sorted_until(ForwardIterator first, ForwardIterator last);
296 template <class ForwardIterator, class Compare>
298 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
300 template <class RandomAccessIterator>
302 sort(RandomAccessIterator first, RandomAccessIterator last);
304 template <class RandomAccessIterator, class Compare>
306 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
308 template <class RandomAccessIterator>
310 stable_sort(RandomAccessIterator first, RandomAccessIterator last);
312 template <class RandomAccessIterator, class Compare>
314 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
316 template <class RandomAccessIterator>
318 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
320 template <class RandomAccessIterator, class Compare>
322 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
324 template <class InputIterator, class RandomAccessIterator>
326 partial_sort_copy(InputIterator first, InputIterator last,
327 RandomAccessIterator result_first, RandomAccessIterator result_last);
329 template <class InputIterator, class RandomAccessIterator, class Compare>
331 partial_sort_copy(InputIterator first, InputIterator last,
332 RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
334 template <class RandomAccessIterator>
336 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
338 template <class RandomAccessIterator, class Compare>
340 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
342 template <class ForwardIterator, class T>
344 lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
346 template <class ForwardIterator, class T, class Compare>
348 lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
350 template <class ForwardIterator, class T>
352 upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
354 template <class ForwardIterator, class T, class Compare>
356 upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
358 template <class ForwardIterator, class T>
359 pair<ForwardIterator, ForwardIterator>
360 equal_range(ForwardIterator first, ForwardIterator last, const T& value);
362 template <class ForwardIterator, class T, class Compare>
363 pair<ForwardIterator, ForwardIterator>
364 equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
366 template <class ForwardIterator, class T>
368 binary_search(ForwardIterator first, ForwardIterator last, const T& value);
370 template <class ForwardIterator, class T, class Compare>
372 binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
374 template <class InputIterator1, class InputIterator2, class OutputIterator>
376 merge(InputIterator1 first1, InputIterator1 last1,
377 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
379 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
381 merge(InputIterator1 first1, InputIterator1 last1,
382 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
384 template <class BidirectionalIterator>
386 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
388 template <class BidirectionalIterator, class Compare>
390 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
392 template <class InputIterator1, class InputIterator2>
394 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
396 template <class InputIterator1, class InputIterator2, class Compare>
398 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
400 template <class InputIterator1, class InputIterator2, class OutputIterator>
402 set_union(InputIterator1 first1, InputIterator1 last1,
403 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
405 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
407 set_union(InputIterator1 first1, InputIterator1 last1,
408 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
410 template <class InputIterator1, class InputIterator2, class OutputIterator>
412 set_intersection(InputIterator1 first1, InputIterator1 last1,
413 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
415 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
417 set_intersection(InputIterator1 first1, InputIterator1 last1,
418 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
420 template <class InputIterator1, class InputIterator2, class OutputIterator>
422 set_difference(InputIterator1 first1, InputIterator1 last1,
423 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
425 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
427 set_difference(InputIterator1 first1, InputIterator1 last1,
428 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
430 template <class InputIterator1, class InputIterator2, class OutputIterator>
432 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
433 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
435 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
437 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
438 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
440 template <class RandomAccessIterator>
442 push_heap(RandomAccessIterator first, RandomAccessIterator last);
444 template <class RandomAccessIterator, class Compare>
446 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
448 template <class RandomAccessIterator>
450 pop_heap(RandomAccessIterator first, RandomAccessIterator last);
452 template <class RandomAccessIterator, class Compare>
454 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
456 template <class RandomAccessIterator>
458 make_heap(RandomAccessIterator first, RandomAccessIterator last);
460 template <class RandomAccessIterator, class Compare>
462 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
464 template <class RandomAccessIterator>
466 sort_heap(RandomAccessIterator first, RandomAccessIterator last);
468 template <class RandomAccessIterator, class Compare>
470 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
472 template <class RandomAccessIterator>
474 is_heap(RandomAccessIterator first, RandomAccessiterator last);
476 template <class RandomAccessIterator, class Compare>
478 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
480 template <class RandomAccessIterator>
482 is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
484 template <class RandomAccessIterator, class Compare>
486 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
488 template <class ForwardIterator>
490 min_element(ForwardIterator first, ForwardIterator last);
492 template <class ForwardIterator, class Compare>
494 min_element(ForwardIterator first, ForwardIterator last, Compare comp);
498 min(const T& a, const T& b);
500 template <class T, class Compare>
502 min(const T& a, const T& b, Compare comp);
506 min(initializer_list<T> t);
508 template<class T, class Compare>
510 min(initializer_list<T> t, Compare comp);
512 template <class ForwardIterator>
514 max_element(ForwardIterator first, ForwardIterator last);
516 template <class ForwardIterator, class Compare>
518 max_element(ForwardIterator first, ForwardIterator last, Compare comp);
522 max(const T& a, const T& b);
524 template <class T, class Compare>
526 max(const T& a, const T& b, Compare comp);
530 max(initializer_list<T> t);
532 template<class T, class Compare>
534 max(initializer_list<T> t, Compare comp);
536 template<class ForwardIterator>
537 pair<ForwardIterator, ForwardIterator>
538 minmax_element(ForwardIterator first, ForwardIterator last);
540 template<class ForwardIterator, class Compare>
541 pair<ForwardIterator, ForwardIterator>
542 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
545 pair<const T&, const T&>
546 minmax(const T& a, const T& b);
548 template<class T, class Compare>
549 pair<const T&, const T&>
550 minmax(const T& a, const T& b, Compare comp);
554 minmax(initializer_list<T> t);
556 template<class T, class Compare>
558 minmax(initializer_list<T> t, Compare comp);
560 template <class InputIterator1, class InputIterator2>
562 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
564 template <class InputIterator1, class InputIterator2, class Compare>
566 lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
567 InputIterator2 first2, InputIterator2 last2, Compare comp);
569 template <class BidirectionalIterator>
571 next_permutation(BidirectionalIterator first, BidirectionalIterator last);
573 template <class BidirectionalIterator, class Compare>
575 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
577 template <class BidirectionalIterator>
579 prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
581 template <class BidirectionalIterator, class Compare>
583 prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
590 #include <initializer_list>
591 #include <type_traits>
598 #include <__undef_min_max>
600 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
601 #pragma GCC system_header
604 _LIBCPP_BEGIN_NAMESPACE_STD
606 template <class _T1, class _T2 = _T1>
609 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
610 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;}
611 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;}
612 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;}
616 struct __equal_to<_T1, _T1>
618 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
622 struct __equal_to<const _T1, _T1>
624 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
628 struct __equal_to<_T1, const _T1>
630 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
633 template <class _T1, class _T2 = _T1>
636 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
637 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;}
638 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;}
639 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;}
643 struct __less<_T1, _T1>
645 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
649 struct __less<const _T1, _T1>
651 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
655 struct __less<_T1, const _T1>
657 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
660 template <class _Predicate>
666 _LIBCPP_INLINE_VISIBILITY __negate() {}
668 _LIBCPP_INLINE_VISIBILITY
669 explicit __negate(_Predicate __p) : __p_(__p) {}
672 _LIBCPP_INLINE_VISIBILITY
673 bool operator()(const _T1& __x) {return !__p_(__x);}
675 template <class _T1, class _T2>
676 _LIBCPP_INLINE_VISIBILITY
677 bool operator()(const _T1& __x, const _T2& __y) {return !__p_(__x, __y);}
680 #ifdef _LIBCPP_DEBUG2
682 template <class _Compare>
686 __debug_less(_Compare& __c) : __comp_(__c) {}
687 template <class _Tp, class _Up>
688 bool operator()(const _Tp& __x, const _Up& __y)
690 bool __r = __comp_(__x, __y);
692 _LIBCPP_ASSERT(!__comp_(__y, __x), "Comparator does not induce a strict weak ordering");
697 #endif // _LIBCPP_DEBUG2
699 // Precondition: __x != 0
700 inline _LIBCPP_INLINE_VISIBILITY
704 return static_cast<unsigned>(__builtin_ctz(__x));
707 inline _LIBCPP_INLINE_VISIBILITY
709 __ctz(unsigned long __x)
711 return static_cast<unsigned long>(__builtin_ctzl(__x));
714 inline _LIBCPP_INLINE_VISIBILITY
716 __ctz(unsigned long long __x)
718 return static_cast<unsigned long long>(__builtin_ctzll(__x));
721 // Precondition: __x != 0
722 inline _LIBCPP_INLINE_VISIBILITY
726 return static_cast<unsigned>(__builtin_clz(__x));
729 inline _LIBCPP_INLINE_VISIBILITY
731 __clz(unsigned long __x)
733 return static_cast<unsigned long>(__builtin_clzl (__x));
736 inline _LIBCPP_INLINE_VISIBILITY
738 __clz(unsigned long long __x)
740 return static_cast<unsigned long long>(__builtin_clzll(__x));
743 inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned __x) {return __builtin_popcount (__x);}
744 inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long __x) {return __builtin_popcountl (__x);}
745 inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long long __x) {return __builtin_popcountll(__x);}
749 template <class _InputIterator, class _Predicate>
750 inline _LIBCPP_INLINE_VISIBILITY
752 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
754 for (; __first != __last; ++__first)
755 if (!__pred(*__first))
762 template <class _InputIterator, class _Predicate>
763 inline _LIBCPP_INLINE_VISIBILITY
765 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
767 for (; __first != __last; ++__first)
768 if (__pred(*__first))
775 template <class _InputIterator, class _Predicate>
776 inline _LIBCPP_INLINE_VISIBILITY
778 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
780 for (; __first != __last; ++__first)
781 if (__pred(*__first))
788 template <class _InputIterator, class _Function>
789 inline _LIBCPP_INLINE_VISIBILITY
791 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
793 for (; __first != __last; ++__first)
795 return _VSTD::move(__f);
800 template <class _InputIterator, class _Tp>
801 inline _LIBCPP_INLINE_VISIBILITY
803 find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
805 for (; __first != __last; ++__first)
806 if (*__first == __value_)
813 template <class _InputIterator, class _Predicate>
814 inline _LIBCPP_INLINE_VISIBILITY
816 find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
818 for (; __first != __last; ++__first)
819 if (__pred(*__first))
826 template<class _InputIterator, class _Predicate>
827 inline _LIBCPP_INLINE_VISIBILITY
829 find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
831 for (; __first != __last; ++__first)
832 if (!__pred(*__first))
839 template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
841 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
842 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
843 forward_iterator_tag, forward_iterator_tag)
845 // modeled after search algorithm
846 _ForwardIterator1 __r = __last1; // __last1 is the "default" answer
847 if (__first2 == __last2)
853 if (__first1 == __last1) // if source exhausted return last correct answer
854 return __r; // (or __last1 if never found)
855 if (__pred(*__first1, *__first2))
859 // *__first1 matches *__first2, now match elements after here
860 _ForwardIterator1 __m1 = __first1;
861 _ForwardIterator2 __m2 = __first2;
864 if (++__m2 == __last2)
865 { // Pattern exhaused, record answer and search for another one
870 if (++__m1 == __last1) // Source exhausted, return last answer
872 if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first
876 } // else there is a match, check next elements
881 template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2>
882 _BidirectionalIterator1
883 __find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,
884 _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred,
885 bidirectional_iterator_tag, bidirectional_iterator_tag)
887 // modeled after search algorithm (in reverse)
888 if (__first2 == __last2)
889 return __last1; // Everything matches an empty sequence
890 _BidirectionalIterator1 __l1 = __last1;
891 _BidirectionalIterator2 __l2 = __last2;
895 // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks
898 if (__first1 == __l1) // return __last1 if no element matches *__first2
900 if (__pred(*--__l1, *__l2))
903 // *__l1 matches *__l2, now match elements before here
904 _BidirectionalIterator1 __m1 = __l1;
905 _BidirectionalIterator2 __m2 = __l2;
908 if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern)
910 if (__m1 == __first1) // Otherwise if source exhaused, pattern not found
912 if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1
915 } // else there is a match, check next elements
920 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
921 _RandomAccessIterator1
922 __find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
923 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
924 random_access_iterator_tag, random_access_iterator_tag)
926 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern
927 typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;
930 typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;
933 const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here
934 _RandomAccessIterator1 __l1 = __last1;
935 _RandomAccessIterator2 __l2 = __last2;
943 if (__pred(*--__l1, *__l2))
946 _RandomAccessIterator1 __m1 = __l1;
947 _RandomAccessIterator2 __m2 = __l2;
950 if (__m2 == __first2)
952 // no need to check range on __m1 because __s guarantees we have enough source
953 if (!__pred(*--__m1, *--__m2))
961 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
962 inline _LIBCPP_INLINE_VISIBILITY
964 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
965 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
967 return _VSTD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type>
968 (__first1, __last1, __first2, __last2, __pred,
969 typename iterator_traits<_ForwardIterator1>::iterator_category(),
970 typename iterator_traits<_ForwardIterator2>::iterator_category());
973 template <class _ForwardIterator1, class _ForwardIterator2>
974 inline _LIBCPP_INLINE_VISIBILITY
976 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
977 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
979 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
980 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
981 return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
986 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
988 find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
989 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
991 for (; __first1 != __last1; ++__first1)
992 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
993 if (__pred(*__first1, *__j))
998 template <class _ForwardIterator1, class _ForwardIterator2>
999 inline _LIBCPP_INLINE_VISIBILITY
1001 find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1002 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1004 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1005 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1006 return _VSTD::find_first_of(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1011 template <class _ForwardIterator, class _BinaryPredicate>
1012 inline _LIBCPP_INLINE_VISIBILITY
1014 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
1016 if (__first != __last)
1018 _ForwardIterator __i = __first;
1019 while (++__i != __last)
1021 if (__pred(*__first, *__i))
1029 template <class _ForwardIterator>
1030 inline _LIBCPP_INLINE_VISIBILITY
1032 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
1034 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1035 return _VSTD::adjacent_find(__first, __last, __equal_to<__v>());
1040 template <class _InputIterator, class _Tp>
1041 inline _LIBCPP_INLINE_VISIBILITY
1042 typename iterator_traits<_InputIterator>::difference_type
1043 count(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
1045 typename iterator_traits<_InputIterator>::difference_type __r(0);
1046 for (; __first != __last; ++__first)
1047 if (*__first == __value_)
1054 template <class _InputIterator, class _Predicate>
1055 inline _LIBCPP_INLINE_VISIBILITY
1056 typename iterator_traits<_InputIterator>::difference_type
1057 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
1059 typename iterator_traits<_InputIterator>::difference_type __r(0);
1060 for (; __first != __last; ++__first)
1061 if (__pred(*__first))
1068 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1069 inline _LIBCPP_INLINE_VISIBILITY
1070 pair<_InputIterator1, _InputIterator2>
1071 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1072 _InputIterator2 __first2, _BinaryPredicate __pred)
1074 for (; __first1 != __last1; ++__first1, ++__first2)
1075 if (!__pred(*__first1, *__first2))
1077 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1080 template <class _InputIterator1, class _InputIterator2>
1081 inline _LIBCPP_INLINE_VISIBILITY
1082 pair<_InputIterator1, _InputIterator2>
1083 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1085 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1086 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1087 return _VSTD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1092 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1093 inline _LIBCPP_INLINE_VISIBILITY
1095 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred)
1097 for (; __first1 != __last1; ++__first1, ++__first2)
1098 if (!__pred(*__first1, *__first2))
1103 template <class _InputIterator1, class _InputIterator2>
1104 inline _LIBCPP_INLINE_VISIBILITY
1106 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1108 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1109 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1110 return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1115 template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1117 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1118 _ForwardIterator2 __first2, _BinaryPredicate __pred)
1120 // shorten sequences as much as possible by lopping of any equal parts
1121 for (; __first1 != __last1; ++__first1, ++__first2)
1122 if (!__pred(*__first1, *__first2))
1126 // __first1 != __last1 && *__first1 != *__first2
1127 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1128 _D1 __l1 = _VSTD::distance(__first1, __last1);
1131 _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1);
1132 // For each element in [f1, l1) see if there are the same number of
1133 // equal elements in [f2, l2)
1134 for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
1136 // Have we already counted the number of *__i in [f1, l1)?
1137 for (_ForwardIterator1 __j = __first1; __j != __i; ++__j)
1138 if (__pred(*__j, *__i))
1141 // Count number of *__i in [f2, l2)
1143 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1144 if (__pred(*__i, *__j))
1148 // Count number of *__i in [__i, l1) (we can start with 1)
1150 for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
1151 if (__pred(*__i, *__j))
1161 template<class _ForwardIterator1, class _ForwardIterator2>
1162 inline _LIBCPP_INLINE_VISIBILITY
1164 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1165 _ForwardIterator2 __first2)
1167 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1168 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1169 return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1174 template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
1176 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1177 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
1178 forward_iterator_tag, forward_iterator_tag)
1180 if (__first2 == __last2)
1181 return __first1; // Everything matches an empty sequence
1184 // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks
1187 if (__first1 == __last1) // return __last1 if no element matches *__first2
1189 if (__pred(*__first1, *__first2))
1193 // *__first1 matches *__first2, now match elements after here
1194 _ForwardIterator1 __m1 = __first1;
1195 _ForwardIterator2 __m2 = __first2;
1198 if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern)
1200 if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found
1202 if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1
1206 } // else there is a match, check next elements
1211 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1212 _RandomAccessIterator1
1213 __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1214 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1215 random_access_iterator_tag, random_access_iterator_tag)
1217 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _D1;
1218 typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _D2;
1219 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern
1220 _D2 __len2 = __last2 - __first2;
1223 _D1 __len1 = __last1 - __first1;
1224 if (__len1 < __len2)
1226 const _RandomAccessIterator1 __s = __last1 - (__len2 - 1); // Start of pattern match can't go beyond here
1229 #if !_LIBCPP_UNROLL_LOOPS
1232 if (__first1 == __s)
1234 if (__pred(*__first1, *__first2))
1238 #else // !_LIBCPP_UNROLL_LOOPS
1239 for (_D1 __loop_unroll = (__s - __first1) / 4; __loop_unroll > 0; --__loop_unroll)
1241 if (__pred(*__first1, *__first2))
1243 if (__pred(*++__first1, *__first2))
1245 if (__pred(*++__first1, *__first2))
1247 if (__pred(*++__first1, *__first2))
1251 switch (__s - __first1)
1254 if (__pred(*__first1, *__first2))
1258 if (__pred(*__first1, *__first2))
1262 if (__pred(*__first1, *__first2))
1268 #endif // !_LIBCPP_UNROLL_LOOPS
1269 _RandomAccessIterator1 __m1 = __first1;
1270 _RandomAccessIterator2 __m2 = __first2;
1271 #if !_LIBCPP_UNROLL_LOOPS
1274 if (++__m2 == __last2)
1276 ++__m1; // no need to check range on __m1 because __s guarantees we have enough source
1277 if (!__pred(*__m1, *__m2))
1283 #else // !_LIBCPP_UNROLL_LOOPS
1286 for (_D2 __loop_unroll = (__last2 - __m2) / 4; __loop_unroll > 0; --__loop_unroll)
1288 if (!__pred(*__m1, *__m2))
1290 if (!__pred(*++__m1, *++__m2))
1292 if (!__pred(*++__m1, *++__m2))
1294 if (!__pred(*++__m1, *++__m2))
1299 switch (__last2 - __m2)
1302 if (!__pred(*__m1, *__m2))
1307 if (!__pred(*__m1, *__m2))
1312 if (!__pred(*__m1, *__m2))
1319 #endif // !_LIBCPP_UNROLL_LOOPS
1323 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1324 inline _LIBCPP_INLINE_VISIBILITY
1326 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1327 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1329 return _VSTD::__search<typename add_lvalue_reference<_BinaryPredicate>::type>
1330 (__first1, __last1, __first2, __last2, __pred,
1331 typename std::iterator_traits<_ForwardIterator1>::iterator_category(),
1332 typename std::iterator_traits<_ForwardIterator2>::iterator_category());
1335 template <class _ForwardIterator1, class _ForwardIterator2>
1336 inline _LIBCPP_INLINE_VISIBILITY
1338 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1339 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1341 typedef typename std::iterator_traits<_ForwardIterator1>::value_type __v1;
1342 typedef typename std::iterator_traits<_ForwardIterator2>::value_type __v2;
1343 return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1348 template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp>
1350 __search_n(_ForwardIterator __first, _ForwardIterator __last,
1351 _Size __count, const _Tp& __value_, _BinaryPredicate __pred, forward_iterator_tag)
1357 // Find first element in sequence that matchs __value_, with a mininum of loop checks
1360 if (__first == __last) // return __last if no element matches __value_
1362 if (__pred(*__first, __value_))
1366 // *__first matches __value_, now match elements after here
1367 _ForwardIterator __m = __first;
1371 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1373 if (++__m == __last) // Otherwise if source exhaused, pattern not found
1375 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1380 } // else there is a match, check next elements
1385 template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp>
1386 _RandomAccessIterator
1387 __search_n(_RandomAccessIterator __first, _RandomAccessIterator __last,
1388 _Size __count, const _Tp& __value_, _BinaryPredicate __pred, random_access_iterator_tag)
1392 _Size __len = static_cast<_Size>(__last - __first);
1393 if (__len < __count)
1395 const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here
1398 // Find first element in sequence that matchs __value_, with a mininum of loop checks
1401 if (__first == __s) // return __last if no element matches __value_
1403 if (__pred(*__first, __value_))
1407 // *__first matches __value_, now match elements after here
1408 _RandomAccessIterator __m = __first;
1412 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1414 ++__m; // no need to check range on __m because __s guarantees we have enough source
1415 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1420 } // else there is a match, check next elements
1425 template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
1426 inline _LIBCPP_INLINE_VISIBILITY
1428 search_n(_ForwardIterator __first, _ForwardIterator __last,
1429 _Size __count, const _Tp& __value_, _BinaryPredicate __pred)
1431 return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>
1432 (__first, __last, __count, __value_, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
1435 template <class _ForwardIterator, class _Size, class _Tp>
1436 inline _LIBCPP_INLINE_VISIBILITY
1438 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
1440 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1441 return _VSTD::search_n(__first, __last, __count, __value_, __equal_to<__v, _Tp>());
1446 template <class _Iter>
1447 struct __libcpp_is_trivial_iterator
1449 static const bool value = is_pointer<_Iter>::value;
1452 template <class _Iter>
1453 struct __libcpp_is_trivial_iterator<move_iterator<_Iter> >
1455 static const bool value = is_pointer<_Iter>::value;
1458 template <class _Iter>
1459 struct __libcpp_is_trivial_iterator<__wrap_iter<_Iter> >
1461 static const bool value = is_pointer<_Iter>::value;
1464 template <class _Iter>
1465 inline _LIBCPP_INLINE_VISIBILITY
1467 __unwrap_iter(_Iter __i)
1472 template <class _Tp>
1473 inline _LIBCPP_INLINE_VISIBILITY
1476 is_trivially_copy_assignable<_Tp>::value,
1479 __unwrap_iter(move_iterator<_Tp*> __i)
1484 template <class _Tp>
1485 inline _LIBCPP_INLINE_VISIBILITY
1488 is_trivially_copy_assignable<_Tp>::value,
1491 __unwrap_iter(__wrap_iter<_Tp*> __i)
1496 template <class _InputIterator, class _OutputIterator>
1497 inline _LIBCPP_INLINE_VISIBILITY
1499 __copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1501 for (; __first != __last; ++__first, ++__result)
1502 *__result = *__first;
1506 template <class _Tp, class _Up>
1507 inline _LIBCPP_INLINE_VISIBILITY
1510 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1511 is_trivially_copy_assignable<_Up>::value,
1514 __copy(_Tp* __first, _Tp* __last, _Up* __result)
1516 const size_t __n = static_cast<size_t>(__last - __first);
1517 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1518 return __result + __n;
1521 template <class _InputIterator, class _OutputIterator>
1522 inline _LIBCPP_INLINE_VISIBILITY
1524 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1526 return _VSTD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1531 template <class _BidirectionalIterator, class _OutputIterator>
1532 inline _LIBCPP_INLINE_VISIBILITY
1534 __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
1536 while (__first != __last)
1537 *--__result = *--__last;
1541 template <class _Tp, class _Up>
1542 inline _LIBCPP_INLINE_VISIBILITY
1545 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1546 is_trivially_copy_assignable<_Up>::value,
1549 __copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
1551 const size_t __n = static_cast<size_t>(__last - __first);
1553 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1557 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1558 inline _LIBCPP_INLINE_VISIBILITY
1559 _BidirectionalIterator2
1560 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1561 _BidirectionalIterator2 __result)
1563 return _VSTD::__copy_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1568 template<class _InputIterator, class _OutputIterator, class _Predicate>
1569 inline _LIBCPP_INLINE_VISIBILITY
1571 copy_if(_InputIterator __first, _InputIterator __last,
1572 _OutputIterator __result, _Predicate __pred)
1574 for (; __first != __last; ++__first)
1576 if (__pred(*__first))
1578 *__result = *__first;
1587 template<class _InputIterator, class _Size, class _OutputIterator>
1588 inline _LIBCPP_INLINE_VISIBILITY
1591 __is_input_iterator<_InputIterator>::value &&
1592 !__is_random_access_iterator<_InputIterator>::value,
1595 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1599 *__result = *__first;
1601 for (--__n; __n > 0; --__n)
1604 *__result = *__first;
1611 template<class _InputIterator, class _Size, class _OutputIterator>
1612 inline _LIBCPP_INLINE_VISIBILITY
1615 __is_random_access_iterator<_InputIterator>::value,
1618 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1620 return _VSTD::copy(__first, __first + __n, __result);
1625 template <class _InputIterator, class _OutputIterator>
1626 inline _LIBCPP_INLINE_VISIBILITY
1628 __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1630 for (; __first != __last; ++__first, ++__result)
1631 *__result = _VSTD::move(*__first);
1635 template <class _Tp, class _Up>
1636 inline _LIBCPP_INLINE_VISIBILITY
1639 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1640 is_trivially_copy_assignable<_Up>::value,
1643 __move(_Tp* __first, _Tp* __last, _Up* __result)
1645 const size_t __n = static_cast<size_t>(__last - __first);
1646 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1647 return __result + __n;
1650 template <class _InputIterator, class _OutputIterator>
1651 inline _LIBCPP_INLINE_VISIBILITY
1653 move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1655 return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1660 template <class _InputIterator, class _OutputIterator>
1661 inline _LIBCPP_INLINE_VISIBILITY
1663 __move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1665 while (__first != __last)
1666 *--__result = _VSTD::move(*--__last);
1670 template <class _Tp, class _Up>
1671 inline _LIBCPP_INLINE_VISIBILITY
1674 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1675 is_trivially_copy_assignable<_Up>::value,
1678 __move_backward(_Tp* __first, _Tp* __last, _Up* __result)
1680 const size_t __n = static_cast<size_t>(__last - __first);
1682 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1686 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1687 inline _LIBCPP_INLINE_VISIBILITY
1688 _BidirectionalIterator2
1689 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1690 _BidirectionalIterator2 __result)
1692 return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1697 // moved to <type_traits> for better swap / noexcept support
1701 template <class _InputIterator, class _OutputIterator, class _UnaryOperation>
1702 inline _LIBCPP_INLINE_VISIBILITY
1704 transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op)
1706 for (; __first != __last; ++__first, ++__result)
1707 *__result = __op(*__first);
1711 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation>
1712 inline _LIBCPP_INLINE_VISIBILITY
1714 transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
1715 _OutputIterator __result, _BinaryOperation __binary_op)
1717 for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
1718 *__result = __binary_op(*__first1, *__first2);
1724 template <class _ForwardIterator, class _Tp>
1725 inline _LIBCPP_INLINE_VISIBILITY
1727 replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value)
1729 for (; __first != __last; ++__first)
1730 if (*__first == __old_value)
1731 *__first = __new_value;
1736 template <class _ForwardIterator, class _Predicate, class _Tp>
1737 inline _LIBCPP_INLINE_VISIBILITY
1739 replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value)
1741 for (; __first != __last; ++__first)
1742 if (__pred(*__first))
1743 *__first = __new_value;
1748 template <class _InputIterator, class _OutputIterator, class _Tp>
1749 inline _LIBCPP_INLINE_VISIBILITY
1751 replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1752 const _Tp& __old_value, const _Tp& __new_value)
1754 for (; __first != __last; ++__first, ++__result)
1755 if (*__first == __old_value)
1756 *__result = __new_value;
1758 *__result = *__first;
1764 template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp>
1765 inline _LIBCPP_INLINE_VISIBILITY
1767 replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1768 _Predicate __pred, const _Tp& __new_value)
1770 for (; __first != __last; ++__first, ++__result)
1771 if (__pred(*__first))
1772 *__result = __new_value;
1774 *__result = *__first;
1780 template <class _OutputIterator, class _Size, class _Tp>
1781 inline _LIBCPP_INLINE_VISIBILITY
1783 __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_, false_type)
1785 for (; __n > 0; ++__first, --__n)
1786 *__first = __value_;
1790 template <class _OutputIterator, class _Size, class _Tp>
1791 inline _LIBCPP_INLINE_VISIBILITY
1793 __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_, true_type)
1796 _VSTD::memset(__first, (unsigned char)__value_, (size_t)(__n));
1797 return __first + __n;
1800 template <class _OutputIterator, class _Size, class _Tp>
1801 inline _LIBCPP_INLINE_VISIBILITY
1803 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
1805 return _VSTD::__fill_n(__first, __n, __value_, integral_constant<bool,
1806 is_pointer<_OutputIterator>::value &&
1807 is_trivially_copy_assignable<_Tp>::value &&
1808 sizeof(_Tp) == 1>());
1813 template <class _ForwardIterator, class _Tp>
1814 inline _LIBCPP_INLINE_VISIBILITY
1816 __fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
1818 for (; __first != __last; ++__first)
1819 *__first = __value_;
1822 template <class _RandomAccessIterator, class _Tp>
1823 inline _LIBCPP_INLINE_VISIBILITY
1825 __fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag)
1827 _VSTD::fill_n(__first, __last - __first, __value_);
1830 template <class _ForwardIterator, class _Tp>
1831 inline _LIBCPP_INLINE_VISIBILITY
1833 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
1835 _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category());
1840 template <class _ForwardIterator, class _Generator>
1841 inline _LIBCPP_INLINE_VISIBILITY
1843 generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
1845 for (; __first != __last; ++__first)
1851 template <class _OutputIterator, class _Size, class _Generator>
1852 inline _LIBCPP_INLINE_VISIBILITY
1854 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
1856 for (; __n > 0; ++__first, --__n)
1863 template <class _ForwardIterator, class _Tp>
1865 remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
1867 __first = _VSTD::find(__first, __last, __value_);
1868 if (__first != __last)
1870 _ForwardIterator __i = __first;
1871 while (++__i != __last)
1873 if (!(*__i == __value_))
1875 *__first = _VSTD::move(*__i);
1885 template <class _ForwardIterator, class _Predicate>
1887 remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
1889 __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
1890 (__first, __last, __pred);
1891 if (__first != __last)
1893 _ForwardIterator __i = __first;
1894 while (++__i != __last)
1898 *__first = _VSTD::move(*__i);
1908 template <class _InputIterator, class _OutputIterator, class _Tp>
1909 inline _LIBCPP_INLINE_VISIBILITY
1911 remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_)
1913 for (; __first != __last; ++__first)
1915 if (!(*__first == __value_))
1917 *__result = *__first;
1926 template <class _InputIterator, class _OutputIterator, class _Predicate>
1927 inline _LIBCPP_INLINE_VISIBILITY
1929 remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
1931 for (; __first != __last; ++__first)
1933 if (!__pred(*__first))
1935 *__result = *__first;
1944 template <class _ForwardIterator, class _BinaryPredicate>
1946 unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
1948 __first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type>
1949 (__first, __last, __pred);
1950 if (__first != __last)
1954 _ForwardIterator __i = __first;
1955 for (++__i; ++__i != __last;)
1956 if (!__pred(*__first, *__i))
1957 *++__first = _VSTD::move(*__i);
1963 template <class _ForwardIterator>
1964 inline _LIBCPP_INLINE_VISIBILITY
1966 unique(_ForwardIterator __first, _ForwardIterator __last)
1968 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1969 return _VSTD::unique(__first, __last, __equal_to<__v>());
1974 template <class _BinaryPredicate, class _InputIterator, class _OutputIterator>
1976 __unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
1977 input_iterator_tag, output_iterator_tag)
1979 if (__first != __last)
1981 typename iterator_traits<_InputIterator>::value_type __t(*__first);
1984 while (++__first != __last)
1986 if (!__pred(__t, *__first))
1997 template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator>
1999 __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2000 forward_iterator_tag, output_iterator_tag)
2002 if (__first != __last)
2004 _ForwardIterator __i = __first;
2007 while (++__first != __last)
2009 if (!__pred(*__i, *__first))
2011 *__result = *__first;
2020 template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator>
2022 __unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred,
2023 input_iterator_tag, forward_iterator_tag)
2025 if (__first != __last)
2027 *__result = *__first;
2028 while (++__first != __last)
2029 if (!__pred(*__result, *__first))
2030 *++__result = *__first;
2036 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
2037 inline _LIBCPP_INLINE_VISIBILITY
2039 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred)
2041 return _VSTD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type>
2042 (__first, __last, __result, __pred,
2043 typename iterator_traits<_InputIterator>::iterator_category(),
2044 typename iterator_traits<_OutputIterator>::iterator_category());
2047 template <class _InputIterator, class _OutputIterator>
2048 inline _LIBCPP_INLINE_VISIBILITY
2050 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
2052 typedef typename iterator_traits<_InputIterator>::value_type __v;
2053 return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());
2058 template <class _BidirectionalIterator>
2059 inline _LIBCPP_INLINE_VISIBILITY
2061 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
2063 while (__first != __last)
2065 if (__first == --__last)
2067 swap(*__first, *__last);
2072 template <class _RandomAccessIterator>
2073 inline _LIBCPP_INLINE_VISIBILITY
2075 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
2077 if (__first != __last)
2078 for (; __first < --__last; ++__first)
2079 swap(*__first, *__last);
2082 template <class _BidirectionalIterator>
2083 inline _LIBCPP_INLINE_VISIBILITY
2085 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
2087 _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());
2092 template <class _BidirectionalIterator, class _OutputIterator>
2093 inline _LIBCPP_INLINE_VISIBILITY
2095 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
2097 for (; __first != __last; ++__result)
2098 *__result = *--__last;
2104 template <class _ForwardIterator>
2106 __rotate_left(_ForwardIterator __first, _ForwardIterator __last)
2108 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2109 value_type __tmp = _VSTD::move(*__first);
2110 _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
2111 *__lm1 = _VSTD::move(__tmp);
2115 template <class _BidirectionalIterator>
2116 _BidirectionalIterator
2117 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
2119 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
2120 _BidirectionalIterator __lm1 = _VSTD::prev(__last);
2121 value_type __tmp = _VSTD::move(*__lm1);
2122 _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
2123 *__first = _VSTD::move(__tmp);
2127 template <class _ForwardIterator>
2129 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2131 _ForwardIterator __i = __middle;
2134 swap(*__first, *__i);
2136 if (++__i == __last)
2138 if (__first == __middle)
2141 _ForwardIterator __r = __first;
2142 if (__first != __middle)
2147 swap(*__first, *__i);
2149 if (++__i == __last)
2151 if (__first == __middle)
2155 else if (__first == __middle)
2162 template<typename _Integral>
2163 inline _LIBCPP_INLINE_VISIBILITY
2165 __gcd(_Integral __x, _Integral __y)
2169 _Integral __t = __x % __y;
2176 template<typename _RandomAccessIterator>
2177 _RandomAccessIterator
2178 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
2180 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2181 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
2183 const difference_type __m1 = __middle - __first;
2184 const difference_type __m2 = __last - __middle;
2187 _VSTD::swap_ranges(__first, __middle, __middle);
2190 const difference_type __g = _VSTD::__gcd(__m1, __m2);
2191 for (_RandomAccessIterator __p = __first + __g; __p != __first;)
2193 value_type __t(_VSTD::move(*--__p));
2194 _RandomAccessIterator __p1 = __p;
2195 _RandomAccessIterator __p2 = __p1 + __m1;
2198 *__p1 = _VSTD::move(*__p2);
2200 const difference_type __d = __last - __p2;
2204 __p2 = __first + (__m1 - __d);
2205 } while (__p2 != __p);
2206 *__p1 = _VSTD::move(__t);
2208 return __first + __m2;
2211 template <class _ForwardIterator>
2212 inline _LIBCPP_INLINE_VISIBILITY
2214 __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
2215 _VSTD::forward_iterator_tag)
2217 typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type;
2218 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2220 if (_VSTD::next(__first) == __middle)
2221 return _VSTD::__rotate_left(__first, __last);
2223 return _VSTD::__rotate_forward(__first, __middle, __last);
2226 template <class _BidirectionalIterator>
2227 inline _LIBCPP_INLINE_VISIBILITY
2228 _BidirectionalIterator
2229 __rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
2230 _VSTD::bidirectional_iterator_tag)
2232 typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type;
2233 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2235 if (_VSTD::next(__first) == __middle)
2236 return _VSTD::__rotate_left(__first, __last);
2237 if (_VSTD::next(__middle) == __last)
2238 return _VSTD::__rotate_right(__first, __last);
2240 return _VSTD::__rotate_forward(__first, __middle, __last);
2243 template <class _RandomAccessIterator>
2244 inline _LIBCPP_INLINE_VISIBILITY
2245 _RandomAccessIterator
2246 __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
2247 _VSTD::random_access_iterator_tag)
2249 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
2250 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2252 if (_VSTD::next(__first) == __middle)
2253 return _VSTD::__rotate_left(__first, __last);
2254 if (_VSTD::next(__middle) == __last)
2255 return _VSTD::__rotate_right(__first, __last);
2256 return _VSTD::__rotate_gcd(__first, __middle, __last);
2258 return _VSTD::__rotate_forward(__first, __middle, __last);
2261 template <class _ForwardIterator>
2262 inline _LIBCPP_INLINE_VISIBILITY
2264 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2266 if (__first == __middle)
2268 if (__middle == __last)
2270 return _VSTD::__rotate(__first, __middle, __last,
2271 typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());
2276 template <class _ForwardIterator, class _OutputIterator>
2277 inline _LIBCPP_INLINE_VISIBILITY
2279 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
2281 return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));
2286 template <class _ForwardIterator, class _Compare>
2287 inline _LIBCPP_INLINE_VISIBILITY
2289 min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2291 if (__first != __last)
2293 _ForwardIterator __i = __first;
2294 while (++__i != __last)
2295 if (__comp(*__i, *__first))
2301 template <class _ForwardIterator>
2302 inline _LIBCPP_INLINE_VISIBILITY
2304 min_element(_ForwardIterator __first, _ForwardIterator __last)
2306 return _VSTD::min_element(__first, __last,
2307 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2312 template <class _Tp, class _Compare>
2313 inline _LIBCPP_INLINE_VISIBILITY
2315 min(const _Tp& __a, const _Tp& __b, _Compare __comp)
2317 return __comp(__b, __a) ? __b : __a;
2320 template <class _Tp>
2321 inline _LIBCPP_INLINE_VISIBILITY
2323 min(const _Tp& __a, const _Tp& __b)
2325 return _VSTD::min(__a, __b, __less<_Tp>());
2328 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2330 template<class _Tp, class _Compare>
2331 inline _LIBCPP_INLINE_VISIBILITY
2333 min(initializer_list<_Tp> __t, _Compare __comp)
2335 return *_VSTD::min_element(__t.begin(), __t.end(), __comp);
2339 inline _LIBCPP_INLINE_VISIBILITY
2341 min(initializer_list<_Tp> __t)
2343 return *_VSTD::min_element(__t.begin(), __t.end());
2346 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2350 template <class _ForwardIterator, class _Compare>
2351 inline _LIBCPP_INLINE_VISIBILITY
2353 max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2355 if (__first != __last)
2357 _ForwardIterator __i = __first;
2358 while (++__i != __last)
2359 if (__comp(*__first, *__i))
2365 template <class _ForwardIterator>
2366 inline _LIBCPP_INLINE_VISIBILITY
2368 max_element(_ForwardIterator __first, _ForwardIterator __last)
2370 return _VSTD::max_element(__first, __last,
2371 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2376 template <class _Tp, class _Compare>
2377 inline _LIBCPP_INLINE_VISIBILITY
2379 max(const _Tp& __a, const _Tp& __b, _Compare __comp)
2381 return __comp(__a, __b) ? __b : __a;
2384 template <class _Tp>
2385 inline _LIBCPP_INLINE_VISIBILITY
2387 max(const _Tp& __a, const _Tp& __b)
2389 return _VSTD::max(__a, __b, __less<_Tp>());
2392 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2394 template<class _Tp, class _Compare>
2395 inline _LIBCPP_INLINE_VISIBILITY
2397 max(initializer_list<_Tp> __t, _Compare __comp)
2399 return *_VSTD::max_element(__t.begin(), __t.end(), __comp);
2403 inline _LIBCPP_INLINE_VISIBILITY
2405 max(initializer_list<_Tp> __t)
2407 return *_VSTD::max_element(__t.begin(), __t.end());
2410 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2414 template <class _ForwardIterator, class _Compare>
2415 std::pair<_ForwardIterator, _ForwardIterator>
2416 minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2418 std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);
2419 if (__first != __last)
2421 if (++__first != __last)
2423 if (__comp(*__first, *__result.first))
2424 __result.first = __first;
2426 __result.second = __first;
2427 while (++__first != __last)
2429 _ForwardIterator __i = __first;
2430 if (++__first == __last)
2432 if (__comp(*__i, *__result.first))
2433 __result.first = __i;
2434 else if (!__comp(*__i, *__result.second))
2435 __result.second = __i;
2440 if (__comp(*__first, *__i))
2442 if (__comp(*__first, *__result.first))
2443 __result.first = __first;
2444 if (!__comp(*__i, *__result.second))
2445 __result.second = __i;
2449 if (__comp(*__i, *__result.first))
2450 __result.first = __i;
2451 if (!__comp(*__first, *__result.second))
2452 __result.second = __first;
2461 template <class _ForwardIterator>
2462 inline _LIBCPP_INLINE_VISIBILITY
2463 std::pair<_ForwardIterator, _ForwardIterator>
2464 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
2466 return _VSTD::minmax_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
2471 template<class _Tp, class _Compare>
2472 inline _LIBCPP_INLINE_VISIBILITY
2473 pair<const _Tp&, const _Tp&>
2474 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
2476 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) :
2477 pair<const _Tp&, const _Tp&>(__a, __b);
2481 inline _LIBCPP_INLINE_VISIBILITY
2482 pair<const _Tp&, const _Tp&>
2483 minmax(const _Tp& __a, const _Tp& __b)
2485 return _VSTD::minmax(__a, __b, __less<_Tp>());
2488 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2491 inline _LIBCPP_INLINE_VISIBILITY
2493 minmax(initializer_list<_Tp> __t)
2495 pair<const _Tp*, const _Tp*> __p =
2496 _VSTD::minmax_element(__t.begin(), __t.end());
2497 return pair<_Tp, _Tp>(*__p.first, *__p.second);
2500 template<class _Tp, class _Compare>
2501 inline _LIBCPP_INLINE_VISIBILITY
2503 minmax(initializer_list<_Tp> __t, _Compare __comp)
2505 pair<const _Tp*, const _Tp*> __p =
2506 _VSTD::minmax_element(__t.begin(), __t.end(), __comp);
2507 return pair<_Tp, _Tp>(*__p.first, *__p.second);
2510 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2514 // __independent_bits_engine
2516 template <unsigned long long _Xp, size_t _Rp>
2519 static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp
2520 : __log2_imp<_Xp, _Rp - 1>::value;
2523 template <unsigned long long _Xp>
2524 struct __log2_imp<_Xp, 0>
2526 static const size_t value = 0;
2529 template <size_t _Rp>
2530 struct __log2_imp<0, _Rp>
2532 static const size_t value = _Rp + 1;
2535 template <class _UI, _UI _Xp>
2538 static const size_t value = __log2_imp<_Xp,
2539 sizeof(_UI) * __CHAR_BIT__ - 1>::value;
2542 template<class _Engine, class _UIntType>
2543 class __independent_bits_engine
2547 typedef _UIntType result_type;
2550 typedef typename _Engine::result_type _Engine_result_type;
2551 typedef typename conditional
2553 sizeof(_Engine_result_type) <= sizeof(result_type),
2556 >::type _Working_result_type;
2563 _Working_result_type __y0_;
2564 _Working_result_type __y1_;
2565 _Engine_result_type __mask0_;
2566 _Engine_result_type __mask1_;
2568 #ifdef _LIBCPP_HAS_NO_CONSTEXPR
2569 static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
2570 + _Working_result_type(1);
2572 static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()
2573 + _Working_result_type(1);
2575 static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value;
2576 static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits;
2577 static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
2580 // constructors and seeding functions
2581 __independent_bits_engine(_Engine& __e, size_t __w);
2583 // generating functions
2584 result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
2587 result_type __eval(false_type);
2588 result_type __eval(true_type);
2591 template<class _Engine, class _UIntType>
2592 __independent_bits_engine<_Engine, _UIntType>
2593 ::__independent_bits_engine(_Engine& __e, size_t __w)
2597 __n_ = __w_ / __m + (__w_ % __m != 0);
2598 __w0_ = __w_ / __n_;
2601 else if (__w0_ < _WDt)
2602 __y0_ = (_Rp >> __w0_) << __w0_;
2605 if (_Rp - __y0_ > __y0_ / __n_)
2608 __w0_ = __w_ / __n_;
2610 __y0_ = (_Rp >> __w0_) << __w0_;
2614 __n0_ = __n_ - __w_ % __n_;
2615 if (__w0_ < _WDt - 1)
2616 __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1);
2619 __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :
2620 _Engine_result_type(0);
2621 __mask1_ = __w0_ < _EDt - 1 ?
2622 _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :
2623 _Engine_result_type(~0);
2626 template<class _Engine, class _UIntType>
2629 __independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
2631 return static_cast<result_type>(__e_() & __mask0_);
2634 template<class _Engine, class _UIntType>
2636 __independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
2638 result_type _Sp = 0;
2639 for (size_t __k = 0; __k < __n0_; ++__k)
2641 _Engine_result_type __u;
2644 __u = __e_() - _Engine::min();
2645 } while (__u >= __y0_);
2650 _Sp += __u & __mask0_;
2652 for (size_t __k = __n0_; __k < __n_; ++__k)
2654 _Engine_result_type __u;
2657 __u = __e_() - _Engine::min();
2658 } while (__u >= __y1_);
2659 if (__w0_ < _WDt - 1)
2663 _Sp += __u & __mask1_;
2668 // uniform_int_distribution
2670 template<class _IntType = int>
2671 class uniform_int_distribution
2675 typedef _IntType result_type;
2682 typedef uniform_int_distribution distribution_type;
2684 explicit param_type(result_type __a = 0,
2685 result_type __b = numeric_limits<result_type>::max())
2686 : __a_(__a), __b_(__b) {}
2688 result_type a() const {return __a_;}
2689 result_type b() const {return __b_;}
2691 friend bool operator==(const param_type& __x, const param_type& __y)
2692 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
2693 friend bool operator!=(const param_type& __x, const param_type& __y)
2694 {return !(__x == __y);}
2701 // constructors and reset functions
2702 explicit uniform_int_distribution(result_type __a = 0,
2703 result_type __b = numeric_limits<result_type>::max())
2704 : __p_(param_type(__a, __b)) {}
2705 explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
2708 // generating functions
2709 template<class _URNG> result_type operator()(_URNG& __g)
2710 {return (*this)(__g, __p_);}
2711 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
2713 // property functions
2714 result_type a() const {return __p_.a();}
2715 result_type b() const {return __p_.b();}
2717 param_type param() const {return __p_;}
2718 void param(const param_type& __p) {__p_ = __p;}
2720 result_type min() const {return a();}
2721 result_type max() const {return b();}
2723 friend bool operator==(const uniform_int_distribution& __x,
2724 const uniform_int_distribution& __y)
2725 {return __x.__p_ == __y.__p_;}
2726 friend bool operator!=(const uniform_int_distribution& __x,
2727 const uniform_int_distribution& __y)
2728 {return !(__x == __y);}
2731 template<class _IntType>
2732 template<class _URNG>
2733 typename uniform_int_distribution<_IntType>::result_type
2734 uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
2736 typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
2737 uint32_t, uint64_t>::type _UIntType;
2738 const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1);
2741 const size_t _Dt = numeric_limits<_UIntType>::digits;
2742 typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
2744 return static_cast<result_type>(_Eng(__g, _Dt)());
2745 size_t __w = _Dt - __clz(_Rp) - 1;
2746 if ((_Rp & (_UIntType(~0) >> (_Dt - __w))) != 0)
2753 } while (__u >= _Rp);
2754 return static_cast<result_type>(__u + __p.a());
2759 __rs_default __rs_get();
2763 static unsigned __c_;
2767 typedef unsigned result_type;
2769 static const result_type _Min = 0;
2770 static const result_type _Max = 0xFFFFFFFF;
2772 __rs_default(const __rs_default&);
2775 result_type operator()();
2777 static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
2778 static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
2780 friend __rs_default __rs_get();
2783 __rs_default __rs_get();
2785 template <class _RandomAccessIterator>
2787 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
2789 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2790 typedef uniform_int_distribution<ptrdiff_t> _Dp;
2791 typedef typename _Dp::param_type _Pp;
2792 difference_type __d = __last - __first;
2796 __rs_default __g = __rs_get();
2797 for (--__last, --__d; __first < __last; ++__first, --__d)
2799 difference_type __i = __uid(__g, _Pp(0, __d));
2800 if (__i != difference_type(0))
2801 swap(*__first, *(__first + __i));
2806 template <class _RandomAccessIterator, class _RandomNumberGenerator>
2808 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
2809 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2810 _RandomNumberGenerator&& __rand)
2812 _RandomNumberGenerator& __rand)
2815 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2816 difference_type __d = __last - __first;
2819 for (--__last; __first < __last; ++__first, --__d)
2821 difference_type __i = __rand(__d);
2822 swap(*__first, *(__first + __i));
2827 template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
2828 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
2829 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2830 _UniformRandomNumberGenerator&& __g)
2832 _UniformRandomNumberGenerator& __g)
2835 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2836 typedef uniform_int_distribution<ptrdiff_t> _Dp;
2837 typedef typename _Dp::param_type _Pp;
2838 difference_type __d = __last - __first;
2842 for (--__last, --__d; __first < __last; ++__first, --__d)
2844 difference_type __i = __uid(__g, _Pp(0, __d));
2845 if (__i != difference_type(0))
2846 swap(*__first, *(__first + __i));
2851 template <class _InputIterator, class _Predicate>
2853 is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2855 for (; __first != __last; ++__first)
2856 if (!__pred(*__first))
2858 for (; __first != __last; ++__first)
2859 if (__pred(*__first))
2866 template <class _Predicate, class _ForwardIterator>
2868 __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
2872 if (__first == __last)
2874 if (!__pred(*__first))
2878 for (_ForwardIterator __p = __first; ++__p != __last;)
2882 swap(*__first, *__p);
2889 template <class _Predicate, class _BidirectionalIterator>
2890 _BidirectionalIterator
2891 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
2892 bidirectional_iterator_tag)
2898 if (__first == __last)
2900 if (!__pred(*__first))
2906 if (__first == --__last)
2908 } while (!__pred(*__last));
2909 swap(*__first, *__last);
2914 template <class _ForwardIterator, class _Predicate>
2915 inline _LIBCPP_INLINE_VISIBILITY
2917 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2919 return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>
2920 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
2925 template <class _InputIterator, class _OutputIterator1,
2926 class _OutputIterator2, class _Predicate>
2927 pair<_OutputIterator1, _OutputIterator2>
2928 partition_copy(_InputIterator __first, _InputIterator __last,
2929 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
2932 for (; __first != __last; ++__first)
2934 if (__pred(*__first))
2936 *__out_true = *__first;
2941 *__out_false = *__first;
2945 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
2950 template<class _ForwardIterator, class _Predicate>
2952 partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2954 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
2955 difference_type __len = _VSTD::distance(__first, __last);
2958 difference_type __l2 = __len / 2;
2959 _ForwardIterator __m = __first;
2960 _VSTD::advance(__m, __l2);
2974 template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
2976 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
2977 _Distance __len, _Pair __p, forward_iterator_tag __fit)
2979 // *__first is known to be false
2985 _ForwardIterator __m = __first;
2988 swap(*__first, *__m);
2993 if (__len <= __p.second)
2994 { // The buffer is big enough to use
2995 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2996 __destruct_n __d(0);
2997 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
2998 // Move the falses into the temporary buffer, and the trues to the front of the line
2999 // Update __first to always point to the end of the trues
3000 value_type* __t = __p.first;
3001 ::new(__t) value_type(_VSTD::move(*__first));
3002 __d.__incr((value_type*)0);
3004 _ForwardIterator __i = __first;
3005 while (++__i != __last)
3009 *__first = _VSTD::move(*__i);
3014 ::new(__t) value_type(_VSTD::move(*__i));
3015 __d.__incr((value_type*)0);
3019 // All trues now at start of range, all falses in buffer
3020 // Move falses back into range, but don't mess up __first which points to first false
3022 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3023 *__i = _VSTD::move(*__t2);
3024 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3027 // Else not enough buffer, do in place
3029 _ForwardIterator __m = __first;
3030 _Distance __len2 = __len / 2; // __len2 >= 2
3031 _VSTD::advance(__m, __len2);
3032 // recurse on [__first, __m), *__first know to be false
3033 // F?????????????????
3035 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3036 _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
3037 // TTTFFFFF??????????
3039 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3040 _ForwardIterator __m1 = __m;
3041 _ForwardIterator __second_false = __last;
3042 _Distance __len_half = __len - __len2;
3043 while (__pred(*__m1))
3045 if (++__m1 == __last)
3046 goto __second_half_done;
3049 // TTTFFFFFTTTF??????
3051 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
3053 // TTTFFFFFTTTTTFFFFF
3055 return _VSTD::rotate(__first_false, __m, __second_false);
3056 // TTTTTTTTFFFFFFFFFF
3060 struct __return_temporary_buffer
3062 template <class _Tp>
3063 _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}
3066 template <class _Predicate, class _ForwardIterator>
3068 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3069 forward_iterator_tag)
3071 const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment
3072 // Either prove all true and return __first or point to first false
3075 if (__first == __last)
3077 if (!__pred(*__first))
3081 // We now have a reduced range [__first, __last)
3082 // *__first is known to be false
3083 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3084 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3085 difference_type __len = _VSTD::distance(__first, __last);
3086 pair<value_type*, ptrdiff_t> __p(0, 0);
3087 unique_ptr<value_type, __return_temporary_buffer> __h;
3088 if (__len >= __alloc_limit)
3090 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3091 __h.reset(__p.first);
3093 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3094 (__first, __last, __pred, __len, __p, forward_iterator_tag());
3097 template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
3098 _BidirectionalIterator
3099 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3100 _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
3102 // *__first is known to be false
3103 // *__last is known to be true
3107 swap(*__first, *__last);
3112 _BidirectionalIterator __m = __first;
3115 swap(*__first, *__m);
3116 swap(*__m, *__last);
3119 swap(*__m, *__last);
3120 swap(*__first, *__m);
3123 if (__len <= __p.second)
3124 { // The buffer is big enough to use
3125 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3126 __destruct_n __d(0);
3127 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3128 // Move the falses into the temporary buffer, and the trues to the front of the line
3129 // Update __first to always point to the end of the trues
3130 value_type* __t = __p.first;
3131 ::new(__t) value_type(_VSTD::move(*__first));
3132 __d.__incr((value_type*)0);
3134 _BidirectionalIterator __i = __first;
3135 while (++__i != __last)
3139 *__first = _VSTD::move(*__i);
3144 ::new(__t) value_type(_VSTD::move(*__i));
3145 __d.__incr((value_type*)0);
3149 // move *__last, known to be true
3150 *__first = _VSTD::move(*__i);
3152 // All trues now at start of range, all falses in buffer
3153 // Move falses back into range, but don't mess up __first which points to first false
3154 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3155 *__i = _VSTD::move(*__t2);
3156 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3159 // Else not enough buffer, do in place
3161 _BidirectionalIterator __m = __first;
3162 _Distance __len2 = __len / 2; // __len2 >= 2
3163 _VSTD::advance(__m, __len2);
3164 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
3165 // F????????????????T
3167 _BidirectionalIterator __m1 = __m;
3168 _BidirectionalIterator __first_false = __first;
3169 _Distance __len_half = __len2;
3170 while (!__pred(*--__m1))
3172 if (__m1 == __first)
3173 goto __first_half_done;
3176 // F???TFFF?????????T
3178 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3179 __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3181 // TTTFFFFF?????????T
3183 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3185 _BidirectionalIterator __second_false = __last;
3187 __len_half = __len - __len2;
3188 while (__pred(*__m1))
3190 if (++__m1 == __last)
3191 goto __second_half_done;
3194 // TTTFFFFFTTTF?????T
3196 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
3198 // TTTFFFFFTTTTTFFFFF
3200 return _VSTD::rotate(__first_false, __m, __second_false);
3201 // TTTTTTTTFFFFFFFFFF
3205 template <class _Predicate, class _BidirectionalIterator>
3206 _BidirectionalIterator
3207 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3208 bidirectional_iterator_tag)
3210 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3211 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3212 const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment
3213 // Either prove all true and return __first or point to first false
3216 if (__first == __last)
3218 if (!__pred(*__first))
3222 // __first points to first false, everything prior to __first is already set.
3223 // Either prove [__first, __last) is all false and return __first, or point __last to last true
3226 if (__first == --__last)
3228 } while (!__pred(*__last));
3229 // We now have a reduced range [__first, __last]
3230 // *__first is known to be false
3231 // *__last is known to be true
3233 difference_type __len = _VSTD::distance(__first, __last) + 1;
3234 pair<value_type*, ptrdiff_t> __p(0, 0);
3235 unique_ptr<value_type, __return_temporary_buffer> __h;
3236 if (__len >= __alloc_limit)
3238 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3239 __h.reset(__p.first);
3241 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3242 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3245 template <class _ForwardIterator, class _Predicate>
3246 inline _LIBCPP_INLINE_VISIBILITY
3248 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3250 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3251 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3256 template <class _ForwardIterator, class _Compare>
3258 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3260 if (__first != __last)
3262 _ForwardIterator __i = __first;
3263 while (++__i != __last)
3265 if (__comp(*__i, *__first))
3273 template<class _ForwardIterator>
3274 inline _LIBCPP_INLINE_VISIBILITY
3276 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3278 return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3283 template <class _ForwardIterator, class _Compare>
3284 inline _LIBCPP_INLINE_VISIBILITY
3286 is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3288 return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
3291 template<class _ForwardIterator>
3292 inline _LIBCPP_INLINE_VISIBILITY
3294 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3296 return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3301 // stable, 2-3 compares, 0-2 swaps
3303 template <class _Compare, class _ForwardIterator>
3305 __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
3308 if (!__c(*__y, *__x)) // if x <= y
3310 if (!__c(*__z, *__y)) // if y <= z
3311 return __r; // x <= y && y <= z
3313 swap(*__y, *__z); // x <= z && y < z
3315 if (__c(*__y, *__x)) // if x > y
3317 swap(*__x, *__y); // x < y && y <= z
3320 return __r; // x <= y && y < z
3322 if (__c(*__z, *__y)) // x > y, if y > z
3324 swap(*__x, *__z); // x < y && y < z
3328 swap(*__x, *__y); // x > y && y <= z
3329 __r = 1; // x < y && x <= z
3330 if (__c(*__z, *__y)) // if y > z
3332 swap(*__y, *__z); // x <= y && y < z
3336 } // x <= y && y <= z
3338 // stable, 3-6 compares, 0-5 swaps
3340 template <class _Compare, class _ForwardIterator>
3342 __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3343 _ForwardIterator __x4, _Compare __c)
3345 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
3346 if (__c(*__x4, *__x3))
3350 if (__c(*__x3, *__x2))
3354 if (__c(*__x2, *__x1))
3364 // stable, 4-10 compares, 0-9 swaps
3366 template <class _Compare, class _ForwardIterator>
3368 __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3369 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
3371 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
3372 if (__c(*__x5, *__x4))
3376 if (__c(*__x4, *__x3))
3380 if (__c(*__x3, *__x2))
3384 if (__c(*__x2, *__x1))
3396 template <class _Compare, class _BirdirectionalIterator>
3398 __selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3400 _BirdirectionalIterator __lm1 = __last;
3401 for (--__lm1; __first != __lm1; ++__first)
3403 _BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator,
3404 typename add_lvalue_reference<_Compare>::type>
3405 (__first, __last, __comp);
3407 swap(*__first, *__i);
3411 template <class _Compare, class _BirdirectionalIterator>
3413 __insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3415 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3416 if (__first != __last)
3418 _BirdirectionalIterator __i = __first;
3419 for (++__i; __i != __last; ++__i)
3421 _BirdirectionalIterator __j = __i;
3422 value_type __t(_VSTD::move(*__j));
3423 for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
3424 *__j = _VSTD::move(*__k);
3425 *__j = _VSTD::move(__t);
3430 template <class _Compare, class _RandomAccessIterator>
3432 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3434 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3435 _RandomAccessIterator __j = __first+2;
3436 __sort3<_Compare>(__first, __first+1, __j, __comp);
3437 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3439 if (__comp(*__i, *__j))
3441 value_type __t(_VSTD::move(*__i));
3442 _RandomAccessIterator __k = __j;
3446 *__j = _VSTD::move(*__k);
3448 } while (__j != __first && __comp(__t, *--__k));
3449 *__j = _VSTD::move(__t);
3455 template <class _Compare, class _RandomAccessIterator>
3457 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3459 switch (__last - __first)
3465 if (__comp(*--__last, *__first))
3466 swap(*__first, *__last);
3469 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3472 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3475 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3478 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3479 _RandomAccessIterator __j = __first+2;
3480 __sort3<_Compare>(__first, __first+1, __j, __comp);
3481 const unsigned __limit = 8;
3482 unsigned __count = 0;
3483 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3485 if (__comp(*__i, *__j))
3487 value_type __t(_VSTD::move(*__i));
3488 _RandomAccessIterator __k = __j;
3492 *__j = _VSTD::move(*__k);
3494 } while (__j != __first && __comp(__t, *--__k));
3495 *__j = _VSTD::move(__t);
3496 if (++__count == __limit)
3497 return ++__i == __last;
3504 template <class _Compare, class _BirdirectionalIterator>
3506 __insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
3507 typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
3509 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3510 if (__first1 != __last1)
3512 __destruct_n __d(0);
3513 unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
3514 value_type* __last2 = __first2;
3515 ::new(__last2) value_type(_VSTD::move(*__first1));
3516 __d.__incr((value_type*)0);
3517 for (++__last2; ++__first1 != __last1; ++__last2)
3519 value_type* __j2 = __last2;
3520 value_type* __i2 = __j2;
3521 if (__comp(*__first1, *--__i2))
3523 ::new(__j2) value_type(_VSTD::move(*__i2));
3524 __d.__incr((value_type*)0);
3525 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2)
3526 *__j2 = _VSTD::move(*__i2);
3527 *__j2 = _VSTD::move(*__first1);
3531 ::new(__j2) value_type(_VSTD::move(*__first1));
3532 __d.__incr((value_type*)0);
3539 template <class _Compare, class _RandomAccessIterator>
3541 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3543 // _Compare is known to be a reference type
3544 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3545 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3546 const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
3547 is_trivially_copy_assignable<value_type>::value ? 30 : 6;
3551 difference_type __len = __last - __first;
3558 if (__comp(*--__last, *__first))
3559 swap(*__first, *__last);
3562 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3565 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3568 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3571 if (__len <= __limit)
3573 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
3577 _RandomAccessIterator __m = __first;
3578 _RandomAccessIterator __lm1 = __last;
3582 difference_type __delta;
3588 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
3594 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
3598 // partition [__first, __m) < *__m and *__m <= [__m, __last)
3599 // (this inhibits tossing elements equivalent to __m around unnecessarily)
3600 _RandomAccessIterator __i = __first;
3601 _RandomAccessIterator __j = __lm1;
3602 // j points beyond range to be tested, *__m is known to be <= *__lm1
3603 // The search going up is known to be guarded but the search coming down isn't.
3604 // Prime the downward search with a guard.
3605 if (!__comp(*__i, *__m)) // if *__first == *__m
3607 // *__first == *__m, *__first doesn't go in first part
3608 // manually guard downward moving __j against __i
3613 // *__first == *__m, *__m <= all other elements
3614 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
3615 ++__i; // __first + 1
3617 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
3622 return; // [__first, __last) all equivalent elements
3623 if (__comp(*__first, *__i))
3633 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
3638 while (!__comp(*__first, *__i))
3640 while (__comp(*__first, *--__j))
3648 // [__first, __i) == *__first and *__first < [__i, __last)
3649 // The first part is sorted, sort the secod part
3650 // _VSTD::__sort<_Compare>(__i, __last, __comp);
3654 if (__comp(*__j, *__m))
3658 break; // found guard for downward moving __j, now use unguarded partition
3662 // It is known that *__i < *__m
3664 // j points beyond range to be tested, *__m is known to be <= *__lm1
3665 // if not yet partitioned...
3668 // known that *(__i - 1) < *__m
3669 // known that __i <= __m
3672 // __m still guards upward moving __i
3673 while (__comp(*__i, *__m))
3675 // It is now known that a guard exists for downward moving __j
3676 while (!__comp(*--__j, *__m))
3682 // It is known that __m != __j
3683 // If __m just moved, follow it
3689 // [__first, __i) < *__m and *__m <= [__i, __last)
3690 if (__i != __m && __comp(*__m, *__i))
3695 // [__first, __i) < *__i and *__i <= [__i+1, __last)
3696 // If we were given a perfect partition, see if insertion sort is quick...
3699 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
3700 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
3716 // sort smaller range with recursive call and larger with tail recursion elimination
3717 if (__i - __first < __last - __i)
3719 _VSTD::__sort<_Compare>(__first, __i, __comp);
3720 // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
3725 _VSTD::__sort<_Compare>(__i+1, __last, __comp);
3726 // _VSTD::__sort<_Compare>(__first, __i, __comp);
3732 // This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
3733 template <class _RandomAccessIterator, class _Compare>
3734 inline _LIBCPP_INLINE_VISIBILITY
3736 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3738 #ifdef _LIBCPP_DEBUG2
3739 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3740 __debug_less<_Compare> __c(__comp);
3741 __sort<_Comp_ref>(__first, __last, __c);
3742 #else // _LIBCPP_DEBUG2
3743 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3744 __sort<_Comp_ref>(__first, __last, __comp);
3745 #endif // _LIBCPP_DEBUG2
3748 template <class _RandomAccessIterator>
3749 inline _LIBCPP_INLINE_VISIBILITY
3751 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
3753 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
3756 template <class _Tp>
3757 inline _LIBCPP_INLINE_VISIBILITY
3759 sort(_Tp** __first, _Tp** __last)
3761 _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
3764 template <class _Tp>
3765 inline _LIBCPP_INLINE_VISIBILITY
3767 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
3769 _VSTD::sort(__first.base(), __last.base());
3772 template <class _Tp, class _Compare>
3773 inline _LIBCPP_INLINE_VISIBILITY
3775 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
3777 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3778 _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
3782 #pragma warning( push )
3783 #pragma warning( disable: 4231)
3785 _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
3786 _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
3787 _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
3788 _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
3789 _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<short>&, short*>(short*, short*, __less<short>&))
3790 _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
3791 _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<int>&, int*>(int*, int*, __less<int>&))
3792 _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
3793 _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<long>&, long*>(long*, long*, __less<long>&))
3794 _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
3795 _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
3796 _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&))
3797 _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<float>&, float*>(float*, float*, __less<float>&))
3798 _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<double>&, double*>(double*, double*, __less<double>&))
3799 _LIBCPP_EXTERN_TEMPLATE(void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
3801 _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))
3802 _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
3803 _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
3804 _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
3805 _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))
3806 _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
3807 _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&))
3808 _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
3809 _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&))
3810 _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
3811 _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
3812 _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&))
3813 _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&))
3814 _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&))
3815 _LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
3817 _LIBCPP_EXTERN_TEMPLATE(unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&))
3819 #pragma warning( pop )
3824 template <class _Compare, class _ForwardIterator, class _Tp>
3826 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
3828 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3829 difference_type __len = _VSTD::distance(__first, __last);
3832 difference_type __l2 = __len / 2;
3833 _ForwardIterator __m = __first;
3834 _VSTD::advance(__m, __l2);
3835 if (__comp(*__m, __value_))
3846 template <class _ForwardIterator, class _Tp, class _Compare>
3847 inline _LIBCPP_INLINE_VISIBILITY
3849 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
3851 #ifdef _LIBCPP_DEBUG2
3852 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3853 __debug_less<_Compare> __c(__comp);
3854 return __lower_bound<_Comp_ref>(__first, __last, __value_, __c);
3855 #else // _LIBCPP_DEBUG2
3856 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3857 return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp);
3858 #endif // _LIBCPP_DEBUG2
3861 template <class _ForwardIterator, class _Tp>
3862 inline _LIBCPP_INLINE_VISIBILITY
3864 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
3866 return _VSTD::lower_bound(__first, __last, __value_,
3867 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
3872 template <class _Compare, class _ForwardIterator, class _Tp>
3874 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
3876 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3877 difference_type __len = _VSTD::distance(__first, __last);
3880 difference_type __l2 = __len / 2;
3881 _ForwardIterator __m = __first;
3882 _VSTD::advance(__m, __l2);
3883 if (__comp(__value_, *__m))
3894 template <class _ForwardIterator, class _Tp, class _Compare>
3895 inline _LIBCPP_INLINE_VISIBILITY
3897 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
3899 #ifdef _LIBCPP_DEBUG2
3900 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3901 __debug_less<_Compare> __c(__comp);
3902 return __upper_bound<_Comp_ref>(__first, __last, __value_, __c);
3903 #else // _LIBCPP_DEBUG2
3904 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3905 return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp);
3906 #endif // _LIBCPP_DEBUG2
3909 template <class _ForwardIterator, class _Tp>
3910 inline _LIBCPP_INLINE_VISIBILITY
3912 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
3914 return _VSTD::upper_bound(__first, __last, __value_,
3915 __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
3920 template <class _Compare, class _ForwardIterator, class _Tp>
3921 pair<_ForwardIterator, _ForwardIterator>
3922 __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
3924 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3925 difference_type __len = _VSTD::distance(__first, __last);
3928 difference_type __l2 = __len / 2;
3929 _ForwardIterator __m = __first;
3930 _VSTD::advance(__m, __l2);
3931 if (__comp(*__m, __value_))
3936 else if (__comp(__value_, *__m))
3943 _ForwardIterator __mp1 = __m;
3944 return pair<_ForwardIterator, _ForwardIterator>
3946 __lower_bound<_Compare>(__first, __m, __value_, __comp),
3947 __upper_bound<_Compare>(++__mp1, __last, __value_, __comp)
3951 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
3954 template <class _ForwardIterator, class _Tp, class _Compare>
3955 inline _LIBCPP_INLINE_VISIBILITY
3956 pair<_ForwardIterator, _ForwardIterator>
3957 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
3959 #ifdef _LIBCPP_DEBUG2
3960 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3961 __debug_less<_Compare> __c(__comp);
3962 return __equal_range<_Comp_ref>(__first, __last, __value_, __c);
3963 #else // _LIBCPP_DEBUG2
3964 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
3965 return __equal_range<_Comp_ref>(__first, __last, __value_, __comp);
3966 #endif // _LIBCPP_DEBUG2
3969 template <class _ForwardIterator, class _Tp>
3970 inline _LIBCPP_INLINE_VISIBILITY
3971 pair<_ForwardIterator, _ForwardIterator>
3972 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
3974 return _VSTD::equal_range(__first, __last, __value_,
3975 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
3980 template <class _Compare, class _ForwardIterator, class _Tp>
3981 inline _LIBCPP_INLINE_VISIBILITY
3983 __binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
3985 __first = __lower_bound<_Compare>(__first, __last, __value_, __comp);
3986 return __first != __last && !__comp(__value_, *__first);
3989 template <class _ForwardIterator, class _Tp, class _Compare>
3990 inline _LIBCPP_INLINE_VISIBILITY
3992 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
3994 #ifdef _LIBCPP_DEBUG2
3995 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
3996 __debug_less<_Compare> __c(__comp);
3997 return __binary_search<_Comp_ref>(__first, __last, __value_, __c);
3998 #else // _LIBCPP_DEBUG2
3999 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4000 return __binary_search<_Comp_ref>(__first, __last, __value_, __comp);
4001 #endif // _LIBCPP_DEBUG2
4004 template <class _ForwardIterator, class _Tp>
4005 inline _LIBCPP_INLINE_VISIBILITY
4007 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4009 return _VSTD::binary_search(__first, __last, __value_,
4010 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4015 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4017 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4018 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4020 for (; __first1 != __last1; ++__result)
4022 if (__first2 == __last2)
4023 return _VSTD::copy(__first1, __last1, __result);
4024 if (__comp(*__first2, *__first1))
4026 *__result = *__first2;
4031 *__result = *__first1;
4035 return _VSTD::copy(__first2, __last2, __result);
4038 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4039 inline _LIBCPP_INLINE_VISIBILITY
4041 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4042 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4044 #ifdef _LIBCPP_DEBUG2
4045 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4046 __debug_less<_Compare> __c(__comp);
4047 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
4048 #else // _LIBCPP_DEBUG2
4049 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4050 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4051 #endif // _LIBCPP_DEBUG2
4054 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4055 inline _LIBCPP_INLINE_VISIBILITY
4057 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4058 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4060 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
4061 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
4062 return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
4067 template <class _Compare, class _BidirectionalIterator>
4069 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4070 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4071 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4072 typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
4074 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4075 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4076 typedef typename iterator_traits<_BidirectionalIterator>::pointer pointer;
4077 __destruct_n __d(0);
4078 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4079 if (__len1 <= __len2)
4081 value_type* __p = __buff;
4082 for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), ++__i, ++__p)
4083 ::new(__p) value_type(_VSTD::move(*__i));
4084 __merge<_Compare>(move_iterator<value_type*>(__buff),
4085 move_iterator<value_type*>(__p),
4086 move_iterator<_BidirectionalIterator>(__middle),
4087 move_iterator<_BidirectionalIterator>(__last),
4092 value_type* __p = __buff;
4093 for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), ++__i, ++__p)
4094 ::new(__p) value_type(_VSTD::move(*__i));
4095 typedef reverse_iterator<_BidirectionalIterator> _RBi;
4096 typedef reverse_iterator<value_type*> _Rv;
4097 __merge(move_iterator<_RBi>(_RBi(__middle)), move_iterator<_RBi>(_RBi(__first)),
4098 move_iterator<_Rv>(_Rv(__p)), move_iterator<_Rv>(_Rv(__buff)),
4099 _RBi(__last), __negate<_Compare>(__comp));
4103 template <class _Compare, class _BidirectionalIterator>
4105 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4106 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4107 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4108 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
4110 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4111 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4114 // if __middle == __last, we're done
4117 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
4118 for (; true; ++__first, --__len1)
4122 if (__comp(*__middle, *__first))
4125 if (__len1 <= __buff_size || __len2 <= __buff_size)
4127 __buffered_inplace_merge<_Compare>(__first, __middle, __last, __comp, __len1, __len2, __buff);
4130 // __first < __middle < __last
4131 // *__first > *__middle
4132 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4134 // [__first, __m1) <= [__middle, __m2)
4135 // [__middle, __m2) < [__m1, __middle)
4136 // [__m1, __middle) <= [__m2, __last)
4137 // and __m1 or __m2 is in the middle of its range
4138 _BidirectionalIterator __m1; // "median" of [__first, __middle)
4139 _BidirectionalIterator __m2; // "median" of [__middle, __last)
4140 difference_type __len11; // distance(__first, __m1)
4141 difference_type __len21; // distance(__middle, __m2)
4142 // binary search smaller range
4143 if (__len1 < __len2)
4144 { // __len >= 1, __len2 >= 2
4145 __len21 = __len2 / 2;
4147 _VSTD::advance(__m2, __len21);
4148 __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4149 __len11 = _VSTD::distance(__first, __m1);
4154 { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
4155 // It is known *__first > *__middle
4156 swap(*__first, *__middle);
4159 // __len1 >= 2, __len2 >= 1
4160 __len11 = __len1 / 2;
4162 _VSTD::advance(__m1, __len11);
4163 __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp);
4164 __len21 = _VSTD::distance(__middle, __m2);
4166 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle)
4167 difference_type __len22 = __len2 - __len21; // distance(__m2, __last)
4168 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4169 // swap middle two partitions
4170 __middle = _VSTD::rotate(__m1, __middle, __m2);
4171 // __len12 and __len21 now have swapped meanings
4172 // merge smaller range with recurisve call and larger with tail recursion elimination
4173 if (__len11 + __len21 < __len12 + __len22)
4175 __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4176 // __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4184 __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4185 // __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4194 template <class _Tp>
4195 struct __inplace_merge_switch
4197 static const unsigned value = is_trivially_copy_assignable<_Tp>::value;
4200 template <class _BidirectionalIterator, class _Compare>
4201 inline _LIBCPP_INLINE_VISIBILITY
4203 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4206 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4207 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4208 difference_type __len1 = _VSTD::distance(__first, __middle);
4209 difference_type __len2 = _VSTD::distance(__middle, __last);
4210 difference_type __buf_size = _VSTD::min(__len1, __len2);
4211 pair<value_type*, ptrdiff_t> __buf(0, 0);
4212 unique_ptr<value_type, __return_temporary_buffer> __h;
4213 if (__inplace_merge_switch<value_type>::value && __buf_size > 8)
4215 __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
4216 __h.reset(__buf.first);
4218 #ifdef _LIBCPP_DEBUG2
4219 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4220 __debug_less<_Compare> __c(__comp);
4221 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2,
4222 __buf.first, __buf.second);
4223 #else // _LIBCPP_DEBUG2
4224 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4225 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4226 __buf.first, __buf.second);
4227 #endif // _LIBCPP_DEBUG2
4230 template <class _BidirectionalIterator>
4231 inline _LIBCPP_INLINE_VISIBILITY
4233 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
4235 _VSTD::inplace_merge(__first, __middle, __last,
4236 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4241 template <class _Compare, class _InputIterator1, class _InputIterator2>
4243 __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
4244 _InputIterator2 __first2, _InputIterator2 __last2,
4245 typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
4247 typedef typename iterator_traits<_InputIterator1>::value_type value_type;
4248 __destruct_n __d(0);
4249 unique_ptr<value_type, __destruct_n&> __h(__result, __d);
4250 for (; true; ++__result)
4252 if (__first1 == __last1)
4254 for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0))
4255 ::new (__result) value_type(_VSTD::move(*__first2));
4259 if (__first2 == __last2)
4261 for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0))
4262 ::new (__result) value_type(_VSTD::move(*__first1));
4266 if (__comp(*__first2, *__first1))
4268 ::new (__result) value_type(_VSTD::move(*__first2));
4269 __d.__incr((value_type*)0);
4274 ::new (__result) value_type(_VSTD::move(*__first1));
4275 __d.__incr((value_type*)0);
4281 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4283 __merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
4284 _InputIterator2 __first2, _InputIterator2 __last2,
4285 _OutputIterator __result, _Compare __comp)
4287 for (; __first1 != __last1; ++__result)
4289 if (__first2 == __last2)
4291 for (; __first1 != __last1; ++__first1, ++__result)
4292 *__result = _VSTD::move(*__first1);
4295 if (__comp(*__first2, *__first1))
4297 *__result = _VSTD::move(*__first2);
4302 *__result = _VSTD::move(*__first1);
4306 for (; __first2 != __last2; ++__first2, ++__result)
4307 *__result = _VSTD::move(*__first2);
4310 template <class _Compare, class _RandomAccessIterator>
4312 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4313 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4314 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
4316 template <class _Compare, class _RandomAccessIterator>
4318 __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
4319 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4320 typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
4322 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4328 ::new(__first2) value_type(_VSTD::move(*__first1));
4331 __destruct_n __d(0);
4332 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
4333 if (__comp(*--__last1, *__first1))
4335 ::new(__first2) value_type(_VSTD::move(*__last1));
4336 __d.__incr((value_type*)0);
4338 ::new(__first2) value_type(_VSTD::move(*__first1));
4342 ::new(__first2) value_type(_VSTD::move(*__first1));
4343 __d.__incr((value_type*)0);
4345 ::new(__first2) value_type(_VSTD::move(*__last1));
4352 __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
4355 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4356 _RandomAccessIterator __m = __first1 + __l2;
4357 __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
4358 __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
4359 __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
4362 template <class _Tp>
4363 struct __stable_sort_switch
4365 static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
4368 template <class _Compare, class _RandomAccessIterator>
4370 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4371 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4372 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
4374 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4375 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4382 if (__comp(*--__last, *__first))
4383 swap(*__first, *__last);
4386 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4388 __insertion_sort<_Compare>(__first, __last, __comp);
4391 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4392 _RandomAccessIterator __m = __first + __l2;
4393 if (__len <= __buff_size)
4395 __destruct_n __d(0);
4396 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4397 __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4398 __d.__set(__l2, (value_type*)0);
4399 __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
4400 __d.__set(__len, (value_type*)0);
4401 __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4402 // __merge<_Compare>(move_iterator<value_type*>(__buff),
4403 // move_iterator<value_type*>(__buff + __l2),
4404 // move_iterator<_RandomAccessIterator>(__buff + __l2),
4405 // move_iterator<_RandomAccessIterator>(__buff + __len),
4406 // __first, __comp);
4409 __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4410 __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
4411 __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4414 template <class _RandomAccessIterator, class _Compare>
4415 inline _LIBCPP_INLINE_VISIBILITY
4417 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4419 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4420 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4421 difference_type __len = __last - __first;
4422 pair<value_type*, ptrdiff_t> __buf(0, 0);
4423 unique_ptr<value_type, __return_temporary_buffer> __h;
4424 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4426 __buf = _VSTD::get_temporary_buffer<value_type>(__len);
4427 __h.reset(__buf.first);
4429 #ifdef _LIBCPP_DEBUG2
4430 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4431 __debug_less<_Compare> __c(__comp);
4432 __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);
4433 #else // _LIBCPP_DEBUG2
4434 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4435 __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4436 #endif // _LIBCPP_DEBUG2
4439 template <class _RandomAccessIterator>
4440 inline _LIBCPP_INLINE_VISIBILITY
4442 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4444 _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4449 template <class _RandomAccessIterator, class _Compare>
4450 _RandomAccessIterator
4451 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4453 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4454 difference_type __len = __last - __first;
4455 difference_type __p = 0;
4456 difference_type __c = 1;
4457 _RandomAccessIterator __pp = __first;
4460 _RandomAccessIterator __cp = __first + __c;
4461 if (__comp(*__pp, *__cp))
4467 if (__comp(*__pp, *__cp))
4476 template<class _RandomAccessIterator>
4477 inline _LIBCPP_INLINE_VISIBILITY
4478 _RandomAccessIterator
4479 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4481 return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4486 template <class _RandomAccessIterator, class _Compare>
4487 inline _LIBCPP_INLINE_VISIBILITY
4489 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4491 return _VSTD::is_heap_until(__first, __last, __comp) == __last;
4494 template<class _RandomAccessIterator>
4495 inline _LIBCPP_INLINE_VISIBILITY
4497 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4499 return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4504 template <class _Compare, class _RandomAccessIterator>
4506 __push_heap_front(_RandomAccessIterator __first, _RandomAccessIterator, _Compare __comp,
4507 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4509 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4510 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4513 difference_type __p = 0;
4514 _RandomAccessIterator __pp = __first;
4515 difference_type __c = 2;
4516 _RandomAccessIterator __cp = __first + __c;
4517 if (__c == __len || __comp(*__cp, *(__cp - 1)))
4522 if (__comp(*__pp, *__cp))
4524 value_type __t(_VSTD::move(*__pp));
4527 *__pp = _VSTD::move(*__cp);
4530 __c = (__p + 1) * 2;
4533 __cp = __first + __c;
4534 if (__c == __len || __comp(*__cp, *(__cp - 1)))
4539 } while (__comp(__t, *__cp));
4540 *__pp = _VSTD::move(__t);
4545 template <class _Compare, class _RandomAccessIterator>
4547 __push_heap_back(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4548 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4550 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4551 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4554 __len = (__len - 2) / 2;
4555 _RandomAccessIterator __ptr = __first + __len;
4556 if (__comp(*__ptr, *--__last))
4558 value_type __t(_VSTD::move(*__last));
4561 *__last = _VSTD::move(*__ptr);
4565 __len = (__len - 1) / 2;
4566 __ptr = __first + __len;
4567 } while (__comp(*__ptr, __t));
4568 *__last = _VSTD::move(__t);
4573 template <class _RandomAccessIterator, class _Compare>
4574 inline _LIBCPP_INLINE_VISIBILITY
4576 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4578 #ifdef _LIBCPP_DEBUG2
4579 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4580 __debug_less<_Compare> __c(__comp);
4581 __push_heap_back<_Comp_ref>(__first, __last, __c, __last - __first);
4582 #else // _LIBCPP_DEBUG2
4583 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4584 __push_heap_back<_Comp_ref>(__first, __last, __comp, __last - __first);
4585 #endif // _LIBCPP_DEBUG2
4588 template <class _RandomAccessIterator>
4589 inline _LIBCPP_INLINE_VISIBILITY
4591 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4593 _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4598 template <class _Compare, class _RandomAccessIterator>
4599 inline _LIBCPP_INLINE_VISIBILITY
4601 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4602 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4606 swap(*__first, *--__last);
4607 __push_heap_front<_Compare>(__first, __last, __comp, __len-1);
4611 template <class _RandomAccessIterator, class _Compare>
4612 inline _LIBCPP_INLINE_VISIBILITY
4614 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4616 #ifdef _LIBCPP_DEBUG2
4617 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4618 __debug_less<_Compare> __c(__comp);
4619 __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);
4620 #else // _LIBCPP_DEBUG2
4621 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4622 __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
4623 #endif // _LIBCPP_DEBUG2
4626 template <class _RandomAccessIterator>
4627 inline _LIBCPP_INLINE_VISIBILITY
4629 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4631 _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4636 template <class _Compare, class _RandomAccessIterator>
4638 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4640 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4641 difference_type __n = __last - __first;
4646 for (difference_type __i = 1; __i < __n;)
4647 __push_heap_back<_Compare>(__first, ++__last, __comp, ++__i);
4651 template <class _RandomAccessIterator, class _Compare>
4652 inline _LIBCPP_INLINE_VISIBILITY
4654 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4656 #ifdef _LIBCPP_DEBUG2
4657 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4658 __debug_less<_Compare> __c(__comp);
4659 __make_heap<_Comp_ref>(__first, __last, __c);
4660 #else // _LIBCPP_DEBUG2
4661 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4662 __make_heap<_Comp_ref>(__first, __last, __comp);
4663 #endif // _LIBCPP_DEBUG2
4666 template <class _RandomAccessIterator>
4667 inline _LIBCPP_INLINE_VISIBILITY
4669 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4671 _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4676 template <class _Compare, class _RandomAccessIterator>
4678 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4680 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4681 for (difference_type __n = __last - __first; __n > 1; --__last, --__n)
4682 __pop_heap<_Compare>(__first, __last, __comp, __n);
4685 template <class _RandomAccessIterator, class _Compare>
4686 inline _LIBCPP_INLINE_VISIBILITY
4688 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4690 #ifdef _LIBCPP_DEBUG2
4691 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4692 __debug_less<_Compare> __c(__comp);
4693 __sort_heap<_Comp_ref>(__first, __last, __c);
4694 #else // _LIBCPP_DEBUG2
4695 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4696 __sort_heap<_Comp_ref>(__first, __last, __comp);
4697 #endif // _LIBCPP_DEBUG2
4700 template <class _RandomAccessIterator>
4701 inline _LIBCPP_INLINE_VISIBILITY
4703 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4705 _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4710 template <class _Compare, class _RandomAccessIterator>
4712 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
4715 __make_heap<_Compare>(__first, __middle, __comp);
4716 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
4717 for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
4719 if (__comp(*__i, *__first))
4721 swap(*__i, *__first);
4722 __push_heap_front<_Compare>(__first, __middle, __comp, __len);
4725 __sort_heap<_Compare>(__first, __middle, __comp);
4728 template <class _RandomAccessIterator, class _Compare>
4729 inline _LIBCPP_INLINE_VISIBILITY
4731 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
4734 #ifdef _LIBCPP_DEBUG2
4735 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4736 __debug_less<_Compare> __c(__comp);
4737 __partial_sort<_Comp_ref>(__first, __middle, __last, __c);
4738 #else // _LIBCPP_DEBUG2
4739 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4740 __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
4741 #endif // _LIBCPP_DEBUG2
4744 template <class _RandomAccessIterator>
4745 inline _LIBCPP_INLINE_VISIBILITY
4747 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
4749 _VSTD::partial_sort(__first, __middle, __last,
4750 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4753 // partial_sort_copy
4755 template <class _Compare, class _InputIterator, class _RandomAccessIterator>
4756 _RandomAccessIterator
4757 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
4758 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
4760 _RandomAccessIterator __r = __result_first;
4761 if (__r != __result_last)
4763 typename iterator_traits<_RandomAccessIterator>::difference_type __len = 0;
4764 for (; __first != __last && __r != __result_last; ++__first, ++__r, ++__len)
4766 __make_heap<_Compare>(__result_first, __r, __comp);
4767 for (; __first != __last; ++__first)
4768 if (__comp(*__first, *__result_first))
4770 *__result_first = *__first;
4771 __push_heap_front<_Compare>(__result_first, __r, __comp, __len);
4773 __sort_heap<_Compare>(__result_first, __r, __comp);
4778 template <class _InputIterator, class _RandomAccessIterator, class _Compare>
4779 inline _LIBCPP_INLINE_VISIBILITY
4780 _RandomAccessIterator
4781 partial_sort_copy(_InputIterator __first, _InputIterator __last,
4782 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
4784 #ifdef _LIBCPP_DEBUG2
4785 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4786 __debug_less<_Compare> __c(__comp);
4787 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);
4788 #else // _LIBCPP_DEBUG2
4789 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4790 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
4791 #endif // _LIBCPP_DEBUG2
4794 template <class _InputIterator, class _RandomAccessIterator>
4795 inline _LIBCPP_INLINE_VISIBILITY
4796 _RandomAccessIterator
4797 partial_sort_copy(_InputIterator __first, _InputIterator __last,
4798 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
4800 return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
4801 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4806 template <class _Compare, class _RandomAccessIterator>
4808 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
4810 // _Compare is known to be a reference type
4811 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4812 const difference_type __limit = 7;
4816 if (__nth == __last)
4818 difference_type __len = __last - __first;
4825 if (__comp(*--__last, *__first))
4826 swap(*__first, *__last);
4830 _RandomAccessIterator __m = __first;
4831 _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
4835 if (__len <= __limit)
4837 __selection_sort<_Compare>(__first, __last, __comp);
4840 // __len > __limit >= 3
4841 _RandomAccessIterator __m = __first + __len/2;
4842 _RandomAccessIterator __lm1 = __last;
4843 unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
4845 // partition [__first, __m) < *__m and *__m <= [__m, __last)
4846 // (this inhibits tossing elements equivalent to __m around unnecessarily)
4847 _RandomAccessIterator __i = __first;
4848 _RandomAccessIterator __j = __lm1;
4849 // j points beyond range to be tested, *__lm1 is known to be <= *__m
4850 // The search going up is known to be guarded but the search coming down isn't.
4851 // Prime the downward search with a guard.
4852 if (!__comp(*__i, *__m)) // if *__first == *__m
4854 // *__first == *__m, *__first doesn't go in first part
4855 // manually guard downward moving __j against __i
4860 // *__first == *__m, *__m <= all other elements
4861 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
4862 ++__i; // __first + 1
4864 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
4869 return; // [__first, __last) all equivalent elements
4870 if (__comp(*__first, *__i))
4880 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
4885 while (!__comp(*__first, *__i))
4887 while (__comp(*__first, *--__j))
4895 // [__first, __i) == *__first and *__first < [__i, __last)
4896 // The first part is sorted,
4899 // __nth_element the secod part
4900 // __nth_element<_Compare>(__i, __nth, __last, __comp);
4904 if (__comp(*__j, *__m))
4908 break; // found guard for downward moving __j, now use unguarded partition
4913 // j points beyond range to be tested, *__lm1 is known to be <= *__m
4914 // if not yet partitioned...
4917 // known that *(__i - 1) < *__m
4920 // __m still guards upward moving __i
4921 while (__comp(*__i, *__m))
4923 // It is now known that a guard exists for downward moving __j
4924 while (!__comp(*--__j, *__m))
4930 // It is known that __m != __j
4931 // If __m just moved, follow it
4937 // [__first, __i) < *__m and *__m <= [__i, __last)
4938 if (__i != __m && __comp(*__m, *__i))
4943 // [__first, __i) < *__i and *__i <= [__i+1, __last)
4948 // We were given a perfectly partitioned sequence. Coincidence?
4951 // Check for [__first, __i) already sorted
4952 __j = __m = __first;
4953 while (++__j != __i)
4955 if (__comp(*__j, *__m))
4956 // not yet sorted, so sort
4960 // [__first, __i) sorted
4965 // Check for [__i, __last) already sorted
4967 while (++__j != __last)
4969 if (__comp(*__j, *__m))
4970 // not yet sorted, so sort
4974 // [__i, __last) sorted
4979 // __nth_element on range containing __nth
4982 // __nth_element<_Compare>(__first, __nth, __i, __comp);
4987 // __nth_element<_Compare>(__i+1, __nth, __last, __comp);
4993 template <class _RandomAccessIterator, class _Compare>
4994 inline _LIBCPP_INLINE_VISIBILITY
4996 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
4998 #ifdef _LIBCPP_DEBUG2
4999 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5000 __debug_less<_Compare> __c(__comp);
5001 __nth_element<_Comp_ref>(__first, __nth, __last, __c);
5002 #else // _LIBCPP_DEBUG2
5003 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5004 __nth_element<_Comp_ref>(__first, __nth, __last, __comp);
5005 #endif // _LIBCPP_DEBUG2
5008 template <class _RandomAccessIterator>
5009 inline _LIBCPP_INLINE_VISIBILITY
5011 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
5013 _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5018 template <class _Compare, class _InputIterator1, class _InputIterator2>
5020 __includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5023 for (; __first2 != __last2; ++__first1)
5025 if (__first1 == __last1 || __comp(*__first2, *__first1))
5027 if (!__comp(*__first1, *__first2))
5033 template <class _InputIterator1, class _InputIterator2, class _Compare>
5034 inline _LIBCPP_INLINE_VISIBILITY
5036 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5039 #ifdef _LIBCPP_DEBUG2
5040 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5041 __debug_less<_Compare> __c(__comp);
5042 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5043 #else // _LIBCPP_DEBUG2
5044 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5045 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5046 #endif // _LIBCPP_DEBUG2
5049 template <class _InputIterator1, class _InputIterator2>
5050 inline _LIBCPP_INLINE_VISIBILITY
5052 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
5054 return _VSTD::includes(__first1, __last1, __first2, __last2,
5055 __less<typename iterator_traits<_InputIterator1>::value_type,
5056 typename iterator_traits<_InputIterator2>::value_type>());
5061 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5063 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5064 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5066 for (; __first1 != __last1; ++__result)
5068 if (__first2 == __last2)
5069 return _VSTD::copy(__first1, __last1, __result);
5070 if (__comp(*__first2, *__first1))
5072 *__result = *__first2;
5077 *__result = *__first1;
5078 if (!__comp(*__first1, *__first2))
5083 return _VSTD::copy(__first2, __last2, __result);
5086 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5087 inline _LIBCPP_INLINE_VISIBILITY
5089 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5090 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5092 #ifdef _LIBCPP_DEBUG2
5093 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5094 __debug_less<_Compare> __c(__comp);
5095 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5096 #else // _LIBCPP_DEBUG2
5097 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5098 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5099 #endif // _LIBCPP_DEBUG2
5102 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5103 inline _LIBCPP_INLINE_VISIBILITY
5105 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5106 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5108 return _VSTD::set_union(__first1, __last1, __first2, __last2, __result,
5109 __less<typename iterator_traits<_InputIterator1>::value_type,
5110 typename iterator_traits<_InputIterator2>::value_type>());
5115 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5117 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5118 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5120 while (__first1 != __last1 && __first2 != __last2)
5122 if (__comp(*__first1, *__first2))
5126 if (!__comp(*__first2, *__first1))
5128 *__result = *__first1;
5138 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5139 inline _LIBCPP_INLINE_VISIBILITY
5141 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5142 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5144 #ifdef _LIBCPP_DEBUG2
5145 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5146 __debug_less<_Compare> __c(__comp);
5147 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5148 #else // _LIBCPP_DEBUG2
5149 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5150 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5151 #endif // _LIBCPP_DEBUG2
5154 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5155 inline _LIBCPP_INLINE_VISIBILITY
5157 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5158 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5160 return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result,
5161 __less<typename iterator_traits<_InputIterator1>::value_type,
5162 typename iterator_traits<_InputIterator2>::value_type>());
5167 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5169 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5170 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5172 while (__first1 != __last1)
5174 if (__first2 == __last2)
5175 return _VSTD::copy(__first1, __last1, __result);
5176 if (__comp(*__first1, *__first2))
5178 *__result = *__first1;
5184 if (!__comp(*__first2, *__first1))
5192 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5193 inline _LIBCPP_INLINE_VISIBILITY
5195 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5196 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5198 #ifdef _LIBCPP_DEBUG2
5199 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5200 __debug_less<_Compare> __c(__comp);
5201 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5202 #else // _LIBCPP_DEBUG2
5203 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5204 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5205 #endif // _LIBCPP_DEBUG2
5208 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5209 inline _LIBCPP_INLINE_VISIBILITY
5211 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5212 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5214 return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result,
5215 __less<typename iterator_traits<_InputIterator1>::value_type,
5216 typename iterator_traits<_InputIterator2>::value_type>());
5219 // set_symmetric_difference
5221 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5223 __set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5224 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5226 while (__first1 != __last1)
5228 if (__first2 == __last2)
5229 return _VSTD::copy(__first1, __last1, __result);
5230 if (__comp(*__first1, *__first2))
5232 *__result = *__first1;
5238 if (__comp(*__first2, *__first1))
5240 *__result = *__first2;
5248 return _VSTD::copy(__first2, __last2, __result);
5251 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5252 inline _LIBCPP_INLINE_VISIBILITY
5254 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5255 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5257 #ifdef _LIBCPP_DEBUG2
5258 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5259 __debug_less<_Compare> __c(__comp);
5260 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5261 #else // _LIBCPP_DEBUG2
5262 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5263 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5264 #endif // _LIBCPP_DEBUG2
5267 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5268 inline _LIBCPP_INLINE_VISIBILITY
5270 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5271 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5273 return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
5274 __less<typename iterator_traits<_InputIterator1>::value_type,
5275 typename iterator_traits<_InputIterator2>::value_type>());
5278 // lexicographical_compare
5280 template <class _Compare, class _InputIterator1, class _InputIterator2>
5282 __lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5283 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5285 for (; __first2 != __last2; ++__first1, ++__first2)
5287 if (__first1 == __last1 || __comp(*__first1, *__first2))
5289 if (__comp(*__first2, *__first1))
5295 template <class _InputIterator1, class _InputIterator2, class _Compare>
5296 inline _LIBCPP_INLINE_VISIBILITY
5298 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5299 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5301 #ifdef _LIBCPP_DEBUG2
5302 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5303 __debug_less<_Compare> __c(__comp);
5304 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5305 #else // _LIBCPP_DEBUG2
5306 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5307 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5308 #endif // _LIBCPP_DEBUG2
5311 template <class _InputIterator1, class _InputIterator2>
5312 inline _LIBCPP_INLINE_VISIBILITY
5314 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5315 _InputIterator2 __first2, _InputIterator2 __last2)
5317 return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,
5318 __less<typename iterator_traits<_InputIterator1>::value_type,
5319 typename iterator_traits<_InputIterator2>::value_type>());
5324 template <class _Compare, class _BidirectionalIterator>
5326 __next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5328 _BidirectionalIterator __i = __last;
5329 if (__first == __last || __first == --__i)
5333 _BidirectionalIterator __ip1 = __i;
5334 if (__comp(*--__i, *__ip1))
5336 _BidirectionalIterator __j = __last;
5337 while (!__comp(*__i, *--__j))
5340 _VSTD::reverse(__ip1, __last);
5345 _VSTD::reverse(__first, __last);
5351 template <class _BidirectionalIterator, class _Compare>
5352 inline _LIBCPP_INLINE_VISIBILITY
5354 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5356 #ifdef _LIBCPP_DEBUG2
5357 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5358 __debug_less<_Compare> __c(__comp);
5359 return __next_permutation<_Comp_ref>(__first, __last, __c);
5360 #else // _LIBCPP_DEBUG2
5361 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5362 return __next_permutation<_Comp_ref>(__first, __last, __comp);
5363 #endif // _LIBCPP_DEBUG2
5366 template <class _BidirectionalIterator>
5367 inline _LIBCPP_INLINE_VISIBILITY
5369 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5371 return _VSTD::next_permutation(__first, __last,
5372 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5377 template <class _Compare, class _BidirectionalIterator>
5379 __prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5381 _BidirectionalIterator __i = __last;
5382 if (__first == __last || __first == --__i)
5386 _BidirectionalIterator __ip1 = __i;
5387 if (__comp(*__ip1, *--__i))
5389 _BidirectionalIterator __j = __last;
5390 while (!__comp(*--__j, *__i))
5393 _VSTD::reverse(__ip1, __last);
5398 _VSTD::reverse(__first, __last);
5404 template <class _BidirectionalIterator, class _Compare>
5405 inline _LIBCPP_INLINE_VISIBILITY
5407 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5409 #ifdef _LIBCPP_DEBUG2
5410 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5411 __debug_less<_Compare> __c(__comp);
5412 return __prev_permutation<_Comp_ref>(__first, __last, __c);
5413 #else // _LIBCPP_DEBUG2
5414 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5415 return __prev_permutation<_Comp_ref>(__first, __last, __comp);
5416 #endif // _LIBCPP_DEBUG2
5419 template <class _BidirectionalIterator>
5420 inline _LIBCPP_INLINE_VISIBILITY
5422 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5424 return _VSTD::prev_permutation(__first, __last,
5425 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5428 template <class _Tp>
5429 inline _LIBCPP_INLINE_VISIBILITY
5432 is_integral<_Tp>::value,
5435 __rotate_left(_Tp __t, _Tp __n = 1)
5437 const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1);
5439 return static_cast<_Tp>((__t << __n) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> (__bits - __n)));
5442 template <class _Tp>
5443 inline _LIBCPP_INLINE_VISIBILITY
5446 is_integral<_Tp>::value,
5449 __rotate_right(_Tp __t, _Tp __n = 1)
5451 const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1);
5453 return static_cast<_Tp>((__t << (__bits - __n)) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> __n));
5456 _LIBCPP_END_NAMESPACE_STD
5458 #endif // _LIBCPP_ALGORITHM