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, removed in C++17
286 template <class RandomAccessIterator, class RandomNumberGenerator>
288 random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
289 RandomNumberGenerator& rand); // deprecated in C++14, removed in C++17
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_COMPILER_MSVC)
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
786 unsigned __ctz(unsigned __x) {
787 #ifndef _LIBCPP_COMPILER_MSVC
788 return static_cast<unsigned>(__builtin_ctz(__x));
790 static_assert(sizeof(unsigned) == sizeof(unsigned long), "");
791 static_assert(sizeof(unsigned long) == 4, "");
793 // Search from LSB to MSB for first set bit.
794 // Returns zero if no set bit is found.
795 if (_BitScanForward(&where, mask))
801 inline _LIBCPP_INLINE_VISIBILITY
802 unsigned long __ctz(unsigned long __x) {
803 #ifndef _LIBCPP_COMPILER_MSVC
804 return static_cast<unsigned long>(__builtin_ctzl(__x));
806 static_assert(sizeof(unsigned long) == sizeof(unsigned), "");
807 return __ctz(static_cast<unsigned>(__x));
811 inline _LIBCPP_INLINE_VISIBILITY
812 unsigned long long __ctz(unsigned long long __x) {
813 #ifndef _LIBCPP_COMPILER_MSVC
814 return static_cast<unsigned long long>(__builtin_ctzll(__x));
817 // Search from LSB to MSB for first set bit.
818 // Returns zero if no set bit is found.
819 #if defined(_LIBCPP_HAS_BITSCAN64)
820 (defined(_M_AMD64) || defined(__x86_64__))
821 if (_BitScanForward64(&where, mask))
822 return static_cast<int>(where);
824 // Win32 doesn't have _BitScanForward64 so emulate it with two 32 bit calls.
825 // Scan the Low Word.
826 if (_BitScanForward(&where, static_cast<unsigned long>(mask)))
828 // Scan the High Word.
829 if (_BitScanForward(&where, static_cast<unsigned long>(mask >> 32)))
830 return where + 32; // Create a bit offset from the LSB.
833 #endif // _LIBCPP_COMPILER_MSVC
836 // Precondition: __x != 0
837 inline _LIBCPP_INLINE_VISIBILITY
838 unsigned __clz(unsigned __x) {
839 #ifndef _LIBCPP_COMPILER_MSVC
840 return static_cast<unsigned>(__builtin_clz(__x));
842 static_assert(sizeof(unsigned) == sizeof(unsigned long), "");
843 static_assert(sizeof(unsigned long) == 4, "");
845 // Search from LSB to MSB for first set bit.
846 // Returns zero if no set bit is found.
847 if (_BitScanReverse(&where, mask))
849 return 32; // Undefined Behavior.
853 inline _LIBCPP_INLINE_VISIBILITY
854 unsigned long __clz(unsigned long __x) {
855 #ifndef _LIBCPP_COMPILER_MSVC
856 return static_cast<unsigned long>(__builtin_clzl (__x));
858 static_assert(sizeof(unsigned) == sizeof(unsigned long), "");
859 return __clz(static_cast<unsigned>(__x));
863 inline _LIBCPP_INLINE_VISIBILITY
864 unsigned long long __clz(unsigned long long __x) {
865 #ifndef _LIBCPP_COMPILER_MSVC
866 return static_cast<unsigned long long>(__builtin_clzll(__x));
869 // BitScanReverse scans from MSB to LSB for first set bit.
870 // Returns 0 if no set bit is found.
871 #if defined(_LIBCPP_HAS_BITSCAN64)
872 if (_BitScanReverse64(&where, mask))
873 return static_cast<int>(63 - where);
875 // Scan the high 32 bits.
876 if (_BitScanReverse(&where, static_cast<unsigned long>(mask >> 32)))
877 return 63 - (where + 32); // Create a bit offset from the MSB.
878 // Scan the low 32 bits.
879 if (_BitScanReverse(&where, static_cast<unsigned long>(mask)))
882 return 64; // Undefined Behavior.
883 #endif // _LIBCPP_COMPILER_MSVC
886 inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned __x) {
887 #ifndef _LIBCPP_COMPILER_MSVC
888 return __builtin_popcount (__x);
890 static_assert(sizeof(unsigned) == 4, "");
891 return __popcnt(__x);
895 inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long __x) {
896 #ifndef _LIBCPP_COMPILER_MSVC
897 return __builtin_popcountl (__x);
899 static_assert(sizeof(unsigned long) == 4, "");
900 return __popcnt(__x);
904 inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long long __x) {
905 #ifndef _LIBCPP_COMPILER_MSVC
906 return __builtin_popcountll(__x);
908 static_assert(sizeof(unsigned long long) == 8, "");
909 return __popcnt64(__x);
915 template <class _InputIterator, class _Predicate>
916 inline _LIBCPP_INLINE_VISIBILITY
918 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
920 for (; __first != __last; ++__first)
921 if (!__pred(*__first))
928 template <class _InputIterator, class _Predicate>
929 inline _LIBCPP_INLINE_VISIBILITY
931 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
933 for (; __first != __last; ++__first)
934 if (__pred(*__first))
941 template <class _InputIterator, class _Predicate>
942 inline _LIBCPP_INLINE_VISIBILITY
944 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
946 for (; __first != __last; ++__first)
947 if (__pred(*__first))
954 template <class _InputIterator, class _Function>
955 inline _LIBCPP_INLINE_VISIBILITY
957 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
959 for (; __first != __last; ++__first)
966 template <class _InputIterator, class _Tp>
967 inline _LIBCPP_INLINE_VISIBILITY
969 find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
971 for (; __first != __last; ++__first)
972 if (*__first == __value_)
979 template <class _InputIterator, class _Predicate>
980 inline _LIBCPP_INLINE_VISIBILITY
982 find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
984 for (; __first != __last; ++__first)
985 if (__pred(*__first))
992 template<class _InputIterator, class _Predicate>
993 inline _LIBCPP_INLINE_VISIBILITY
995 find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
997 for (; __first != __last; ++__first)
998 if (!__pred(*__first))
1005 template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
1007 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1008 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
1009 forward_iterator_tag, forward_iterator_tag)
1011 // modeled after search algorithm
1012 _ForwardIterator1 __r = __last1; // __last1 is the "default" answer
1013 if (__first2 == __last2)
1019 if (__first1 == __last1) // if source exhausted return last correct answer
1020 return __r; // (or __last1 if never found)
1021 if (__pred(*__first1, *__first2))
1025 // *__first1 matches *__first2, now match elements after here
1026 _ForwardIterator1 __m1 = __first1;
1027 _ForwardIterator2 __m2 = __first2;
1030 if (++__m2 == __last2)
1031 { // Pattern exhaused, record answer and search for another one
1036 if (++__m1 == __last1) // Source exhausted, return last answer
1038 if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first
1042 } // else there is a match, check next elements
1047 template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2>
1048 _BidirectionalIterator1
1049 __find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,
1050 _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred,
1051 bidirectional_iterator_tag, bidirectional_iterator_tag)
1053 // modeled after search algorithm (in reverse)
1054 if (__first2 == __last2)
1055 return __last1; // Everything matches an empty sequence
1056 _BidirectionalIterator1 __l1 = __last1;
1057 _BidirectionalIterator2 __l2 = __last2;
1061 // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks
1064 if (__first1 == __l1) // return __last1 if no element matches *__first2
1066 if (__pred(*--__l1, *__l2))
1069 // *__l1 matches *__l2, now match elements before here
1070 _BidirectionalIterator1 __m1 = __l1;
1071 _BidirectionalIterator2 __m2 = __l2;
1074 if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern)
1076 if (__m1 == __first1) // Otherwise if source exhaused, pattern not found
1078 if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1
1081 } // else there is a match, check next elements
1086 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1087 _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1
1088 __find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1089 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1090 random_access_iterator_tag, random_access_iterator_tag)
1092 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern
1093 typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;
1096 typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;
1097 if (__len1 < __len2)
1099 const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here
1100 _RandomAccessIterator1 __l1 = __last1;
1101 _RandomAccessIterator2 __l2 = __last2;
1109 if (__pred(*--__l1, *__l2))
1112 _RandomAccessIterator1 __m1 = __l1;
1113 _RandomAccessIterator2 __m2 = __l2;
1116 if (__m2 == __first2)
1118 // no need to check range on __m1 because __s guarantees we have enough source
1119 if (!__pred(*--__m1, *--__m2))
1127 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1128 inline _LIBCPP_INLINE_VISIBILITY
1130 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1131 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1133 return _VSTD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type>
1134 (__first1, __last1, __first2, __last2, __pred,
1135 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1136 typename iterator_traits<_ForwardIterator2>::iterator_category());
1139 template <class _ForwardIterator1, class _ForwardIterator2>
1140 inline _LIBCPP_INLINE_VISIBILITY
1142 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1143 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1145 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1146 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1147 return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1152 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1153 _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator1
1154 __find_first_of_ce(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1155 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1157 for (; __first1 != __last1; ++__first1)
1158 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1159 if (__pred(*__first1, *__j))
1165 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1166 inline _LIBCPP_INLINE_VISIBILITY
1168 find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1169 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1171 return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred);
1174 template <class _ForwardIterator1, class _ForwardIterator2>
1175 inline _LIBCPP_INLINE_VISIBILITY
1177 find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1178 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1180 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1181 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1182 return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1187 template <class _ForwardIterator, class _BinaryPredicate>
1188 inline _LIBCPP_INLINE_VISIBILITY
1190 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
1192 if (__first != __last)
1194 _ForwardIterator __i = __first;
1195 while (++__i != __last)
1197 if (__pred(*__first, *__i))
1205 template <class _ForwardIterator>
1206 inline _LIBCPP_INLINE_VISIBILITY
1208 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
1210 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1211 return _VSTD::adjacent_find(__first, __last, __equal_to<__v>());
1216 template <class _InputIterator, class _Tp>
1217 inline _LIBCPP_INLINE_VISIBILITY
1218 typename iterator_traits<_InputIterator>::difference_type
1219 count(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
1221 typename iterator_traits<_InputIterator>::difference_type __r(0);
1222 for (; __first != __last; ++__first)
1223 if (*__first == __value_)
1230 template <class _InputIterator, class _Predicate>
1231 inline _LIBCPP_INLINE_VISIBILITY
1232 typename iterator_traits<_InputIterator>::difference_type
1233 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
1235 typename iterator_traits<_InputIterator>::difference_type __r(0);
1236 for (; __first != __last; ++__first)
1237 if (__pred(*__first))
1244 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1245 inline _LIBCPP_INLINE_VISIBILITY
1246 pair<_InputIterator1, _InputIterator2>
1247 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1248 _InputIterator2 __first2, _BinaryPredicate __pred)
1250 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1251 if (!__pred(*__first1, *__first2))
1253 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1256 template <class _InputIterator1, class _InputIterator2>
1257 inline _LIBCPP_INLINE_VISIBILITY
1258 pair<_InputIterator1, _InputIterator2>
1259 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1261 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1262 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1263 return _VSTD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1266 #if _LIBCPP_STD_VER > 11
1267 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1268 inline _LIBCPP_INLINE_VISIBILITY
1269 pair<_InputIterator1, _InputIterator2>
1270 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1271 _InputIterator2 __first2, _InputIterator2 __last2,
1272 _BinaryPredicate __pred)
1274 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1275 if (!__pred(*__first1, *__first2))
1277 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1280 template <class _InputIterator1, class _InputIterator2>
1281 inline _LIBCPP_INLINE_VISIBILITY
1282 pair<_InputIterator1, _InputIterator2>
1283 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1284 _InputIterator2 __first2, _InputIterator2 __last2)
1286 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1287 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1288 return _VSTD::mismatch(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1294 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1295 inline _LIBCPP_INLINE_VISIBILITY
1297 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred)
1299 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1300 if (!__pred(*__first1, *__first2))
1305 template <class _InputIterator1, class _InputIterator2>
1306 inline _LIBCPP_INLINE_VISIBILITY
1308 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1310 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1311 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1312 return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1315 #if _LIBCPP_STD_VER > 11
1316 template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2>
1317 inline _LIBCPP_INLINE_VISIBILITY
1319 __equal(_InputIterator1 __first1, _InputIterator1 __last1,
1320 _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred,
1321 input_iterator_tag, input_iterator_tag )
1323 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1324 if (!__pred(*__first1, *__first2))
1326 return __first1 == __last1 && __first2 == __last2;
1329 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1330 inline _LIBCPP_INLINE_VISIBILITY
1332 __equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1333 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1334 random_access_iterator_tag, random_access_iterator_tag )
1336 if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
1338 return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2,
1339 typename add_lvalue_reference<_BinaryPredicate>::type>
1340 (__first1, __last1, __first2, __pred );
1343 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1344 inline _LIBCPP_INLINE_VISIBILITY
1346 equal(_InputIterator1 __first1, _InputIterator1 __last1,
1347 _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred )
1349 return _VSTD::__equal<typename add_lvalue_reference<_BinaryPredicate>::type>
1350 (__first1, __last1, __first2, __last2, __pred,
1351 typename iterator_traits<_InputIterator1>::iterator_category(),
1352 typename iterator_traits<_InputIterator2>::iterator_category());
1355 template <class _InputIterator1, class _InputIterator2>
1356 inline _LIBCPP_INLINE_VISIBILITY
1358 equal(_InputIterator1 __first1, _InputIterator1 __last1,
1359 _InputIterator2 __first2, _InputIterator2 __last2)
1361 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1362 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1363 return _VSTD::__equal(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(),
1364 typename iterator_traits<_InputIterator1>::iterator_category(),
1365 typename iterator_traits<_InputIterator2>::iterator_category());
1371 template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1373 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1374 _ForwardIterator2 __first2, _BinaryPredicate __pred)
1376 // shorten sequences as much as possible by lopping of any equal parts
1377 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1378 if (!__pred(*__first1, *__first2))
1382 // __first1 != __last1 && *__first1 != *__first2
1383 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1384 _D1 __l1 = _VSTD::distance(__first1, __last1);
1387 _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1);
1388 // For each element in [f1, l1) see if there are the same number of
1389 // equal elements in [f2, l2)
1390 for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
1392 // Have we already counted the number of *__i in [f1, l1)?
1393 for (_ForwardIterator1 __j = __first1; __j != __i; ++__j)
1394 if (__pred(*__j, *__i))
1397 // Count number of *__i in [f2, l2)
1399 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1400 if (__pred(*__i, *__j))
1404 // Count number of *__i in [__i, l1) (we can start with 1)
1406 for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
1407 if (__pred(*__i, *__j))
1417 template<class _ForwardIterator1, class _ForwardIterator2>
1418 inline _LIBCPP_INLINE_VISIBILITY
1420 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1421 _ForwardIterator2 __first2)
1423 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1424 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1425 return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1428 #if _LIBCPP_STD_VER > 11
1429 template<class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
1431 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1432 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1433 _BinaryPredicate __pred,
1434 forward_iterator_tag, forward_iterator_tag )
1436 // shorten sequences as much as possible by lopping of any equal parts
1437 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1438 if (!__pred(*__first1, *__first2))
1440 return __first1 == __last1 && __first2 == __last2;
1442 // __first1 != __last1 && __first2 != __last2 && *__first1 != *__first2
1443 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1444 _D1 __l1 = _VSTD::distance(__first1, __last1);
1446 typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2;
1447 _D2 __l2 = _VSTD::distance(__first2, __last2);
1451 // For each element in [f1, l1) see if there are the same number of
1452 // equal elements in [f2, l2)
1453 for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
1455 // Have we already counted the number of *__i in [f1, l1)?
1456 for (_ForwardIterator1 __j = __first1; __j != __i; ++__j)
1457 if (__pred(*__j, *__i))
1460 // Count number of *__i in [f2, l2)
1462 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1463 if (__pred(*__i, *__j))
1467 // Count number of *__i in [__i, l1) (we can start with 1)
1469 for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
1470 if (__pred(*__i, *__j))
1480 template<class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1482 __is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1,
1483 _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2,
1484 _BinaryPredicate __pred,
1485 random_access_iterator_tag, random_access_iterator_tag )
1487 if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
1489 return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2,
1490 typename add_lvalue_reference<_BinaryPredicate>::type>
1491 (__first1, __last1, __first2, __pred );
1494 template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1495 inline _LIBCPP_INLINE_VISIBILITY
1497 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1498 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1499 _BinaryPredicate __pred )
1501 return _VSTD::__is_permutation<typename add_lvalue_reference<_BinaryPredicate>::type>
1502 (__first1, __last1, __first2, __last2, __pred,
1503 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1504 typename iterator_traits<_ForwardIterator2>::iterator_category());
1507 template<class _ForwardIterator1, class _ForwardIterator2>
1508 inline _LIBCPP_INLINE_VISIBILITY
1510 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1511 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1513 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1514 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1515 return _VSTD::__is_permutation(__first1, __last1, __first2, __last2,
1516 __equal_to<__v1, __v2>(),
1517 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1518 typename iterator_traits<_ForwardIterator2>::iterator_category());
1524 template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
1525 pair<_ForwardIterator1, _ForwardIterator1>
1526 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1527 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
1528 forward_iterator_tag, forward_iterator_tag)
1530 if (__first2 == __last2)
1531 return make_pair(__first1, __first1); // Everything matches an empty sequence
1534 // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks
1537 if (__first1 == __last1) // return __last1 if no element matches *__first2
1538 return make_pair(__last1, __last1);
1539 if (__pred(*__first1, *__first2))
1543 // *__first1 matches *__first2, now match elements after here
1544 _ForwardIterator1 __m1 = __first1;
1545 _ForwardIterator2 __m2 = __first2;
1548 if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern)
1549 return make_pair(__first1, __m1);
1550 if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found
1551 return make_pair(__last1, __last1);
1552 if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1
1556 } // else there is a match, check next elements
1561 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1562 _LIBCPP_CONSTEXPR_AFTER_CXX11
1563 pair<_RandomAccessIterator1, _RandomAccessIterator1>
1564 __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1565 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1566 random_access_iterator_tag, random_access_iterator_tag)
1568 typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1;
1569 typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2;
1570 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern
1571 const _D2 __len2 = __last2 - __first2;
1573 return make_pair(__first1, __first1);
1574 const _D1 __len1 = __last1 - __first1;
1575 if (__len1 < __len2)
1576 return make_pair(__last1, __last1);
1577 const _RandomAccessIterator1 __s = __last1 - (__len2 - 1); // Start of pattern match can't go beyond here
1583 if (__first1 == __s)
1584 return make_pair(__last1, __last1);
1585 if (__pred(*__first1, *__first2))
1590 _RandomAccessIterator1 __m1 = __first1;
1591 _RandomAccessIterator2 __m2 = __first2;
1594 if (++__m2 == __last2)
1595 return make_pair(__first1, __first1 + __len2);
1596 ++__m1; // no need to check range on __m1 because __s guarantees we have enough source
1597 if (!__pred(*__m1, *__m2))
1606 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1607 inline _LIBCPP_INLINE_VISIBILITY
1609 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1610 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1612 return _VSTD::__search<typename add_lvalue_reference<_BinaryPredicate>::type>
1613 (__first1, __last1, __first2, __last2, __pred,
1614 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1615 typename iterator_traits<_ForwardIterator2>::iterator_category())
1619 template <class _ForwardIterator1, class _ForwardIterator2>
1620 inline _LIBCPP_INLINE_VISIBILITY
1622 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1623 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1625 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1626 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1627 return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1632 template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp>
1634 __search_n(_ForwardIterator __first, _ForwardIterator __last,
1635 _Size __count, const _Tp& __value_, _BinaryPredicate __pred, forward_iterator_tag)
1641 // Find first element in sequence that matchs __value_, with a mininum of loop checks
1644 if (__first == __last) // return __last if no element matches __value_
1646 if (__pred(*__first, __value_))
1650 // *__first matches __value_, now match elements after here
1651 _ForwardIterator __m = __first;
1655 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1657 if (++__m == __last) // Otherwise if source exhaused, pattern not found
1659 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1664 } // else there is a match, check next elements
1669 template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp>
1670 _RandomAccessIterator
1671 __search_n(_RandomAccessIterator __first, _RandomAccessIterator __last,
1672 _Size __count, const _Tp& __value_, _BinaryPredicate __pred, random_access_iterator_tag)
1676 _Size __len = static_cast<_Size>(__last - __first);
1677 if (__len < __count)
1679 const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here
1682 // Find first element in sequence that matchs __value_, with a mininum of loop checks
1685 if (__first >= __s) // return __last if no element matches __value_
1687 if (__pred(*__first, __value_))
1691 // *__first matches __value_, now match elements after here
1692 _RandomAccessIterator __m = __first;
1696 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1698 ++__m; // no need to check range on __m because __s guarantees we have enough source
1699 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1704 } // else there is a match, check next elements
1709 template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
1710 inline _LIBCPP_INLINE_VISIBILITY
1712 search_n(_ForwardIterator __first, _ForwardIterator __last,
1713 _Size __count, const _Tp& __value_, _BinaryPredicate __pred)
1715 return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>
1716 (__first, __last, __convert_to_integral(__count), __value_, __pred,
1717 typename iterator_traits<_ForwardIterator>::iterator_category());
1720 template <class _ForwardIterator, class _Size, class _Tp>
1721 inline _LIBCPP_INLINE_VISIBILITY
1723 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
1725 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1726 return _VSTD::search_n(__first, __last, __convert_to_integral(__count),
1727 __value_, __equal_to<__v, _Tp>());
1731 template <class _Iter>
1732 inline _LIBCPP_INLINE_VISIBILITY
1734 __unwrap_iter(_Iter __i)
1739 template <class _Tp>
1740 inline _LIBCPP_INLINE_VISIBILITY
1743 is_trivially_copy_assignable<_Tp>::value,
1746 __unwrap_iter(move_iterator<_Tp*> __i)
1751 #if _LIBCPP_DEBUG_LEVEL < 2
1753 template <class _Tp>
1754 inline _LIBCPP_INLINE_VISIBILITY
1757 is_trivially_copy_assignable<_Tp>::value,
1760 __unwrap_iter(__wrap_iter<_Tp*> __i)
1767 template <class _Tp>
1768 inline _LIBCPP_INLINE_VISIBILITY
1771 is_trivially_copy_assignable<_Tp>::value,
1774 __unwrap_iter(__wrap_iter<_Tp*> __i)
1779 #endif // _LIBCPP_DEBUG_LEVEL < 2
1781 template <class _InputIterator, class _OutputIterator>
1782 inline _LIBCPP_INLINE_VISIBILITY
1784 __copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1786 for (; __first != __last; ++__first, (void) ++__result)
1787 *__result = *__first;
1791 template <class _Tp, class _Up>
1792 inline _LIBCPP_INLINE_VISIBILITY
1795 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1796 is_trivially_copy_assignable<_Up>::value,
1799 __copy(_Tp* __first, _Tp* __last, _Up* __result)
1801 const size_t __n = static_cast<size_t>(__last - __first);
1803 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1804 return __result + __n;
1807 template <class _InputIterator, class _OutputIterator>
1808 inline _LIBCPP_INLINE_VISIBILITY
1810 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1812 return _VSTD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1817 template <class _BidirectionalIterator, class _OutputIterator>
1818 inline _LIBCPP_INLINE_VISIBILITY
1820 __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
1822 while (__first != __last)
1823 *--__result = *--__last;
1827 template <class _Tp, class _Up>
1828 inline _LIBCPP_INLINE_VISIBILITY
1831 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1832 is_trivially_copy_assignable<_Up>::value,
1835 __copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
1837 const size_t __n = static_cast<size_t>(__last - __first);
1841 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1846 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1847 inline _LIBCPP_INLINE_VISIBILITY
1848 _BidirectionalIterator2
1849 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1850 _BidirectionalIterator2 __result)
1852 return _VSTD::__copy_backward(__unwrap_iter(__first),
1853 __unwrap_iter(__last),
1854 __unwrap_iter(__result));
1859 template<class _InputIterator, class _OutputIterator, class _Predicate>
1860 inline _LIBCPP_INLINE_VISIBILITY
1862 copy_if(_InputIterator __first, _InputIterator __last,
1863 _OutputIterator __result, _Predicate __pred)
1865 for (; __first != __last; ++__first)
1867 if (__pred(*__first))
1869 *__result = *__first;
1878 template<class _InputIterator, class _Size, class _OutputIterator>
1879 inline _LIBCPP_INLINE_VISIBILITY
1882 __is_input_iterator<_InputIterator>::value &&
1883 !__is_random_access_iterator<_InputIterator>::value,
1886 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1888 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
1889 _IntegralSize __n = __orig_n;
1892 *__result = *__first;
1894 for (--__n; __n > 0; --__n)
1897 *__result = *__first;
1904 template<class _InputIterator, class _Size, class _OutputIterator>
1905 inline _LIBCPP_INLINE_VISIBILITY
1908 __is_random_access_iterator<_InputIterator>::value,
1911 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1913 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
1914 _IntegralSize __n = __orig_n;
1915 return _VSTD::copy(__first, __first + __n, __result);
1920 template <class _InputIterator, class _OutputIterator>
1921 inline _LIBCPP_INLINE_VISIBILITY
1923 __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1925 for (; __first != __last; ++__first, (void) ++__result)
1926 *__result = _VSTD::move(*__first);
1930 template <class _Tp, class _Up>
1931 inline _LIBCPP_INLINE_VISIBILITY
1934 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1935 is_trivially_copy_assignable<_Up>::value,
1938 __move(_Tp* __first, _Tp* __last, _Up* __result)
1940 const size_t __n = static_cast<size_t>(__last - __first);
1942 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1943 return __result + __n;
1946 template <class _InputIterator, class _OutputIterator>
1947 inline _LIBCPP_INLINE_VISIBILITY
1949 move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1951 return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1956 template <class _InputIterator, class _OutputIterator>
1957 inline _LIBCPP_INLINE_VISIBILITY
1959 __move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1961 while (__first != __last)
1962 *--__result = _VSTD::move(*--__last);
1966 template <class _Tp, class _Up>
1967 inline _LIBCPP_INLINE_VISIBILITY
1970 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1971 is_trivially_copy_assignable<_Up>::value,
1974 __move_backward(_Tp* __first, _Tp* __last, _Up* __result)
1976 const size_t __n = static_cast<size_t>(__last - __first);
1980 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1985 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1986 inline _LIBCPP_INLINE_VISIBILITY
1987 _BidirectionalIterator2
1988 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1989 _BidirectionalIterator2 __result)
1991 return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1996 // moved to <type_traits> for better swap / noexcept support
2000 template <class _InputIterator, class _OutputIterator, class _UnaryOperation>
2001 inline _LIBCPP_INLINE_VISIBILITY
2003 transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op)
2005 for (; __first != __last; ++__first, (void) ++__result)
2006 *__result = __op(*__first);
2010 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation>
2011 inline _LIBCPP_INLINE_VISIBILITY
2013 transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
2014 _OutputIterator __result, _BinaryOperation __binary_op)
2016 for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result)
2017 *__result = __binary_op(*__first1, *__first2);
2023 template <class _ForwardIterator, class _Tp>
2024 inline _LIBCPP_INLINE_VISIBILITY
2026 replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value)
2028 for (; __first != __last; ++__first)
2029 if (*__first == __old_value)
2030 *__first = __new_value;
2035 template <class _ForwardIterator, class _Predicate, class _Tp>
2036 inline _LIBCPP_INLINE_VISIBILITY
2038 replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value)
2040 for (; __first != __last; ++__first)
2041 if (__pred(*__first))
2042 *__first = __new_value;
2047 template <class _InputIterator, class _OutputIterator, class _Tp>
2048 inline _LIBCPP_INLINE_VISIBILITY
2050 replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
2051 const _Tp& __old_value, const _Tp& __new_value)
2053 for (; __first != __last; ++__first, (void) ++__result)
2054 if (*__first == __old_value)
2055 *__result = __new_value;
2057 *__result = *__first;
2063 template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp>
2064 inline _LIBCPP_INLINE_VISIBILITY
2066 replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
2067 _Predicate __pred, const _Tp& __new_value)
2069 for (; __first != __last; ++__first, (void) ++__result)
2070 if (__pred(*__first))
2071 *__result = __new_value;
2073 *__result = *__first;
2079 template <class _OutputIterator, class _Size, class _Tp>
2080 inline _LIBCPP_INLINE_VISIBILITY
2082 __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2084 for (; __n > 0; ++__first, (void) --__n)
2085 *__first = __value_;
2089 template <class _Tp, class _Size, class _Up>
2090 inline _LIBCPP_INLINE_VISIBILITY
2093 is_integral<_Tp>::value && sizeof(_Tp) == 1 &&
2094 !is_same<_Tp, bool>::value &&
2095 is_integral<_Up>::value && sizeof(_Up) == 1,
2098 __fill_n(_Tp* __first, _Size __n,_Up __value_)
2101 _VSTD::memset(__first, (unsigned char)__value_, (size_t)(__n));
2102 return __first + __n;
2105 template <class _OutputIterator, class _Size, class _Tp>
2106 inline _LIBCPP_INLINE_VISIBILITY
2108 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2110 return _VSTD::__fill_n(__first, __convert_to_integral(__n), __value_);
2115 template <class _ForwardIterator, class _Tp>
2116 inline _LIBCPP_INLINE_VISIBILITY
2118 __fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
2120 for (; __first != __last; ++__first)
2121 *__first = __value_;
2124 template <class _RandomAccessIterator, class _Tp>
2125 inline _LIBCPP_INLINE_VISIBILITY
2127 __fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag)
2129 _VSTD::fill_n(__first, __last - __first, __value_);
2132 template <class _ForwardIterator, class _Tp>
2133 inline _LIBCPP_INLINE_VISIBILITY
2135 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2137 _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category());
2142 template <class _ForwardIterator, class _Generator>
2143 inline _LIBCPP_INLINE_VISIBILITY
2145 generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
2147 for (; __first != __last; ++__first)
2153 template <class _OutputIterator, class _Size, class _Generator>
2154 inline _LIBCPP_INLINE_VISIBILITY
2156 generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen)
2158 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
2159 _IntegralSize __n = __orig_n;
2160 for (; __n > 0; ++__first, (void) --__n)
2167 template <class _ForwardIterator, class _Tp>
2169 remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2171 __first = _VSTD::find(__first, __last, __value_);
2172 if (__first != __last)
2174 _ForwardIterator __i = __first;
2175 while (++__i != __last)
2177 if (!(*__i == __value_))
2179 *__first = _VSTD::move(*__i);
2189 template <class _ForwardIterator, class _Predicate>
2191 remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2193 __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
2194 (__first, __last, __pred);
2195 if (__first != __last)
2197 _ForwardIterator __i = __first;
2198 while (++__i != __last)
2202 *__first = _VSTD::move(*__i);
2212 template <class _InputIterator, class _OutputIterator, class _Tp>
2213 inline _LIBCPP_INLINE_VISIBILITY
2215 remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_)
2217 for (; __first != __last; ++__first)
2219 if (!(*__first == __value_))
2221 *__result = *__first;
2230 template <class _InputIterator, class _OutputIterator, class _Predicate>
2231 inline _LIBCPP_INLINE_VISIBILITY
2233 remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
2235 for (; __first != __last; ++__first)
2237 if (!__pred(*__first))
2239 *__result = *__first;
2248 template <class _ForwardIterator, class _BinaryPredicate>
2250 unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
2252 __first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type>
2253 (__first, __last, __pred);
2254 if (__first != __last)
2258 _ForwardIterator __i = __first;
2259 for (++__i; ++__i != __last;)
2260 if (!__pred(*__first, *__i))
2261 *++__first = _VSTD::move(*__i);
2267 template <class _ForwardIterator>
2268 inline _LIBCPP_INLINE_VISIBILITY
2270 unique(_ForwardIterator __first, _ForwardIterator __last)
2272 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
2273 return _VSTD::unique(__first, __last, __equal_to<__v>());
2278 template <class _BinaryPredicate, class _InputIterator, class _OutputIterator>
2280 __unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2281 input_iterator_tag, output_iterator_tag)
2283 if (__first != __last)
2285 typename iterator_traits<_InputIterator>::value_type __t(*__first);
2288 while (++__first != __last)
2290 if (!__pred(__t, *__first))
2301 template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator>
2303 __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2304 forward_iterator_tag, output_iterator_tag)
2306 if (__first != __last)
2308 _ForwardIterator __i = __first;
2311 while (++__first != __last)
2313 if (!__pred(*__i, *__first))
2315 *__result = *__first;
2324 template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator>
2326 __unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred,
2327 input_iterator_tag, forward_iterator_tag)
2329 if (__first != __last)
2331 *__result = *__first;
2332 while (++__first != __last)
2333 if (!__pred(*__result, *__first))
2334 *++__result = *__first;
2340 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
2341 inline _LIBCPP_INLINE_VISIBILITY
2343 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred)
2345 return _VSTD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type>
2346 (__first, __last, __result, __pred,
2347 typename iterator_traits<_InputIterator>::iterator_category(),
2348 typename iterator_traits<_OutputIterator>::iterator_category());
2351 template <class _InputIterator, class _OutputIterator>
2352 inline _LIBCPP_INLINE_VISIBILITY
2354 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
2356 typedef typename iterator_traits<_InputIterator>::value_type __v;
2357 return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());
2362 template <class _BidirectionalIterator>
2363 inline _LIBCPP_INLINE_VISIBILITY
2365 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
2367 while (__first != __last)
2369 if (__first == --__last)
2371 _VSTD::iter_swap(__first, __last);
2376 template <class _RandomAccessIterator>
2377 inline _LIBCPP_INLINE_VISIBILITY
2379 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
2381 if (__first != __last)
2382 for (; __first < --__last; ++__first)
2383 _VSTD::iter_swap(__first, __last);
2386 template <class _BidirectionalIterator>
2387 inline _LIBCPP_INLINE_VISIBILITY
2389 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
2391 _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());
2396 template <class _BidirectionalIterator, class _OutputIterator>
2397 inline _LIBCPP_INLINE_VISIBILITY
2399 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
2401 for (; __first != __last; ++__result)
2402 *__result = *--__last;
2408 template <class _ForwardIterator>
2410 __rotate_left(_ForwardIterator __first, _ForwardIterator __last)
2412 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2413 value_type __tmp = _VSTD::move(*__first);
2414 _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
2415 *__lm1 = _VSTD::move(__tmp);
2419 template <class _BidirectionalIterator>
2420 _BidirectionalIterator
2421 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
2423 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
2424 _BidirectionalIterator __lm1 = _VSTD::prev(__last);
2425 value_type __tmp = _VSTD::move(*__lm1);
2426 _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
2427 *__first = _VSTD::move(__tmp);
2431 template <class _ForwardIterator>
2433 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2435 _ForwardIterator __i = __middle;
2438 swap(*__first, *__i);
2440 if (++__i == __last)
2442 if (__first == __middle)
2445 _ForwardIterator __r = __first;
2446 if (__first != __middle)
2451 swap(*__first, *__i);
2453 if (++__i == __last)
2455 if (__first == __middle)
2459 else if (__first == __middle)
2466 template<typename _Integral>
2467 inline _LIBCPP_INLINE_VISIBILITY
2469 __algo_gcd(_Integral __x, _Integral __y)
2473 _Integral __t = __x % __y;
2480 template<typename _RandomAccessIterator>
2481 _RandomAccessIterator
2482 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
2484 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2485 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
2487 const difference_type __m1 = __middle - __first;
2488 const difference_type __m2 = __last - __middle;
2491 _VSTD::swap_ranges(__first, __middle, __middle);
2494 const difference_type __g = _VSTD::__algo_gcd(__m1, __m2);
2495 for (_RandomAccessIterator __p = __first + __g; __p != __first;)
2497 value_type __t(_VSTD::move(*--__p));
2498 _RandomAccessIterator __p1 = __p;
2499 _RandomAccessIterator __p2 = __p1 + __m1;
2502 *__p1 = _VSTD::move(*__p2);
2504 const difference_type __d = __last - __p2;
2508 __p2 = __first + (__m1 - __d);
2509 } while (__p2 != __p);
2510 *__p1 = _VSTD::move(__t);
2512 return __first + __m2;
2515 template <class _ForwardIterator>
2516 inline _LIBCPP_INLINE_VISIBILITY
2518 __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
2519 _VSTD::forward_iterator_tag)
2521 typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type;
2522 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2524 if (_VSTD::next(__first) == __middle)
2525 return _VSTD::__rotate_left(__first, __last);
2527 return _VSTD::__rotate_forward(__first, __middle, __last);
2530 template <class _BidirectionalIterator>
2531 inline _LIBCPP_INLINE_VISIBILITY
2532 _BidirectionalIterator
2533 __rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
2534 _VSTD::bidirectional_iterator_tag)
2536 typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type;
2537 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2539 if (_VSTD::next(__first) == __middle)
2540 return _VSTD::__rotate_left(__first, __last);
2541 if (_VSTD::next(__middle) == __last)
2542 return _VSTD::__rotate_right(__first, __last);
2544 return _VSTD::__rotate_forward(__first, __middle, __last);
2547 template <class _RandomAccessIterator>
2548 inline _LIBCPP_INLINE_VISIBILITY
2549 _RandomAccessIterator
2550 __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
2551 _VSTD::random_access_iterator_tag)
2553 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
2554 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2556 if (_VSTD::next(__first) == __middle)
2557 return _VSTD::__rotate_left(__first, __last);
2558 if (_VSTD::next(__middle) == __last)
2559 return _VSTD::__rotate_right(__first, __last);
2560 return _VSTD::__rotate_gcd(__first, __middle, __last);
2562 return _VSTD::__rotate_forward(__first, __middle, __last);
2565 template <class _ForwardIterator>
2566 inline _LIBCPP_INLINE_VISIBILITY
2568 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2570 if (__first == __middle)
2572 if (__middle == __last)
2574 return _VSTD::__rotate(__first, __middle, __last,
2575 typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());
2580 template <class _ForwardIterator, class _OutputIterator>
2581 inline _LIBCPP_INLINE_VISIBILITY
2583 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
2585 return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));
2590 template <class _ForwardIterator, class _Compare>
2591 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2593 min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2595 if (__first != __last)
2597 _ForwardIterator __i = __first;
2598 while (++__i != __last)
2599 if (__comp(*__i, *__first))
2605 template <class _ForwardIterator>
2606 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2608 min_element(_ForwardIterator __first, _ForwardIterator __last)
2610 return _VSTD::min_element(__first, __last,
2611 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2616 template <class _Tp, class _Compare>
2617 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2619 min(const _Tp& __a, const _Tp& __b, _Compare __comp)
2621 return __comp(__b, __a) ? __b : __a;
2624 template <class _Tp>
2625 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2627 min(const _Tp& __a, const _Tp& __b)
2629 return _VSTD::min(__a, __b, __less<_Tp>());
2632 #ifndef _LIBCPP_CXX03_LANG
2634 template<class _Tp, class _Compare>
2635 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2637 min(initializer_list<_Tp> __t, _Compare __comp)
2639 return *_VSTD::min_element(__t.begin(), __t.end(), __comp);
2643 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2645 min(initializer_list<_Tp> __t)
2647 return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>());
2650 #endif // _LIBCPP_CXX03_LANG
2654 template <class _ForwardIterator, class _Compare>
2655 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2657 max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2659 if (__first != __last)
2661 _ForwardIterator __i = __first;
2662 while (++__i != __last)
2663 if (__comp(*__first, *__i))
2670 template <class _ForwardIterator>
2671 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2673 max_element(_ForwardIterator __first, _ForwardIterator __last)
2675 return _VSTD::max_element(__first, __last,
2676 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2681 template <class _Tp, class _Compare>
2682 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2684 max(const _Tp& __a, const _Tp& __b, _Compare __comp)
2686 return __comp(__a, __b) ? __b : __a;
2689 template <class _Tp>
2690 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2692 max(const _Tp& __a, const _Tp& __b)
2694 return _VSTD::max(__a, __b, __less<_Tp>());
2697 #ifndef _LIBCPP_CXX03_LANG
2699 template<class _Tp, class _Compare>
2700 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2702 max(initializer_list<_Tp> __t, _Compare __comp)
2704 return *_VSTD::max_element(__t.begin(), __t.end(), __comp);
2708 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2710 max(initializer_list<_Tp> __t)
2712 return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>());
2715 #endif // _LIBCPP_CXX03_LANG
2717 #if _LIBCPP_STD_VER > 14
2719 template<class _Tp, class _Compare>
2720 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
2722 clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
2724 _LIBCPP_ASSERT(!__comp(__hi, __lo), "Bad bounds passed to std::clamp");
2725 return __comp(__v, __lo) ? __lo : __comp(__hi, __v) ? __hi : __v;
2730 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
2732 clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi)
2734 return _VSTD::clamp(__v, __lo, __hi, __less<_Tp>());
2740 template <class _ForwardIterator, class _Compare>
2741 _LIBCPP_CONSTEXPR_AFTER_CXX11
2742 std::pair<_ForwardIterator, _ForwardIterator>
2743 minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2745 std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);
2746 if (__first != __last)
2748 if (++__first != __last)
2750 if (__comp(*__first, *__result.first))
2751 __result.first = __first;
2753 __result.second = __first;
2754 while (++__first != __last)
2756 _ForwardIterator __i = __first;
2757 if (++__first == __last)
2759 if (__comp(*__i, *__result.first))
2760 __result.first = __i;
2761 else if (!__comp(*__i, *__result.second))
2762 __result.second = __i;
2767 if (__comp(*__first, *__i))
2769 if (__comp(*__first, *__result.first))
2770 __result.first = __first;
2771 if (!__comp(*__i, *__result.second))
2772 __result.second = __i;
2776 if (__comp(*__i, *__result.first))
2777 __result.first = __i;
2778 if (!__comp(*__first, *__result.second))
2779 __result.second = __first;
2788 template <class _ForwardIterator>
2789 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2790 std::pair<_ForwardIterator, _ForwardIterator>
2791 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
2793 return _VSTD::minmax_element(__first, __last,
2794 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2799 template<class _Tp, class _Compare>
2800 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2801 pair<const _Tp&, const _Tp&>
2802 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
2804 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) :
2805 pair<const _Tp&, const _Tp&>(__a, __b);
2809 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2810 pair<const _Tp&, const _Tp&>
2811 minmax(const _Tp& __a, const _Tp& __b)
2813 return _VSTD::minmax(__a, __b, __less<_Tp>());
2816 #ifndef _LIBCPP_CXX03_LANG
2818 template<class _Tp, class _Compare>
2819 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2821 minmax(initializer_list<_Tp> __t, _Compare __comp)
2823 typedef typename initializer_list<_Tp>::const_iterator _Iter;
2824 _Iter __first = __t.begin();
2825 _Iter __last = __t.end();
2826 std::pair<_Tp, _Tp> __result(*__first, *__first);
2829 if (__t.size() % 2 == 0)
2831 if (__comp(*__first, __result.first))
2832 __result.first = *__first;
2834 __result.second = *__first;
2838 while (__first != __last)
2840 _Tp __prev = *__first++;
2841 if (__comp(*__first, __prev)) {
2842 if ( __comp(*__first, __result.first)) __result.first = *__first;
2843 if (!__comp(__prev, __result.second)) __result.second = __prev;
2846 if ( __comp(__prev, __result.first)) __result.first = __prev;
2847 if (!__comp(*__first, __result.second)) __result.second = *__first;
2856 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2858 minmax(initializer_list<_Tp> __t)
2860 return _VSTD::minmax(__t, __less<_Tp>());
2863 #endif // _LIBCPP_CXX03_LANG
2867 // __independent_bits_engine
2869 template <unsigned long long _Xp, size_t _Rp>
2872 static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp
2873 : __log2_imp<_Xp, _Rp - 1>::value;
2876 template <unsigned long long _Xp>
2877 struct __log2_imp<_Xp, 0>
2879 static const size_t value = 0;
2882 template <size_t _Rp>
2883 struct __log2_imp<0, _Rp>
2885 static const size_t value = _Rp + 1;
2888 template <class _UI, _UI _Xp>
2891 static const size_t value = __log2_imp<_Xp,
2892 sizeof(_UI) * __CHAR_BIT__ - 1>::value;
2895 template<class _Engine, class _UIntType>
2896 class __independent_bits_engine
2900 typedef _UIntType result_type;
2903 typedef typename _Engine::result_type _Engine_result_type;
2904 typedef typename conditional
2906 sizeof(_Engine_result_type) <= sizeof(result_type),
2909 >::type _Working_result_type;
2916 _Working_result_type __y0_;
2917 _Working_result_type __y1_;
2918 _Engine_result_type __mask0_;
2919 _Engine_result_type __mask1_;
2921 #ifdef _LIBCPP_CXX03_LANG
2922 static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
2923 + _Working_result_type(1);
2925 static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()
2926 + _Working_result_type(1);
2928 static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value;
2929 static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits;
2930 static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
2933 // constructors and seeding functions
2934 __independent_bits_engine(_Engine& __e, size_t __w);
2936 // generating functions
2937 result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
2940 result_type __eval(false_type);
2941 result_type __eval(true_type);
2944 template<class _Engine, class _UIntType>
2945 __independent_bits_engine<_Engine, _UIntType>
2946 ::__independent_bits_engine(_Engine& __e, size_t __w)
2950 __n_ = __w_ / __m + (__w_ % __m != 0);
2951 __w0_ = __w_ / __n_;
2954 else if (__w0_ < _WDt)
2955 __y0_ = (_Rp >> __w0_) << __w0_;
2958 if (_Rp - __y0_ > __y0_ / __n_)
2961 __w0_ = __w_ / __n_;
2963 __y0_ = (_Rp >> __w0_) << __w0_;
2967 __n0_ = __n_ - __w_ % __n_;
2968 if (__w0_ < _WDt - 1)
2969 __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1);
2972 __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :
2973 _Engine_result_type(0);
2974 __mask1_ = __w0_ < _EDt - 1 ?
2975 _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :
2976 _Engine_result_type(~0);
2979 template<class _Engine, class _UIntType>
2982 __independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
2984 return static_cast<result_type>(__e_() & __mask0_);
2987 template<class _Engine, class _UIntType>
2989 __independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
2991 result_type _Sp = 0;
2992 for (size_t __k = 0; __k < __n0_; ++__k)
2994 _Engine_result_type __u;
2997 __u = __e_() - _Engine::min();
2998 } while (__u >= __y0_);
3003 _Sp += __u & __mask0_;
3005 for (size_t __k = __n0_; __k < __n_; ++__k)
3007 _Engine_result_type __u;
3010 __u = __e_() - _Engine::min();
3011 } while (__u >= __y1_);
3012 if (__w0_ < _WDt - 1)
3016 _Sp += __u & __mask1_;
3021 // uniform_int_distribution
3023 template<class _IntType = int>
3024 class uniform_int_distribution
3028 typedef _IntType result_type;
3035 typedef uniform_int_distribution distribution_type;
3037 explicit param_type(result_type __a = 0,
3038 result_type __b = numeric_limits<result_type>::max())
3039 : __a_(__a), __b_(__b) {}
3041 result_type a() const {return __a_;}
3042 result_type b() const {return __b_;}
3044 friend bool operator==(const param_type& __x, const param_type& __y)
3045 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
3046 friend bool operator!=(const param_type& __x, const param_type& __y)
3047 {return !(__x == __y);}
3054 // constructors and reset functions
3055 explicit uniform_int_distribution(result_type __a = 0,
3056 result_type __b = numeric_limits<result_type>::max())
3057 : __p_(param_type(__a, __b)) {}
3058 explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
3061 // generating functions
3062 template<class _URNG> result_type operator()(_URNG& __g)
3063 {return (*this)(__g, __p_);}
3064 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3066 // property functions
3067 result_type a() const {return __p_.a();}
3068 result_type b() const {return __p_.b();}
3070 param_type param() const {return __p_;}
3071 void param(const param_type& __p) {__p_ = __p;}
3073 result_type min() const {return a();}
3074 result_type max() const {return b();}
3076 friend bool operator==(const uniform_int_distribution& __x,
3077 const uniform_int_distribution& __y)
3078 {return __x.__p_ == __y.__p_;}
3079 friend bool operator!=(const uniform_int_distribution& __x,
3080 const uniform_int_distribution& __y)
3081 {return !(__x == __y);}
3084 template<class _IntType>
3085 template<class _URNG>
3086 typename uniform_int_distribution<_IntType>::result_type
3087 uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
3089 typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
3090 uint32_t, uint64_t>::type _UIntType;
3091 const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1);
3094 const size_t _Dt = numeric_limits<_UIntType>::digits;
3095 typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
3097 return static_cast<result_type>(_Eng(__g, _Dt)());
3098 size_t __w = _Dt - __clz(_Rp) - 1;
3099 if ((_Rp & (std::numeric_limits<_UIntType>::max() >> (_Dt - __w))) != 0)
3106 } while (__u >= _Rp);
3107 return static_cast<result_type>(__u + __p.a());
3110 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \
3111 || defined(_LIBCPP_BUILDING_LIBRARY)
3112 class _LIBCPP_TYPE_VIS __rs_default;
3114 _LIBCPP_FUNC_VIS __rs_default __rs_get();
3116 class _LIBCPP_TYPE_VIS __rs_default
3118 static unsigned __c_;
3122 typedef uint_fast32_t result_type;
3124 static const result_type _Min = 0;
3125 static const result_type _Max = 0xFFFFFFFF;
3127 __rs_default(const __rs_default&);
3130 result_type operator()();
3132 static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
3133 static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
3135 friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
3138 _LIBCPP_FUNC_VIS __rs_default __rs_get();
3140 template <class _RandomAccessIterator>
3142 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
3144 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3145 typedef uniform_int_distribution<ptrdiff_t> _Dp;
3146 typedef typename _Dp::param_type _Pp;
3147 difference_type __d = __last - __first;
3151 __rs_default __g = __rs_get();
3152 for (--__last, --__d; __first < __last; ++__first, --__d)
3154 difference_type __i = __uid(__g, _Pp(0, __d));
3155 if (__i != difference_type(0))
3156 swap(*__first, *(__first + __i));
3161 template <class _RandomAccessIterator, class _RandomNumberGenerator>
3163 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3164 #ifndef _LIBCPP_CXX03_LANG
3165 _RandomNumberGenerator&& __rand)
3167 _RandomNumberGenerator& __rand)
3170 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3171 difference_type __d = __last - __first;
3174 for (--__last; __first < __last; ++__first, --__d)
3176 difference_type __i = __rand(__d);
3177 swap(*__first, *(__first + __i));
3183 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3184 class _UniformRandomNumberGenerator>
3185 _LIBCPP_INLINE_VISIBILITY
3186 _SampleIterator __sample(_PopulationIterator __first,
3187 _PopulationIterator __last, _SampleIterator __output,
3189 _UniformRandomNumberGenerator & __g,
3190 input_iterator_tag) {
3193 for (; __first != __last && __k < __n; ++__first, (void)++__k)
3194 __output[__k] = *__first;
3195 _Distance __sz = __k;
3196 for (; __first != __last; ++__first, (void)++__k) {
3197 _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g);
3199 __output[__r] = *__first;
3201 return __output + _VSTD::min(__n, __k);
3204 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3205 class _UniformRandomNumberGenerator>
3206 _LIBCPP_INLINE_VISIBILITY
3207 _SampleIterator __sample(_PopulationIterator __first,
3208 _PopulationIterator __last, _SampleIterator __output,
3210 _UniformRandomNumberGenerator& __g,
3211 forward_iterator_tag) {
3212 _Distance __unsampled_sz = _VSTD::distance(__first, __last);
3213 for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
3215 _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g);
3217 *__output++ = *__first;
3224 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3225 class _UniformRandomNumberGenerator>
3226 _LIBCPP_INLINE_VISIBILITY
3227 _SampleIterator __sample(_PopulationIterator __first,
3228 _PopulationIterator __last, _SampleIterator __output,
3229 _Distance __n, _UniformRandomNumberGenerator& __g) {
3230 typedef typename iterator_traits<_PopulationIterator>::iterator_category
3232 typedef typename iterator_traits<_PopulationIterator>::difference_type
3234 static_assert(__is_forward_iterator<_PopulationIterator>::value ||
3235 __is_random_access_iterator<_SampleIterator>::value,
3236 "SampleIterator must meet the requirements of RandomAccessIterator");
3237 typedef typename common_type<_Distance, _Difference>::type _CommonType;
3238 _LIBCPP_ASSERT(__n >= 0, "N must be a positive number.");
3239 return _VSTD::__sample(
3240 __first, __last, __output, _CommonType(__n),
3241 __g, _PopCategory());
3244 #if _LIBCPP_STD_VER > 14
3245 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3246 class _UniformRandomNumberGenerator>
3247 inline _LIBCPP_INLINE_VISIBILITY
3248 _SampleIterator sample(_PopulationIterator __first,
3249 _PopulationIterator __last, _SampleIterator __output,
3250 _Distance __n, _UniformRandomNumberGenerator&& __g) {
3251 return _VSTD::__sample(__first, __last, __output, __n, __g);
3253 #endif // _LIBCPP_STD_VER > 14
3255 template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
3256 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3257 #ifndef _LIBCPP_CXX03_LANG
3258 _UniformRandomNumberGenerator&& __g)
3260 _UniformRandomNumberGenerator& __g)
3263 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3264 typedef uniform_int_distribution<ptrdiff_t> _Dp;
3265 typedef typename _Dp::param_type _Pp;
3266 difference_type __d = __last - __first;
3270 for (--__last, --__d; __first < __last; ++__first, --__d)
3272 difference_type __i = __uid(__g, _Pp(0, __d));
3273 if (__i != difference_type(0))
3274 swap(*__first, *(__first + __i));
3279 template <class _InputIterator, class _Predicate>
3281 is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3283 for (; __first != __last; ++__first)
3284 if (!__pred(*__first))
3286 if ( __first == __last )
3289 for (; __first != __last; ++__first)
3290 if (__pred(*__first))
3297 template <class _Predicate, class _ForwardIterator>
3299 __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
3303 if (__first == __last)
3305 if (!__pred(*__first))
3309 for (_ForwardIterator __p = __first; ++__p != __last;)
3313 swap(*__first, *__p);
3320 template <class _Predicate, class _BidirectionalIterator>
3321 _BidirectionalIterator
3322 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3323 bidirectional_iterator_tag)
3329 if (__first == __last)
3331 if (!__pred(*__first))
3337 if (__first == --__last)
3339 } while (!__pred(*__last));
3340 swap(*__first, *__last);
3345 template <class _ForwardIterator, class _Predicate>
3346 inline _LIBCPP_INLINE_VISIBILITY
3348 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3350 return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>
3351 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3356 template <class _InputIterator, class _OutputIterator1,
3357 class _OutputIterator2, class _Predicate>
3358 pair<_OutputIterator1, _OutputIterator2>
3359 partition_copy(_InputIterator __first, _InputIterator __last,
3360 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
3363 for (; __first != __last; ++__first)
3365 if (__pred(*__first))
3367 *__out_true = *__first;
3372 *__out_false = *__first;
3376 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
3381 template<class _ForwardIterator, class _Predicate>
3383 partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3385 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3386 difference_type __len = _VSTD::distance(__first, __last);
3389 difference_type __l2 = __len / 2;
3390 _ForwardIterator __m = __first;
3391 _VSTD::advance(__m, __l2);
3405 template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
3407 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3408 _Distance __len, _Pair __p, forward_iterator_tag __fit)
3410 // *__first is known to be false
3416 _ForwardIterator __m = __first;
3419 swap(*__first, *__m);
3424 if (__len <= __p.second)
3425 { // The buffer is big enough to use
3426 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3427 __destruct_n __d(0);
3428 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3429 // Move the falses into the temporary buffer, and the trues to the front of the line
3430 // Update __first to always point to the end of the trues
3431 value_type* __t = __p.first;
3432 ::new(__t) value_type(_VSTD::move(*__first));
3433 __d.__incr((value_type*)0);
3435 _ForwardIterator __i = __first;
3436 while (++__i != __last)
3440 *__first = _VSTD::move(*__i);
3445 ::new(__t) value_type(_VSTD::move(*__i));
3446 __d.__incr((value_type*)0);
3450 // All trues now at start of range, all falses in buffer
3451 // Move falses back into range, but don't mess up __first which points to first false
3453 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3454 *__i = _VSTD::move(*__t2);
3455 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3458 // Else not enough buffer, do in place
3460 _ForwardIterator __m = __first;
3461 _Distance __len2 = __len / 2; // __len2 >= 2
3462 _VSTD::advance(__m, __len2);
3463 // recurse on [__first, __m), *__first know to be false
3464 // F?????????????????
3466 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3467 _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
3468 // TTTFFFFF??????????
3470 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3471 _ForwardIterator __m1 = __m;
3472 _ForwardIterator __second_false = __last;
3473 _Distance __len_half = __len - __len2;
3474 while (__pred(*__m1))
3476 if (++__m1 == __last)
3477 goto __second_half_done;
3480 // TTTFFFFFTTTF??????
3482 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
3484 // TTTFFFFFTTTTTFFFFF
3486 return _VSTD::rotate(__first_false, __m, __second_false);
3487 // TTTTTTTTFFFFFFFFFF
3491 struct __return_temporary_buffer
3493 template <class _Tp>
3494 _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}
3497 template <class _Predicate, class _ForwardIterator>
3499 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3500 forward_iterator_tag)
3502 const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment
3503 // Either prove all true and return __first or point to first false
3506 if (__first == __last)
3508 if (!__pred(*__first))
3512 // We now have a reduced range [__first, __last)
3513 // *__first is known to be false
3514 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3515 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3516 difference_type __len = _VSTD::distance(__first, __last);
3517 pair<value_type*, ptrdiff_t> __p(0, 0);
3518 unique_ptr<value_type, __return_temporary_buffer> __h;
3519 if (__len >= __alloc_limit)
3521 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3522 __h.reset(__p.first);
3524 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3525 (__first, __last, __pred, __len, __p, forward_iterator_tag());
3528 template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
3529 _BidirectionalIterator
3530 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3531 _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
3533 // *__first is known to be false
3534 // *__last is known to be true
3538 swap(*__first, *__last);
3543 _BidirectionalIterator __m = __first;
3546 swap(*__first, *__m);
3547 swap(*__m, *__last);
3550 swap(*__m, *__last);
3551 swap(*__first, *__m);
3554 if (__len <= __p.second)
3555 { // The buffer is big enough to use
3556 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3557 __destruct_n __d(0);
3558 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3559 // Move the falses into the temporary buffer, and the trues to the front of the line
3560 // Update __first to always point to the end of the trues
3561 value_type* __t = __p.first;
3562 ::new(__t) value_type(_VSTD::move(*__first));
3563 __d.__incr((value_type*)0);
3565 _BidirectionalIterator __i = __first;
3566 while (++__i != __last)
3570 *__first = _VSTD::move(*__i);
3575 ::new(__t) value_type(_VSTD::move(*__i));
3576 __d.__incr((value_type*)0);
3580 // move *__last, known to be true
3581 *__first = _VSTD::move(*__i);
3583 // All trues now at start of range, all falses in buffer
3584 // Move falses back into range, but don't mess up __first which points to first false
3585 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3586 *__i = _VSTD::move(*__t2);
3587 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3590 // Else not enough buffer, do in place
3592 _BidirectionalIterator __m = __first;
3593 _Distance __len2 = __len / 2; // __len2 >= 2
3594 _VSTD::advance(__m, __len2);
3595 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
3596 // F????????????????T
3598 _BidirectionalIterator __m1 = __m;
3599 _BidirectionalIterator __first_false = __first;
3600 _Distance __len_half = __len2;
3601 while (!__pred(*--__m1))
3603 if (__m1 == __first)
3604 goto __first_half_done;
3607 // F???TFFF?????????T
3609 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3610 __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3612 // TTTFFFFF?????????T
3614 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3616 _BidirectionalIterator __second_false = __last;
3618 __len_half = __len - __len2;
3619 while (__pred(*__m1))
3621 if (++__m1 == __last)
3622 goto __second_half_done;
3625 // TTTFFFFFTTTF?????T
3627 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
3629 // TTTFFFFFTTTTTFFFFF
3631 return _VSTD::rotate(__first_false, __m, __second_false);
3632 // TTTTTTTTFFFFFFFFFF
3636 template <class _Predicate, class _BidirectionalIterator>
3637 _BidirectionalIterator
3638 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3639 bidirectional_iterator_tag)
3641 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3642 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3643 const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment
3644 // Either prove all true and return __first or point to first false
3647 if (__first == __last)
3649 if (!__pred(*__first))
3653 // __first points to first false, everything prior to __first is already set.
3654 // Either prove [__first, __last) is all false and return __first, or point __last to last true
3657 if (__first == --__last)
3659 } while (!__pred(*__last));
3660 // We now have a reduced range [__first, __last]
3661 // *__first is known to be false
3662 // *__last is known to be true
3664 difference_type __len = _VSTD::distance(__first, __last) + 1;
3665 pair<value_type*, ptrdiff_t> __p(0, 0);
3666 unique_ptr<value_type, __return_temporary_buffer> __h;
3667 if (__len >= __alloc_limit)
3669 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3670 __h.reset(__p.first);
3672 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3673 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3676 template <class _ForwardIterator, class _Predicate>
3677 inline _LIBCPP_INLINE_VISIBILITY
3679 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3681 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3682 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3687 template <class _ForwardIterator, class _Compare>
3689 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3691 if (__first != __last)
3693 _ForwardIterator __i = __first;
3694 while (++__i != __last)
3696 if (__comp(*__i, *__first))
3704 template<class _ForwardIterator>
3705 inline _LIBCPP_INLINE_VISIBILITY
3707 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3709 return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3714 template <class _ForwardIterator, class _Compare>
3715 inline _LIBCPP_INLINE_VISIBILITY
3717 is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3719 return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
3722 template<class _ForwardIterator>
3723 inline _LIBCPP_INLINE_VISIBILITY
3725 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3727 return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3732 // stable, 2-3 compares, 0-2 swaps
3734 template <class _Compare, class _ForwardIterator>
3736 __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
3739 if (!__c(*__y, *__x)) // if x <= y
3741 if (!__c(*__z, *__y)) // if y <= z
3742 return __r; // x <= y && y <= z
3744 swap(*__y, *__z); // x <= z && y < z
3746 if (__c(*__y, *__x)) // if x > y
3748 swap(*__x, *__y); // x < y && y <= z
3751 return __r; // x <= y && y < z
3753 if (__c(*__z, *__y)) // x > y, if y > z
3755 swap(*__x, *__z); // x < y && y < z
3759 swap(*__x, *__y); // x > y && y <= z
3760 __r = 1; // x < y && x <= z
3761 if (__c(*__z, *__y)) // if y > z
3763 swap(*__y, *__z); // x <= y && y < z
3767 } // x <= y && y <= z
3769 // stable, 3-6 compares, 0-5 swaps
3771 template <class _Compare, class _ForwardIterator>
3773 __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3774 _ForwardIterator __x4, _Compare __c)
3776 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
3777 if (__c(*__x4, *__x3))
3781 if (__c(*__x3, *__x2))
3785 if (__c(*__x2, *__x1))
3795 // stable, 4-10 compares, 0-9 swaps
3797 template <class _Compare, class _ForwardIterator>
3799 __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3800 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
3802 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
3803 if (__c(*__x5, *__x4))
3807 if (__c(*__x4, *__x3))
3811 if (__c(*__x3, *__x2))
3815 if (__c(*__x2, *__x1))
3827 template <class _Compare, class _BirdirectionalIterator>
3829 __selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3831 _BirdirectionalIterator __lm1 = __last;
3832 for (--__lm1; __first != __lm1; ++__first)
3834 _BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator,
3835 typename add_lvalue_reference<_Compare>::type>
3836 (__first, __last, __comp);
3838 swap(*__first, *__i);
3842 template <class _Compare, class _BirdirectionalIterator>
3844 __insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3846 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3847 if (__first != __last)
3849 _BirdirectionalIterator __i = __first;
3850 for (++__i; __i != __last; ++__i)
3852 _BirdirectionalIterator __j = __i;
3853 value_type __t(_VSTD::move(*__j));
3854 for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
3855 *__j = _VSTD::move(*__k);
3856 *__j = _VSTD::move(__t);
3861 template <class _Compare, class _RandomAccessIterator>
3863 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3865 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3866 _RandomAccessIterator __j = __first+2;
3867 __sort3<_Compare>(__first, __first+1, __j, __comp);
3868 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3870 if (__comp(*__i, *__j))
3872 value_type __t(_VSTD::move(*__i));
3873 _RandomAccessIterator __k = __j;
3877 *__j = _VSTD::move(*__k);
3879 } while (__j != __first && __comp(__t, *--__k));
3880 *__j = _VSTD::move(__t);
3886 template <class _Compare, class _RandomAccessIterator>
3888 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3890 switch (__last - __first)
3896 if (__comp(*--__last, *__first))
3897 swap(*__first, *__last);
3900 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3903 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3906 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3909 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3910 _RandomAccessIterator __j = __first+2;
3911 __sort3<_Compare>(__first, __first+1, __j, __comp);
3912 const unsigned __limit = 8;
3913 unsigned __count = 0;
3914 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3916 if (__comp(*__i, *__j))
3918 value_type __t(_VSTD::move(*__i));
3919 _RandomAccessIterator __k = __j;
3923 *__j = _VSTD::move(*__k);
3925 } while (__j != __first && __comp(__t, *--__k));
3926 *__j = _VSTD::move(__t);
3927 if (++__count == __limit)
3928 return ++__i == __last;
3935 template <class _Compare, class _BirdirectionalIterator>
3937 __insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
3938 typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
3940 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3941 if (__first1 != __last1)
3943 __destruct_n __d(0);
3944 unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
3945 value_type* __last2 = __first2;
3946 ::new(__last2) value_type(_VSTD::move(*__first1));
3947 __d.__incr((value_type*)0);
3948 for (++__last2; ++__first1 != __last1; ++__last2)
3950 value_type* __j2 = __last2;
3951 value_type* __i2 = __j2;
3952 if (__comp(*__first1, *--__i2))
3954 ::new(__j2) value_type(_VSTD::move(*__i2));
3955 __d.__incr((value_type*)0);
3956 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2)
3957 *__j2 = _VSTD::move(*__i2);
3958 *__j2 = _VSTD::move(*__first1);
3962 ::new(__j2) value_type(_VSTD::move(*__first1));
3963 __d.__incr((value_type*)0);
3970 template <class _Compare, class _RandomAccessIterator>
3972 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3974 // _Compare is known to be a reference type
3975 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3976 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3977 const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
3978 is_trivially_copy_assignable<value_type>::value ? 30 : 6;
3982 difference_type __len = __last - __first;
3989 if (__comp(*--__last, *__first))
3990 swap(*__first, *__last);
3993 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3996 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3999 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
4002 if (__len <= __limit)
4004 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
4008 _RandomAccessIterator __m = __first;
4009 _RandomAccessIterator __lm1 = __last;
4013 difference_type __delta;
4019 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
4025 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
4029 // partition [__first, __m) < *__m and *__m <= [__m, __last)
4030 // (this inhibits tossing elements equivalent to __m around unnecessarily)
4031 _RandomAccessIterator __i = __first;
4032 _RandomAccessIterator __j = __lm1;
4033 // j points beyond range to be tested, *__m is known to be <= *__lm1
4034 // The search going up is known to be guarded but the search coming down isn't.
4035 // Prime the downward search with a guard.
4036 if (!__comp(*__i, *__m)) // if *__first == *__m
4038 // *__first == *__m, *__first doesn't go in first part
4039 // manually guard downward moving __j against __i
4044 // *__first == *__m, *__m <= all other elements
4045 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
4046 ++__i; // __first + 1
4048 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
4053 return; // [__first, __last) all equivalent elements
4054 if (__comp(*__first, *__i))
4064 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
4069 while (!__comp(*__first, *__i))
4071 while (__comp(*__first, *--__j))
4079 // [__first, __i) == *__first and *__first < [__i, __last)
4080 // The first part is sorted, sort the secod part
4081 // _VSTD::__sort<_Compare>(__i, __last, __comp);
4085 if (__comp(*__j, *__m))
4089 break; // found guard for downward moving __j, now use unguarded partition
4093 // It is known that *__i < *__m
4095 // j points beyond range to be tested, *__m is known to be <= *__lm1
4096 // if not yet partitioned...
4099 // known that *(__i - 1) < *__m
4100 // known that __i <= __m
4103 // __m still guards upward moving __i
4104 while (__comp(*__i, *__m))
4106 // It is now known that a guard exists for downward moving __j
4107 while (!__comp(*--__j, *__m))
4113 // It is known that __m != __j
4114 // If __m just moved, follow it
4120 // [__first, __i) < *__m and *__m <= [__i, __last)
4121 if (__i != __m && __comp(*__m, *__i))
4126 // [__first, __i) < *__i and *__i <= [__i+1, __last)
4127 // If we were given a perfect partition, see if insertion sort is quick...
4130 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
4131 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
4147 // sort smaller range with recursive call and larger with tail recursion elimination
4148 if (__i - __first < __last - __i)
4150 _VSTD::__sort<_Compare>(__first, __i, __comp);
4151 // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4156 _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4157 // _VSTD::__sort<_Compare>(__first, __i, __comp);
4163 // This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
4164 template <class _RandomAccessIterator, class _Compare>
4165 inline _LIBCPP_INLINE_VISIBILITY
4167 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4169 #ifdef _LIBCPP_DEBUG
4170 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4171 __debug_less<_Compare> __c(__comp);
4172 __sort<_Comp_ref>(__first, __last, __c);
4173 #else // _LIBCPP_DEBUG
4174 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4175 __sort<_Comp_ref>(__first, __last, __comp);
4176 #endif // _LIBCPP_DEBUG
4179 template <class _RandomAccessIterator>
4180 inline _LIBCPP_INLINE_VISIBILITY
4182 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4184 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4187 template <class _Tp>
4188 inline _LIBCPP_INLINE_VISIBILITY
4190 sort(_Tp** __first, _Tp** __last)
4192 _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
4195 template <class _Tp>
4196 inline _LIBCPP_INLINE_VISIBILITY
4198 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
4200 _VSTD::sort(__first.base(), __last.base());
4203 template <class _Tp, class _Compare>
4204 inline _LIBCPP_INLINE_VISIBILITY
4206 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
4208 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4209 _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
4213 #pragma warning( push )
4214 #pragma warning( disable: 4231)
4215 #endif // _LIBCPP_MSVC
4216 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
4217 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4218 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4219 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4220 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))
4221 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4222 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&))
4223 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4224 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&))
4225 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4226 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4227 _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>&))
4228 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&))
4229 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&))
4230 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4232 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))
4233 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4234 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4235 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4236 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))
4237 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4238 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&))
4239 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4240 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&))
4241 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4242 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4243 _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>&))
4244 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&))
4245 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&))
4246 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4248 _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>&))
4250 #pragma warning( pop )
4251 #endif // _LIBCPP_MSVC
4255 template <class _Compare, class _ForwardIterator, class _Tp>
4257 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4259 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4260 difference_type __len = _VSTD::distance(__first, __last);
4263 difference_type __l2 = __len / 2;
4264 _ForwardIterator __m = __first;
4265 _VSTD::advance(__m, __l2);
4266 if (__comp(*__m, __value_))
4277 template <class _ForwardIterator, class _Tp, class _Compare>
4278 inline _LIBCPP_INLINE_VISIBILITY
4280 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4282 #ifdef _LIBCPP_DEBUG
4283 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4284 __debug_less<_Compare> __c(__comp);
4285 return __lower_bound<_Comp_ref>(__first, __last, __value_, __c);
4286 #else // _LIBCPP_DEBUG
4287 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4288 return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp);
4289 #endif // _LIBCPP_DEBUG
4292 template <class _ForwardIterator, class _Tp>
4293 inline _LIBCPP_INLINE_VISIBILITY
4295 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4297 return _VSTD::lower_bound(__first, __last, __value_,
4298 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4303 template <class _Compare, class _ForwardIterator, class _Tp>
4305 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4307 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4308 difference_type __len = _VSTD::distance(__first, __last);
4311 difference_type __l2 = __len / 2;
4312 _ForwardIterator __m = __first;
4313 _VSTD::advance(__m, __l2);
4314 if (__comp(__value_, *__m))
4325 template <class _ForwardIterator, class _Tp, class _Compare>
4326 inline _LIBCPP_INLINE_VISIBILITY
4328 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4330 #ifdef _LIBCPP_DEBUG
4331 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4332 __debug_less<_Compare> __c(__comp);
4333 return __upper_bound<_Comp_ref>(__first, __last, __value_, __c);
4334 #else // _LIBCPP_DEBUG
4335 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4336 return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp);
4337 #endif // _LIBCPP_DEBUG
4340 template <class _ForwardIterator, class _Tp>
4341 inline _LIBCPP_INLINE_VISIBILITY
4343 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4345 return _VSTD::upper_bound(__first, __last, __value_,
4346 __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
4351 template <class _Compare, class _ForwardIterator, class _Tp>
4352 pair<_ForwardIterator, _ForwardIterator>
4353 __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4355 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4356 difference_type __len = _VSTD::distance(__first, __last);
4359 difference_type __l2 = __len / 2;
4360 _ForwardIterator __m = __first;
4361 _VSTD::advance(__m, __l2);
4362 if (__comp(*__m, __value_))
4367 else if (__comp(__value_, *__m))
4374 _ForwardIterator __mp1 = __m;
4375 return pair<_ForwardIterator, _ForwardIterator>
4377 __lower_bound<_Compare>(__first, __m, __value_, __comp),
4378 __upper_bound<_Compare>(++__mp1, __last, __value_, __comp)
4382 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4385 template <class _ForwardIterator, class _Tp, class _Compare>
4386 inline _LIBCPP_INLINE_VISIBILITY
4387 pair<_ForwardIterator, _ForwardIterator>
4388 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4390 #ifdef _LIBCPP_DEBUG
4391 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4392 __debug_less<_Compare> __c(__comp);
4393 return __equal_range<_Comp_ref>(__first, __last, __value_, __c);
4394 #else // _LIBCPP_DEBUG
4395 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4396 return __equal_range<_Comp_ref>(__first, __last, __value_, __comp);
4397 #endif // _LIBCPP_DEBUG
4400 template <class _ForwardIterator, class _Tp>
4401 inline _LIBCPP_INLINE_VISIBILITY
4402 pair<_ForwardIterator, _ForwardIterator>
4403 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4405 return _VSTD::equal_range(__first, __last, __value_,
4406 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4411 template <class _Compare, class _ForwardIterator, class _Tp>
4412 inline _LIBCPP_INLINE_VISIBILITY
4414 __binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4416 __first = __lower_bound<_Compare>(__first, __last, __value_, __comp);
4417 return __first != __last && !__comp(__value_, *__first);
4420 template <class _ForwardIterator, class _Tp, class _Compare>
4421 inline _LIBCPP_INLINE_VISIBILITY
4423 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4425 #ifdef _LIBCPP_DEBUG
4426 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4427 __debug_less<_Compare> __c(__comp);
4428 return __binary_search<_Comp_ref>(__first, __last, __value_, __c);
4429 #else // _LIBCPP_DEBUG
4430 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4431 return __binary_search<_Comp_ref>(__first, __last, __value_, __comp);
4432 #endif // _LIBCPP_DEBUG
4435 template <class _ForwardIterator, class _Tp>
4436 inline _LIBCPP_INLINE_VISIBILITY
4438 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4440 return _VSTD::binary_search(__first, __last, __value_,
4441 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4446 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4448 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4449 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4451 for (; __first1 != __last1; ++__result)
4453 if (__first2 == __last2)
4454 return _VSTD::copy(__first1, __last1, __result);
4455 if (__comp(*__first2, *__first1))
4457 *__result = *__first2;
4462 *__result = *__first1;
4466 return _VSTD::copy(__first2, __last2, __result);
4469 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4470 inline _LIBCPP_INLINE_VISIBILITY
4472 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4473 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4475 #ifdef _LIBCPP_DEBUG
4476 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4477 __debug_less<_Compare> __c(__comp);
4478 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
4479 #else // _LIBCPP_DEBUG
4480 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4481 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4482 #endif // _LIBCPP_DEBUG
4485 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4486 inline _LIBCPP_INLINE_VISIBILITY
4488 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4489 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4491 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
4492 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
4493 return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
4498 template <class _Compare, class _InputIterator1, class _InputIterator2,
4499 class _OutputIterator>
4500 void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
4501 _InputIterator2 __first2, _InputIterator2 __last2,
4502 _OutputIterator __result, _Compare __comp)
4504 for (; __first1 != __last1; ++__result)
4506 if (__first2 == __last2)
4508 _VSTD::move(__first1, __last1, __result);
4512 if (__comp(*__first2, *__first1))
4514 *__result = _VSTD::move(*__first2);
4519 *__result = _VSTD::move(*__first1);
4523 // __first2 through __last2 are already in the right spot.
4526 template <class _Compare, class _BidirectionalIterator>
4528 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4529 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4530 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4531 typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
4533 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4534 __destruct_n __d(0);
4535 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4536 if (__len1 <= __len2)
4538 value_type* __p = __buff;
4539 for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4540 ::new(__p) value_type(_VSTD::move(*__i));
4541 __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);
4545 value_type* __p = __buff;
4546 for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4547 ::new(__p) value_type(_VSTD::move(*__i));
4548 typedef reverse_iterator<_BidirectionalIterator> _RBi;
4549 typedef reverse_iterator<value_type*> _Rv;
4550 __half_inplace_merge(_Rv(__p), _Rv(__buff),
4551 _RBi(__middle), _RBi(__first),
4552 _RBi(__last), __negate<_Compare>(__comp));
4556 template <class _Compare, class _BidirectionalIterator>
4558 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4559 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4560 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4561 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
4563 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4566 // if __middle == __last, we're done
4569 if (__len1 <= __buff_size || __len2 <= __buff_size)
4570 return __buffered_inplace_merge<_Compare>
4571 (__first, __middle, __last, __comp, __len1, __len2, __buff);
4572 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
4573 for (; true; ++__first, (void) --__len1)
4577 if (__comp(*__middle, *__first))
4580 // __first < __middle < __last
4581 // *__first > *__middle
4582 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4584 // [__first, __m1) <= [__middle, __m2)
4585 // [__middle, __m2) < [__m1, __middle)
4586 // [__m1, __middle) <= [__m2, __last)
4587 // and __m1 or __m2 is in the middle of its range
4588 _BidirectionalIterator __m1; // "median" of [__first, __middle)
4589 _BidirectionalIterator __m2; // "median" of [__middle, __last)
4590 difference_type __len11; // distance(__first, __m1)
4591 difference_type __len21; // distance(__middle, __m2)
4592 // binary search smaller range
4593 if (__len1 < __len2)
4594 { // __len >= 1, __len2 >= 2
4595 __len21 = __len2 / 2;
4597 _VSTD::advance(__m2, __len21);
4598 __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4599 __len11 = _VSTD::distance(__first, __m1);
4604 { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
4605 // It is known *__first > *__middle
4606 swap(*__first, *__middle);
4609 // __len1 >= 2, __len2 >= 1
4610 __len11 = __len1 / 2;
4612 _VSTD::advance(__m1, __len11);
4613 __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp);
4614 __len21 = _VSTD::distance(__middle, __m2);
4616 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle)
4617 difference_type __len22 = __len2 - __len21; // distance(__m2, __last)
4618 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4619 // swap middle two partitions
4620 __middle = _VSTD::rotate(__m1, __middle, __m2);
4621 // __len12 and __len21 now have swapped meanings
4622 // merge smaller range with recurisve call and larger with tail recursion elimination
4623 if (__len11 + __len21 < __len12 + __len22)
4625 __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4626 // __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4634 __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4635 // __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4644 template <class _BidirectionalIterator, class _Compare>
4645 inline _LIBCPP_INLINE_VISIBILITY
4647 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4650 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4651 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4652 difference_type __len1 = _VSTD::distance(__first, __middle);
4653 difference_type __len2 = _VSTD::distance(__middle, __last);
4654 difference_type __buf_size = _VSTD::min(__len1, __len2);
4655 pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
4656 unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
4658 #ifdef _LIBCPP_DEBUG
4659 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4660 __debug_less<_Compare> __c(__comp);
4661 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2,
4662 __buf.first, __buf.second);
4663 #else // _LIBCPP_DEBUG
4664 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4665 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4666 __buf.first, __buf.second);
4667 #endif // _LIBCPP_DEBUG
4670 template <class _BidirectionalIterator>
4671 inline _LIBCPP_INLINE_VISIBILITY
4673 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
4675 _VSTD::inplace_merge(__first, __middle, __last,
4676 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4681 template <class _Compare, class _InputIterator1, class _InputIterator2>
4683 __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
4684 _InputIterator2 __first2, _InputIterator2 __last2,
4685 typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
4687 typedef typename iterator_traits<_InputIterator1>::value_type value_type;
4688 __destruct_n __d(0);
4689 unique_ptr<value_type, __destruct_n&> __h(__result, __d);
4690 for (; true; ++__result)
4692 if (__first1 == __last1)
4694 for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0))
4695 ::new (__result) value_type(_VSTD::move(*__first2));
4699 if (__first2 == __last2)
4701 for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0))
4702 ::new (__result) value_type(_VSTD::move(*__first1));
4706 if (__comp(*__first2, *__first1))
4708 ::new (__result) value_type(_VSTD::move(*__first2));
4709 __d.__incr((value_type*)0);
4714 ::new (__result) value_type(_VSTD::move(*__first1));
4715 __d.__incr((value_type*)0);
4721 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4723 __merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
4724 _InputIterator2 __first2, _InputIterator2 __last2,
4725 _OutputIterator __result, _Compare __comp)
4727 for (; __first1 != __last1; ++__result)
4729 if (__first2 == __last2)
4731 for (; __first1 != __last1; ++__first1, ++__result)
4732 *__result = _VSTD::move(*__first1);
4735 if (__comp(*__first2, *__first1))
4737 *__result = _VSTD::move(*__first2);
4742 *__result = _VSTD::move(*__first1);
4746 for (; __first2 != __last2; ++__first2, ++__result)
4747 *__result = _VSTD::move(*__first2);
4750 template <class _Compare, class _RandomAccessIterator>
4752 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4753 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4754 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
4756 template <class _Compare, class _RandomAccessIterator>
4758 __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
4759 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4760 typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
4762 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4768 ::new(__first2) value_type(_VSTD::move(*__first1));
4771 __destruct_n __d(0);
4772 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
4773 if (__comp(*--__last1, *__first1))
4775 ::new(__first2) value_type(_VSTD::move(*__last1));
4776 __d.__incr((value_type*)0);
4778 ::new(__first2) value_type(_VSTD::move(*__first1));
4782 ::new(__first2) value_type(_VSTD::move(*__first1));
4783 __d.__incr((value_type*)0);
4785 ::new(__first2) value_type(_VSTD::move(*__last1));
4792 __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
4795 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4796 _RandomAccessIterator __m = __first1 + __l2;
4797 __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
4798 __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
4799 __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
4802 template <class _Tp>
4803 struct __stable_sort_switch
4805 static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
4808 template <class _Compare, class _RandomAccessIterator>
4810 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4811 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4812 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
4814 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4815 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4822 if (__comp(*--__last, *__first))
4823 swap(*__first, *__last);
4826 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4828 __insertion_sort<_Compare>(__first, __last, __comp);
4831 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4832 _RandomAccessIterator __m = __first + __l2;
4833 if (__len <= __buff_size)
4835 __destruct_n __d(0);
4836 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4837 __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4838 __d.__set(__l2, (value_type*)0);
4839 __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
4840 __d.__set(__len, (value_type*)0);
4841 __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4842 // __merge<_Compare>(move_iterator<value_type*>(__buff),
4843 // move_iterator<value_type*>(__buff + __l2),
4844 // move_iterator<_RandomAccessIterator>(__buff + __l2),
4845 // move_iterator<_RandomAccessIterator>(__buff + __len),
4846 // __first, __comp);
4849 __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4850 __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
4851 __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4854 template <class _RandomAccessIterator, class _Compare>
4855 inline _LIBCPP_INLINE_VISIBILITY
4857 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4859 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4860 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4861 difference_type __len = __last - __first;
4862 pair<value_type*, ptrdiff_t> __buf(0, 0);
4863 unique_ptr<value_type, __return_temporary_buffer> __h;
4864 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4866 __buf = _VSTD::get_temporary_buffer<value_type>(__len);
4867 __h.reset(__buf.first);
4869 #ifdef _LIBCPP_DEBUG
4870 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4871 __debug_less<_Compare> __c(__comp);
4872 __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);
4873 #else // _LIBCPP_DEBUG
4874 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4875 __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4876 #endif // _LIBCPP_DEBUG
4879 template <class _RandomAccessIterator>
4880 inline _LIBCPP_INLINE_VISIBILITY
4882 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4884 _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4889 template <class _RandomAccessIterator, class _Compare>
4890 _RandomAccessIterator
4891 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4893 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4894 difference_type __len = __last - __first;
4895 difference_type __p = 0;
4896 difference_type __c = 1;
4897 _RandomAccessIterator __pp = __first;
4900 _RandomAccessIterator __cp = __first + __c;
4901 if (__comp(*__pp, *__cp))
4907 if (__comp(*__pp, *__cp))
4916 template<class _RandomAccessIterator>
4917 inline _LIBCPP_INLINE_VISIBILITY
4918 _RandomAccessIterator
4919 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4921 return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4926 template <class _RandomAccessIterator, class _Compare>
4927 inline _LIBCPP_INLINE_VISIBILITY
4929 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4931 return _VSTD::is_heap_until(__first, __last, __comp) == __last;
4934 template<class _RandomAccessIterator>
4935 inline _LIBCPP_INLINE_VISIBILITY
4937 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4939 return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4944 template <class _Compare, class _RandomAccessIterator>
4946 __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4947 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4949 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4952 __len = (__len - 2) / 2;
4953 _RandomAccessIterator __ptr = __first + __len;
4954 if (__comp(*__ptr, *--__last))
4956 value_type __t(_VSTD::move(*__last));
4959 *__last = _VSTD::move(*__ptr);
4963 __len = (__len - 1) / 2;
4964 __ptr = __first + __len;
4965 } while (__comp(*__ptr, __t));
4966 *__last = _VSTD::move(__t);
4971 template <class _RandomAccessIterator, class _Compare>
4972 inline _LIBCPP_INLINE_VISIBILITY
4974 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4976 #ifdef _LIBCPP_DEBUG
4977 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4978 __debug_less<_Compare> __c(__comp);
4979 __sift_up<_Comp_ref>(__first, __last, __c, __last - __first);
4980 #else // _LIBCPP_DEBUG
4981 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4982 __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
4983 #endif // _LIBCPP_DEBUG
4986 template <class _RandomAccessIterator>
4987 inline _LIBCPP_INLINE_VISIBILITY
4989 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4991 _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4996 template <class _Compare, class _RandomAccessIterator>
4998 __sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/,
5000 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
5001 _RandomAccessIterator __start)
5003 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5004 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
5005 // left-child of __start is at 2 * __start + 1
5006 // right-child of __start is at 2 * __start + 2
5007 difference_type __child = __start - __first;
5009 if (__len < 2 || (__len - 2) / 2 < __child)
5012 __child = 2 * __child + 1;
5013 _RandomAccessIterator __child_i = __first + __child;
5015 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
5016 // right-child exists and is greater than left-child
5021 // check if we are in heap-order
5022 if (__comp(*__child_i, *__start))
5023 // we are, __start is larger than it's largest child
5026 value_type __top(_VSTD::move(*__start));
5029 // we are not in heap-order, swap the parent with it's largest child
5030 *__start = _VSTD::move(*__child_i);
5031 __start = __child_i;
5033 if ((__len - 2) / 2 < __child)
5036 // recompute the child based off of the updated parent
5037 __child = 2 * __child + 1;
5038 __child_i = __first + __child;
5040 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
5041 // right-child exists and is greater than left-child
5046 // check if we are in heap-order
5047 } while (!__comp(*__child_i, __top));
5048 *__start = _VSTD::move(__top);
5051 template <class _Compare, class _RandomAccessIterator>
5052 inline _LIBCPP_INLINE_VISIBILITY
5054 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
5055 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
5059 swap(*__first, *--__last);
5060 __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);
5064 template <class _RandomAccessIterator, class _Compare>
5065 inline _LIBCPP_INLINE_VISIBILITY
5067 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5069 #ifdef _LIBCPP_DEBUG
5070 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5071 __debug_less<_Compare> __c(__comp);
5072 __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);
5073 #else // _LIBCPP_DEBUG
5074 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5075 __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
5076 #endif // _LIBCPP_DEBUG
5079 template <class _RandomAccessIterator>
5080 inline _LIBCPP_INLINE_VISIBILITY
5082 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5084 _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5089 template <class _Compare, class _RandomAccessIterator>
5091 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5093 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5094 difference_type __n = __last - __first;
5097 // start from the first parent, there is no need to consider children
5098 for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start)
5100 __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start);
5105 template <class _RandomAccessIterator, class _Compare>
5106 inline _LIBCPP_INLINE_VISIBILITY
5108 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5110 #ifdef _LIBCPP_DEBUG
5111 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5112 __debug_less<_Compare> __c(__comp);
5113 __make_heap<_Comp_ref>(__first, __last, __c);
5114 #else // _LIBCPP_DEBUG
5115 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5116 __make_heap<_Comp_ref>(__first, __last, __comp);
5117 #endif // _LIBCPP_DEBUG
5120 template <class _RandomAccessIterator>
5121 inline _LIBCPP_INLINE_VISIBILITY
5123 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5125 _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5130 template <class _Compare, class _RandomAccessIterator>
5132 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5134 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5135 for (difference_type __n = __last - __first; __n > 1; --__last, --__n)
5136 __pop_heap<_Compare>(__first, __last, __comp, __n);
5139 template <class _RandomAccessIterator, class _Compare>
5140 inline _LIBCPP_INLINE_VISIBILITY
5142 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5144 #ifdef _LIBCPP_DEBUG
5145 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5146 __debug_less<_Compare> __c(__comp);
5147 __sort_heap<_Comp_ref>(__first, __last, __c);
5148 #else // _LIBCPP_DEBUG
5149 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5150 __sort_heap<_Comp_ref>(__first, __last, __comp);
5151 #endif // _LIBCPP_DEBUG
5154 template <class _RandomAccessIterator>
5155 inline _LIBCPP_INLINE_VISIBILITY
5157 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5159 _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5164 template <class _Compare, class _RandomAccessIterator>
5166 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5169 __make_heap<_Compare>(__first, __middle, __comp);
5170 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
5171 for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
5173 if (__comp(*__i, *__first))
5175 swap(*__i, *__first);
5176 __sift_down<_Compare>(__first, __middle, __comp, __len, __first);
5179 __sort_heap<_Compare>(__first, __middle, __comp);
5182 template <class _RandomAccessIterator, class _Compare>
5183 inline _LIBCPP_INLINE_VISIBILITY
5185 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5188 #ifdef _LIBCPP_DEBUG
5189 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5190 __debug_less<_Compare> __c(__comp);
5191 __partial_sort<_Comp_ref>(__first, __middle, __last, __c);
5192 #else // _LIBCPP_DEBUG
5193 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5194 __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
5195 #endif // _LIBCPP_DEBUG
5198 template <class _RandomAccessIterator>
5199 inline _LIBCPP_INLINE_VISIBILITY
5201 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
5203 _VSTD::partial_sort(__first, __middle, __last,
5204 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5207 // partial_sort_copy
5209 template <class _Compare, class _InputIterator, class _RandomAccessIterator>
5210 _RandomAccessIterator
5211 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
5212 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5214 _RandomAccessIterator __r = __result_first;
5215 if (__r != __result_last)
5217 for (; __first != __last && __r != __result_last; (void) ++__first, ++__r)
5219 __make_heap<_Compare>(__result_first, __r, __comp);
5220 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
5221 for (; __first != __last; ++__first)
5222 if (__comp(*__first, *__result_first))
5224 *__result_first = *__first;
5225 __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first);
5227 __sort_heap<_Compare>(__result_first, __r, __comp);
5232 template <class _InputIterator, class _RandomAccessIterator, class _Compare>
5233 inline _LIBCPP_INLINE_VISIBILITY
5234 _RandomAccessIterator
5235 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5236 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5238 #ifdef _LIBCPP_DEBUG
5239 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5240 __debug_less<_Compare> __c(__comp);
5241 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);
5242 #else // _LIBCPP_DEBUG
5243 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5244 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
5245 #endif // _LIBCPP_DEBUG
5248 template <class _InputIterator, class _RandomAccessIterator>
5249 inline _LIBCPP_INLINE_VISIBILITY
5250 _RandomAccessIterator
5251 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5252 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
5254 return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
5255 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5260 template <class _Compare, class _RandomAccessIterator>
5262 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5264 // _Compare is known to be a reference type
5265 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5266 const difference_type __limit = 7;
5270 if (__nth == __last)
5272 difference_type __len = __last - __first;
5279 if (__comp(*--__last, *__first))
5280 swap(*__first, *__last);
5284 _RandomAccessIterator __m = __first;
5285 _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
5289 if (__len <= __limit)
5291 __selection_sort<_Compare>(__first, __last, __comp);
5294 // __len > __limit >= 3
5295 _RandomAccessIterator __m = __first + __len/2;
5296 _RandomAccessIterator __lm1 = __last;
5297 unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
5299 // partition [__first, __m) < *__m and *__m <= [__m, __last)
5300 // (this inhibits tossing elements equivalent to __m around unnecessarily)
5301 _RandomAccessIterator __i = __first;
5302 _RandomAccessIterator __j = __lm1;
5303 // j points beyond range to be tested, *__lm1 is known to be <= *__m
5304 // The search going up is known to be guarded but the search coming down isn't.
5305 // Prime the downward search with a guard.
5306 if (!__comp(*__i, *__m)) // if *__first == *__m
5308 // *__first == *__m, *__first doesn't go in first part
5309 // manually guard downward moving __j against __i
5314 // *__first == *__m, *__m <= all other elements
5315 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
5316 ++__i; // __first + 1
5318 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
5323 return; // [__first, __last) all equivalent elements
5324 if (__comp(*__first, *__i))
5334 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
5339 while (!__comp(*__first, *__i))
5341 while (__comp(*__first, *--__j))
5349 // [__first, __i) == *__first and *__first < [__i, __last)
5350 // The first part is sorted,
5353 // __nth_element the secod part
5354 // __nth_element<_Compare>(__i, __nth, __last, __comp);
5358 if (__comp(*__j, *__m))
5362 break; // found guard for downward moving __j, now use unguarded partition
5367 // j points beyond range to be tested, *__lm1 is known to be <= *__m
5368 // if not yet partitioned...
5371 // known that *(__i - 1) < *__m
5374 // __m still guards upward moving __i
5375 while (__comp(*__i, *__m))
5377 // It is now known that a guard exists for downward moving __j
5378 while (!__comp(*--__j, *__m))
5384 // It is known that __m != __j
5385 // If __m just moved, follow it
5391 // [__first, __i) < *__m and *__m <= [__i, __last)
5392 if (__i != __m && __comp(*__m, *__i))
5397 // [__first, __i) < *__i and *__i <= [__i+1, __last)
5402 // We were given a perfectly partitioned sequence. Coincidence?
5405 // Check for [__first, __i) already sorted
5406 __j = __m = __first;
5407 while (++__j != __i)
5409 if (__comp(*__j, *__m))
5410 // not yet sorted, so sort
5414 // [__first, __i) sorted
5419 // Check for [__i, __last) already sorted
5421 while (++__j != __last)
5423 if (__comp(*__j, *__m))
5424 // not yet sorted, so sort
5428 // [__i, __last) sorted
5433 // __nth_element on range containing __nth
5436 // __nth_element<_Compare>(__first, __nth, __i, __comp);
5441 // __nth_element<_Compare>(__i+1, __nth, __last, __comp);
5447 template <class _RandomAccessIterator, class _Compare>
5448 inline _LIBCPP_INLINE_VISIBILITY
5450 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5452 #ifdef _LIBCPP_DEBUG
5453 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5454 __debug_less<_Compare> __c(__comp);
5455 __nth_element<_Comp_ref>(__first, __nth, __last, __c);
5456 #else // _LIBCPP_DEBUG
5457 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5458 __nth_element<_Comp_ref>(__first, __nth, __last, __comp);
5459 #endif // _LIBCPP_DEBUG
5462 template <class _RandomAccessIterator>
5463 inline _LIBCPP_INLINE_VISIBILITY
5465 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
5467 _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5472 template <class _Compare, class _InputIterator1, class _InputIterator2>
5474 __includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5477 for (; __first2 != __last2; ++__first1)
5479 if (__first1 == __last1 || __comp(*__first2, *__first1))
5481 if (!__comp(*__first1, *__first2))
5487 template <class _InputIterator1, class _InputIterator2, class _Compare>
5488 inline _LIBCPP_INLINE_VISIBILITY
5490 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5493 #ifdef _LIBCPP_DEBUG
5494 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5495 __debug_less<_Compare> __c(__comp);
5496 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5497 #else // _LIBCPP_DEBUG
5498 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5499 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5500 #endif // _LIBCPP_DEBUG
5503 template <class _InputIterator1, class _InputIterator2>
5504 inline _LIBCPP_INLINE_VISIBILITY
5506 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
5508 return _VSTD::includes(__first1, __last1, __first2, __last2,
5509 __less<typename iterator_traits<_InputIterator1>::value_type,
5510 typename iterator_traits<_InputIterator2>::value_type>());
5515 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5517 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5518 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5520 for (; __first1 != __last1; ++__result)
5522 if (__first2 == __last2)
5523 return _VSTD::copy(__first1, __last1, __result);
5524 if (__comp(*__first2, *__first1))
5526 *__result = *__first2;
5531 *__result = *__first1;
5532 if (!__comp(*__first1, *__first2))
5537 return _VSTD::copy(__first2, __last2, __result);
5540 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5541 inline _LIBCPP_INLINE_VISIBILITY
5543 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5544 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5546 #ifdef _LIBCPP_DEBUG
5547 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5548 __debug_less<_Compare> __c(__comp);
5549 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5550 #else // _LIBCPP_DEBUG
5551 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5552 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5553 #endif // _LIBCPP_DEBUG
5556 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5557 inline _LIBCPP_INLINE_VISIBILITY
5559 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5560 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5562 return _VSTD::set_union(__first1, __last1, __first2, __last2, __result,
5563 __less<typename iterator_traits<_InputIterator1>::value_type,
5564 typename iterator_traits<_InputIterator2>::value_type>());
5569 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5571 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5572 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5574 while (__first1 != __last1 && __first2 != __last2)
5576 if (__comp(*__first1, *__first2))
5580 if (!__comp(*__first2, *__first1))
5582 *__result = *__first1;
5592 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5593 inline _LIBCPP_INLINE_VISIBILITY
5595 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5596 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5598 #ifdef _LIBCPP_DEBUG
5599 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5600 __debug_less<_Compare> __c(__comp);
5601 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5602 #else // _LIBCPP_DEBUG
5603 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5604 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5605 #endif // _LIBCPP_DEBUG
5608 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5609 inline _LIBCPP_INLINE_VISIBILITY
5611 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5612 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5614 return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result,
5615 __less<typename iterator_traits<_InputIterator1>::value_type,
5616 typename iterator_traits<_InputIterator2>::value_type>());
5621 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5623 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5624 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5626 while (__first1 != __last1)
5628 if (__first2 == __last2)
5629 return _VSTD::copy(__first1, __last1, __result);
5630 if (__comp(*__first1, *__first2))
5632 *__result = *__first1;
5638 if (!__comp(*__first2, *__first1))
5646 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5647 inline _LIBCPP_INLINE_VISIBILITY
5649 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5650 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5652 #ifdef _LIBCPP_DEBUG
5653 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5654 __debug_less<_Compare> __c(__comp);
5655 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5656 #else // _LIBCPP_DEBUG
5657 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5658 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5659 #endif // _LIBCPP_DEBUG
5662 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5663 inline _LIBCPP_INLINE_VISIBILITY
5665 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5666 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5668 return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result,
5669 __less<typename iterator_traits<_InputIterator1>::value_type,
5670 typename iterator_traits<_InputIterator2>::value_type>());
5673 // set_symmetric_difference
5675 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5677 __set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5678 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5680 while (__first1 != __last1)
5682 if (__first2 == __last2)
5683 return _VSTD::copy(__first1, __last1, __result);
5684 if (__comp(*__first1, *__first2))
5686 *__result = *__first1;
5692 if (__comp(*__first2, *__first1))
5694 *__result = *__first2;
5702 return _VSTD::copy(__first2, __last2, __result);
5705 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5706 inline _LIBCPP_INLINE_VISIBILITY
5708 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5709 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5711 #ifdef _LIBCPP_DEBUG
5712 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5713 __debug_less<_Compare> __c(__comp);
5714 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5715 #else // _LIBCPP_DEBUG
5716 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5717 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5718 #endif // _LIBCPP_DEBUG
5721 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5722 inline _LIBCPP_INLINE_VISIBILITY
5724 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5725 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5727 return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
5728 __less<typename iterator_traits<_InputIterator1>::value_type,
5729 typename iterator_traits<_InputIterator2>::value_type>());
5732 // lexicographical_compare
5734 template <class _Compare, class _InputIterator1, class _InputIterator2>
5736 __lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5737 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5739 for (; __first2 != __last2; ++__first1, (void) ++__first2)
5741 if (__first1 == __last1 || __comp(*__first1, *__first2))
5743 if (__comp(*__first2, *__first1))
5749 template <class _InputIterator1, class _InputIterator2, class _Compare>
5750 inline _LIBCPP_INLINE_VISIBILITY
5752 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5753 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5755 #ifdef _LIBCPP_DEBUG
5756 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5757 __debug_less<_Compare> __c(__comp);
5758 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5759 #else // _LIBCPP_DEBUG
5760 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5761 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5762 #endif // _LIBCPP_DEBUG
5765 template <class _InputIterator1, class _InputIterator2>
5766 inline _LIBCPP_INLINE_VISIBILITY
5768 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5769 _InputIterator2 __first2, _InputIterator2 __last2)
5771 return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,
5772 __less<typename iterator_traits<_InputIterator1>::value_type,
5773 typename iterator_traits<_InputIterator2>::value_type>());
5778 template <class _Compare, class _BidirectionalIterator>
5780 __next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5782 _BidirectionalIterator __i = __last;
5783 if (__first == __last || __first == --__i)
5787 _BidirectionalIterator __ip1 = __i;
5788 if (__comp(*--__i, *__ip1))
5790 _BidirectionalIterator __j = __last;
5791 while (!__comp(*__i, *--__j))
5794 _VSTD::reverse(__ip1, __last);
5799 _VSTD::reverse(__first, __last);
5805 template <class _BidirectionalIterator, class _Compare>
5806 inline _LIBCPP_INLINE_VISIBILITY
5808 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5810 #ifdef _LIBCPP_DEBUG
5811 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5812 __debug_less<_Compare> __c(__comp);
5813 return __next_permutation<_Comp_ref>(__first, __last, __c);
5814 #else // _LIBCPP_DEBUG
5815 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5816 return __next_permutation<_Comp_ref>(__first, __last, __comp);
5817 #endif // _LIBCPP_DEBUG
5820 template <class _BidirectionalIterator>
5821 inline _LIBCPP_INLINE_VISIBILITY
5823 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5825 return _VSTD::next_permutation(__first, __last,
5826 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5831 template <class _Compare, class _BidirectionalIterator>
5833 __prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5835 _BidirectionalIterator __i = __last;
5836 if (__first == __last || __first == --__i)
5840 _BidirectionalIterator __ip1 = __i;
5841 if (__comp(*__ip1, *--__i))
5843 _BidirectionalIterator __j = __last;
5844 while (!__comp(*--__j, *__i))
5847 _VSTD::reverse(__ip1, __last);
5852 _VSTD::reverse(__first, __last);
5858 template <class _BidirectionalIterator, class _Compare>
5859 inline _LIBCPP_INLINE_VISIBILITY
5861 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5863 #ifdef _LIBCPP_DEBUG
5864 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5865 __debug_less<_Compare> __c(__comp);
5866 return __prev_permutation<_Comp_ref>(__first, __last, __c);
5867 #else // _LIBCPP_DEBUG
5868 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5869 return __prev_permutation<_Comp_ref>(__first, __last, __comp);
5870 #endif // _LIBCPP_DEBUG
5873 template <class _BidirectionalIterator>
5874 inline _LIBCPP_INLINE_VISIBILITY
5876 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5878 return _VSTD::prev_permutation(__first, __last,
5879 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5882 _LIBCPP_END_NAMESPACE_STD
5884 #endif // _LIBCPP_ALGORITHM