2 //===-------------------------- algorithm ---------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_ALGORITHM
12 #define _LIBCPP_ALGORITHM
17 #include <initializer_list>
22 template <class InputIterator, class Predicate>
24 all_of(InputIterator first, InputIterator last, Predicate pred);
26 template <class InputIterator, class Predicate>
28 any_of(InputIterator first, InputIterator last, Predicate pred);
30 template <class InputIterator, class Predicate>
32 none_of(InputIterator first, InputIterator last, Predicate pred);
34 template <class InputIterator, class Function>
36 for_each(InputIterator first, InputIterator last, Function f);
38 template <class InputIterator, class T>
40 find(InputIterator first, InputIterator last, const T& value);
42 template <class InputIterator, class Predicate>
44 find_if(InputIterator first, InputIterator last, Predicate pred);
46 template<class InputIterator, class Predicate>
48 find_if_not(InputIterator first, InputIterator last, Predicate pred);
50 template <class ForwardIterator1, class ForwardIterator2>
52 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
53 ForwardIterator2 first2, ForwardIterator2 last2);
55 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
57 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
58 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
60 template <class ForwardIterator1, class ForwardIterator2>
62 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
63 ForwardIterator2 first2, ForwardIterator2 last2);
65 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
67 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
68 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
70 template <class ForwardIterator>
72 adjacent_find(ForwardIterator first, ForwardIterator last);
74 template <class ForwardIterator, class BinaryPredicate>
76 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
78 template <class InputIterator, class T>
79 typename iterator_traits<InputIterator>::difference_type
80 count(InputIterator first, InputIterator last, const T& value);
82 template <class InputIterator, class Predicate>
83 typename iterator_traits<InputIterator>::difference_type
84 count_if(InputIterator first, InputIterator last, Predicate pred);
86 template <class InputIterator1, class InputIterator2>
87 pair<InputIterator1, InputIterator2>
88 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
90 template <class InputIterator1, class InputIterator2>
91 pair<InputIterator1, InputIterator2>
92 mismatch(InputIterator1 first1, InputIterator1 last1,
93 InputIterator2 first2, InputIterator2 last2); // **C++14**
95 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
96 pair<InputIterator1, InputIterator2>
97 mismatch(InputIterator1 first1, InputIterator1 last1,
98 InputIterator2 first2, BinaryPredicate pred);
100 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
101 pair<InputIterator1, InputIterator2>
102 mismatch(InputIterator1 first1, InputIterator1 last1,
103 InputIterator2 first2, InputIterator2 last2,
104 BinaryPredicate pred); // **C++14**
106 template <class InputIterator1, class InputIterator2>
108 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
110 template <class InputIterator1, class InputIterator2>
112 equal(InputIterator1 first1, InputIterator1 last1,
113 InputIterator2 first2, InputIterator2 last2); // **C++14**
115 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
117 equal(InputIterator1 first1, InputIterator1 last1,
118 InputIterator2 first2, BinaryPredicate pred);
120 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
122 equal(InputIterator1 first1, InputIterator1 last1,
123 InputIterator2 first2, InputIterator2 last2,
124 BinaryPredicate pred); // **C++14**
126 template<class ForwardIterator1, class ForwardIterator2>
128 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
129 ForwardIterator2 first2);
131 template<class ForwardIterator1, class ForwardIterator2>
133 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
134 ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**
136 template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
138 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
139 ForwardIterator2 first2, BinaryPredicate pred);
141 template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
143 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
144 ForwardIterator2 first2, ForwardIterator2 last2,
145 BinaryPredicate pred); // **C++14**
147 template <class ForwardIterator1, class ForwardIterator2>
149 search(ForwardIterator1 first1, ForwardIterator1 last1,
150 ForwardIterator2 first2, ForwardIterator2 last2);
152 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
154 search(ForwardIterator1 first1, ForwardIterator1 last1,
155 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
157 template <class ForwardIterator, class Size, class T>
159 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
161 template <class ForwardIterator, class Size, class T, class BinaryPredicate>
163 search_n(ForwardIterator first, ForwardIterator last,
164 Size count, const T& value, BinaryPredicate pred);
166 template <class InputIterator, class OutputIterator>
168 copy(InputIterator first, InputIterator last, OutputIterator result);
170 template<class InputIterator, class OutputIterator, class Predicate>
172 copy_if(InputIterator first, InputIterator last,
173 OutputIterator result, Predicate pred);
175 template<class InputIterator, class Size, class OutputIterator>
177 copy_n(InputIterator first, Size n, OutputIterator result);
179 template <class BidirectionalIterator1, class BidirectionalIterator2>
180 BidirectionalIterator2
181 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
182 BidirectionalIterator2 result);
184 template <class ForwardIterator1, class ForwardIterator2>
186 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
188 template <class ForwardIterator1, class ForwardIterator2>
190 iter_swap(ForwardIterator1 a, ForwardIterator2 b);
192 template <class InputIterator, class OutputIterator, class UnaryOperation>
194 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
196 template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
198 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
199 OutputIterator result, BinaryOperation binary_op);
201 template <class ForwardIterator, class T>
203 replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
205 template <class ForwardIterator, class Predicate, class T>
207 replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
209 template <class InputIterator, class OutputIterator, class T>
211 replace_copy(InputIterator first, InputIterator last, OutputIterator result,
212 const T& old_value, const T& new_value);
214 template <class InputIterator, class OutputIterator, class Predicate, class T>
216 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
218 template <class ForwardIterator, class T>
220 fill(ForwardIterator first, ForwardIterator last, const T& value);
222 template <class OutputIterator, class Size, class T>
224 fill_n(OutputIterator first, Size n, const T& value);
226 template <class ForwardIterator, class Generator>
228 generate(ForwardIterator first, ForwardIterator last, Generator gen);
230 template <class OutputIterator, class Size, class Generator>
232 generate_n(OutputIterator first, Size n, Generator gen);
234 template <class ForwardIterator, class T>
236 remove(ForwardIterator first, ForwardIterator last, const T& value);
238 template <class ForwardIterator, class Predicate>
240 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
242 template <class InputIterator, class OutputIterator, class T>
244 remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
246 template <class InputIterator, class OutputIterator, class Predicate>
248 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
250 template <class ForwardIterator>
252 unique(ForwardIterator first, ForwardIterator last);
254 template <class ForwardIterator, class BinaryPredicate>
256 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
258 template <class InputIterator, class OutputIterator>
260 unique_copy(InputIterator first, InputIterator last, OutputIterator result);
262 template <class InputIterator, class OutputIterator, class BinaryPredicate>
264 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
266 template <class BidirectionalIterator>
268 reverse(BidirectionalIterator first, BidirectionalIterator last);
270 template <class BidirectionalIterator, class OutputIterator>
272 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
274 template <class ForwardIterator>
276 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
278 template <class ForwardIterator, class OutputIterator>
280 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
282 template <class RandomAccessIterator>
284 random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14
286 template <class RandomAccessIterator, class RandomNumberGenerator>
288 random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
289 RandomNumberGenerator& rand); // deprecated in C++14
291 template<class PopulationIterator, class SampleIterator,
292 class Distance, class UniformRandomBitGenerator>
293 SampleIterator sample(PopulationIterator first, PopulationIterator last,
294 SampleIterator out, Distance n,
295 UniformRandomBitGenerator&& g); // C++17
297 template<class RandomAccessIterator, class UniformRandomNumberGenerator>
298 void shuffle(RandomAccessIterator first, RandomAccessIterator last,
299 UniformRandomNumberGenerator&& g);
301 template <class InputIterator, class Predicate>
303 is_partitioned(InputIterator first, InputIterator last, Predicate pred);
305 template <class ForwardIterator, class Predicate>
307 partition(ForwardIterator first, ForwardIterator last, Predicate pred);
309 template <class InputIterator, class OutputIterator1,
310 class OutputIterator2, class Predicate>
311 pair<OutputIterator1, OutputIterator2>
312 partition_copy(InputIterator first, InputIterator last,
313 OutputIterator1 out_true, OutputIterator2 out_false,
316 template <class ForwardIterator, class Predicate>
318 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
320 template<class ForwardIterator, class Predicate>
322 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
324 template <class ForwardIterator>
326 is_sorted(ForwardIterator first, ForwardIterator last);
328 template <class ForwardIterator, class Compare>
330 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
332 template<class ForwardIterator>
334 is_sorted_until(ForwardIterator first, ForwardIterator last);
336 template <class ForwardIterator, class Compare>
338 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
340 template <class RandomAccessIterator>
342 sort(RandomAccessIterator first, RandomAccessIterator last);
344 template <class RandomAccessIterator, class Compare>
346 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
348 template <class RandomAccessIterator>
350 stable_sort(RandomAccessIterator first, RandomAccessIterator last);
352 template <class RandomAccessIterator, class Compare>
354 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
356 template <class RandomAccessIterator>
358 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
360 template <class RandomAccessIterator, class Compare>
362 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
364 template <class InputIterator, class RandomAccessIterator>
366 partial_sort_copy(InputIterator first, InputIterator last,
367 RandomAccessIterator result_first, RandomAccessIterator result_last);
369 template <class InputIterator, class RandomAccessIterator, class Compare>
371 partial_sort_copy(InputIterator first, InputIterator last,
372 RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
374 template <class RandomAccessIterator>
376 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
378 template <class RandomAccessIterator, class Compare>
380 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
382 template <class ForwardIterator, class T>
384 lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
386 template <class ForwardIterator, class T, class Compare>
388 lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
390 template <class ForwardIterator, class T>
392 upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
394 template <class ForwardIterator, class T, class Compare>
396 upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
398 template <class ForwardIterator, class T>
399 pair<ForwardIterator, ForwardIterator>
400 equal_range(ForwardIterator first, ForwardIterator last, const T& value);
402 template <class ForwardIterator, class T, class Compare>
403 pair<ForwardIterator, ForwardIterator>
404 equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
406 template <class ForwardIterator, class T>
408 binary_search(ForwardIterator first, ForwardIterator last, const T& value);
410 template <class ForwardIterator, class T, class Compare>
412 binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
414 template <class InputIterator1, class InputIterator2, class OutputIterator>
416 merge(InputIterator1 first1, InputIterator1 last1,
417 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
419 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
421 merge(InputIterator1 first1, InputIterator1 last1,
422 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
424 template <class BidirectionalIterator>
426 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
428 template <class BidirectionalIterator, class Compare>
430 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
432 template <class InputIterator1, class InputIterator2>
434 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
436 template <class InputIterator1, class InputIterator2, class Compare>
438 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
440 template <class InputIterator1, class InputIterator2, class OutputIterator>
442 set_union(InputIterator1 first1, InputIterator1 last1,
443 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
445 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
447 set_union(InputIterator1 first1, InputIterator1 last1,
448 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
450 template <class InputIterator1, class InputIterator2, class OutputIterator>
452 set_intersection(InputIterator1 first1, InputIterator1 last1,
453 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
455 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
457 set_intersection(InputIterator1 first1, InputIterator1 last1,
458 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
460 template <class InputIterator1, class InputIterator2, class OutputIterator>
462 set_difference(InputIterator1 first1, InputIterator1 last1,
463 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
465 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
467 set_difference(InputIterator1 first1, InputIterator1 last1,
468 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
470 template <class InputIterator1, class InputIterator2, class OutputIterator>
472 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
473 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
475 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
477 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
478 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
480 template <class RandomAccessIterator>
482 push_heap(RandomAccessIterator first, RandomAccessIterator last);
484 template <class RandomAccessIterator, class Compare>
486 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
488 template <class RandomAccessIterator>
490 pop_heap(RandomAccessIterator first, RandomAccessIterator last);
492 template <class RandomAccessIterator, class Compare>
494 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
496 template <class RandomAccessIterator>
498 make_heap(RandomAccessIterator first, RandomAccessIterator last);
500 template <class RandomAccessIterator, class Compare>
502 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
504 template <class RandomAccessIterator>
506 sort_heap(RandomAccessIterator first, RandomAccessIterator last);
508 template <class RandomAccessIterator, class Compare>
510 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
512 template <class RandomAccessIterator>
514 is_heap(RandomAccessIterator first, RandomAccessiterator last);
516 template <class RandomAccessIterator, class Compare>
518 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
520 template <class RandomAccessIterator>
522 is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
524 template <class RandomAccessIterator, class Compare>
526 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
528 template <class ForwardIterator>
530 min_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14
532 template <class ForwardIterator, class Compare>
534 min_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14
538 min(const T& a, const T& b); // constexpr in C++14
540 template <class T, class Compare>
542 min(const T& a, const T& b, Compare comp); // constexpr in C++14
546 min(initializer_list<T> t); // constexpr in C++14
548 template<class T, class Compare>
550 min(initializer_list<T> t, Compare comp); // constexpr in C++14
553 constexpr const T& clamp( const T& v, const T& lo, const T& hi ); // C++17
555 template<class T, class Compare>
556 constexpr const T& clamp( const T& v, const T& lo, const T& hi, Compare comp ); // C++17
558 template <class ForwardIterator>
560 max_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14
562 template <class ForwardIterator, class Compare>
564 max_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14
568 max(const T& a, const T& b); // constexpr in C++14
570 template <class T, class Compare>
572 max(const T& a, const T& b, Compare comp); // constexpr in C++14
576 max(initializer_list<T> t); // constexpr in C++14
578 template<class T, class Compare>
580 max(initializer_list<T> t, Compare comp); // constexpr in C++14
582 template<class ForwardIterator>
583 pair<ForwardIterator, ForwardIterator>
584 minmax_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14
586 template<class ForwardIterator, class Compare>
587 pair<ForwardIterator, ForwardIterator>
588 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14
591 pair<const T&, const T&>
592 minmax(const T& a, const T& b); // constexpr in C++14
594 template<class T, class Compare>
595 pair<const T&, const T&>
596 minmax(const T& a, const T& b, Compare comp); // constexpr in C++14
600 minmax(initializer_list<T> t); // constexpr in C++14
602 template<class T, class Compare>
604 minmax(initializer_list<T> t, Compare comp); // constexpr in C++14
606 template <class InputIterator1, class InputIterator2>
608 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
610 template <class InputIterator1, class InputIterator2, class Compare>
612 lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
613 InputIterator2 first2, InputIterator2 last2, Compare comp);
615 template <class BidirectionalIterator>
617 next_permutation(BidirectionalIterator first, BidirectionalIterator last);
619 template <class BidirectionalIterator, class Compare>
621 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
623 template <class BidirectionalIterator>
625 prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
627 template <class BidirectionalIterator, class Compare>
629 prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
636 #include <initializer_list>
637 #include <type_traits>
639 #include <utility> // needed to provide swap_ranges.
644 #if defined(__IBMCPP__)
645 #include "support/ibm/support.h"
647 #if defined(_LIBCPP_MSVCRT) || defined(__MINGW32__)
648 #include "support/win32/support.h"
651 #include <__undef_min_max>
655 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
656 #pragma GCC system_header
659 _LIBCPP_BEGIN_NAMESPACE_STD
661 // I'd like to replace these with _VSTD::equal_to<void>, but can't because:
662 // * That only works with C++14 and later, and
663 // * We haven't included <functional> here.
664 template <class _T1, class _T2 = _T1>
667 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
668 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;}
669 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;}
670 _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;}
674 struct __equal_to<_T1, _T1>
676 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
677 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
681 struct __equal_to<const _T1, _T1>
683 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
684 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
688 struct __equal_to<_T1, const _T1>
690 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
691 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
694 template <class _T1, class _T2 = _T1>
697 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
698 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
700 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
701 bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;}
703 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
704 bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;}
706 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
707 bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;}
711 struct __less<_T1, _T1>
713 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
714 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
718 struct __less<const _T1, _T1>
720 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
721 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
725 struct __less<_T1, const _T1>
727 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
728 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
731 template <class _Predicate>
737 _LIBCPP_INLINE_VISIBILITY __negate() {}
739 _LIBCPP_INLINE_VISIBILITY
740 explicit __negate(_Predicate __p) : __p_(__p) {}
743 _LIBCPP_INLINE_VISIBILITY
744 bool operator()(const _T1& __x) {return !__p_(__x);}
746 template <class _T1, class _T2>
747 _LIBCPP_INLINE_VISIBILITY
748 bool operator()(const _T1& __x, const _T2& __y) {return !__p_(__x, __y);}
753 template <class _Compare>
757 __debug_less(_Compare& __c) : __comp_(__c) {}
759 template <class _Tp, class _Up>
760 bool operator()(const _Tp& __x, const _Up& __y)
762 bool __r = __comp_(__x, __y);
764 __do_compare_assert(0, __y, __x);
768 template <class _LHS, class _RHS>
769 inline _LIBCPP_INLINE_VISIBILITY
770 decltype((void)_VSTD::declval<_Compare&>()(
771 _VSTD::declval<_LHS const&>(), _VSTD::declval<_RHS const&>()))
772 __do_compare_assert(int, _LHS const& __l, _RHS const& __r) {
773 _LIBCPP_ASSERT(!__comp_(__l, __r),
774 "Comparator does not induce a strict weak ordering");
777 template <class _LHS, class _RHS>
778 inline _LIBCPP_INLINE_VISIBILITY
779 void __do_compare_assert(long, _LHS const&, _RHS const&) {}
782 #endif // _LIBCPP_DEBUG
784 // Precondition: __x != 0
785 inline _LIBCPP_INLINE_VISIBILITY
789 return static_cast<unsigned>(__builtin_ctz(__x));
792 inline _LIBCPP_INLINE_VISIBILITY
794 __ctz(unsigned long __x)
796 return static_cast<unsigned long>(__builtin_ctzl(__x));
799 inline _LIBCPP_INLINE_VISIBILITY
801 __ctz(unsigned long long __x)
803 return static_cast<unsigned long long>(__builtin_ctzll(__x));
806 // Precondition: __x != 0
807 inline _LIBCPP_INLINE_VISIBILITY
811 return static_cast<unsigned>(__builtin_clz(__x));
814 inline _LIBCPP_INLINE_VISIBILITY
816 __clz(unsigned long __x)
818 return static_cast<unsigned long>(__builtin_clzl (__x));
821 inline _LIBCPP_INLINE_VISIBILITY
823 __clz(unsigned long long __x)
825 return static_cast<unsigned long long>(__builtin_clzll(__x));
828 inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned __x) {return __builtin_popcount (__x);}
829 inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long __x) {return __builtin_popcountl (__x);}
830 inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long long __x) {return __builtin_popcountll(__x);}
834 template <class _InputIterator, class _Predicate>
835 inline _LIBCPP_INLINE_VISIBILITY
837 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
839 for (; __first != __last; ++__first)
840 if (!__pred(*__first))
847 template <class _InputIterator, class _Predicate>
848 inline _LIBCPP_INLINE_VISIBILITY
850 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
852 for (; __first != __last; ++__first)
853 if (__pred(*__first))
860 template <class _InputIterator, class _Predicate>
861 inline _LIBCPP_INLINE_VISIBILITY
863 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
865 for (; __first != __last; ++__first)
866 if (__pred(*__first))
873 template <class _InputIterator, class _Function>
874 inline _LIBCPP_INLINE_VISIBILITY
876 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
878 for (; __first != __last; ++__first)
885 template <class _InputIterator, class _Tp>
886 inline _LIBCPP_INLINE_VISIBILITY
888 find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
890 for (; __first != __last; ++__first)
891 if (*__first == __value_)
898 template <class _InputIterator, class _Predicate>
899 inline _LIBCPP_INLINE_VISIBILITY
901 find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
903 for (; __first != __last; ++__first)
904 if (__pred(*__first))
911 template<class _InputIterator, class _Predicate>
912 inline _LIBCPP_INLINE_VISIBILITY
914 find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
916 for (; __first != __last; ++__first)
917 if (!__pred(*__first))
924 template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
926 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
927 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
928 forward_iterator_tag, forward_iterator_tag)
930 // modeled after search algorithm
931 _ForwardIterator1 __r = __last1; // __last1 is the "default" answer
932 if (__first2 == __last2)
938 if (__first1 == __last1) // if source exhausted return last correct answer
939 return __r; // (or __last1 if never found)
940 if (__pred(*__first1, *__first2))
944 // *__first1 matches *__first2, now match elements after here
945 _ForwardIterator1 __m1 = __first1;
946 _ForwardIterator2 __m2 = __first2;
949 if (++__m2 == __last2)
950 { // Pattern exhaused, record answer and search for another one
955 if (++__m1 == __last1) // Source exhausted, return last answer
957 if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first
961 } // else there is a match, check next elements
966 template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2>
967 _BidirectionalIterator1
968 __find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,
969 _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred,
970 bidirectional_iterator_tag, bidirectional_iterator_tag)
972 // modeled after search algorithm (in reverse)
973 if (__first2 == __last2)
974 return __last1; // Everything matches an empty sequence
975 _BidirectionalIterator1 __l1 = __last1;
976 _BidirectionalIterator2 __l2 = __last2;
980 // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks
983 if (__first1 == __l1) // return __last1 if no element matches *__first2
985 if (__pred(*--__l1, *__l2))
988 // *__l1 matches *__l2, now match elements before here
989 _BidirectionalIterator1 __m1 = __l1;
990 _BidirectionalIterator2 __m2 = __l2;
993 if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern)
995 if (__m1 == __first1) // Otherwise if source exhaused, pattern not found
997 if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1
1000 } // else there is a match, check next elements
1005 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1006 _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1
1007 __find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1008 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1009 random_access_iterator_tag, random_access_iterator_tag)
1011 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern
1012 typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;
1015 typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;
1016 if (__len1 < __len2)
1018 const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here
1019 _RandomAccessIterator1 __l1 = __last1;
1020 _RandomAccessIterator2 __l2 = __last2;
1028 if (__pred(*--__l1, *__l2))
1031 _RandomAccessIterator1 __m1 = __l1;
1032 _RandomAccessIterator2 __m2 = __l2;
1035 if (__m2 == __first2)
1037 // no need to check range on __m1 because __s guarantees we have enough source
1038 if (!__pred(*--__m1, *--__m2))
1046 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1047 inline _LIBCPP_INLINE_VISIBILITY
1049 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1050 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1052 return _VSTD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type>
1053 (__first1, __last1, __first2, __last2, __pred,
1054 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1055 typename iterator_traits<_ForwardIterator2>::iterator_category());
1058 template <class _ForwardIterator1, class _ForwardIterator2>
1059 inline _LIBCPP_INLINE_VISIBILITY
1061 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1062 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1064 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1065 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1066 return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1071 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1072 _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator1
1073 __find_first_of_ce(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1074 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1076 for (; __first1 != __last1; ++__first1)
1077 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1078 if (__pred(*__first1, *__j))
1084 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1085 inline _LIBCPP_INLINE_VISIBILITY
1087 find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1088 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1090 return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred);
1093 template <class _ForwardIterator1, class _ForwardIterator2>
1094 inline _LIBCPP_INLINE_VISIBILITY
1096 find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1097 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1099 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1100 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1101 return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1106 template <class _ForwardIterator, class _BinaryPredicate>
1107 inline _LIBCPP_INLINE_VISIBILITY
1109 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
1111 if (__first != __last)
1113 _ForwardIterator __i = __first;
1114 while (++__i != __last)
1116 if (__pred(*__first, *__i))
1124 template <class _ForwardIterator>
1125 inline _LIBCPP_INLINE_VISIBILITY
1127 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
1129 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1130 return _VSTD::adjacent_find(__first, __last, __equal_to<__v>());
1135 template <class _InputIterator, class _Tp>
1136 inline _LIBCPP_INLINE_VISIBILITY
1137 typename iterator_traits<_InputIterator>::difference_type
1138 count(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
1140 typename iterator_traits<_InputIterator>::difference_type __r(0);
1141 for (; __first != __last; ++__first)
1142 if (*__first == __value_)
1149 template <class _InputIterator, class _Predicate>
1150 inline _LIBCPP_INLINE_VISIBILITY
1151 typename iterator_traits<_InputIterator>::difference_type
1152 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
1154 typename iterator_traits<_InputIterator>::difference_type __r(0);
1155 for (; __first != __last; ++__first)
1156 if (__pred(*__first))
1163 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1164 inline _LIBCPP_INLINE_VISIBILITY
1165 pair<_InputIterator1, _InputIterator2>
1166 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1167 _InputIterator2 __first2, _BinaryPredicate __pred)
1169 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1170 if (!__pred(*__first1, *__first2))
1172 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1175 template <class _InputIterator1, class _InputIterator2>
1176 inline _LIBCPP_INLINE_VISIBILITY
1177 pair<_InputIterator1, _InputIterator2>
1178 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1180 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1181 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1182 return _VSTD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1185 #if _LIBCPP_STD_VER > 11
1186 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1187 inline _LIBCPP_INLINE_VISIBILITY
1188 pair<_InputIterator1, _InputIterator2>
1189 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1190 _InputIterator2 __first2, _InputIterator2 __last2,
1191 _BinaryPredicate __pred)
1193 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1194 if (!__pred(*__first1, *__first2))
1196 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1199 template <class _InputIterator1, class _InputIterator2>
1200 inline _LIBCPP_INLINE_VISIBILITY
1201 pair<_InputIterator1, _InputIterator2>
1202 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1203 _InputIterator2 __first2, _InputIterator2 __last2)
1205 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1206 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1207 return _VSTD::mismatch(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1213 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1214 inline _LIBCPP_INLINE_VISIBILITY
1216 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred)
1218 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1219 if (!__pred(*__first1, *__first2))
1224 template <class _InputIterator1, class _InputIterator2>
1225 inline _LIBCPP_INLINE_VISIBILITY
1227 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1229 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1230 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1231 return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1234 #if _LIBCPP_STD_VER > 11
1235 template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2>
1236 inline _LIBCPP_INLINE_VISIBILITY
1238 __equal(_InputIterator1 __first1, _InputIterator1 __last1,
1239 _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred,
1240 input_iterator_tag, input_iterator_tag )
1242 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1243 if (!__pred(*__first1, *__first2))
1245 return __first1 == __last1 && __first2 == __last2;
1248 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1249 inline _LIBCPP_INLINE_VISIBILITY
1251 __equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1252 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1253 random_access_iterator_tag, random_access_iterator_tag )
1255 if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
1257 return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2,
1258 typename add_lvalue_reference<_BinaryPredicate>::type>
1259 (__first1, __last1, __first2, __pred );
1262 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1263 inline _LIBCPP_INLINE_VISIBILITY
1265 equal(_InputIterator1 __first1, _InputIterator1 __last1,
1266 _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred )
1268 return _VSTD::__equal<typename add_lvalue_reference<_BinaryPredicate>::type>
1269 (__first1, __last1, __first2, __last2, __pred,
1270 typename iterator_traits<_InputIterator1>::iterator_category(),
1271 typename iterator_traits<_InputIterator2>::iterator_category());
1274 template <class _InputIterator1, class _InputIterator2>
1275 inline _LIBCPP_INLINE_VISIBILITY
1277 equal(_InputIterator1 __first1, _InputIterator1 __last1,
1278 _InputIterator2 __first2, _InputIterator2 __last2)
1280 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1281 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1282 return _VSTD::__equal(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(),
1283 typename iterator_traits<_InputIterator1>::iterator_category(),
1284 typename iterator_traits<_InputIterator2>::iterator_category());
1290 template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1292 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1293 _ForwardIterator2 __first2, _BinaryPredicate __pred)
1295 // shorten sequences as much as possible by lopping of any equal parts
1296 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1297 if (!__pred(*__first1, *__first2))
1301 // __first1 != __last1 && *__first1 != *__first2
1302 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1303 _D1 __l1 = _VSTD::distance(__first1, __last1);
1306 _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1);
1307 // For each element in [f1, l1) see if there are the same number of
1308 // equal elements in [f2, l2)
1309 for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
1311 // Have we already counted the number of *__i in [f1, l1)?
1312 for (_ForwardIterator1 __j = __first1; __j != __i; ++__j)
1313 if (__pred(*__j, *__i))
1316 // Count number of *__i in [f2, l2)
1318 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1319 if (__pred(*__i, *__j))
1323 // Count number of *__i in [__i, l1) (we can start with 1)
1325 for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
1326 if (__pred(*__i, *__j))
1336 template<class _ForwardIterator1, class _ForwardIterator2>
1337 inline _LIBCPP_INLINE_VISIBILITY
1339 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1340 _ForwardIterator2 __first2)
1342 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1343 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1344 return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1347 #if _LIBCPP_STD_VER > 11
1348 template<class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
1350 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1351 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1352 _BinaryPredicate __pred,
1353 forward_iterator_tag, forward_iterator_tag )
1355 // shorten sequences as much as possible by lopping of any equal parts
1356 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1357 if (!__pred(*__first1, *__first2))
1359 return __first1 == __last1 && __first2 == __last2;
1361 // __first1 != __last1 && __first2 != __last2 && *__first1 != *__first2
1362 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1363 _D1 __l1 = _VSTD::distance(__first1, __last1);
1365 typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2;
1366 _D2 __l2 = _VSTD::distance(__first2, __last2);
1370 // For each element in [f1, l1) see if there are the same number of
1371 // equal elements in [f2, l2)
1372 for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
1374 // Have we already counted the number of *__i in [f1, l1)?
1375 for (_ForwardIterator1 __j = __first1; __j != __i; ++__j)
1376 if (__pred(*__j, *__i))
1379 // Count number of *__i in [f2, l2)
1381 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1382 if (__pred(*__i, *__j))
1386 // Count number of *__i in [__i, l1) (we can start with 1)
1388 for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
1389 if (__pred(*__i, *__j))
1399 template<class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1401 __is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1,
1402 _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2,
1403 _BinaryPredicate __pred,
1404 random_access_iterator_tag, random_access_iterator_tag )
1406 if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
1408 return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2,
1409 typename add_lvalue_reference<_BinaryPredicate>::type>
1410 (__first1, __last1, __first2, __pred );
1413 template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1414 inline _LIBCPP_INLINE_VISIBILITY
1416 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1417 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1418 _BinaryPredicate __pred )
1420 return _VSTD::__is_permutation<typename add_lvalue_reference<_BinaryPredicate>::type>
1421 (__first1, __last1, __first2, __last2, __pred,
1422 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1423 typename iterator_traits<_ForwardIterator2>::iterator_category());
1426 template<class _ForwardIterator1, class _ForwardIterator2>
1427 inline _LIBCPP_INLINE_VISIBILITY
1429 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1430 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1432 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1433 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1434 return _VSTD::__is_permutation(__first1, __last1, __first2, __last2,
1435 __equal_to<__v1, __v2>(),
1436 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1437 typename iterator_traits<_ForwardIterator2>::iterator_category());
1443 template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
1444 pair<_ForwardIterator1, _ForwardIterator1>
1445 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1446 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
1447 forward_iterator_tag, forward_iterator_tag)
1449 if (__first2 == __last2)
1450 return make_pair(__first1, __first1); // Everything matches an empty sequence
1453 // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks
1456 if (__first1 == __last1) // return __last1 if no element matches *__first2
1457 return make_pair(__last1, __last1);
1458 if (__pred(*__first1, *__first2))
1462 // *__first1 matches *__first2, now match elements after here
1463 _ForwardIterator1 __m1 = __first1;
1464 _ForwardIterator2 __m2 = __first2;
1467 if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern)
1468 return make_pair(__first1, __m1);
1469 if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found
1470 return make_pair(__last1, __last1);
1471 if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1
1475 } // else there is a match, check next elements
1480 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1481 _LIBCPP_CONSTEXPR_AFTER_CXX11
1482 pair<_RandomAccessIterator1, _RandomAccessIterator1>
1483 __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1484 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1485 random_access_iterator_tag, random_access_iterator_tag)
1487 typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1;
1488 typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2;
1489 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern
1490 const _D2 __len2 = __last2 - __first2;
1492 return make_pair(__first1, __first1);
1493 const _D1 __len1 = __last1 - __first1;
1494 if (__len1 < __len2)
1495 return make_pair(__last1, __last1);
1496 const _RandomAccessIterator1 __s = __last1 - (__len2 - 1); // Start of pattern match can't go beyond here
1502 if (__first1 == __s)
1503 return make_pair(__last1, __last1);
1504 if (__pred(*__first1, *__first2))
1509 _RandomAccessIterator1 __m1 = __first1;
1510 _RandomAccessIterator2 __m2 = __first2;
1513 if (++__m2 == __last2)
1514 return make_pair(__first1, __first1 + __len2);
1515 ++__m1; // no need to check range on __m1 because __s guarantees we have enough source
1516 if (!__pred(*__m1, *__m2))
1525 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1526 inline _LIBCPP_INLINE_VISIBILITY
1528 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1529 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1531 return _VSTD::__search<typename add_lvalue_reference<_BinaryPredicate>::type>
1532 (__first1, __last1, __first2, __last2, __pred,
1533 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1534 typename iterator_traits<_ForwardIterator2>::iterator_category())
1538 template <class _ForwardIterator1, class _ForwardIterator2>
1539 inline _LIBCPP_INLINE_VISIBILITY
1541 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1542 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1544 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1545 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1546 return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1551 template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp>
1553 __search_n(_ForwardIterator __first, _ForwardIterator __last,
1554 _Size __count, const _Tp& __value_, _BinaryPredicate __pred, forward_iterator_tag)
1560 // Find first element in sequence that matchs __value_, with a mininum of loop checks
1563 if (__first == __last) // return __last if no element matches __value_
1565 if (__pred(*__first, __value_))
1569 // *__first matches __value_, now match elements after here
1570 _ForwardIterator __m = __first;
1574 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1576 if (++__m == __last) // Otherwise if source exhaused, pattern not found
1578 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1583 } // else there is a match, check next elements
1588 template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp>
1589 _RandomAccessIterator
1590 __search_n(_RandomAccessIterator __first, _RandomAccessIterator __last,
1591 _Size __count, const _Tp& __value_, _BinaryPredicate __pred, random_access_iterator_tag)
1595 _Size __len = static_cast<_Size>(__last - __first);
1596 if (__len < __count)
1598 const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here
1601 // Find first element in sequence that matchs __value_, with a mininum of loop checks
1604 if (__first >= __s) // return __last if no element matches __value_
1606 if (__pred(*__first, __value_))
1610 // *__first matches __value_, now match elements after here
1611 _RandomAccessIterator __m = __first;
1615 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1617 ++__m; // no need to check range on __m because __s guarantees we have enough source
1618 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1623 } // else there is a match, check next elements
1628 template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
1629 inline _LIBCPP_INLINE_VISIBILITY
1631 search_n(_ForwardIterator __first, _ForwardIterator __last,
1632 _Size __count, const _Tp& __value_, _BinaryPredicate __pred)
1634 return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>
1635 (__first, __last, __convert_to_integral(__count), __value_, __pred,
1636 typename iterator_traits<_ForwardIterator>::iterator_category());
1639 template <class _ForwardIterator, class _Size, class _Tp>
1640 inline _LIBCPP_INLINE_VISIBILITY
1642 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
1644 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1645 return _VSTD::search_n(__first, __last, __convert_to_integral(__count),
1646 __value_, __equal_to<__v, _Tp>());
1650 template <class _Iter>
1651 inline _LIBCPP_INLINE_VISIBILITY
1653 __unwrap_iter(_Iter __i)
1658 template <class _Tp>
1659 inline _LIBCPP_INLINE_VISIBILITY
1662 is_trivially_copy_assignable<_Tp>::value,
1665 __unwrap_iter(move_iterator<_Tp*> __i)
1670 #if _LIBCPP_DEBUG_LEVEL < 2
1672 template <class _Tp>
1673 inline _LIBCPP_INLINE_VISIBILITY
1676 is_trivially_copy_assignable<_Tp>::value,
1679 __unwrap_iter(__wrap_iter<_Tp*> __i)
1686 template <class _Tp>
1687 inline _LIBCPP_INLINE_VISIBILITY
1690 is_trivially_copy_assignable<_Tp>::value,
1693 __unwrap_iter(__wrap_iter<_Tp*> __i)
1698 #endif // _LIBCPP_DEBUG_LEVEL < 2
1700 template <class _InputIterator, class _OutputIterator>
1701 inline _LIBCPP_INLINE_VISIBILITY
1703 __copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1705 for (; __first != __last; ++__first, (void) ++__result)
1706 *__result = *__first;
1710 template <class _Tp, class _Up>
1711 inline _LIBCPP_INLINE_VISIBILITY
1714 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1715 is_trivially_copy_assignable<_Up>::value,
1718 __copy(_Tp* __first, _Tp* __last, _Up* __result)
1720 const size_t __n = static_cast<size_t>(__last - __first);
1722 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1723 return __result + __n;
1726 template <class _InputIterator, class _OutputIterator>
1727 inline _LIBCPP_INLINE_VISIBILITY
1729 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1731 return _VSTD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1736 template <class _BidirectionalIterator, class _OutputIterator>
1737 inline _LIBCPP_INLINE_VISIBILITY
1739 __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
1741 while (__first != __last)
1742 *--__result = *--__last;
1746 template <class _Tp, class _Up>
1747 inline _LIBCPP_INLINE_VISIBILITY
1750 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1751 is_trivially_copy_assignable<_Up>::value,
1754 __copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
1756 const size_t __n = static_cast<size_t>(__last - __first);
1760 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1765 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1766 inline _LIBCPP_INLINE_VISIBILITY
1767 _BidirectionalIterator2
1768 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1769 _BidirectionalIterator2 __result)
1771 return _VSTD::__copy_backward(__unwrap_iter(__first),
1772 __unwrap_iter(__last),
1773 __unwrap_iter(__result));
1778 template<class _InputIterator, class _OutputIterator, class _Predicate>
1779 inline _LIBCPP_INLINE_VISIBILITY
1781 copy_if(_InputIterator __first, _InputIterator __last,
1782 _OutputIterator __result, _Predicate __pred)
1784 for (; __first != __last; ++__first)
1786 if (__pred(*__first))
1788 *__result = *__first;
1797 template<class _InputIterator, class _Size, class _OutputIterator>
1798 inline _LIBCPP_INLINE_VISIBILITY
1801 __is_input_iterator<_InputIterator>::value &&
1802 !__is_random_access_iterator<_InputIterator>::value,
1805 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1807 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
1808 _IntegralSize __n = __orig_n;
1811 *__result = *__first;
1813 for (--__n; __n > 0; --__n)
1816 *__result = *__first;
1823 template<class _InputIterator, class _Size, class _OutputIterator>
1824 inline _LIBCPP_INLINE_VISIBILITY
1827 __is_random_access_iterator<_InputIterator>::value,
1830 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1832 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
1833 _IntegralSize __n = __orig_n;
1834 return _VSTD::copy(__first, __first + __n, __result);
1839 template <class _InputIterator, class _OutputIterator>
1840 inline _LIBCPP_INLINE_VISIBILITY
1842 __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1844 for (; __first != __last; ++__first, (void) ++__result)
1845 *__result = _VSTD::move(*__first);
1849 template <class _Tp, class _Up>
1850 inline _LIBCPP_INLINE_VISIBILITY
1853 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1854 is_trivially_copy_assignable<_Up>::value,
1857 __move(_Tp* __first, _Tp* __last, _Up* __result)
1859 const size_t __n = static_cast<size_t>(__last - __first);
1861 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1862 return __result + __n;
1865 template <class _InputIterator, class _OutputIterator>
1866 inline _LIBCPP_INLINE_VISIBILITY
1868 move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1870 return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1875 template <class _InputIterator, class _OutputIterator>
1876 inline _LIBCPP_INLINE_VISIBILITY
1878 __move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1880 while (__first != __last)
1881 *--__result = _VSTD::move(*--__last);
1885 template <class _Tp, class _Up>
1886 inline _LIBCPP_INLINE_VISIBILITY
1889 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1890 is_trivially_copy_assignable<_Up>::value,
1893 __move_backward(_Tp* __first, _Tp* __last, _Up* __result)
1895 const size_t __n = static_cast<size_t>(__last - __first);
1899 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1904 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1905 inline _LIBCPP_INLINE_VISIBILITY
1906 _BidirectionalIterator2
1907 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1908 _BidirectionalIterator2 __result)
1910 return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1915 // moved to <type_traits> for better swap / noexcept support
1919 template <class _InputIterator, class _OutputIterator, class _UnaryOperation>
1920 inline _LIBCPP_INLINE_VISIBILITY
1922 transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op)
1924 for (; __first != __last; ++__first, (void) ++__result)
1925 *__result = __op(*__first);
1929 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation>
1930 inline _LIBCPP_INLINE_VISIBILITY
1932 transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
1933 _OutputIterator __result, _BinaryOperation __binary_op)
1935 for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result)
1936 *__result = __binary_op(*__first1, *__first2);
1942 template <class _ForwardIterator, class _Tp>
1943 inline _LIBCPP_INLINE_VISIBILITY
1945 replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value)
1947 for (; __first != __last; ++__first)
1948 if (*__first == __old_value)
1949 *__first = __new_value;
1954 template <class _ForwardIterator, class _Predicate, class _Tp>
1955 inline _LIBCPP_INLINE_VISIBILITY
1957 replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value)
1959 for (; __first != __last; ++__first)
1960 if (__pred(*__first))
1961 *__first = __new_value;
1966 template <class _InputIterator, class _OutputIterator, class _Tp>
1967 inline _LIBCPP_INLINE_VISIBILITY
1969 replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1970 const _Tp& __old_value, const _Tp& __new_value)
1972 for (; __first != __last; ++__first, (void) ++__result)
1973 if (*__first == __old_value)
1974 *__result = __new_value;
1976 *__result = *__first;
1982 template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp>
1983 inline _LIBCPP_INLINE_VISIBILITY
1985 replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1986 _Predicate __pred, const _Tp& __new_value)
1988 for (; __first != __last; ++__first, (void) ++__result)
1989 if (__pred(*__first))
1990 *__result = __new_value;
1992 *__result = *__first;
1998 template <class _OutputIterator, class _Size, class _Tp>
1999 inline _LIBCPP_INLINE_VISIBILITY
2001 __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2003 for (; __n > 0; ++__first, (void) --__n)
2004 *__first = __value_;
2008 template <class _Tp, class _Size, class _Up>
2009 inline _LIBCPP_INLINE_VISIBILITY
2012 is_integral<_Tp>::value && sizeof(_Tp) == 1 &&
2013 !is_same<_Tp, bool>::value &&
2014 is_integral<_Up>::value && sizeof(_Up) == 1,
2017 __fill_n(_Tp* __first, _Size __n,_Up __value_)
2020 _VSTD::memset(__first, (unsigned char)__value_, (size_t)(__n));
2021 return __first + __n;
2024 template <class _OutputIterator, class _Size, class _Tp>
2025 inline _LIBCPP_INLINE_VISIBILITY
2027 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2029 return _VSTD::__fill_n(__first, __convert_to_integral(__n), __value_);
2034 template <class _ForwardIterator, class _Tp>
2035 inline _LIBCPP_INLINE_VISIBILITY
2037 __fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
2039 for (; __first != __last; ++__first)
2040 *__first = __value_;
2043 template <class _RandomAccessIterator, class _Tp>
2044 inline _LIBCPP_INLINE_VISIBILITY
2046 __fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag)
2048 _VSTD::fill_n(__first, __last - __first, __value_);
2051 template <class _ForwardIterator, class _Tp>
2052 inline _LIBCPP_INLINE_VISIBILITY
2054 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2056 _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category());
2061 template <class _ForwardIterator, class _Generator>
2062 inline _LIBCPP_INLINE_VISIBILITY
2064 generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
2066 for (; __first != __last; ++__first)
2072 template <class _OutputIterator, class _Size, class _Generator>
2073 inline _LIBCPP_INLINE_VISIBILITY
2075 generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen)
2077 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
2078 _IntegralSize __n = __orig_n;
2079 for (; __n > 0; ++__first, (void) --__n)
2086 template <class _ForwardIterator, class _Tp>
2088 remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2090 __first = _VSTD::find(__first, __last, __value_);
2091 if (__first != __last)
2093 _ForwardIterator __i = __first;
2094 while (++__i != __last)
2096 if (!(*__i == __value_))
2098 *__first = _VSTD::move(*__i);
2108 template <class _ForwardIterator, class _Predicate>
2110 remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2112 __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
2113 (__first, __last, __pred);
2114 if (__first != __last)
2116 _ForwardIterator __i = __first;
2117 while (++__i != __last)
2121 *__first = _VSTD::move(*__i);
2131 template <class _InputIterator, class _OutputIterator, class _Tp>
2132 inline _LIBCPP_INLINE_VISIBILITY
2134 remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_)
2136 for (; __first != __last; ++__first)
2138 if (!(*__first == __value_))
2140 *__result = *__first;
2149 template <class _InputIterator, class _OutputIterator, class _Predicate>
2150 inline _LIBCPP_INLINE_VISIBILITY
2152 remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
2154 for (; __first != __last; ++__first)
2156 if (!__pred(*__first))
2158 *__result = *__first;
2167 template <class _ForwardIterator, class _BinaryPredicate>
2169 unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
2171 __first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type>
2172 (__first, __last, __pred);
2173 if (__first != __last)
2177 _ForwardIterator __i = __first;
2178 for (++__i; ++__i != __last;)
2179 if (!__pred(*__first, *__i))
2180 *++__first = _VSTD::move(*__i);
2186 template <class _ForwardIterator>
2187 inline _LIBCPP_INLINE_VISIBILITY
2189 unique(_ForwardIterator __first, _ForwardIterator __last)
2191 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
2192 return _VSTD::unique(__first, __last, __equal_to<__v>());
2197 template <class _BinaryPredicate, class _InputIterator, class _OutputIterator>
2199 __unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2200 input_iterator_tag, output_iterator_tag)
2202 if (__first != __last)
2204 typename iterator_traits<_InputIterator>::value_type __t(*__first);
2207 while (++__first != __last)
2209 if (!__pred(__t, *__first))
2220 template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator>
2222 __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2223 forward_iterator_tag, output_iterator_tag)
2225 if (__first != __last)
2227 _ForwardIterator __i = __first;
2230 while (++__first != __last)
2232 if (!__pred(*__i, *__first))
2234 *__result = *__first;
2243 template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator>
2245 __unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred,
2246 input_iterator_tag, forward_iterator_tag)
2248 if (__first != __last)
2250 *__result = *__first;
2251 while (++__first != __last)
2252 if (!__pred(*__result, *__first))
2253 *++__result = *__first;
2259 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
2260 inline _LIBCPP_INLINE_VISIBILITY
2262 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred)
2264 return _VSTD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type>
2265 (__first, __last, __result, __pred,
2266 typename iterator_traits<_InputIterator>::iterator_category(),
2267 typename iterator_traits<_OutputIterator>::iterator_category());
2270 template <class _InputIterator, class _OutputIterator>
2271 inline _LIBCPP_INLINE_VISIBILITY
2273 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
2275 typedef typename iterator_traits<_InputIterator>::value_type __v;
2276 return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());
2281 template <class _BidirectionalIterator>
2282 inline _LIBCPP_INLINE_VISIBILITY
2284 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
2286 while (__first != __last)
2288 if (__first == --__last)
2290 _VSTD::iter_swap(__first, __last);
2295 template <class _RandomAccessIterator>
2296 inline _LIBCPP_INLINE_VISIBILITY
2298 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
2300 if (__first != __last)
2301 for (; __first < --__last; ++__first)
2302 _VSTD::iter_swap(__first, __last);
2305 template <class _BidirectionalIterator>
2306 inline _LIBCPP_INLINE_VISIBILITY
2308 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
2310 _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());
2315 template <class _BidirectionalIterator, class _OutputIterator>
2316 inline _LIBCPP_INLINE_VISIBILITY
2318 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
2320 for (; __first != __last; ++__result)
2321 *__result = *--__last;
2327 template <class _ForwardIterator>
2329 __rotate_left(_ForwardIterator __first, _ForwardIterator __last)
2331 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2332 value_type __tmp = _VSTD::move(*__first);
2333 _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
2334 *__lm1 = _VSTD::move(__tmp);
2338 template <class _BidirectionalIterator>
2339 _BidirectionalIterator
2340 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
2342 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
2343 _BidirectionalIterator __lm1 = _VSTD::prev(__last);
2344 value_type __tmp = _VSTD::move(*__lm1);
2345 _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
2346 *__first = _VSTD::move(__tmp);
2350 template <class _ForwardIterator>
2352 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2354 _ForwardIterator __i = __middle;
2357 swap(*__first, *__i);
2359 if (++__i == __last)
2361 if (__first == __middle)
2364 _ForwardIterator __r = __first;
2365 if (__first != __middle)
2370 swap(*__first, *__i);
2372 if (++__i == __last)
2374 if (__first == __middle)
2378 else if (__first == __middle)
2385 template<typename _Integral>
2386 inline _LIBCPP_INLINE_VISIBILITY
2388 __algo_gcd(_Integral __x, _Integral __y)
2392 _Integral __t = __x % __y;
2399 template<typename _RandomAccessIterator>
2400 _RandomAccessIterator
2401 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
2403 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2404 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
2406 const difference_type __m1 = __middle - __first;
2407 const difference_type __m2 = __last - __middle;
2410 _VSTD::swap_ranges(__first, __middle, __middle);
2413 const difference_type __g = _VSTD::__algo_gcd(__m1, __m2);
2414 for (_RandomAccessIterator __p = __first + __g; __p != __first;)
2416 value_type __t(_VSTD::move(*--__p));
2417 _RandomAccessIterator __p1 = __p;
2418 _RandomAccessIterator __p2 = __p1 + __m1;
2421 *__p1 = _VSTD::move(*__p2);
2423 const difference_type __d = __last - __p2;
2427 __p2 = __first + (__m1 - __d);
2428 } while (__p2 != __p);
2429 *__p1 = _VSTD::move(__t);
2431 return __first + __m2;
2434 template <class _ForwardIterator>
2435 inline _LIBCPP_INLINE_VISIBILITY
2437 __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
2438 _VSTD::forward_iterator_tag)
2440 typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type;
2441 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2443 if (_VSTD::next(__first) == __middle)
2444 return _VSTD::__rotate_left(__first, __last);
2446 return _VSTD::__rotate_forward(__first, __middle, __last);
2449 template <class _BidirectionalIterator>
2450 inline _LIBCPP_INLINE_VISIBILITY
2451 _BidirectionalIterator
2452 __rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
2453 _VSTD::bidirectional_iterator_tag)
2455 typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type;
2456 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2458 if (_VSTD::next(__first) == __middle)
2459 return _VSTD::__rotate_left(__first, __last);
2460 if (_VSTD::next(__middle) == __last)
2461 return _VSTD::__rotate_right(__first, __last);
2463 return _VSTD::__rotate_forward(__first, __middle, __last);
2466 template <class _RandomAccessIterator>
2467 inline _LIBCPP_INLINE_VISIBILITY
2468 _RandomAccessIterator
2469 __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
2470 _VSTD::random_access_iterator_tag)
2472 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
2473 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2475 if (_VSTD::next(__first) == __middle)
2476 return _VSTD::__rotate_left(__first, __last);
2477 if (_VSTD::next(__middle) == __last)
2478 return _VSTD::__rotate_right(__first, __last);
2479 return _VSTD::__rotate_gcd(__first, __middle, __last);
2481 return _VSTD::__rotate_forward(__first, __middle, __last);
2484 template <class _ForwardIterator>
2485 inline _LIBCPP_INLINE_VISIBILITY
2487 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2489 if (__first == __middle)
2491 if (__middle == __last)
2493 return _VSTD::__rotate(__first, __middle, __last,
2494 typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());
2499 template <class _ForwardIterator, class _OutputIterator>
2500 inline _LIBCPP_INLINE_VISIBILITY
2502 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
2504 return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));
2509 template <class _ForwardIterator, class _Compare>
2510 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2512 min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2514 if (__first != __last)
2516 _ForwardIterator __i = __first;
2517 while (++__i != __last)
2518 if (__comp(*__i, *__first))
2524 template <class _ForwardIterator>
2525 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2527 min_element(_ForwardIterator __first, _ForwardIterator __last)
2529 return _VSTD::min_element(__first, __last,
2530 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2535 template <class _Tp, class _Compare>
2536 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2538 min(const _Tp& __a, const _Tp& __b, _Compare __comp)
2540 return __comp(__b, __a) ? __b : __a;
2543 template <class _Tp>
2544 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2546 min(const _Tp& __a, const _Tp& __b)
2548 return _VSTD::min(__a, __b, __less<_Tp>());
2551 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2553 template<class _Tp, class _Compare>
2554 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2556 min(initializer_list<_Tp> __t, _Compare __comp)
2558 return *_VSTD::min_element(__t.begin(), __t.end(), __comp);
2562 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2564 min(initializer_list<_Tp> __t)
2566 return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>());
2569 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2573 template <class _ForwardIterator, class _Compare>
2574 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2576 max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2578 if (__first != __last)
2580 _ForwardIterator __i = __first;
2581 while (++__i != __last)
2582 if (__comp(*__first, *__i))
2589 template <class _ForwardIterator>
2590 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2592 max_element(_ForwardIterator __first, _ForwardIterator __last)
2594 return _VSTD::max_element(__first, __last,
2595 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2600 template <class _Tp, class _Compare>
2601 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2603 max(const _Tp& __a, const _Tp& __b, _Compare __comp)
2605 return __comp(__a, __b) ? __b : __a;
2608 template <class _Tp>
2609 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2611 max(const _Tp& __a, const _Tp& __b)
2613 return _VSTD::max(__a, __b, __less<_Tp>());
2616 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2618 template<class _Tp, class _Compare>
2619 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2621 max(initializer_list<_Tp> __t, _Compare __comp)
2623 return *_VSTD::max_element(__t.begin(), __t.end(), __comp);
2627 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2629 max(initializer_list<_Tp> __t)
2631 return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>());
2634 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2636 #if _LIBCPP_STD_VER > 14
2638 template<class _Tp, class _Compare>
2639 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
2641 clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
2643 _LIBCPP_ASSERT(!__comp(__hi, __lo), "Bad bounds passed to std::clamp");
2644 return __comp(__v, __lo) ? __lo : __comp(__hi, __v) ? __hi : __v;
2649 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
2651 clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi)
2653 return _VSTD::clamp(__v, __lo, __hi, __less<_Tp>());
2659 template <class _ForwardIterator, class _Compare>
2660 _LIBCPP_CONSTEXPR_AFTER_CXX11
2661 std::pair<_ForwardIterator, _ForwardIterator>
2662 minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2664 std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);
2665 if (__first != __last)
2667 if (++__first != __last)
2669 if (__comp(*__first, *__result.first))
2670 __result.first = __first;
2672 __result.second = __first;
2673 while (++__first != __last)
2675 _ForwardIterator __i = __first;
2676 if (++__first == __last)
2678 if (__comp(*__i, *__result.first))
2679 __result.first = __i;
2680 else if (!__comp(*__i, *__result.second))
2681 __result.second = __i;
2686 if (__comp(*__first, *__i))
2688 if (__comp(*__first, *__result.first))
2689 __result.first = __first;
2690 if (!__comp(*__i, *__result.second))
2691 __result.second = __i;
2695 if (__comp(*__i, *__result.first))
2696 __result.first = __i;
2697 if (!__comp(*__first, *__result.second))
2698 __result.second = __first;
2707 template <class _ForwardIterator>
2708 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2709 std::pair<_ForwardIterator, _ForwardIterator>
2710 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
2712 return _VSTD::minmax_element(__first, __last,
2713 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2718 template<class _Tp, class _Compare>
2719 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2720 pair<const _Tp&, const _Tp&>
2721 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
2723 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) :
2724 pair<const _Tp&, const _Tp&>(__a, __b);
2728 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2729 pair<const _Tp&, const _Tp&>
2730 minmax(const _Tp& __a, const _Tp& __b)
2732 return _VSTD::minmax(__a, __b, __less<_Tp>());
2735 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2737 template<class _Tp, class _Compare>
2738 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2740 minmax(initializer_list<_Tp> __t, _Compare __comp)
2742 typedef typename initializer_list<_Tp>::const_iterator _Iter;
2743 _Iter __first = __t.begin();
2744 _Iter __last = __t.end();
2745 std::pair<_Tp, _Tp> __result(*__first, *__first);
2748 if (__t.size() % 2 == 0)
2750 if (__comp(*__first, __result.first))
2751 __result.first = *__first;
2753 __result.second = *__first;
2757 while (__first != __last)
2759 _Tp __prev = *__first++;
2760 if (__comp(*__first, __prev)) {
2761 if ( __comp(*__first, __result.first)) __result.first = *__first;
2762 if (!__comp(__prev, __result.second)) __result.second = __prev;
2765 if ( __comp(__prev, __result.first)) __result.first = __prev;
2766 if (!__comp(*__first, __result.second)) __result.second = *__first;
2775 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2777 minmax(initializer_list<_Tp> __t)
2779 return _VSTD::minmax(__t, __less<_Tp>());
2782 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2786 // __independent_bits_engine
2788 template <unsigned long long _Xp, size_t _Rp>
2791 static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp
2792 : __log2_imp<_Xp, _Rp - 1>::value;
2795 template <unsigned long long _Xp>
2796 struct __log2_imp<_Xp, 0>
2798 static const size_t value = 0;
2801 template <size_t _Rp>
2802 struct __log2_imp<0, _Rp>
2804 static const size_t value = _Rp + 1;
2807 template <class _UI, _UI _Xp>
2810 static const size_t value = __log2_imp<_Xp,
2811 sizeof(_UI) * __CHAR_BIT__ - 1>::value;
2814 template<class _Engine, class _UIntType>
2815 class __independent_bits_engine
2819 typedef _UIntType result_type;
2822 typedef typename _Engine::result_type _Engine_result_type;
2823 typedef typename conditional
2825 sizeof(_Engine_result_type) <= sizeof(result_type),
2828 >::type _Working_result_type;
2835 _Working_result_type __y0_;
2836 _Working_result_type __y1_;
2837 _Engine_result_type __mask0_;
2838 _Engine_result_type __mask1_;
2840 #ifdef _LIBCPP_HAS_NO_CONSTEXPR
2841 static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
2842 + _Working_result_type(1);
2844 static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()
2845 + _Working_result_type(1);
2847 static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value;
2848 static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits;
2849 static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
2852 // constructors and seeding functions
2853 __independent_bits_engine(_Engine& __e, size_t __w);
2855 // generating functions
2856 result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
2859 result_type __eval(false_type);
2860 result_type __eval(true_type);
2863 template<class _Engine, class _UIntType>
2864 __independent_bits_engine<_Engine, _UIntType>
2865 ::__independent_bits_engine(_Engine& __e, size_t __w)
2869 __n_ = __w_ / __m + (__w_ % __m != 0);
2870 __w0_ = __w_ / __n_;
2873 else if (__w0_ < _WDt)
2874 __y0_ = (_Rp >> __w0_) << __w0_;
2877 if (_Rp - __y0_ > __y0_ / __n_)
2880 __w0_ = __w_ / __n_;
2882 __y0_ = (_Rp >> __w0_) << __w0_;
2886 __n0_ = __n_ - __w_ % __n_;
2887 if (__w0_ < _WDt - 1)
2888 __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1);
2891 __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :
2892 _Engine_result_type(0);
2893 __mask1_ = __w0_ < _EDt - 1 ?
2894 _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :
2895 _Engine_result_type(~0);
2898 template<class _Engine, class _UIntType>
2901 __independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
2903 return static_cast<result_type>(__e_() & __mask0_);
2906 template<class _Engine, class _UIntType>
2908 __independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
2910 result_type _Sp = 0;
2911 for (size_t __k = 0; __k < __n0_; ++__k)
2913 _Engine_result_type __u;
2916 __u = __e_() - _Engine::min();
2917 } while (__u >= __y0_);
2922 _Sp += __u & __mask0_;
2924 for (size_t __k = __n0_; __k < __n_; ++__k)
2926 _Engine_result_type __u;
2929 __u = __e_() - _Engine::min();
2930 } while (__u >= __y1_);
2931 if (__w0_ < _WDt - 1)
2935 _Sp += __u & __mask1_;
2940 // uniform_int_distribution
2942 template<class _IntType = int>
2943 class uniform_int_distribution
2947 typedef _IntType result_type;
2954 typedef uniform_int_distribution distribution_type;
2956 explicit param_type(result_type __a = 0,
2957 result_type __b = numeric_limits<result_type>::max())
2958 : __a_(__a), __b_(__b) {}
2960 result_type a() const {return __a_;}
2961 result_type b() const {return __b_;}
2963 friend bool operator==(const param_type& __x, const param_type& __y)
2964 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
2965 friend bool operator!=(const param_type& __x, const param_type& __y)
2966 {return !(__x == __y);}
2973 // constructors and reset functions
2974 explicit uniform_int_distribution(result_type __a = 0,
2975 result_type __b = numeric_limits<result_type>::max())
2976 : __p_(param_type(__a, __b)) {}
2977 explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
2980 // generating functions
2981 template<class _URNG> result_type operator()(_URNG& __g)
2982 {return (*this)(__g, __p_);}
2983 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
2985 // property functions
2986 result_type a() const {return __p_.a();}
2987 result_type b() const {return __p_.b();}
2989 param_type param() const {return __p_;}
2990 void param(const param_type& __p) {__p_ = __p;}
2992 result_type min() const {return a();}
2993 result_type max() const {return b();}
2995 friend bool operator==(const uniform_int_distribution& __x,
2996 const uniform_int_distribution& __y)
2997 {return __x.__p_ == __y.__p_;}
2998 friend bool operator!=(const uniform_int_distribution& __x,
2999 const uniform_int_distribution& __y)
3000 {return !(__x == __y);}
3003 template<class _IntType>
3004 template<class _URNG>
3005 typename uniform_int_distribution<_IntType>::result_type
3006 uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
3008 typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
3009 uint32_t, uint64_t>::type _UIntType;
3010 const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1);
3013 const size_t _Dt = numeric_limits<_UIntType>::digits;
3014 typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
3016 return static_cast<result_type>(_Eng(__g, _Dt)());
3017 size_t __w = _Dt - __clz(_Rp) - 1;
3018 if ((_Rp & (std::numeric_limits<_UIntType>::max() >> (_Dt - __w))) != 0)
3025 } while (__u >= _Rp);
3026 return static_cast<result_type>(__u + __p.a());
3029 class _LIBCPP_TYPE_VIS __rs_default;
3031 _LIBCPP_FUNC_VIS __rs_default __rs_get();
3033 class _LIBCPP_TYPE_VIS __rs_default
3035 static unsigned __c_;
3039 typedef uint_fast32_t result_type;
3041 static const result_type _Min = 0;
3042 static const result_type _Max = 0xFFFFFFFF;
3044 __rs_default(const __rs_default&);
3047 result_type operator()();
3049 static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
3050 static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
3052 friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
3055 _LIBCPP_FUNC_VIS __rs_default __rs_get();
3057 template <class _RandomAccessIterator>
3059 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
3061 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3062 typedef uniform_int_distribution<ptrdiff_t> _Dp;
3063 typedef typename _Dp::param_type _Pp;
3064 difference_type __d = __last - __first;
3068 __rs_default __g = __rs_get();
3069 for (--__last, --__d; __first < __last; ++__first, --__d)
3071 difference_type __i = __uid(__g, _Pp(0, __d));
3072 if (__i != difference_type(0))
3073 swap(*__first, *(__first + __i));
3078 template <class _RandomAccessIterator, class _RandomNumberGenerator>
3080 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3081 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3082 _RandomNumberGenerator&& __rand)
3084 _RandomNumberGenerator& __rand)
3087 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3088 difference_type __d = __last - __first;
3091 for (--__last; __first < __last; ++__first, --__d)
3093 difference_type __i = __rand(__d);
3094 swap(*__first, *(__first + __i));
3099 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3100 class _UniformRandomNumberGenerator>
3101 _LIBCPP_INLINE_VISIBILITY
3102 _SampleIterator __sample(_PopulationIterator __first,
3103 _PopulationIterator __last, _SampleIterator __output,
3105 _UniformRandomNumberGenerator & __g,
3106 input_iterator_tag) {
3109 for (; __first != __last && __k < __n; ++__first, (void)++__k)
3110 __output[__k] = *__first;
3111 _Distance __sz = __k;
3112 for (; __first != __last; ++__first, (void)++__k) {
3113 _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g);
3115 __output[__r] = *__first;
3117 return __output + _VSTD::min(__n, __k);
3120 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3121 class _UniformRandomNumberGenerator>
3122 _LIBCPP_INLINE_VISIBILITY
3123 _SampleIterator __sample(_PopulationIterator __first,
3124 _PopulationIterator __last, _SampleIterator __output,
3126 _UniformRandomNumberGenerator& __g,
3127 forward_iterator_tag) {
3128 _Distance __unsampled_sz = _VSTD::distance(__first, __last);
3129 for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
3131 _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g);
3133 *__output++ = *__first;
3140 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3141 class _UniformRandomNumberGenerator>
3142 _LIBCPP_INLINE_VISIBILITY
3143 _SampleIterator __sample(_PopulationIterator __first,
3144 _PopulationIterator __last, _SampleIterator __output,
3145 _Distance __n, _UniformRandomNumberGenerator& __g) {
3146 typedef typename iterator_traits<_PopulationIterator>::iterator_category
3148 typedef typename iterator_traits<_PopulationIterator>::difference_type
3150 static_assert(__is_forward_iterator<_PopulationIterator>::value ||
3151 __is_random_access_iterator<_SampleIterator>::value,
3152 "SampleIterator must meet the requirements of RandomAccessIterator");
3153 typedef typename common_type<_Distance, _Difference>::type _CommonType;
3154 _LIBCPP_ASSERT(__n >= 0, "N must be a positive number.");
3155 return _VSTD::__sample(
3156 __first, __last, __output, _CommonType(__n),
3157 __g, _PopCategory());
3160 #if _LIBCPP_STD_VER > 14
3161 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3162 class _UniformRandomNumberGenerator>
3163 inline _LIBCPP_INLINE_VISIBILITY
3164 _SampleIterator sample(_PopulationIterator __first,
3165 _PopulationIterator __last, _SampleIterator __output,
3166 _Distance __n, _UniformRandomNumberGenerator&& __g) {
3167 return _VSTD::__sample(__first, __last, __output, __n, __g);
3169 #endif // _LIBCPP_STD_VER > 14
3171 template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
3172 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3173 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3174 _UniformRandomNumberGenerator&& __g)
3176 _UniformRandomNumberGenerator& __g)
3179 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3180 typedef uniform_int_distribution<ptrdiff_t> _Dp;
3181 typedef typename _Dp::param_type _Pp;
3182 difference_type __d = __last - __first;
3186 for (--__last, --__d; __first < __last; ++__first, --__d)
3188 difference_type __i = __uid(__g, _Pp(0, __d));
3189 if (__i != difference_type(0))
3190 swap(*__first, *(__first + __i));
3195 template <class _InputIterator, class _Predicate>
3197 is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3199 for (; __first != __last; ++__first)
3200 if (!__pred(*__first))
3202 if ( __first == __last )
3205 for (; __first != __last; ++__first)
3206 if (__pred(*__first))
3213 template <class _Predicate, class _ForwardIterator>
3215 __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
3219 if (__first == __last)
3221 if (!__pred(*__first))
3225 for (_ForwardIterator __p = __first; ++__p != __last;)
3229 swap(*__first, *__p);
3236 template <class _Predicate, class _BidirectionalIterator>
3237 _BidirectionalIterator
3238 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3239 bidirectional_iterator_tag)
3245 if (__first == __last)
3247 if (!__pred(*__first))
3253 if (__first == --__last)
3255 } while (!__pred(*__last));
3256 swap(*__first, *__last);
3261 template <class _ForwardIterator, class _Predicate>
3262 inline _LIBCPP_INLINE_VISIBILITY
3264 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3266 return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>
3267 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3272 template <class _InputIterator, class _OutputIterator1,
3273 class _OutputIterator2, class _Predicate>
3274 pair<_OutputIterator1, _OutputIterator2>
3275 partition_copy(_InputIterator __first, _InputIterator __last,
3276 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
3279 for (; __first != __last; ++__first)
3281 if (__pred(*__first))
3283 *__out_true = *__first;
3288 *__out_false = *__first;
3292 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
3297 template<class _ForwardIterator, class _Predicate>
3299 partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3301 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3302 difference_type __len = _VSTD::distance(__first, __last);
3305 difference_type __l2 = __len / 2;
3306 _ForwardIterator __m = __first;
3307 _VSTD::advance(__m, __l2);
3321 template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
3323 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3324 _Distance __len, _Pair __p, forward_iterator_tag __fit)
3326 // *__first is known to be false
3332 _ForwardIterator __m = __first;
3335 swap(*__first, *__m);
3340 if (__len <= __p.second)
3341 { // The buffer is big enough to use
3342 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3343 __destruct_n __d(0);
3344 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3345 // Move the falses into the temporary buffer, and the trues to the front of the line
3346 // Update __first to always point to the end of the trues
3347 value_type* __t = __p.first;
3348 ::new(__t) value_type(_VSTD::move(*__first));
3349 __d.__incr((value_type*)0);
3351 _ForwardIterator __i = __first;
3352 while (++__i != __last)
3356 *__first = _VSTD::move(*__i);
3361 ::new(__t) value_type(_VSTD::move(*__i));
3362 __d.__incr((value_type*)0);
3366 // All trues now at start of range, all falses in buffer
3367 // Move falses back into range, but don't mess up __first which points to first false
3369 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3370 *__i = _VSTD::move(*__t2);
3371 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3374 // Else not enough buffer, do in place
3376 _ForwardIterator __m = __first;
3377 _Distance __len2 = __len / 2; // __len2 >= 2
3378 _VSTD::advance(__m, __len2);
3379 // recurse on [__first, __m), *__first know to be false
3380 // F?????????????????
3382 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3383 _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
3384 // TTTFFFFF??????????
3386 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3387 _ForwardIterator __m1 = __m;
3388 _ForwardIterator __second_false = __last;
3389 _Distance __len_half = __len - __len2;
3390 while (__pred(*__m1))
3392 if (++__m1 == __last)
3393 goto __second_half_done;
3396 // TTTFFFFFTTTF??????
3398 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
3400 // TTTFFFFFTTTTTFFFFF
3402 return _VSTD::rotate(__first_false, __m, __second_false);
3403 // TTTTTTTTFFFFFFFFFF
3407 struct __return_temporary_buffer
3409 template <class _Tp>
3410 _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}
3413 template <class _Predicate, class _ForwardIterator>
3415 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3416 forward_iterator_tag)
3418 const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment
3419 // Either prove all true and return __first or point to first false
3422 if (__first == __last)
3424 if (!__pred(*__first))
3428 // We now have a reduced range [__first, __last)
3429 // *__first is known to be false
3430 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3431 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3432 difference_type __len = _VSTD::distance(__first, __last);
3433 pair<value_type*, ptrdiff_t> __p(0, 0);
3434 unique_ptr<value_type, __return_temporary_buffer> __h;
3435 if (__len >= __alloc_limit)
3437 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3438 __h.reset(__p.first);
3440 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3441 (__first, __last, __pred, __len, __p, forward_iterator_tag());
3444 template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
3445 _BidirectionalIterator
3446 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3447 _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
3449 // *__first is known to be false
3450 // *__last is known to be true
3454 swap(*__first, *__last);
3459 _BidirectionalIterator __m = __first;
3462 swap(*__first, *__m);
3463 swap(*__m, *__last);
3466 swap(*__m, *__last);
3467 swap(*__first, *__m);
3470 if (__len <= __p.second)
3471 { // The buffer is big enough to use
3472 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3473 __destruct_n __d(0);
3474 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3475 // Move the falses into the temporary buffer, and the trues to the front of the line
3476 // Update __first to always point to the end of the trues
3477 value_type* __t = __p.first;
3478 ::new(__t) value_type(_VSTD::move(*__first));
3479 __d.__incr((value_type*)0);
3481 _BidirectionalIterator __i = __first;
3482 while (++__i != __last)
3486 *__first = _VSTD::move(*__i);
3491 ::new(__t) value_type(_VSTD::move(*__i));
3492 __d.__incr((value_type*)0);
3496 // move *__last, known to be true
3497 *__first = _VSTD::move(*__i);
3499 // All trues now at start of range, all falses in buffer
3500 // Move falses back into range, but don't mess up __first which points to first false
3501 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3502 *__i = _VSTD::move(*__t2);
3503 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3506 // Else not enough buffer, do in place
3508 _BidirectionalIterator __m = __first;
3509 _Distance __len2 = __len / 2; // __len2 >= 2
3510 _VSTD::advance(__m, __len2);
3511 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
3512 // F????????????????T
3514 _BidirectionalIterator __m1 = __m;
3515 _BidirectionalIterator __first_false = __first;
3516 _Distance __len_half = __len2;
3517 while (!__pred(*--__m1))
3519 if (__m1 == __first)
3520 goto __first_half_done;
3523 // F???TFFF?????????T
3525 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3526 __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3528 // TTTFFFFF?????????T
3530 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3532 _BidirectionalIterator __second_false = __last;
3534 __len_half = __len - __len2;
3535 while (__pred(*__m1))
3537 if (++__m1 == __last)
3538 goto __second_half_done;
3541 // TTTFFFFFTTTF?????T
3543 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
3545 // TTTFFFFFTTTTTFFFFF
3547 return _VSTD::rotate(__first_false, __m, __second_false);
3548 // TTTTTTTTFFFFFFFFFF
3552 template <class _Predicate, class _BidirectionalIterator>
3553 _BidirectionalIterator
3554 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3555 bidirectional_iterator_tag)
3557 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3558 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3559 const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment
3560 // Either prove all true and return __first or point to first false
3563 if (__first == __last)
3565 if (!__pred(*__first))
3569 // __first points to first false, everything prior to __first is already set.
3570 // Either prove [__first, __last) is all false and return __first, or point __last to last true
3573 if (__first == --__last)
3575 } while (!__pred(*__last));
3576 // We now have a reduced range [__first, __last]
3577 // *__first is known to be false
3578 // *__last is known to be true
3580 difference_type __len = _VSTD::distance(__first, __last) + 1;
3581 pair<value_type*, ptrdiff_t> __p(0, 0);
3582 unique_ptr<value_type, __return_temporary_buffer> __h;
3583 if (__len >= __alloc_limit)
3585 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3586 __h.reset(__p.first);
3588 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3589 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3592 template <class _ForwardIterator, class _Predicate>
3593 inline _LIBCPP_INLINE_VISIBILITY
3595 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3597 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3598 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3603 template <class _ForwardIterator, class _Compare>
3605 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3607 if (__first != __last)
3609 _ForwardIterator __i = __first;
3610 while (++__i != __last)
3612 if (__comp(*__i, *__first))
3620 template<class _ForwardIterator>
3621 inline _LIBCPP_INLINE_VISIBILITY
3623 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3625 return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3630 template <class _ForwardIterator, class _Compare>
3631 inline _LIBCPP_INLINE_VISIBILITY
3633 is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3635 return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
3638 template<class _ForwardIterator>
3639 inline _LIBCPP_INLINE_VISIBILITY
3641 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3643 return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3648 // stable, 2-3 compares, 0-2 swaps
3650 template <class _Compare, class _ForwardIterator>
3652 __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
3655 if (!__c(*__y, *__x)) // if x <= y
3657 if (!__c(*__z, *__y)) // if y <= z
3658 return __r; // x <= y && y <= z
3660 swap(*__y, *__z); // x <= z && y < z
3662 if (__c(*__y, *__x)) // if x > y
3664 swap(*__x, *__y); // x < y && y <= z
3667 return __r; // x <= y && y < z
3669 if (__c(*__z, *__y)) // x > y, if y > z
3671 swap(*__x, *__z); // x < y && y < z
3675 swap(*__x, *__y); // x > y && y <= z
3676 __r = 1; // x < y && x <= z
3677 if (__c(*__z, *__y)) // if y > z
3679 swap(*__y, *__z); // x <= y && y < z
3683 } // x <= y && y <= z
3685 // stable, 3-6 compares, 0-5 swaps
3687 template <class _Compare, class _ForwardIterator>
3689 __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3690 _ForwardIterator __x4, _Compare __c)
3692 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
3693 if (__c(*__x4, *__x3))
3697 if (__c(*__x3, *__x2))
3701 if (__c(*__x2, *__x1))
3711 // stable, 4-10 compares, 0-9 swaps
3713 template <class _Compare, class _ForwardIterator>
3715 __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3716 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
3718 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
3719 if (__c(*__x5, *__x4))
3723 if (__c(*__x4, *__x3))
3727 if (__c(*__x3, *__x2))
3731 if (__c(*__x2, *__x1))
3743 template <class _Compare, class _BirdirectionalIterator>
3745 __selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3747 _BirdirectionalIterator __lm1 = __last;
3748 for (--__lm1; __first != __lm1; ++__first)
3750 _BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator,
3751 typename add_lvalue_reference<_Compare>::type>
3752 (__first, __last, __comp);
3754 swap(*__first, *__i);
3758 template <class _Compare, class _BirdirectionalIterator>
3760 __insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3762 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3763 if (__first != __last)
3765 _BirdirectionalIterator __i = __first;
3766 for (++__i; __i != __last; ++__i)
3768 _BirdirectionalIterator __j = __i;
3769 value_type __t(_VSTD::move(*__j));
3770 for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
3771 *__j = _VSTD::move(*__k);
3772 *__j = _VSTD::move(__t);
3777 template <class _Compare, class _RandomAccessIterator>
3779 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3781 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3782 _RandomAccessIterator __j = __first+2;
3783 __sort3<_Compare>(__first, __first+1, __j, __comp);
3784 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3786 if (__comp(*__i, *__j))
3788 value_type __t(_VSTD::move(*__i));
3789 _RandomAccessIterator __k = __j;
3793 *__j = _VSTD::move(*__k);
3795 } while (__j != __first && __comp(__t, *--__k));
3796 *__j = _VSTD::move(__t);
3802 template <class _Compare, class _RandomAccessIterator>
3804 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3806 switch (__last - __first)
3812 if (__comp(*--__last, *__first))
3813 swap(*__first, *__last);
3816 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3819 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3822 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3825 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3826 _RandomAccessIterator __j = __first+2;
3827 __sort3<_Compare>(__first, __first+1, __j, __comp);
3828 const unsigned __limit = 8;
3829 unsigned __count = 0;
3830 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3832 if (__comp(*__i, *__j))
3834 value_type __t(_VSTD::move(*__i));
3835 _RandomAccessIterator __k = __j;
3839 *__j = _VSTD::move(*__k);
3841 } while (__j != __first && __comp(__t, *--__k));
3842 *__j = _VSTD::move(__t);
3843 if (++__count == __limit)
3844 return ++__i == __last;
3851 template <class _Compare, class _BirdirectionalIterator>
3853 __insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
3854 typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
3856 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3857 if (__first1 != __last1)
3859 __destruct_n __d(0);
3860 unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
3861 value_type* __last2 = __first2;
3862 ::new(__last2) value_type(_VSTD::move(*__first1));
3863 __d.__incr((value_type*)0);
3864 for (++__last2; ++__first1 != __last1; ++__last2)
3866 value_type* __j2 = __last2;
3867 value_type* __i2 = __j2;
3868 if (__comp(*__first1, *--__i2))
3870 ::new(__j2) value_type(_VSTD::move(*__i2));
3871 __d.__incr((value_type*)0);
3872 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2)
3873 *__j2 = _VSTD::move(*__i2);
3874 *__j2 = _VSTD::move(*__first1);
3878 ::new(__j2) value_type(_VSTD::move(*__first1));
3879 __d.__incr((value_type*)0);
3886 template <class _Compare, class _RandomAccessIterator>
3888 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3890 // _Compare is known to be a reference type
3891 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3892 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3893 const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
3894 is_trivially_copy_assignable<value_type>::value ? 30 : 6;
3898 difference_type __len = __last - __first;
3905 if (__comp(*--__last, *__first))
3906 swap(*__first, *__last);
3909 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3912 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3915 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3918 if (__len <= __limit)
3920 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
3924 _RandomAccessIterator __m = __first;
3925 _RandomAccessIterator __lm1 = __last;
3929 difference_type __delta;
3935 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
3941 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
3945 // partition [__first, __m) < *__m and *__m <= [__m, __last)
3946 // (this inhibits tossing elements equivalent to __m around unnecessarily)
3947 _RandomAccessIterator __i = __first;
3948 _RandomAccessIterator __j = __lm1;
3949 // j points beyond range to be tested, *__m is known to be <= *__lm1
3950 // The search going up is known to be guarded but the search coming down isn't.
3951 // Prime the downward search with a guard.
3952 if (!__comp(*__i, *__m)) // if *__first == *__m
3954 // *__first == *__m, *__first doesn't go in first part
3955 // manually guard downward moving __j against __i
3960 // *__first == *__m, *__m <= all other elements
3961 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
3962 ++__i; // __first + 1
3964 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
3969 return; // [__first, __last) all equivalent elements
3970 if (__comp(*__first, *__i))
3980 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
3985 while (!__comp(*__first, *__i))
3987 while (__comp(*__first, *--__j))
3995 // [__first, __i) == *__first and *__first < [__i, __last)
3996 // The first part is sorted, sort the secod part
3997 // _VSTD::__sort<_Compare>(__i, __last, __comp);
4001 if (__comp(*__j, *__m))
4005 break; // found guard for downward moving __j, now use unguarded partition
4009 // It is known that *__i < *__m
4011 // j points beyond range to be tested, *__m is known to be <= *__lm1
4012 // if not yet partitioned...
4015 // known that *(__i - 1) < *__m
4016 // known that __i <= __m
4019 // __m still guards upward moving __i
4020 while (__comp(*__i, *__m))
4022 // It is now known that a guard exists for downward moving __j
4023 while (!__comp(*--__j, *__m))
4029 // It is known that __m != __j
4030 // If __m just moved, follow it
4036 // [__first, __i) < *__m and *__m <= [__i, __last)
4037 if (__i != __m && __comp(*__m, *__i))
4042 // [__first, __i) < *__i and *__i <= [__i+1, __last)
4043 // If we were given a perfect partition, see if insertion sort is quick...
4046 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
4047 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
4063 // sort smaller range with recursive call and larger with tail recursion elimination
4064 if (__i - __first < __last - __i)
4066 _VSTD::__sort<_Compare>(__first, __i, __comp);
4067 // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4072 _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4073 // _VSTD::__sort<_Compare>(__first, __i, __comp);
4079 // This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
4080 template <class _RandomAccessIterator, class _Compare>
4081 inline _LIBCPP_INLINE_VISIBILITY
4083 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4085 #ifdef _LIBCPP_DEBUG
4086 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4087 __debug_less<_Compare> __c(__comp);
4088 __sort<_Comp_ref>(__first, __last, __c);
4089 #else // _LIBCPP_DEBUG
4090 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4091 __sort<_Comp_ref>(__first, __last, __comp);
4092 #endif // _LIBCPP_DEBUG
4095 template <class _RandomAccessIterator>
4096 inline _LIBCPP_INLINE_VISIBILITY
4098 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4100 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4103 template <class _Tp>
4104 inline _LIBCPP_INLINE_VISIBILITY
4106 sort(_Tp** __first, _Tp** __last)
4108 _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
4111 template <class _Tp>
4112 inline _LIBCPP_INLINE_VISIBILITY
4114 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
4116 _VSTD::sort(__first.base(), __last.base());
4119 template <class _Tp, class _Compare>
4120 inline _LIBCPP_INLINE_VISIBILITY
4122 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
4124 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4125 _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
4129 #pragma warning( push )
4130 #pragma warning( disable: 4231)
4131 #endif // _LIBCPP_MSVC
4132 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
4133 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4134 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4135 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4136 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))
4137 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4138 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&))
4139 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4140 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&))
4141 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4142 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4143 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&))
4144 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&))
4145 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&))
4146 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4148 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))
4149 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4150 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4151 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4152 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))
4153 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4154 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&))
4155 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4156 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&))
4157 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4158 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4159 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&))
4160 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&))
4161 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&))
4162 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4164 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&))
4166 #pragma warning( pop )
4167 #endif // _LIBCPP_MSVC
4171 template <class _Compare, class _ForwardIterator, class _Tp>
4173 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4175 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4176 difference_type __len = _VSTD::distance(__first, __last);
4179 difference_type __l2 = __len / 2;
4180 _ForwardIterator __m = __first;
4181 _VSTD::advance(__m, __l2);
4182 if (__comp(*__m, __value_))
4193 template <class _ForwardIterator, class _Tp, class _Compare>
4194 inline _LIBCPP_INLINE_VISIBILITY
4196 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4198 #ifdef _LIBCPP_DEBUG
4199 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4200 __debug_less<_Compare> __c(__comp);
4201 return __lower_bound<_Comp_ref>(__first, __last, __value_, __c);
4202 #else // _LIBCPP_DEBUG
4203 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4204 return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp);
4205 #endif // _LIBCPP_DEBUG
4208 template <class _ForwardIterator, class _Tp>
4209 inline _LIBCPP_INLINE_VISIBILITY
4211 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4213 return _VSTD::lower_bound(__first, __last, __value_,
4214 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4219 template <class _Compare, class _ForwardIterator, class _Tp>
4221 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4223 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4224 difference_type __len = _VSTD::distance(__first, __last);
4227 difference_type __l2 = __len / 2;
4228 _ForwardIterator __m = __first;
4229 _VSTD::advance(__m, __l2);
4230 if (__comp(__value_, *__m))
4241 template <class _ForwardIterator, class _Tp, class _Compare>
4242 inline _LIBCPP_INLINE_VISIBILITY
4244 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4246 #ifdef _LIBCPP_DEBUG
4247 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4248 __debug_less<_Compare> __c(__comp);
4249 return __upper_bound<_Comp_ref>(__first, __last, __value_, __c);
4250 #else // _LIBCPP_DEBUG
4251 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4252 return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp);
4253 #endif // _LIBCPP_DEBUG
4256 template <class _ForwardIterator, class _Tp>
4257 inline _LIBCPP_INLINE_VISIBILITY
4259 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4261 return _VSTD::upper_bound(__first, __last, __value_,
4262 __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
4267 template <class _Compare, class _ForwardIterator, class _Tp>
4268 pair<_ForwardIterator, _ForwardIterator>
4269 __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4271 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4272 difference_type __len = _VSTD::distance(__first, __last);
4275 difference_type __l2 = __len / 2;
4276 _ForwardIterator __m = __first;
4277 _VSTD::advance(__m, __l2);
4278 if (__comp(*__m, __value_))
4283 else if (__comp(__value_, *__m))
4290 _ForwardIterator __mp1 = __m;
4291 return pair<_ForwardIterator, _ForwardIterator>
4293 __lower_bound<_Compare>(__first, __m, __value_, __comp),
4294 __upper_bound<_Compare>(++__mp1, __last, __value_, __comp)
4298 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4301 template <class _ForwardIterator, class _Tp, class _Compare>
4302 inline _LIBCPP_INLINE_VISIBILITY
4303 pair<_ForwardIterator, _ForwardIterator>
4304 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4306 #ifdef _LIBCPP_DEBUG
4307 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4308 __debug_less<_Compare> __c(__comp);
4309 return __equal_range<_Comp_ref>(__first, __last, __value_, __c);
4310 #else // _LIBCPP_DEBUG
4311 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4312 return __equal_range<_Comp_ref>(__first, __last, __value_, __comp);
4313 #endif // _LIBCPP_DEBUG
4316 template <class _ForwardIterator, class _Tp>
4317 inline _LIBCPP_INLINE_VISIBILITY
4318 pair<_ForwardIterator, _ForwardIterator>
4319 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4321 return _VSTD::equal_range(__first, __last, __value_,
4322 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4327 template <class _Compare, class _ForwardIterator, class _Tp>
4328 inline _LIBCPP_INLINE_VISIBILITY
4330 __binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4332 __first = __lower_bound<_Compare>(__first, __last, __value_, __comp);
4333 return __first != __last && !__comp(__value_, *__first);
4336 template <class _ForwardIterator, class _Tp, class _Compare>
4337 inline _LIBCPP_INLINE_VISIBILITY
4339 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4341 #ifdef _LIBCPP_DEBUG
4342 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4343 __debug_less<_Compare> __c(__comp);
4344 return __binary_search<_Comp_ref>(__first, __last, __value_, __c);
4345 #else // _LIBCPP_DEBUG
4346 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4347 return __binary_search<_Comp_ref>(__first, __last, __value_, __comp);
4348 #endif // _LIBCPP_DEBUG
4351 template <class _ForwardIterator, class _Tp>
4352 inline _LIBCPP_INLINE_VISIBILITY
4354 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4356 return _VSTD::binary_search(__first, __last, __value_,
4357 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4362 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4364 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4365 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4367 for (; __first1 != __last1; ++__result)
4369 if (__first2 == __last2)
4370 return _VSTD::copy(__first1, __last1, __result);
4371 if (__comp(*__first2, *__first1))
4373 *__result = *__first2;
4378 *__result = *__first1;
4382 return _VSTD::copy(__first2, __last2, __result);
4385 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4386 inline _LIBCPP_INLINE_VISIBILITY
4388 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4389 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4391 #ifdef _LIBCPP_DEBUG
4392 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4393 __debug_less<_Compare> __c(__comp);
4394 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
4395 #else // _LIBCPP_DEBUG
4396 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4397 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4398 #endif // _LIBCPP_DEBUG
4401 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4402 inline _LIBCPP_INLINE_VISIBILITY
4404 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4405 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4407 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
4408 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
4409 return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
4414 template <class _Compare, class _InputIterator1, class _InputIterator2,
4415 class _OutputIterator>
4416 void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
4417 _InputIterator2 __first2, _InputIterator2 __last2,
4418 _OutputIterator __result, _Compare __comp)
4420 for (; __first1 != __last1; ++__result)
4422 if (__first2 == __last2)
4424 _VSTD::move(__first1, __last1, __result);
4428 if (__comp(*__first2, *__first1))
4430 *__result = _VSTD::move(*__first2);
4435 *__result = _VSTD::move(*__first1);
4439 // __first2 through __last2 are already in the right spot.
4442 template <class _Compare, class _BidirectionalIterator>
4444 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4445 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4446 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4447 typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
4449 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4450 __destruct_n __d(0);
4451 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4452 if (__len1 <= __len2)
4454 value_type* __p = __buff;
4455 for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4456 ::new(__p) value_type(_VSTD::move(*__i));
4457 __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);
4461 value_type* __p = __buff;
4462 for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4463 ::new(__p) value_type(_VSTD::move(*__i));
4464 typedef reverse_iterator<_BidirectionalIterator> _RBi;
4465 typedef reverse_iterator<value_type*> _Rv;
4466 __half_inplace_merge(_Rv(__p), _Rv(__buff),
4467 _RBi(__middle), _RBi(__first),
4468 _RBi(__last), __negate<_Compare>(__comp));
4472 template <class _Compare, class _BidirectionalIterator>
4474 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4475 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4476 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4477 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
4479 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4482 // if __middle == __last, we're done
4485 if (__len1 <= __buff_size || __len2 <= __buff_size)
4486 return __buffered_inplace_merge<_Compare>
4487 (__first, __middle, __last, __comp, __len1, __len2, __buff);
4488 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
4489 for (; true; ++__first, (void) --__len1)
4493 if (__comp(*__middle, *__first))
4496 // __first < __middle < __last
4497 // *__first > *__middle
4498 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4500 // [__first, __m1) <= [__middle, __m2)
4501 // [__middle, __m2) < [__m1, __middle)
4502 // [__m1, __middle) <= [__m2, __last)
4503 // and __m1 or __m2 is in the middle of its range
4504 _BidirectionalIterator __m1; // "median" of [__first, __middle)
4505 _BidirectionalIterator __m2; // "median" of [__middle, __last)
4506 difference_type __len11; // distance(__first, __m1)
4507 difference_type __len21; // distance(__middle, __m2)
4508 // binary search smaller range
4509 if (__len1 < __len2)
4510 { // __len >= 1, __len2 >= 2
4511 __len21 = __len2 / 2;
4513 _VSTD::advance(__m2, __len21);
4514 __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4515 __len11 = _VSTD::distance(__first, __m1);
4520 { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
4521 // It is known *__first > *__middle
4522 swap(*__first, *__middle);
4525 // __len1 >= 2, __len2 >= 1
4526 __len11 = __len1 / 2;
4528 _VSTD::advance(__m1, __len11);
4529 __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp);
4530 __len21 = _VSTD::distance(__middle, __m2);
4532 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle)
4533 difference_type __len22 = __len2 - __len21; // distance(__m2, __last)
4534 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4535 // swap middle two partitions
4536 __middle = _VSTD::rotate(__m1, __middle, __m2);
4537 // __len12 and __len21 now have swapped meanings
4538 // merge smaller range with recurisve call and larger with tail recursion elimination
4539 if (__len11 + __len21 < __len12 + __len22)
4541 __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4542 // __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4550 __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4551 // __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4560 template <class _BidirectionalIterator, class _Compare>
4561 inline _LIBCPP_INLINE_VISIBILITY
4563 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4566 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4567 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4568 difference_type __len1 = _VSTD::distance(__first, __middle);
4569 difference_type __len2 = _VSTD::distance(__middle, __last);
4570 difference_type __buf_size = _VSTD::min(__len1, __len2);
4571 pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
4572 unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
4574 #ifdef _LIBCPP_DEBUG
4575 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4576 __debug_less<_Compare> __c(__comp);
4577 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2,
4578 __buf.first, __buf.second);
4579 #else // _LIBCPP_DEBUG
4580 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4581 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4582 __buf.first, __buf.second);
4583 #endif // _LIBCPP_DEBUG
4586 template <class _BidirectionalIterator>
4587 inline _LIBCPP_INLINE_VISIBILITY
4589 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
4591 _VSTD::inplace_merge(__first, __middle, __last,
4592 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4597 template <class _Compare, class _InputIterator1, class _InputIterator2>
4599 __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
4600 _InputIterator2 __first2, _InputIterator2 __last2,
4601 typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
4603 typedef typename iterator_traits<_InputIterator1>::value_type value_type;
4604 __destruct_n __d(0);
4605 unique_ptr<value_type, __destruct_n&> __h(__result, __d);
4606 for (; true; ++__result)
4608 if (__first1 == __last1)
4610 for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0))
4611 ::new (__result) value_type(_VSTD::move(*__first2));
4615 if (__first2 == __last2)
4617 for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0))
4618 ::new (__result) value_type(_VSTD::move(*__first1));
4622 if (__comp(*__first2, *__first1))
4624 ::new (__result) value_type(_VSTD::move(*__first2));
4625 __d.__incr((value_type*)0);
4630 ::new (__result) value_type(_VSTD::move(*__first1));
4631 __d.__incr((value_type*)0);
4637 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4639 __merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
4640 _InputIterator2 __first2, _InputIterator2 __last2,
4641 _OutputIterator __result, _Compare __comp)
4643 for (; __first1 != __last1; ++__result)
4645 if (__first2 == __last2)
4647 for (; __first1 != __last1; ++__first1, ++__result)
4648 *__result = _VSTD::move(*__first1);
4651 if (__comp(*__first2, *__first1))
4653 *__result = _VSTD::move(*__first2);
4658 *__result = _VSTD::move(*__first1);
4662 for (; __first2 != __last2; ++__first2, ++__result)
4663 *__result = _VSTD::move(*__first2);
4666 template <class _Compare, class _RandomAccessIterator>
4668 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4669 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4670 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
4672 template <class _Compare, class _RandomAccessIterator>
4674 __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
4675 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4676 typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
4678 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4684 ::new(__first2) value_type(_VSTD::move(*__first1));
4687 __destruct_n __d(0);
4688 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
4689 if (__comp(*--__last1, *__first1))
4691 ::new(__first2) value_type(_VSTD::move(*__last1));
4692 __d.__incr((value_type*)0);
4694 ::new(__first2) value_type(_VSTD::move(*__first1));
4698 ::new(__first2) value_type(_VSTD::move(*__first1));
4699 __d.__incr((value_type*)0);
4701 ::new(__first2) value_type(_VSTD::move(*__last1));
4708 __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
4711 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4712 _RandomAccessIterator __m = __first1 + __l2;
4713 __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
4714 __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
4715 __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
4718 template <class _Tp>
4719 struct __stable_sort_switch
4721 static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
4724 template <class _Compare, class _RandomAccessIterator>
4726 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4727 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4728 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
4730 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4731 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4738 if (__comp(*--__last, *__first))
4739 swap(*__first, *__last);
4742 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4744 __insertion_sort<_Compare>(__first, __last, __comp);
4747 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4748 _RandomAccessIterator __m = __first + __l2;
4749 if (__len <= __buff_size)
4751 __destruct_n __d(0);
4752 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4753 __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4754 __d.__set(__l2, (value_type*)0);
4755 __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
4756 __d.__set(__len, (value_type*)0);
4757 __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4758 // __merge<_Compare>(move_iterator<value_type*>(__buff),
4759 // move_iterator<value_type*>(__buff + __l2),
4760 // move_iterator<_RandomAccessIterator>(__buff + __l2),
4761 // move_iterator<_RandomAccessIterator>(__buff + __len),
4762 // __first, __comp);
4765 __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4766 __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
4767 __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4770 template <class _RandomAccessIterator, class _Compare>
4771 inline _LIBCPP_INLINE_VISIBILITY
4773 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4775 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4776 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4777 difference_type __len = __last - __first;
4778 pair<value_type*, ptrdiff_t> __buf(0, 0);
4779 unique_ptr<value_type, __return_temporary_buffer> __h;
4780 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4782 __buf = _VSTD::get_temporary_buffer<value_type>(__len);
4783 __h.reset(__buf.first);
4785 #ifdef _LIBCPP_DEBUG
4786 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4787 __debug_less<_Compare> __c(__comp);
4788 __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);
4789 #else // _LIBCPP_DEBUG
4790 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4791 __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4792 #endif // _LIBCPP_DEBUG
4795 template <class _RandomAccessIterator>
4796 inline _LIBCPP_INLINE_VISIBILITY
4798 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4800 _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4805 template <class _RandomAccessIterator, class _Compare>
4806 _RandomAccessIterator
4807 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4809 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4810 difference_type __len = __last - __first;
4811 difference_type __p = 0;
4812 difference_type __c = 1;
4813 _RandomAccessIterator __pp = __first;
4816 _RandomAccessIterator __cp = __first + __c;
4817 if (__comp(*__pp, *__cp))
4823 if (__comp(*__pp, *__cp))
4832 template<class _RandomAccessIterator>
4833 inline _LIBCPP_INLINE_VISIBILITY
4834 _RandomAccessIterator
4835 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4837 return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4842 template <class _RandomAccessIterator, class _Compare>
4843 inline _LIBCPP_INLINE_VISIBILITY
4845 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4847 return _VSTD::is_heap_until(__first, __last, __comp) == __last;
4850 template<class _RandomAccessIterator>
4851 inline _LIBCPP_INLINE_VISIBILITY
4853 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4855 return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4860 template <class _Compare, class _RandomAccessIterator>
4862 __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4863 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4865 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4868 __len = (__len - 2) / 2;
4869 _RandomAccessIterator __ptr = __first + __len;
4870 if (__comp(*__ptr, *--__last))
4872 value_type __t(_VSTD::move(*__last));
4875 *__last = _VSTD::move(*__ptr);
4879 __len = (__len - 1) / 2;
4880 __ptr = __first + __len;
4881 } while (__comp(*__ptr, __t));
4882 *__last = _VSTD::move(__t);
4887 template <class _RandomAccessIterator, class _Compare>
4888 inline _LIBCPP_INLINE_VISIBILITY
4890 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4892 #ifdef _LIBCPP_DEBUG
4893 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4894 __debug_less<_Compare> __c(__comp);
4895 __sift_up<_Comp_ref>(__first, __last, __c, __last - __first);
4896 #else // _LIBCPP_DEBUG
4897 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4898 __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
4899 #endif // _LIBCPP_DEBUG
4902 template <class _RandomAccessIterator>
4903 inline _LIBCPP_INLINE_VISIBILITY
4905 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4907 _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4912 template <class _Compare, class _RandomAccessIterator>
4914 __sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/,
4916 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4917 _RandomAccessIterator __start)
4919 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4920 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4921 // left-child of __start is at 2 * __start + 1
4922 // right-child of __start is at 2 * __start + 2
4923 difference_type __child = __start - __first;
4925 if (__len < 2 || (__len - 2) / 2 < __child)
4928 __child = 2 * __child + 1;
4929 _RandomAccessIterator __child_i = __first + __child;
4931 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4932 // right-child exists and is greater than left-child
4937 // check if we are in heap-order
4938 if (__comp(*__child_i, *__start))
4939 // we are, __start is larger than it's largest child
4942 value_type __top(_VSTD::move(*__start));
4945 // we are not in heap-order, swap the parent with it's largest child
4946 *__start = _VSTD::move(*__child_i);
4947 __start = __child_i;
4949 if ((__len - 2) / 2 < __child)
4952 // recompute the child based off of the updated parent
4953 __child = 2 * __child + 1;
4954 __child_i = __first + __child;
4956 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4957 // right-child exists and is greater than left-child
4962 // check if we are in heap-order
4963 } while (!__comp(*__child_i, __top));
4964 *__start = _VSTD::move(__top);
4967 template <class _Compare, class _RandomAccessIterator>
4968 inline _LIBCPP_INLINE_VISIBILITY
4970 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4971 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4975 swap(*__first, *--__last);
4976 __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);
4980 template <class _RandomAccessIterator, class _Compare>
4981 inline _LIBCPP_INLINE_VISIBILITY
4983 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4985 #ifdef _LIBCPP_DEBUG
4986 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4987 __debug_less<_Compare> __c(__comp);
4988 __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);
4989 #else // _LIBCPP_DEBUG
4990 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4991 __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
4992 #endif // _LIBCPP_DEBUG
4995 template <class _RandomAccessIterator>
4996 inline _LIBCPP_INLINE_VISIBILITY
4998 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5000 _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5005 template <class _Compare, class _RandomAccessIterator>
5007 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5009 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5010 difference_type __n = __last - __first;
5013 // start from the first parent, there is no need to consider children
5014 for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start)
5016 __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start);
5021 template <class _RandomAccessIterator, class _Compare>
5022 inline _LIBCPP_INLINE_VISIBILITY
5024 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5026 #ifdef _LIBCPP_DEBUG
5027 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5028 __debug_less<_Compare> __c(__comp);
5029 __make_heap<_Comp_ref>(__first, __last, __c);
5030 #else // _LIBCPP_DEBUG
5031 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5032 __make_heap<_Comp_ref>(__first, __last, __comp);
5033 #endif // _LIBCPP_DEBUG
5036 template <class _RandomAccessIterator>
5037 inline _LIBCPP_INLINE_VISIBILITY
5039 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5041 _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5046 template <class _Compare, class _RandomAccessIterator>
5048 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5050 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5051 for (difference_type __n = __last - __first; __n > 1; --__last, --__n)
5052 __pop_heap<_Compare>(__first, __last, __comp, __n);
5055 template <class _RandomAccessIterator, class _Compare>
5056 inline _LIBCPP_INLINE_VISIBILITY
5058 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5060 #ifdef _LIBCPP_DEBUG
5061 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5062 __debug_less<_Compare> __c(__comp);
5063 __sort_heap<_Comp_ref>(__first, __last, __c);
5064 #else // _LIBCPP_DEBUG
5065 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5066 __sort_heap<_Comp_ref>(__first, __last, __comp);
5067 #endif // _LIBCPP_DEBUG
5070 template <class _RandomAccessIterator>
5071 inline _LIBCPP_INLINE_VISIBILITY
5073 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5075 _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5080 template <class _Compare, class _RandomAccessIterator>
5082 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5085 __make_heap<_Compare>(__first, __middle, __comp);
5086 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
5087 for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
5089 if (__comp(*__i, *__first))
5091 swap(*__i, *__first);
5092 __sift_down<_Compare>(__first, __middle, __comp, __len, __first);
5095 __sort_heap<_Compare>(__first, __middle, __comp);
5098 template <class _RandomAccessIterator, class _Compare>
5099 inline _LIBCPP_INLINE_VISIBILITY
5101 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5104 #ifdef _LIBCPP_DEBUG
5105 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5106 __debug_less<_Compare> __c(__comp);
5107 __partial_sort<_Comp_ref>(__first, __middle, __last, __c);
5108 #else // _LIBCPP_DEBUG
5109 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5110 __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
5111 #endif // _LIBCPP_DEBUG
5114 template <class _RandomAccessIterator>
5115 inline _LIBCPP_INLINE_VISIBILITY
5117 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
5119 _VSTD::partial_sort(__first, __middle, __last,
5120 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5123 // partial_sort_copy
5125 template <class _Compare, class _InputIterator, class _RandomAccessIterator>
5126 _RandomAccessIterator
5127 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
5128 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5130 _RandomAccessIterator __r = __result_first;
5131 if (__r != __result_last)
5133 for (; __first != __last && __r != __result_last; (void) ++__first, ++__r)
5135 __make_heap<_Compare>(__result_first, __r, __comp);
5136 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
5137 for (; __first != __last; ++__first)
5138 if (__comp(*__first, *__result_first))
5140 *__result_first = *__first;
5141 __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first);
5143 __sort_heap<_Compare>(__result_first, __r, __comp);
5148 template <class _InputIterator, class _RandomAccessIterator, class _Compare>
5149 inline _LIBCPP_INLINE_VISIBILITY
5150 _RandomAccessIterator
5151 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5152 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5154 #ifdef _LIBCPP_DEBUG
5155 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5156 __debug_less<_Compare> __c(__comp);
5157 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);
5158 #else // _LIBCPP_DEBUG
5159 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5160 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
5161 #endif // _LIBCPP_DEBUG
5164 template <class _InputIterator, class _RandomAccessIterator>
5165 inline _LIBCPP_INLINE_VISIBILITY
5166 _RandomAccessIterator
5167 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5168 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
5170 return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
5171 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5176 template <class _Compare, class _RandomAccessIterator>
5178 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5180 // _Compare is known to be a reference type
5181 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5182 const difference_type __limit = 7;
5186 if (__nth == __last)
5188 difference_type __len = __last - __first;
5195 if (__comp(*--__last, *__first))
5196 swap(*__first, *__last);
5200 _RandomAccessIterator __m = __first;
5201 _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
5205 if (__len <= __limit)
5207 __selection_sort<_Compare>(__first, __last, __comp);
5210 // __len > __limit >= 3
5211 _RandomAccessIterator __m = __first + __len/2;
5212 _RandomAccessIterator __lm1 = __last;
5213 unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
5215 // partition [__first, __m) < *__m and *__m <= [__m, __last)
5216 // (this inhibits tossing elements equivalent to __m around unnecessarily)
5217 _RandomAccessIterator __i = __first;
5218 _RandomAccessIterator __j = __lm1;
5219 // j points beyond range to be tested, *__lm1 is known to be <= *__m
5220 // The search going up is known to be guarded but the search coming down isn't.
5221 // Prime the downward search with a guard.
5222 if (!__comp(*__i, *__m)) // if *__first == *__m
5224 // *__first == *__m, *__first doesn't go in first part
5225 // manually guard downward moving __j against __i
5230 // *__first == *__m, *__m <= all other elements
5231 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
5232 ++__i; // __first + 1
5234 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
5239 return; // [__first, __last) all equivalent elements
5240 if (__comp(*__first, *__i))
5250 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
5255 while (!__comp(*__first, *__i))
5257 while (__comp(*__first, *--__j))
5265 // [__first, __i) == *__first and *__first < [__i, __last)
5266 // The first part is sorted,
5269 // __nth_element the secod part
5270 // __nth_element<_Compare>(__i, __nth, __last, __comp);
5274 if (__comp(*__j, *__m))
5278 break; // found guard for downward moving __j, now use unguarded partition
5283 // j points beyond range to be tested, *__lm1 is known to be <= *__m
5284 // if not yet partitioned...
5287 // known that *(__i - 1) < *__m
5290 // __m still guards upward moving __i
5291 while (__comp(*__i, *__m))
5293 // It is now known that a guard exists for downward moving __j
5294 while (!__comp(*--__j, *__m))
5300 // It is known that __m != __j
5301 // If __m just moved, follow it
5307 // [__first, __i) < *__m and *__m <= [__i, __last)
5308 if (__i != __m && __comp(*__m, *__i))
5313 // [__first, __i) < *__i and *__i <= [__i+1, __last)
5318 // We were given a perfectly partitioned sequence. Coincidence?
5321 // Check for [__first, __i) already sorted
5322 __j = __m = __first;
5323 while (++__j != __i)
5325 if (__comp(*__j, *__m))
5326 // not yet sorted, so sort
5330 // [__first, __i) sorted
5335 // Check for [__i, __last) already sorted
5337 while (++__j != __last)
5339 if (__comp(*__j, *__m))
5340 // not yet sorted, so sort
5344 // [__i, __last) sorted
5349 // __nth_element on range containing __nth
5352 // __nth_element<_Compare>(__first, __nth, __i, __comp);
5357 // __nth_element<_Compare>(__i+1, __nth, __last, __comp);
5363 template <class _RandomAccessIterator, class _Compare>
5364 inline _LIBCPP_INLINE_VISIBILITY
5366 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5368 #ifdef _LIBCPP_DEBUG
5369 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5370 __debug_less<_Compare> __c(__comp);
5371 __nth_element<_Comp_ref>(__first, __nth, __last, __c);
5372 #else // _LIBCPP_DEBUG
5373 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5374 __nth_element<_Comp_ref>(__first, __nth, __last, __comp);
5375 #endif // _LIBCPP_DEBUG
5378 template <class _RandomAccessIterator>
5379 inline _LIBCPP_INLINE_VISIBILITY
5381 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
5383 _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5388 template <class _Compare, class _InputIterator1, class _InputIterator2>
5390 __includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5393 for (; __first2 != __last2; ++__first1)
5395 if (__first1 == __last1 || __comp(*__first2, *__first1))
5397 if (!__comp(*__first1, *__first2))
5403 template <class _InputIterator1, class _InputIterator2, class _Compare>
5404 inline _LIBCPP_INLINE_VISIBILITY
5406 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5409 #ifdef _LIBCPP_DEBUG
5410 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5411 __debug_less<_Compare> __c(__comp);
5412 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5413 #else // _LIBCPP_DEBUG
5414 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5415 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5416 #endif // _LIBCPP_DEBUG
5419 template <class _InputIterator1, class _InputIterator2>
5420 inline _LIBCPP_INLINE_VISIBILITY
5422 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
5424 return _VSTD::includes(__first1, __last1, __first2, __last2,
5425 __less<typename iterator_traits<_InputIterator1>::value_type,
5426 typename iterator_traits<_InputIterator2>::value_type>());
5431 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5433 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5434 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5436 for (; __first1 != __last1; ++__result)
5438 if (__first2 == __last2)
5439 return _VSTD::copy(__first1, __last1, __result);
5440 if (__comp(*__first2, *__first1))
5442 *__result = *__first2;
5447 *__result = *__first1;
5448 if (!__comp(*__first1, *__first2))
5453 return _VSTD::copy(__first2, __last2, __result);
5456 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5457 inline _LIBCPP_INLINE_VISIBILITY
5459 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5460 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5462 #ifdef _LIBCPP_DEBUG
5463 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5464 __debug_less<_Compare> __c(__comp);
5465 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5466 #else // _LIBCPP_DEBUG
5467 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5468 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5469 #endif // _LIBCPP_DEBUG
5472 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5473 inline _LIBCPP_INLINE_VISIBILITY
5475 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5476 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5478 return _VSTD::set_union(__first1, __last1, __first2, __last2, __result,
5479 __less<typename iterator_traits<_InputIterator1>::value_type,
5480 typename iterator_traits<_InputIterator2>::value_type>());
5485 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5487 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5488 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5490 while (__first1 != __last1 && __first2 != __last2)
5492 if (__comp(*__first1, *__first2))
5496 if (!__comp(*__first2, *__first1))
5498 *__result = *__first1;
5508 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5509 inline _LIBCPP_INLINE_VISIBILITY
5511 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5512 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5514 #ifdef _LIBCPP_DEBUG
5515 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5516 __debug_less<_Compare> __c(__comp);
5517 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5518 #else // _LIBCPP_DEBUG
5519 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5520 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5521 #endif // _LIBCPP_DEBUG
5524 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5525 inline _LIBCPP_INLINE_VISIBILITY
5527 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5528 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5530 return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result,
5531 __less<typename iterator_traits<_InputIterator1>::value_type,
5532 typename iterator_traits<_InputIterator2>::value_type>());
5537 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5539 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5540 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5542 while (__first1 != __last1)
5544 if (__first2 == __last2)
5545 return _VSTD::copy(__first1, __last1, __result);
5546 if (__comp(*__first1, *__first2))
5548 *__result = *__first1;
5554 if (!__comp(*__first2, *__first1))
5562 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5563 inline _LIBCPP_INLINE_VISIBILITY
5565 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5566 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5568 #ifdef _LIBCPP_DEBUG
5569 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5570 __debug_less<_Compare> __c(__comp);
5571 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5572 #else // _LIBCPP_DEBUG
5573 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5574 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5575 #endif // _LIBCPP_DEBUG
5578 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5579 inline _LIBCPP_INLINE_VISIBILITY
5581 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5582 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5584 return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result,
5585 __less<typename iterator_traits<_InputIterator1>::value_type,
5586 typename iterator_traits<_InputIterator2>::value_type>());
5589 // set_symmetric_difference
5591 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5593 __set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5594 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5596 while (__first1 != __last1)
5598 if (__first2 == __last2)
5599 return _VSTD::copy(__first1, __last1, __result);
5600 if (__comp(*__first1, *__first2))
5602 *__result = *__first1;
5608 if (__comp(*__first2, *__first1))
5610 *__result = *__first2;
5618 return _VSTD::copy(__first2, __last2, __result);
5621 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5622 inline _LIBCPP_INLINE_VISIBILITY
5624 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5625 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5627 #ifdef _LIBCPP_DEBUG
5628 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5629 __debug_less<_Compare> __c(__comp);
5630 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5631 #else // _LIBCPP_DEBUG
5632 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5633 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5634 #endif // _LIBCPP_DEBUG
5637 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5638 inline _LIBCPP_INLINE_VISIBILITY
5640 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5641 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5643 return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
5644 __less<typename iterator_traits<_InputIterator1>::value_type,
5645 typename iterator_traits<_InputIterator2>::value_type>());
5648 // lexicographical_compare
5650 template <class _Compare, class _InputIterator1, class _InputIterator2>
5652 __lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5653 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5655 for (; __first2 != __last2; ++__first1, (void) ++__first2)
5657 if (__first1 == __last1 || __comp(*__first1, *__first2))
5659 if (__comp(*__first2, *__first1))
5665 template <class _InputIterator1, class _InputIterator2, class _Compare>
5666 inline _LIBCPP_INLINE_VISIBILITY
5668 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5669 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5671 #ifdef _LIBCPP_DEBUG
5672 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5673 __debug_less<_Compare> __c(__comp);
5674 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5675 #else // _LIBCPP_DEBUG
5676 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5677 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5678 #endif // _LIBCPP_DEBUG
5681 template <class _InputIterator1, class _InputIterator2>
5682 inline _LIBCPP_INLINE_VISIBILITY
5684 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5685 _InputIterator2 __first2, _InputIterator2 __last2)
5687 return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,
5688 __less<typename iterator_traits<_InputIterator1>::value_type,
5689 typename iterator_traits<_InputIterator2>::value_type>());
5694 template <class _Compare, class _BidirectionalIterator>
5696 __next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5698 _BidirectionalIterator __i = __last;
5699 if (__first == __last || __first == --__i)
5703 _BidirectionalIterator __ip1 = __i;
5704 if (__comp(*--__i, *__ip1))
5706 _BidirectionalIterator __j = __last;
5707 while (!__comp(*__i, *--__j))
5710 _VSTD::reverse(__ip1, __last);
5715 _VSTD::reverse(__first, __last);
5721 template <class _BidirectionalIterator, class _Compare>
5722 inline _LIBCPP_INLINE_VISIBILITY
5724 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5726 #ifdef _LIBCPP_DEBUG
5727 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5728 __debug_less<_Compare> __c(__comp);
5729 return __next_permutation<_Comp_ref>(__first, __last, __c);
5730 #else // _LIBCPP_DEBUG
5731 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5732 return __next_permutation<_Comp_ref>(__first, __last, __comp);
5733 #endif // _LIBCPP_DEBUG
5736 template <class _BidirectionalIterator>
5737 inline _LIBCPP_INLINE_VISIBILITY
5739 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5741 return _VSTD::next_permutation(__first, __last,
5742 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5747 template <class _Compare, class _BidirectionalIterator>
5749 __prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5751 _BidirectionalIterator __i = __last;
5752 if (__first == __last || __first == --__i)
5756 _BidirectionalIterator __ip1 = __i;
5757 if (__comp(*__ip1, *--__i))
5759 _BidirectionalIterator __j = __last;
5760 while (!__comp(*--__j, *__i))
5763 _VSTD::reverse(__ip1, __last);
5768 _VSTD::reverse(__first, __last);
5774 template <class _BidirectionalIterator, class _Compare>
5775 inline _LIBCPP_INLINE_VISIBILITY
5777 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5779 #ifdef _LIBCPP_DEBUG
5780 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5781 __debug_less<_Compare> __c(__comp);
5782 return __prev_permutation<_Comp_ref>(__first, __last, __c);
5783 #else // _LIBCPP_DEBUG
5784 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5785 return __prev_permutation<_Comp_ref>(__first, __last, __comp);
5786 #endif // _LIBCPP_DEBUG
5789 template <class _BidirectionalIterator>
5790 inline _LIBCPP_INLINE_VISIBILITY
5792 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5794 return _VSTD::prev_permutation(__first, __last,
5795 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5798 _LIBCPP_END_NAMESPACE_STD
5800 #endif // _LIBCPP_ALGORITHM