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>
23 constexpr bool // constexpr in C++20
24 all_of(InputIterator first, InputIterator last, Predicate pred);
26 template <class InputIterator, class Predicate>
27 constexpr bool // constexpr in C++20
28 any_of(InputIterator first, InputIterator last, Predicate pred);
30 template <class InputIterator, class Predicate>
31 constexpr bool // constexpr in C++20
32 none_of(InputIterator first, InputIterator last, Predicate pred);
34 template <class InputIterator, class Function>
35 constexpr Function // constexpr in C++20
36 for_each(InputIterator first, InputIterator last, Function f);
38 template<class InputIterator, class Size, class Function>
39 constexpr InputIterator // constexpr in C++20
40 for_each_n(InputIterator first, Size n, Function f); // C++17
42 template <class InputIterator, class T>
43 constexpr InputIterator // constexpr in C++20
44 find(InputIterator first, InputIterator last, const T& value);
46 template <class InputIterator, class Predicate>
47 constexpr InputIterator // constexpr in C++20
48 find_if(InputIterator first, InputIterator last, Predicate pred);
50 template<class InputIterator, class Predicate>
51 InputIterator // constexpr in C++20
52 find_if_not(InputIterator first, InputIterator last, Predicate pred);
54 template <class ForwardIterator1, class ForwardIterator2>
55 ForwardIterator1 // constexpr in C++20
56 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
57 ForwardIterator2 first2, ForwardIterator2 last2);
59 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
60 ForwardIterator1 // constexpr in C++20
61 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
62 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
64 template <class ForwardIterator1, class ForwardIterator2>
65 constexpr ForwardIterator1 // constexpr in C++20
66 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
67 ForwardIterator2 first2, ForwardIterator2 last2);
69 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
70 constexpr ForwardIterator1 // constexpr in C++20
71 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
72 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
74 template <class ForwardIterator>
75 constexpr ForwardIterator // constexpr in C++20
76 adjacent_find(ForwardIterator first, ForwardIterator last);
78 template <class ForwardIterator, class BinaryPredicate>
79 constexpr ForwardIterator // constexpr in C++20
80 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
82 template <class InputIterator, class T>
83 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20
84 count(InputIterator first, InputIterator last, const T& value);
86 template <class InputIterator, class Predicate>
87 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20
88 count_if(InputIterator first, InputIterator last, Predicate pred);
90 template <class InputIterator1, class InputIterator2>
91 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
92 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
94 template <class InputIterator1, class InputIterator2>
95 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
96 mismatch(InputIterator1 first1, InputIterator1 last1,
97 InputIterator2 first2, InputIterator2 last2); // **C++14**
99 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
100 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
101 mismatch(InputIterator1 first1, InputIterator1 last1,
102 InputIterator2 first2, BinaryPredicate pred);
104 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
105 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
106 mismatch(InputIterator1 first1, InputIterator1 last1,
107 InputIterator2 first2, InputIterator2 last2,
108 BinaryPredicate pred); // **C++14**
110 template <class InputIterator1, class InputIterator2>
111 constexpr bool // constexpr in C++20
112 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
114 template <class InputIterator1, class InputIterator2>
115 constexpr bool // constexpr in C++20
116 equal(InputIterator1 first1, InputIterator1 last1,
117 InputIterator2 first2, InputIterator2 last2); // **C++14**
119 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
120 constexpr bool // constexpr in C++20
121 equal(InputIterator1 first1, InputIterator1 last1,
122 InputIterator2 first2, BinaryPredicate pred);
124 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
125 constexpr bool // constexpr in C++20
126 equal(InputIterator1 first1, InputIterator1 last1,
127 InputIterator2 first2, InputIterator2 last2,
128 BinaryPredicate pred); // **C++14**
130 template<class ForwardIterator1, class ForwardIterator2>
131 constexpr bool // constexpr in C++20
132 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
133 ForwardIterator2 first2);
135 template<class ForwardIterator1, class ForwardIterator2>
136 constexpr bool // constexpr in C++20
137 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
138 ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**
140 template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
141 constexpr bool // constexpr in C++20
142 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
143 ForwardIterator2 first2, BinaryPredicate pred);
145 template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
146 constexpr bool // constexpr in C++20
147 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
148 ForwardIterator2 first2, ForwardIterator2 last2,
149 BinaryPredicate pred); // **C++14**
151 template <class ForwardIterator1, class ForwardIterator2>
152 constexpr ForwardIterator1 // constexpr in C++20
153 search(ForwardIterator1 first1, ForwardIterator1 last1,
154 ForwardIterator2 first2, ForwardIterator2 last2);
156 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
157 constexpr ForwardIterator1 // constexpr in C++20
158 search(ForwardIterator1 first1, ForwardIterator1 last1,
159 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
161 template <class ForwardIterator, class Size, class T>
162 constexpr ForwardIterator // constexpr in C++20
163 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
165 template <class ForwardIterator, class Size, class T, class BinaryPredicate>
166 constexpr ForwardIterator // constexpr in C++20
167 search_n(ForwardIterator first, ForwardIterator last,
168 Size count, const T& value, BinaryPredicate pred);
170 template <class InputIterator, class OutputIterator>
172 copy(InputIterator first, InputIterator last, OutputIterator result);
174 template<class InputIterator, class OutputIterator, class Predicate>
176 copy_if(InputIterator first, InputIterator last,
177 OutputIterator result, Predicate pred);
179 template<class InputIterator, class Size, class OutputIterator>
181 copy_n(InputIterator first, Size n, OutputIterator result);
183 template <class BidirectionalIterator1, class BidirectionalIterator2>
184 BidirectionalIterator2
185 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
186 BidirectionalIterator2 result);
188 template <class ForwardIterator1, class ForwardIterator2>
190 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
192 template <class ForwardIterator1, class ForwardIterator2>
194 iter_swap(ForwardIterator1 a, ForwardIterator2 b);
196 template <class InputIterator, class OutputIterator, class UnaryOperation>
197 constexpr OutputIterator // constexpr in C++20
198 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
200 template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
201 constexpr OutputIterator // constexpr in C++20
202 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
203 OutputIterator result, BinaryOperation binary_op);
205 template <class ForwardIterator, class T>
206 constexpr void // constexpr in C++20
207 replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
209 template <class ForwardIterator, class Predicate, class T>
210 constexpr void // constexpr in C++20
211 replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
213 template <class InputIterator, class OutputIterator, class T>
214 constexpr OutputIterator // constexpr in C++20
215 replace_copy(InputIterator first, InputIterator last, OutputIterator result,
216 const T& old_value, const T& new_value);
218 template <class InputIterator, class OutputIterator, class Predicate, class T>
219 constexpr OutputIterator // constexpr in C++20
220 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
222 template <class ForwardIterator, class T>
223 constexpr void // constexpr in C++20
224 fill(ForwardIterator first, ForwardIterator last, const T& value);
226 template <class OutputIterator, class Size, class T>
227 constexpr OutputIterator // constexpr in C++20
228 fill_n(OutputIterator first, Size n, const T& value);
230 template <class ForwardIterator, class Generator>
231 constexpr void // constexpr in C++20
232 generate(ForwardIterator first, ForwardIterator last, Generator gen);
234 template <class OutputIterator, class Size, class Generator>
235 constexpr OutputIterator // constexpr in C++20
236 generate_n(OutputIterator first, Size n, Generator gen);
238 template <class ForwardIterator, class T>
239 constexpr ForwardIterator // constexpr in C++20
240 remove(ForwardIterator first, ForwardIterator last, const T& value);
242 template <class ForwardIterator, class Predicate>
243 constexpr ForwardIterator // constexpr in C++20
244 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
246 template <class InputIterator, class OutputIterator, class T>
247 constexpr OutputIterator // constexpr in C++20
248 remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
250 template <class InputIterator, class OutputIterator, class Predicate>
251 constexpr OutputIterator // constexpr in C++20
252 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
254 template <class ForwardIterator>
256 unique(ForwardIterator first, ForwardIterator last);
258 template <class ForwardIterator, class BinaryPredicate>
260 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
262 template <class InputIterator, class OutputIterator>
264 unique_copy(InputIterator first, InputIterator last, OutputIterator result);
266 template <class InputIterator, class OutputIterator, class BinaryPredicate>
268 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
270 template <class BidirectionalIterator>
272 reverse(BidirectionalIterator first, BidirectionalIterator last);
274 template <class BidirectionalIterator, class OutputIterator>
275 constexpr OutputIterator // constexpr in C++20
276 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
278 template <class ForwardIterator>
280 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
282 template <class ForwardIterator, class OutputIterator>
284 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
286 template <class RandomAccessIterator>
288 random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17
290 template <class RandomAccessIterator, class RandomNumberGenerator>
292 random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
293 RandomNumberGenerator& rand); // deprecated in C++14, removed in C++17
295 template<class PopulationIterator, class SampleIterator,
296 class Distance, class UniformRandomBitGenerator>
297 SampleIterator sample(PopulationIterator first, PopulationIterator last,
298 SampleIterator out, Distance n,
299 UniformRandomBitGenerator&& g); // C++17
301 template<class RandomAccessIterator, class UniformRandomNumberGenerator>
302 void shuffle(RandomAccessIterator first, RandomAccessIterator last,
303 UniformRandomNumberGenerator&& g);
305 template <class InputIterator, class Predicate>
306 constexpr bool // constexpr in C++20
307 is_partitioned(InputIterator first, InputIterator last, Predicate pred);
309 template <class ForwardIterator, class Predicate>
311 partition(ForwardIterator first, ForwardIterator last, Predicate pred);
313 template <class InputIterator, class OutputIterator1,
314 class OutputIterator2, class Predicate>
315 constexpr pair<OutputIterator1, OutputIterator2> // constexpr in C++20
316 partition_copy(InputIterator first, InputIterator last,
317 OutputIterator1 out_true, OutputIterator2 out_false,
320 template <class ForwardIterator, class Predicate>
322 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
324 template<class ForwardIterator, class Predicate>
325 constexpr ForwardIterator // constexpr in C++20
326 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
328 template <class ForwardIterator>
329 constexpr bool // constexpr in C++20
330 is_sorted(ForwardIterator first, ForwardIterator last);
332 template <class ForwardIterator, class Compare>
334 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
336 template<class ForwardIterator>
337 constexpr ForwardIterator // constexpr in C++20
338 is_sorted_until(ForwardIterator first, ForwardIterator last);
340 template <class ForwardIterator, class Compare>
341 constexpr ForwardIterator // constexpr in C++20
342 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
344 template <class RandomAccessIterator>
346 sort(RandomAccessIterator first, RandomAccessIterator last);
348 template <class RandomAccessIterator, class Compare>
350 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
352 template <class RandomAccessIterator>
354 stable_sort(RandomAccessIterator first, RandomAccessIterator last);
356 template <class RandomAccessIterator, class Compare>
358 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
360 template <class RandomAccessIterator>
362 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
364 template <class RandomAccessIterator, class Compare>
366 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
368 template <class InputIterator, class RandomAccessIterator>
370 partial_sort_copy(InputIterator first, InputIterator last,
371 RandomAccessIterator result_first, RandomAccessIterator result_last);
373 template <class InputIterator, class RandomAccessIterator, class Compare>
375 partial_sort_copy(InputIterator first, InputIterator last,
376 RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
378 template <class RandomAccessIterator>
380 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
382 template <class RandomAccessIterator, class Compare>
384 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
386 template <class ForwardIterator, class T>
387 constexpr ForwardIterator // constexpr in C++20
388 lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
390 template <class ForwardIterator, class T, class Compare>
391 constexpr ForwardIterator // constexpr in C++20
392 lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
394 template <class ForwardIterator, class T>
395 constexpr ForwardIterator // constexpr in C++20
396 upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
398 template <class ForwardIterator, class T, class Compare>
399 constexpr ForwardIterator // constexpr in C++20
400 upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
402 template <class ForwardIterator, class T>
403 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20
404 equal_range(ForwardIterator first, ForwardIterator last, const T& value);
406 template <class ForwardIterator, class T, class Compare>
407 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20
408 equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
410 template <class ForwardIterator, class T>
411 constexpr bool // constexpr in C++20
412 binary_search(ForwardIterator first, ForwardIterator last, const T& value);
414 template <class ForwardIterator, class T, class Compare>
415 constexpr bool // constexpr in C++20
416 binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
418 template <class InputIterator1, class InputIterator2, class OutputIterator>
420 merge(InputIterator1 first1, InputIterator1 last1,
421 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
423 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
425 merge(InputIterator1 first1, InputIterator1 last1,
426 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
428 template <class BidirectionalIterator>
430 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
432 template <class BidirectionalIterator, class Compare>
434 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
436 template <class InputIterator1, class InputIterator2>
437 constexpr bool // constexpr in C++20
438 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
440 template <class InputIterator1, class InputIterator2, class Compare>
441 constexpr bool // constexpr in C++20
442 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
444 template <class InputIterator1, class InputIterator2, class OutputIterator>
446 set_union(InputIterator1 first1, InputIterator1 last1,
447 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
449 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
451 set_union(InputIterator1 first1, InputIterator1 last1,
452 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
454 template <class InputIterator1, class InputIterator2, class OutputIterator>
455 constexpr OutputIterator // constexpr in C++20
456 set_intersection(InputIterator1 first1, InputIterator1 last1,
457 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
459 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
460 constexpr OutputIterator // constexpr in C++20
461 set_intersection(InputIterator1 first1, InputIterator1 last1,
462 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
464 template <class InputIterator1, class InputIterator2, class OutputIterator>
466 set_difference(InputIterator1 first1, InputIterator1 last1,
467 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
469 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
471 set_difference(InputIterator1 first1, InputIterator1 last1,
472 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
474 template <class InputIterator1, class InputIterator2, class OutputIterator>
476 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
477 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
479 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
481 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
482 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
484 template <class RandomAccessIterator>
486 push_heap(RandomAccessIterator first, RandomAccessIterator last);
488 template <class RandomAccessIterator, class Compare>
490 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
492 template <class RandomAccessIterator>
494 pop_heap(RandomAccessIterator first, RandomAccessIterator last);
496 template <class RandomAccessIterator, class Compare>
498 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
500 template <class RandomAccessIterator>
502 make_heap(RandomAccessIterator first, RandomAccessIterator last);
504 template <class RandomAccessIterator, class Compare>
506 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
508 template <class RandomAccessIterator>
510 sort_heap(RandomAccessIterator first, RandomAccessIterator last);
512 template <class RandomAccessIterator, class Compare>
514 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
516 template <class RandomAccessIterator>
517 constexpr bool // constexpr in C++20
518 is_heap(RandomAccessIterator first, RandomAccessiterator last);
520 template <class RandomAccessIterator, class Compare>
521 constexpr bool // constexpr in C++20
522 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
524 template <class RandomAccessIterator>
525 constexpr RandomAccessIterator // constexpr in C++20
526 is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
528 template <class RandomAccessIterator, class Compare>
529 constexpr RandomAccessIterator // constexpr in C++20
530 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
532 template <class ForwardIterator>
534 min_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14
536 template <class ForwardIterator, class Compare>
538 min_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14
542 min(const T& a, const T& b); // constexpr in C++14
544 template <class T, class Compare>
546 min(const T& a, const T& b, Compare comp); // constexpr in C++14
550 min(initializer_list<T> t); // constexpr in C++14
552 template<class T, class Compare>
554 min(initializer_list<T> t, Compare comp); // constexpr in C++14
557 constexpr const T& clamp( const T& v, const T& lo, const T& hi ); // C++17
559 template<class T, class Compare>
560 constexpr const T& clamp( const T& v, const T& lo, const T& hi, Compare comp ); // C++17
562 template <class ForwardIterator>
564 max_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14
566 template <class ForwardIterator, class Compare>
568 max_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14
572 max(const T& a, const T& b); // constexpr in C++14
574 template <class T, class Compare>
576 max(const T& a, const T& b, Compare comp); // constexpr in C++14
580 max(initializer_list<T> t); // constexpr in C++14
582 template<class T, class Compare>
584 max(initializer_list<T> t, Compare comp); // constexpr in C++14
586 template<class ForwardIterator>
587 pair<ForwardIterator, ForwardIterator>
588 minmax_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14
590 template<class ForwardIterator, class Compare>
591 pair<ForwardIterator, ForwardIterator>
592 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14
595 pair<const T&, const T&>
596 minmax(const T& a, const T& b); // constexpr in C++14
598 template<class T, class Compare>
599 pair<const T&, const T&>
600 minmax(const T& a, const T& b, Compare comp); // constexpr in C++14
604 minmax(initializer_list<T> t); // constexpr in C++14
606 template<class T, class Compare>
608 minmax(initializer_list<T> t, Compare comp); // constexpr in C++14
610 template <class InputIterator1, class InputIterator2>
611 constexpr bool // constexpr in C++20
612 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
614 template <class InputIterator1, class InputIterator2, class Compare>
615 constexpr bool // constexpr in C++20
616 lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
617 InputIterator2 first2, InputIterator2 last2, Compare comp);
619 template <class BidirectionalIterator>
621 next_permutation(BidirectionalIterator first, BidirectionalIterator last);
623 template <class BidirectionalIterator, class Compare>
625 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
627 template <class BidirectionalIterator>
629 prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
631 template <class BidirectionalIterator, class Compare>
633 prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
640 #include <initializer_list>
641 #include <type_traits>
643 #include <utility> // needed to provide swap_ranges.
645 #include <functional>
653 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
654 #pragma GCC system_header
658 #include <__undef_macros>
661 _LIBCPP_BEGIN_NAMESPACE_STD
663 // I'd like to replace these with _VSTD::equal_to<void>, but can't because:
664 // * That only works with C++14 and later, and
665 // * We haven't included <functional> here.
666 template <class _T1, class _T2 = _T1>
669 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
670 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;}
671 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;}
672 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;}
676 struct __equal_to<_T1, _T1>
678 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
679 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
683 struct __equal_to<const _T1, _T1>
685 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
686 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
690 struct __equal_to<_T1, const _T1>
692 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
693 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
696 template <class _T1, class _T2 = _T1>
699 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
700 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
702 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
703 bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;}
705 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
706 bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;}
708 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
709 bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;}
713 struct __less<_T1, _T1>
715 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
716 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
720 struct __less<const _T1, _T1>
722 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
723 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
727 struct __less<_T1, const _T1>
729 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
730 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
733 template <class _Predicate>
734 class __invert // invert the sense of a comparison
739 _LIBCPP_INLINE_VISIBILITY __invert() {}
741 _LIBCPP_INLINE_VISIBILITY
742 explicit __invert(_Predicate __p) : __p_(__p) {}
745 _LIBCPP_INLINE_VISIBILITY
746 bool operator()(const _T1& __x) {return !__p_(__x);}
748 template <class _T1, class _T2>
749 _LIBCPP_INLINE_VISIBILITY
750 bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);}
753 // Perform division by two quickly for positive integers (llvm.org/PR39129)
755 template <typename _Integral>
756 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
759 is_integral<_Integral>::value,
762 __half_positive(_Integral __value)
764 return static_cast<_Integral>(static_cast<typename make_unsigned<_Integral>::type>(__value) / 2);
767 template <typename _Tp>
768 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
771 !is_integral<_Tp>::value,
774 __half_positive(_Tp __value)
781 template <class _Compare>
785 __debug_less(_Compare& __c) : __comp_(__c) {}
787 template <class _Tp, class _Up>
788 bool operator()(const _Tp& __x, const _Up& __y)
790 bool __r = __comp_(__x, __y);
792 __do_compare_assert(0, __y, __x);
796 template <class _LHS, class _RHS>
797 inline _LIBCPP_INLINE_VISIBILITY
798 decltype((void)_VSTD::declval<_Compare&>()(
799 _VSTD::declval<_LHS const&>(), _VSTD::declval<_RHS const&>()))
800 __do_compare_assert(int, _LHS const& __l, _RHS const& __r) {
801 _LIBCPP_ASSERT(!__comp_(__l, __r),
802 "Comparator does not induce a strict weak ordering");
805 template <class _LHS, class _RHS>
806 inline _LIBCPP_INLINE_VISIBILITY
807 void __do_compare_assert(long, _LHS const&, _RHS const&) {}
810 #endif // _LIBCPP_DEBUG
814 template <class _InputIterator, class _Predicate>
815 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
817 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
819 for (; __first != __last; ++__first)
820 if (!__pred(*__first))
827 template <class _InputIterator, class _Predicate>
828 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
830 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
832 for (; __first != __last; ++__first)
833 if (__pred(*__first))
840 template <class _InputIterator, class _Predicate>
841 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
843 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
845 for (; __first != __last; ++__first)
846 if (__pred(*__first))
853 template <class _InputIterator, class _Function>
854 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
856 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
858 for (; __first != __last; ++__first)
863 #if _LIBCPP_STD_VER > 14
866 template <class _InputIterator, class _Size, class _Function>
867 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
869 for_each_n(_InputIterator __first, _Size __orig_n, _Function __f)
871 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
872 _IntegralSize __n = __orig_n;
885 template <class _InputIterator, class _Tp>
886 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
888 find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
890 for (; __first != __last; ++__first)
891 if (*__first == __value_)
898 template <class _InputIterator, class _Predicate>
899 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
901 find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
903 for (; __first != __last; ++__first)
904 if (__pred(*__first))
911 template<class _InputIterator, class _Predicate>
912 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
914 find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
916 for (; __first != __last; ++__first)
917 if (!__pred(*__first))
924 template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
925 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1
926 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
927 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
928 forward_iterator_tag, forward_iterator_tag)
930 // modeled after search algorithm
931 _ForwardIterator1 __r = __last1; // __last1 is the "default" answer
932 if (__first2 == __last2)
938 if (__first1 == __last1) // if source exhausted return last correct answer
939 return __r; // (or __last1 if never found)
940 if (__pred(*__first1, *__first2))
944 // *__first1 matches *__first2, now match elements after here
945 _ForwardIterator1 __m1 = __first1;
946 _ForwardIterator2 __m2 = __first2;
949 if (++__m2 == __last2)
950 { // Pattern exhaused, record answer and search for another one
955 if (++__m1 == __last1) // Source exhausted, return last answer
957 if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first
961 } // else there is a match, check next elements
966 template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2>
967 _LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator1
968 __find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,
969 _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred,
970 bidirectional_iterator_tag, bidirectional_iterator_tag)
972 // modeled after search algorithm (in reverse)
973 if (__first2 == __last2)
974 return __last1; // Everything matches an empty sequence
975 _BidirectionalIterator1 __l1 = __last1;
976 _BidirectionalIterator2 __l2 = __last2;
980 // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks
983 if (__first1 == __l1) // return __last1 if no element matches *__first2
985 if (__pred(*--__l1, *__l2))
988 // *__l1 matches *__l2, now match elements before here
989 _BidirectionalIterator1 __m1 = __l1;
990 _BidirectionalIterator2 __m2 = __l2;
993 if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern)
995 if (__m1 == __first1) // Otherwise if source exhaused, pattern not found
997 if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1
1000 } // else there is a match, check next elements
1005 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1006 _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1
1007 __find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1008 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1009 random_access_iterator_tag, random_access_iterator_tag)
1011 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern
1012 typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;
1015 typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;
1016 if (__len1 < __len2)
1018 const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here
1019 _RandomAccessIterator1 __l1 = __last1;
1020 _RandomAccessIterator2 __l2 = __last2;
1028 if (__pred(*--__l1, *__l2))
1031 _RandomAccessIterator1 __m1 = __l1;
1032 _RandomAccessIterator2 __m2 = __l2;
1035 if (__m2 == __first2)
1037 // no need to check range on __m1 because __s guarantees we have enough source
1038 if (!__pred(*--__m1, *--__m2))
1046 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1047 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1049 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1050 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1052 return _VSTD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type>
1053 (__first1, __last1, __first2, __last2, __pred,
1054 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1055 typename iterator_traits<_ForwardIterator2>::iterator_category());
1058 template <class _ForwardIterator1, class _ForwardIterator2>
1059 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1061 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1062 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1064 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1065 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1066 return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1071 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1072 _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator1
1073 __find_first_of_ce(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1074 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1076 for (; __first1 != __last1; ++__first1)
1077 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1078 if (__pred(*__first1, *__j))
1084 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1085 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1087 find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1088 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1090 return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred);
1093 template <class _ForwardIterator1, class _ForwardIterator2>
1094 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1096 find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1097 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1099 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1100 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1101 return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1106 template <class _ForwardIterator, class _BinaryPredicate>
1107 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1109 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
1111 if (__first != __last)
1113 _ForwardIterator __i = __first;
1114 while (++__i != __last)
1116 if (__pred(*__first, *__i))
1124 template <class _ForwardIterator>
1125 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1127 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
1129 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1130 return _VSTD::adjacent_find(__first, __last, __equal_to<__v>());
1135 template <class _InputIterator, class _Tp>
1136 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1137 typename iterator_traits<_InputIterator>::difference_type
1138 count(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
1140 typename iterator_traits<_InputIterator>::difference_type __r(0);
1141 for (; __first != __last; ++__first)
1142 if (*__first == __value_)
1149 template <class _InputIterator, class _Predicate>
1150 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1151 typename iterator_traits<_InputIterator>::difference_type
1152 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
1154 typename iterator_traits<_InputIterator>::difference_type __r(0);
1155 for (; __first != __last; ++__first)
1156 if (__pred(*__first))
1163 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1164 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1165 pair<_InputIterator1, _InputIterator2>
1166 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1167 _InputIterator2 __first2, _BinaryPredicate __pred)
1169 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1170 if (!__pred(*__first1, *__first2))
1172 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1175 template <class _InputIterator1, class _InputIterator2>
1176 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1177 pair<_InputIterator1, _InputIterator2>
1178 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1180 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1181 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1182 return _VSTD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1185 #if _LIBCPP_STD_VER > 11
1186 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1187 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1188 pair<_InputIterator1, _InputIterator2>
1189 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1190 _InputIterator2 __first2, _InputIterator2 __last2,
1191 _BinaryPredicate __pred)
1193 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1194 if (!__pred(*__first1, *__first2))
1196 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1199 template <class _InputIterator1, class _InputIterator2>
1200 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1201 pair<_InputIterator1, _InputIterator2>
1202 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1203 _InputIterator2 __first2, _InputIterator2 __last2)
1205 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1206 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1207 return _VSTD::mismatch(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1213 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1214 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1216 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred)
1218 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1219 if (!__pred(*__first1, *__first2))
1224 template <class _InputIterator1, class _InputIterator2>
1225 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1227 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1229 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1230 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1231 return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1234 #if _LIBCPP_STD_VER > 11
1235 template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2>
1236 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1238 __equal(_InputIterator1 __first1, _InputIterator1 __last1,
1239 _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred,
1240 input_iterator_tag, input_iterator_tag )
1242 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1243 if (!__pred(*__first1, *__first2))
1245 return __first1 == __last1 && __first2 == __last2;
1248 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1249 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1251 __equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1252 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1253 random_access_iterator_tag, random_access_iterator_tag )
1255 if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
1257 return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2,
1258 typename add_lvalue_reference<_BinaryPredicate>::type>
1259 (__first1, __last1, __first2, __pred );
1262 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1263 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1265 equal(_InputIterator1 __first1, _InputIterator1 __last1,
1266 _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred )
1268 return _VSTD::__equal<typename add_lvalue_reference<_BinaryPredicate>::type>
1269 (__first1, __last1, __first2, __last2, __pred,
1270 typename iterator_traits<_InputIterator1>::iterator_category(),
1271 typename iterator_traits<_InputIterator2>::iterator_category());
1274 template <class _InputIterator1, class _InputIterator2>
1275 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1277 equal(_InputIterator1 __first1, _InputIterator1 __last1,
1278 _InputIterator2 __first2, _InputIterator2 __last2)
1280 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1281 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1282 return _VSTD::__equal(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(),
1283 typename iterator_traits<_InputIterator1>::iterator_category(),
1284 typename iterator_traits<_InputIterator2>::iterator_category());
1290 template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1291 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
1292 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1293 _ForwardIterator2 __first2, _BinaryPredicate __pred)
1295 // shorten sequences as much as possible by lopping of any equal prefix
1296 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1297 if (!__pred(*__first1, *__first2))
1299 if (__first1 == __last1)
1302 // __first1 != __last1 && *__first1 != *__first2
1303 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1304 _D1 __l1 = _VSTD::distance(__first1, __last1);
1307 _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1);
1308 // For each element in [f1, l1) see if there are the same number of
1309 // equal elements in [f2, l2)
1310 for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
1312 // Have we already counted the number of *__i in [f1, l1)?
1313 _ForwardIterator1 __match = __first1;
1314 for (; __match != __i; ++__match)
1315 if (__pred(*__match, *__i))
1317 if (__match == __i) {
1318 // Count number of *__i in [f2, l2)
1320 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1321 if (__pred(*__i, *__j))
1325 // Count number of *__i in [__i, l1) (we can start with 1)
1327 for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
1328 if (__pred(*__i, *__j))
1337 template<class _ForwardIterator1, class _ForwardIterator2>
1338 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1340 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1341 _ForwardIterator2 __first2)
1343 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1344 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1345 return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1348 #if _LIBCPP_STD_VER > 11
1349 template<class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
1350 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
1351 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1352 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1353 _BinaryPredicate __pred,
1354 forward_iterator_tag, forward_iterator_tag )
1356 // shorten sequences as much as possible by lopping of any equal prefix
1357 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1358 if (!__pred(*__first1, *__first2))
1360 if (__first1 == __last1)
1361 return __first2 == __last2;
1362 else if (__first2 == __last2)
1365 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1366 _D1 __l1 = _VSTD::distance(__first1, __last1);
1368 typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2;
1369 _D2 __l2 = _VSTD::distance(__first2, __last2);
1373 // For each element in [f1, l1) see if there are the same number of
1374 // equal elements in [f2, l2)
1375 for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
1377 // Have we already counted the number of *__i in [f1, l1)?
1378 _ForwardIterator1 __match = __first1;
1379 for (; __match != __i; ++__match)
1380 if (__pred(*__match, *__i))
1382 if (__match == __i) {
1383 // Count number of *__i in [f2, l2)
1385 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1386 if (__pred(*__i, *__j))
1390 // Count number of *__i in [__i, l1) (we can start with 1)
1392 for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
1393 if (__pred(*__i, *__j))
1402 template<class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1403 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
1404 __is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1,
1405 _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2,
1406 _BinaryPredicate __pred,
1407 random_access_iterator_tag, random_access_iterator_tag )
1409 if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
1411 return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2,
1412 typename add_lvalue_reference<_BinaryPredicate>::type>
1413 (__first1, __last1, __first2, __pred );
1416 template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1417 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1419 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1420 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1421 _BinaryPredicate __pred )
1423 return _VSTD::__is_permutation<typename add_lvalue_reference<_BinaryPredicate>::type>
1424 (__first1, __last1, __first2, __last2, __pred,
1425 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1426 typename iterator_traits<_ForwardIterator2>::iterator_category());
1429 template<class _ForwardIterator1, class _ForwardIterator2>
1430 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1432 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1433 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1435 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1436 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1437 return _VSTD::__is_permutation(__first1, __last1, __first2, __last2,
1438 __equal_to<__v1, __v2>(),
1439 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1440 typename iterator_traits<_ForwardIterator2>::iterator_category());
1445 // __search is in <functional>
1447 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1448 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1450 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1451 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1453 return _VSTD::__search<typename add_lvalue_reference<_BinaryPredicate>::type>
1454 (__first1, __last1, __first2, __last2, __pred,
1455 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1456 typename iterator_traits<_ForwardIterator2>::iterator_category())
1460 template <class _ForwardIterator1, class _ForwardIterator2>
1461 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1463 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1464 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1466 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1467 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1468 return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1472 #if _LIBCPP_STD_VER > 14
1473 template <class _ForwardIterator, class _Searcher>
1474 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1475 _ForwardIterator search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher &__s)
1476 { return __s(__f, __l).first; }
1481 template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp>
1482 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
1483 __search_n(_ForwardIterator __first, _ForwardIterator __last,
1484 _Size __count, const _Tp& __value_, _BinaryPredicate __pred, forward_iterator_tag)
1490 // Find first element in sequence that matchs __value_, with a mininum of loop checks
1493 if (__first == __last) // return __last if no element matches __value_
1495 if (__pred(*__first, __value_))
1499 // *__first matches __value_, now match elements after here
1500 _ForwardIterator __m = __first;
1504 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1506 if (++__m == __last) // Otherwise if source exhaused, pattern not found
1508 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1513 } // else there is a match, check next elements
1518 template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp>
1519 _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
1520 __search_n(_RandomAccessIterator __first, _RandomAccessIterator __last,
1521 _Size __count, const _Tp& __value_, _BinaryPredicate __pred, random_access_iterator_tag)
1525 _Size __len = static_cast<_Size>(__last - __first);
1526 if (__len < __count)
1528 const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here
1531 // Find first element in sequence that matchs __value_, with a mininum of loop checks
1534 if (__first >= __s) // return __last if no element matches __value_
1536 if (__pred(*__first, __value_))
1540 // *__first matches __value_, now match elements after here
1541 _RandomAccessIterator __m = __first;
1545 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1547 ++__m; // no need to check range on __m because __s guarantees we have enough source
1548 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1553 } // else there is a match, check next elements
1558 template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
1559 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1561 search_n(_ForwardIterator __first, _ForwardIterator __last,
1562 _Size __count, const _Tp& __value_, _BinaryPredicate __pred)
1564 return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>
1565 (__first, __last, __convert_to_integral(__count), __value_, __pred,
1566 typename iterator_traits<_ForwardIterator>::iterator_category());
1569 template <class _ForwardIterator, class _Size, class _Tp>
1570 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1572 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
1574 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1575 return _VSTD::search_n(__first, __last, __convert_to_integral(__count),
1576 __value_, __equal_to<__v, _Tp>());
1580 template <class _Iter>
1581 inline _LIBCPP_INLINE_VISIBILITY
1583 __unwrap_iter(_Iter __i)
1588 template <class _Tp>
1589 inline _LIBCPP_INLINE_VISIBILITY
1592 is_trivially_copy_assignable<_Tp>::value,
1595 __unwrap_iter(move_iterator<_Tp*> __i)
1600 #if _LIBCPP_DEBUG_LEVEL < 2
1602 template <class _Tp>
1603 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
1606 is_trivially_copy_assignable<_Tp>::value,
1609 __unwrap_iter(__wrap_iter<_Tp*> __i)
1616 template <class _Tp>
1617 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
1620 is_trivially_copy_assignable<_Tp>::value,
1623 __unwrap_iter(__wrap_iter<_Tp*> __i)
1628 #endif // _LIBCPP_DEBUG_LEVEL < 2
1630 template <class _InputIterator, class _OutputIterator>
1631 inline _LIBCPP_INLINE_VISIBILITY
1633 __copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1635 for (; __first != __last; ++__first, (void) ++__result)
1636 *__result = *__first;
1640 template <class _Tp, class _Up>
1641 inline _LIBCPP_INLINE_VISIBILITY
1644 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1645 is_trivially_copy_assignable<_Up>::value,
1648 __copy(_Tp* __first, _Tp* __last, _Up* __result)
1650 const size_t __n = static_cast<size_t>(__last - __first);
1652 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1653 return __result + __n;
1656 template <class _InputIterator, class _OutputIterator>
1657 inline _LIBCPP_INLINE_VISIBILITY
1659 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1661 return _VSTD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1666 template <class _BidirectionalIterator, class _OutputIterator>
1667 inline _LIBCPP_INLINE_VISIBILITY
1669 __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
1671 while (__first != __last)
1672 *--__result = *--__last;
1676 template <class _Tp, class _Up>
1677 inline _LIBCPP_INLINE_VISIBILITY
1680 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1681 is_trivially_copy_assignable<_Up>::value,
1684 __copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
1686 const size_t __n = static_cast<size_t>(__last - __first);
1690 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1695 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1696 inline _LIBCPP_INLINE_VISIBILITY
1697 _BidirectionalIterator2
1698 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1699 _BidirectionalIterator2 __result)
1701 return _VSTD::__copy_backward(__unwrap_iter(__first),
1702 __unwrap_iter(__last),
1703 __unwrap_iter(__result));
1708 template<class _InputIterator, class _OutputIterator, class _Predicate>
1709 inline _LIBCPP_INLINE_VISIBILITY
1711 copy_if(_InputIterator __first, _InputIterator __last,
1712 _OutputIterator __result, _Predicate __pred)
1714 for (; __first != __last; ++__first)
1716 if (__pred(*__first))
1718 *__result = *__first;
1727 template<class _InputIterator, class _Size, class _OutputIterator>
1728 inline _LIBCPP_INLINE_VISIBILITY
1731 __is_input_iterator<_InputIterator>::value &&
1732 !__is_random_access_iterator<_InputIterator>::value,
1735 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1737 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
1738 _IntegralSize __n = __orig_n;
1741 *__result = *__first;
1743 for (--__n; __n > 0; --__n)
1746 *__result = *__first;
1753 template<class _InputIterator, class _Size, class _OutputIterator>
1754 inline _LIBCPP_INLINE_VISIBILITY
1757 __is_random_access_iterator<_InputIterator>::value,
1760 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1762 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
1763 _IntegralSize __n = __orig_n;
1764 return _VSTD::copy(__first, __first + __n, __result);
1769 template <class _InputIterator, class _OutputIterator>
1770 inline _LIBCPP_INLINE_VISIBILITY
1772 __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1774 for (; __first != __last; ++__first, (void) ++__result)
1775 *__result = _VSTD::move(*__first);
1779 template <class _Tp, class _Up>
1780 inline _LIBCPP_INLINE_VISIBILITY
1783 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1784 is_trivially_copy_assignable<_Up>::value,
1787 __move(_Tp* __first, _Tp* __last, _Up* __result)
1789 const size_t __n = static_cast<size_t>(__last - __first);
1791 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1792 return __result + __n;
1795 template <class _InputIterator, class _OutputIterator>
1796 inline _LIBCPP_INLINE_VISIBILITY
1798 move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1800 return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1805 template <class _InputIterator, class _OutputIterator>
1806 inline _LIBCPP_INLINE_VISIBILITY
1808 __move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1810 while (__first != __last)
1811 *--__result = _VSTD::move(*--__last);
1815 template <class _Tp, class _Up>
1816 inline _LIBCPP_INLINE_VISIBILITY
1819 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1820 is_trivially_copy_assignable<_Up>::value,
1823 __move_backward(_Tp* __first, _Tp* __last, _Up* __result)
1825 const size_t __n = static_cast<size_t>(__last - __first);
1829 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1834 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1835 inline _LIBCPP_INLINE_VISIBILITY
1836 _BidirectionalIterator2
1837 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1838 _BidirectionalIterator2 __result)
1840 return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1845 // moved to <type_traits> for better swap / noexcept support
1849 template <class _InputIterator, class _OutputIterator, class _UnaryOperation>
1850 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1852 transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op)
1854 for (; __first != __last; ++__first, (void) ++__result)
1855 *__result = __op(*__first);
1859 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation>
1860 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1862 transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
1863 _OutputIterator __result, _BinaryOperation __binary_op)
1865 for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result)
1866 *__result = __binary_op(*__first1, *__first2);
1872 template <class _ForwardIterator, class _Tp>
1873 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1875 replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value)
1877 for (; __first != __last; ++__first)
1878 if (*__first == __old_value)
1879 *__first = __new_value;
1884 template <class _ForwardIterator, class _Predicate, class _Tp>
1885 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1887 replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value)
1889 for (; __first != __last; ++__first)
1890 if (__pred(*__first))
1891 *__first = __new_value;
1896 template <class _InputIterator, class _OutputIterator, class _Tp>
1897 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1899 replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1900 const _Tp& __old_value, const _Tp& __new_value)
1902 for (; __first != __last; ++__first, (void) ++__result)
1903 if (*__first == __old_value)
1904 *__result = __new_value;
1906 *__result = *__first;
1912 template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp>
1913 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1915 replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1916 _Predicate __pred, const _Tp& __new_value)
1918 for (; __first != __last; ++__first, (void) ++__result)
1919 if (__pred(*__first))
1920 *__result = __new_value;
1922 *__result = *__first;
1928 template <class _OutputIterator, class _Size, class _Tp>
1929 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1931 __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
1933 for (; __n > 0; ++__first, (void) --__n)
1934 *__first = __value_;
1938 template <class _OutputIterator, class _Size, class _Tp>
1939 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1941 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
1943 return _VSTD::__fill_n(__first, __convert_to_integral(__n), __value_);
1948 template <class _ForwardIterator, class _Tp>
1949 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1951 __fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
1953 for (; __first != __last; ++__first)
1954 *__first = __value_;
1957 template <class _RandomAccessIterator, class _Tp>
1958 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1960 __fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag)
1962 _VSTD::fill_n(__first, __last - __first, __value_);
1965 template <class _ForwardIterator, class _Tp>
1966 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1968 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
1970 _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category());
1975 template <class _ForwardIterator, class _Generator>
1976 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1978 generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
1980 for (; __first != __last; ++__first)
1986 template <class _OutputIterator, class _Size, class _Generator>
1987 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1989 generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen)
1991 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
1992 _IntegralSize __n = __orig_n;
1993 for (; __n > 0; ++__first, (void) --__n)
2000 template <class _ForwardIterator, class _Tp>
2001 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
2002 remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2004 __first = _VSTD::find(__first, __last, __value_);
2005 if (__first != __last)
2007 _ForwardIterator __i = __first;
2008 while (++__i != __last)
2010 if (!(*__i == __value_))
2012 *__first = _VSTD::move(*__i);
2022 template <class _ForwardIterator, class _Predicate>
2023 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
2024 remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2026 __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
2027 (__first, __last, __pred);
2028 if (__first != __last)
2030 _ForwardIterator __i = __first;
2031 while (++__i != __last)
2035 *__first = _VSTD::move(*__i);
2045 template <class _InputIterator, class _OutputIterator, class _Tp>
2046 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2048 remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_)
2050 for (; __first != __last; ++__first)
2052 if (!(*__first == __value_))
2054 *__result = *__first;
2063 template <class _InputIterator, class _OutputIterator, class _Predicate>
2064 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2066 remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
2068 for (; __first != __last; ++__first)
2070 if (!__pred(*__first))
2072 *__result = *__first;
2081 template <class _ForwardIterator, class _BinaryPredicate>
2082 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
2083 unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
2085 __first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type>
2086 (__first, __last, __pred);
2087 if (__first != __last)
2091 _ForwardIterator __i = __first;
2092 for (++__i; ++__i != __last;)
2093 if (!__pred(*__first, *__i))
2094 *++__first = _VSTD::move(*__i);
2100 template <class _ForwardIterator>
2101 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2103 unique(_ForwardIterator __first, _ForwardIterator __last)
2105 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
2106 return _VSTD::unique(__first, __last, __equal_to<__v>());
2111 template <class _BinaryPredicate, class _InputIterator, class _OutputIterator>
2112 _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
2113 __unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2114 input_iterator_tag, output_iterator_tag)
2116 if (__first != __last)
2118 typename iterator_traits<_InputIterator>::value_type __t(*__first);
2121 while (++__first != __last)
2123 if (!__pred(__t, *__first))
2134 template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator>
2135 _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
2136 __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2137 forward_iterator_tag, output_iterator_tag)
2139 if (__first != __last)
2141 _ForwardIterator __i = __first;
2144 while (++__first != __last)
2146 if (!__pred(*__i, *__first))
2148 *__result = *__first;
2157 template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator>
2158 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
2159 __unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred,
2160 input_iterator_tag, forward_iterator_tag)
2162 if (__first != __last)
2164 *__result = *__first;
2165 while (++__first != __last)
2166 if (!__pred(*__result, *__first))
2167 *++__result = *__first;
2173 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
2174 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2176 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred)
2178 return _VSTD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type>
2179 (__first, __last, __result, __pred,
2180 typename iterator_traits<_InputIterator>::iterator_category(),
2181 typename iterator_traits<_OutputIterator>::iterator_category());
2184 template <class _InputIterator, class _OutputIterator>
2185 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2187 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
2189 typedef typename iterator_traits<_InputIterator>::value_type __v;
2190 return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());
2195 template <class _BidirectionalIterator>
2196 inline _LIBCPP_INLINE_VISIBILITY
2198 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
2200 while (__first != __last)
2202 if (__first == --__last)
2204 _VSTD::iter_swap(__first, __last);
2209 template <class _RandomAccessIterator>
2210 inline _LIBCPP_INLINE_VISIBILITY
2212 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
2214 if (__first != __last)
2215 for (; __first < --__last; ++__first)
2216 _VSTD::iter_swap(__first, __last);
2219 template <class _BidirectionalIterator>
2220 inline _LIBCPP_INLINE_VISIBILITY
2222 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
2224 _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());
2229 template <class _BidirectionalIterator, class _OutputIterator>
2230 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2232 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
2234 for (; __first != __last; ++__result)
2235 *__result = *--__last;
2241 template <class _ForwardIterator>
2243 __rotate_left(_ForwardIterator __first, _ForwardIterator __last)
2245 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2246 value_type __tmp = _VSTD::move(*__first);
2247 _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
2248 *__lm1 = _VSTD::move(__tmp);
2252 template <class _BidirectionalIterator>
2253 _BidirectionalIterator
2254 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
2256 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
2257 _BidirectionalIterator __lm1 = _VSTD::prev(__last);
2258 value_type __tmp = _VSTD::move(*__lm1);
2259 _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
2260 *__first = _VSTD::move(__tmp);
2264 template <class _ForwardIterator>
2266 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2268 _ForwardIterator __i = __middle;
2271 swap(*__first, *__i);
2273 if (++__i == __last)
2275 if (__first == __middle)
2278 _ForwardIterator __r = __first;
2279 if (__first != __middle)
2284 swap(*__first, *__i);
2286 if (++__i == __last)
2288 if (__first == __middle)
2292 else if (__first == __middle)
2299 template<typename _Integral>
2300 inline _LIBCPP_INLINE_VISIBILITY
2302 __algo_gcd(_Integral __x, _Integral __y)
2306 _Integral __t = __x % __y;
2313 template<typename _RandomAccessIterator>
2314 _RandomAccessIterator
2315 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
2317 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2318 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
2320 const difference_type __m1 = __middle - __first;
2321 const difference_type __m2 = __last - __middle;
2324 _VSTD::swap_ranges(__first, __middle, __middle);
2327 const difference_type __g = _VSTD::__algo_gcd(__m1, __m2);
2328 for (_RandomAccessIterator __p = __first + __g; __p != __first;)
2330 value_type __t(_VSTD::move(*--__p));
2331 _RandomAccessIterator __p1 = __p;
2332 _RandomAccessIterator __p2 = __p1 + __m1;
2335 *__p1 = _VSTD::move(*__p2);
2337 const difference_type __d = __last - __p2;
2341 __p2 = __first + (__m1 - __d);
2342 } while (__p2 != __p);
2343 *__p1 = _VSTD::move(__t);
2345 return __first + __m2;
2348 template <class _ForwardIterator>
2349 inline _LIBCPP_INLINE_VISIBILITY
2351 __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
2352 _VSTD::forward_iterator_tag)
2354 typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type;
2355 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2357 if (_VSTD::next(__first) == __middle)
2358 return _VSTD::__rotate_left(__first, __last);
2360 return _VSTD::__rotate_forward(__first, __middle, __last);
2363 template <class _BidirectionalIterator>
2364 inline _LIBCPP_INLINE_VISIBILITY
2365 _BidirectionalIterator
2366 __rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
2367 _VSTD::bidirectional_iterator_tag)
2369 typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type;
2370 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2372 if (_VSTD::next(__first) == __middle)
2373 return _VSTD::__rotate_left(__first, __last);
2374 if (_VSTD::next(__middle) == __last)
2375 return _VSTD::__rotate_right(__first, __last);
2377 return _VSTD::__rotate_forward(__first, __middle, __last);
2380 template <class _RandomAccessIterator>
2381 inline _LIBCPP_INLINE_VISIBILITY
2382 _RandomAccessIterator
2383 __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
2384 _VSTD::random_access_iterator_tag)
2386 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
2387 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2389 if (_VSTD::next(__first) == __middle)
2390 return _VSTD::__rotate_left(__first, __last);
2391 if (_VSTD::next(__middle) == __last)
2392 return _VSTD::__rotate_right(__first, __last);
2393 return _VSTD::__rotate_gcd(__first, __middle, __last);
2395 return _VSTD::__rotate_forward(__first, __middle, __last);
2398 template <class _ForwardIterator>
2399 inline _LIBCPP_INLINE_VISIBILITY
2401 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2403 if (__first == __middle)
2405 if (__middle == __last)
2407 return _VSTD::__rotate(__first, __middle, __last,
2408 typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());
2413 template <class _ForwardIterator, class _OutputIterator>
2414 inline _LIBCPP_INLINE_VISIBILITY
2416 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
2418 return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));
2423 template <class _ForwardIterator, class _Compare>
2424 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2426 min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2428 static_assert(__is_forward_iterator<_ForwardIterator>::value,
2429 "std::min_element requires a ForwardIterator");
2430 if (__first != __last)
2432 _ForwardIterator __i = __first;
2433 while (++__i != __last)
2434 if (__comp(*__i, *__first))
2440 template <class _ForwardIterator>
2441 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2443 min_element(_ForwardIterator __first, _ForwardIterator __last)
2445 return _VSTD::min_element(__first, __last,
2446 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2451 template <class _Tp, class _Compare>
2452 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2454 min(const _Tp& __a, const _Tp& __b, _Compare __comp)
2456 return __comp(__b, __a) ? __b : __a;
2459 template <class _Tp>
2460 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2462 min(const _Tp& __a, const _Tp& __b)
2464 return _VSTD::min(__a, __b, __less<_Tp>());
2467 #ifndef _LIBCPP_CXX03_LANG
2469 template<class _Tp, class _Compare>
2470 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2472 min(initializer_list<_Tp> __t, _Compare __comp)
2474 return *_VSTD::min_element(__t.begin(), __t.end(), __comp);
2478 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2480 min(initializer_list<_Tp> __t)
2482 return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>());
2485 #endif // _LIBCPP_CXX03_LANG
2489 template <class _ForwardIterator, class _Compare>
2490 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2492 max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2494 static_assert(__is_forward_iterator<_ForwardIterator>::value,
2495 "std::max_element requires a ForwardIterator");
2496 if (__first != __last)
2498 _ForwardIterator __i = __first;
2499 while (++__i != __last)
2500 if (__comp(*__first, *__i))
2507 template <class _ForwardIterator>
2508 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2510 max_element(_ForwardIterator __first, _ForwardIterator __last)
2512 return _VSTD::max_element(__first, __last,
2513 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2518 template <class _Tp, class _Compare>
2519 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2521 max(const _Tp& __a, const _Tp& __b, _Compare __comp)
2523 return __comp(__a, __b) ? __b : __a;
2526 template <class _Tp>
2527 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2529 max(const _Tp& __a, const _Tp& __b)
2531 return _VSTD::max(__a, __b, __less<_Tp>());
2534 #ifndef _LIBCPP_CXX03_LANG
2536 template<class _Tp, class _Compare>
2537 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2539 max(initializer_list<_Tp> __t, _Compare __comp)
2541 return *_VSTD::max_element(__t.begin(), __t.end(), __comp);
2545 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2547 max(initializer_list<_Tp> __t)
2549 return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>());
2552 #endif // _LIBCPP_CXX03_LANG
2554 #if _LIBCPP_STD_VER > 14
2556 template<class _Tp, class _Compare>
2557 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
2559 clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
2561 _LIBCPP_ASSERT(!__comp(__hi, __lo), "Bad bounds passed to std::clamp");
2562 return __comp(__v, __lo) ? __lo : __comp(__hi, __v) ? __hi : __v;
2567 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
2569 clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi)
2571 return _VSTD::clamp(__v, __lo, __hi, __less<_Tp>());
2577 template <class _ForwardIterator, class _Compare>
2578 _LIBCPP_CONSTEXPR_AFTER_CXX11
2579 std::pair<_ForwardIterator, _ForwardIterator>
2580 minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2582 static_assert(__is_forward_iterator<_ForwardIterator>::value,
2583 "std::minmax_element requires a ForwardIterator");
2584 std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);
2585 if (__first != __last)
2587 if (++__first != __last)
2589 if (__comp(*__first, *__result.first))
2590 __result.first = __first;
2592 __result.second = __first;
2593 while (++__first != __last)
2595 _ForwardIterator __i = __first;
2596 if (++__first == __last)
2598 if (__comp(*__i, *__result.first))
2599 __result.first = __i;
2600 else if (!__comp(*__i, *__result.second))
2601 __result.second = __i;
2606 if (__comp(*__first, *__i))
2608 if (__comp(*__first, *__result.first))
2609 __result.first = __first;
2610 if (!__comp(*__i, *__result.second))
2611 __result.second = __i;
2615 if (__comp(*__i, *__result.first))
2616 __result.first = __i;
2617 if (!__comp(*__first, *__result.second))
2618 __result.second = __first;
2627 template <class _ForwardIterator>
2628 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2629 std::pair<_ForwardIterator, _ForwardIterator>
2630 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
2632 return _VSTD::minmax_element(__first, __last,
2633 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2638 template<class _Tp, class _Compare>
2639 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2640 pair<const _Tp&, const _Tp&>
2641 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
2643 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) :
2644 pair<const _Tp&, const _Tp&>(__a, __b);
2648 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2649 pair<const _Tp&, const _Tp&>
2650 minmax(const _Tp& __a, const _Tp& __b)
2652 return _VSTD::minmax(__a, __b, __less<_Tp>());
2655 #ifndef _LIBCPP_CXX03_LANG
2657 template<class _Tp, class _Compare>
2658 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2660 minmax(initializer_list<_Tp> __t, _Compare __comp)
2662 typedef typename initializer_list<_Tp>::const_iterator _Iter;
2663 _Iter __first = __t.begin();
2664 _Iter __last = __t.end();
2665 std::pair<_Tp, _Tp> __result(*__first, *__first);
2668 if (__t.size() % 2 == 0)
2670 if (__comp(*__first, __result.first))
2671 __result.first = *__first;
2673 __result.second = *__first;
2677 while (__first != __last)
2679 _Tp __prev = *__first++;
2680 if (__comp(*__first, __prev)) {
2681 if ( __comp(*__first, __result.first)) __result.first = *__first;
2682 if (!__comp(__prev, __result.second)) __result.second = __prev;
2685 if ( __comp(__prev, __result.first)) __result.first = __prev;
2686 if (!__comp(*__first, __result.second)) __result.second = *__first;
2695 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2697 minmax(initializer_list<_Tp> __t)
2699 return _VSTD::minmax(__t, __less<_Tp>());
2702 #endif // _LIBCPP_CXX03_LANG
2706 // __independent_bits_engine
2708 template <unsigned long long _Xp, size_t _Rp>
2711 static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp
2712 : __log2_imp<_Xp, _Rp - 1>::value;
2715 template <unsigned long long _Xp>
2716 struct __log2_imp<_Xp, 0>
2718 static const size_t value = 0;
2721 template <size_t _Rp>
2722 struct __log2_imp<0, _Rp>
2724 static const size_t value = _Rp + 1;
2727 template <class _UIntType, _UIntType _Xp>
2730 static const size_t value = __log2_imp<_Xp,
2731 sizeof(_UIntType) * __CHAR_BIT__ - 1>::value;
2734 template<class _Engine, class _UIntType>
2735 class __independent_bits_engine
2739 typedef _UIntType result_type;
2742 typedef typename _Engine::result_type _Engine_result_type;
2743 typedef typename conditional
2745 sizeof(_Engine_result_type) <= sizeof(result_type),
2748 >::type _Working_result_type;
2755 _Working_result_type __y0_;
2756 _Working_result_type __y1_;
2757 _Engine_result_type __mask0_;
2758 _Engine_result_type __mask1_;
2760 #ifdef _LIBCPP_CXX03_LANG
2761 static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
2762 + _Working_result_type(1);
2764 static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()
2765 + _Working_result_type(1);
2767 static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value;
2768 static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits;
2769 static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
2772 // constructors and seeding functions
2773 __independent_bits_engine(_Engine& __e, size_t __w);
2775 // generating functions
2776 result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
2779 result_type __eval(false_type);
2780 result_type __eval(true_type);
2783 template<class _Engine, class _UIntType>
2784 __independent_bits_engine<_Engine, _UIntType>
2785 ::__independent_bits_engine(_Engine& __e, size_t __w)
2789 __n_ = __w_ / __m + (__w_ % __m != 0);
2790 __w0_ = __w_ / __n_;
2793 else if (__w0_ < _WDt)
2794 __y0_ = (_Rp >> __w0_) << __w0_;
2797 if (_Rp - __y0_ > __y0_ / __n_)
2800 __w0_ = __w_ / __n_;
2802 __y0_ = (_Rp >> __w0_) << __w0_;
2806 __n0_ = __n_ - __w_ % __n_;
2807 if (__w0_ < _WDt - 1)
2808 __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1);
2811 __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :
2812 _Engine_result_type(0);
2813 __mask1_ = __w0_ < _EDt - 1 ?
2814 _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :
2815 _Engine_result_type(~0);
2818 template<class _Engine, class _UIntType>
2821 __independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
2823 return static_cast<result_type>(__e_() & __mask0_);
2826 template<class _Engine, class _UIntType>
2828 __independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
2830 const size_t _WRt = numeric_limits<result_type>::digits;
2831 result_type _Sp = 0;
2832 for (size_t __k = 0; __k < __n0_; ++__k)
2834 _Engine_result_type __u;
2837 __u = __e_() - _Engine::min();
2838 } while (__u >= __y0_);
2843 _Sp += __u & __mask0_;
2845 for (size_t __k = __n0_; __k < __n_; ++__k)
2847 _Engine_result_type __u;
2850 __u = __e_() - _Engine::min();
2851 } while (__u >= __y1_);
2852 if (__w0_ < _WRt - 1)
2856 _Sp += __u & __mask1_;
2861 // uniform_int_distribution
2863 template<class _IntType = int>
2864 class uniform_int_distribution
2868 typedef _IntType result_type;
2875 typedef uniform_int_distribution distribution_type;
2877 explicit param_type(result_type __a = 0,
2878 result_type __b = numeric_limits<result_type>::max())
2879 : __a_(__a), __b_(__b) {}
2881 result_type a() const {return __a_;}
2882 result_type b() const {return __b_;}
2884 friend bool operator==(const param_type& __x, const param_type& __y)
2885 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
2886 friend bool operator!=(const param_type& __x, const param_type& __y)
2887 {return !(__x == __y);}
2894 // constructors and reset functions
2895 explicit uniform_int_distribution(result_type __a = 0,
2896 result_type __b = numeric_limits<result_type>::max())
2897 : __p_(param_type(__a, __b)) {}
2898 explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
2901 // generating functions
2902 template<class _URNG> result_type operator()(_URNG& __g)
2903 {return (*this)(__g, __p_);}
2904 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
2906 // property functions
2907 result_type a() const {return __p_.a();}
2908 result_type b() const {return __p_.b();}
2910 param_type param() const {return __p_;}
2911 void param(const param_type& __p) {__p_ = __p;}
2913 result_type min() const {return a();}
2914 result_type max() const {return b();}
2916 friend bool operator==(const uniform_int_distribution& __x,
2917 const uniform_int_distribution& __y)
2918 {return __x.__p_ == __y.__p_;}
2919 friend bool operator!=(const uniform_int_distribution& __x,
2920 const uniform_int_distribution& __y)
2921 {return !(__x == __y);}
2924 template<class _IntType>
2925 template<class _URNG>
2926 typename uniform_int_distribution<_IntType>::result_type
2927 uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
2928 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
2930 typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
2931 uint32_t, uint64_t>::type _UIntType;
2932 const _UIntType _Rp = _UIntType(__p.b()) - _UIntType(__p.a()) + _UIntType(1);
2935 const size_t _Dt = numeric_limits<_UIntType>::digits;
2936 typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
2938 return static_cast<result_type>(_Eng(__g, _Dt)());
2939 size_t __w = _Dt - __clz(_Rp) - 1;
2940 if ((_Rp & (std::numeric_limits<_UIntType>::max() >> (_Dt - __w))) != 0)
2947 } while (__u >= _Rp);
2948 return static_cast<result_type>(__u + __p.a());
2951 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \
2952 || defined(_LIBCPP_BUILDING_LIBRARY)
2953 class _LIBCPP_TYPE_VIS __rs_default;
2955 _LIBCPP_FUNC_VIS __rs_default __rs_get();
2957 class _LIBCPP_TYPE_VIS __rs_default
2959 static unsigned __c_;
2963 typedef uint_fast32_t result_type;
2965 static const result_type _Min = 0;
2966 static const result_type _Max = 0xFFFFFFFF;
2968 __rs_default(const __rs_default&);
2971 result_type operator()();
2973 static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
2974 static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
2976 friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
2979 _LIBCPP_FUNC_VIS __rs_default __rs_get();
2981 template <class _RandomAccessIterator>
2982 _LIBCPP_DEPRECATED_IN_CXX14 void
2983 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
2985 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2986 typedef uniform_int_distribution<ptrdiff_t> _Dp;
2987 typedef typename _Dp::param_type _Pp;
2988 difference_type __d = __last - __first;
2992 __rs_default __g = __rs_get();
2993 for (--__last, --__d; __first < __last; ++__first, --__d)
2995 difference_type __i = __uid(__g, _Pp(0, __d));
2996 if (__i != difference_type(0))
2997 swap(*__first, *(__first + __i));
3002 template <class _RandomAccessIterator, class _RandomNumberGenerator>
3003 _LIBCPP_DEPRECATED_IN_CXX14 void
3004 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3005 #ifndef _LIBCPP_CXX03_LANG
3006 _RandomNumberGenerator&& __rand)
3008 _RandomNumberGenerator& __rand)
3011 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3012 difference_type __d = __last - __first;
3015 for (--__last; __first < __last; ++__first, --__d)
3017 difference_type __i = __rand(__d);
3018 if (__i != difference_type(0))
3019 swap(*__first, *(__first + __i));
3025 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3026 class _UniformRandomNumberGenerator>
3027 _LIBCPP_INLINE_VISIBILITY
3028 _SampleIterator __sample(_PopulationIterator __first,
3029 _PopulationIterator __last, _SampleIterator __output_iter,
3031 _UniformRandomNumberGenerator & __g,
3032 input_iterator_tag) {
3035 for (; __first != __last && __k < __n; ++__first, (void)++__k)
3036 __output_iter[__k] = *__first;
3037 _Distance __sz = __k;
3038 for (; __first != __last; ++__first, (void)++__k) {
3039 _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g);
3041 __output_iter[__r] = *__first;
3043 return __output_iter + _VSTD::min(__n, __k);
3046 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3047 class _UniformRandomNumberGenerator>
3048 _LIBCPP_INLINE_VISIBILITY
3049 _SampleIterator __sample(_PopulationIterator __first,
3050 _PopulationIterator __last, _SampleIterator __output_iter,
3052 _UniformRandomNumberGenerator& __g,
3053 forward_iterator_tag) {
3054 _Distance __unsampled_sz = _VSTD::distance(__first, __last);
3055 for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
3057 _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g);
3059 *__output_iter++ = *__first;
3063 return __output_iter;
3066 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3067 class _UniformRandomNumberGenerator>
3068 _LIBCPP_INLINE_VISIBILITY
3069 _SampleIterator __sample(_PopulationIterator __first,
3070 _PopulationIterator __last, _SampleIterator __output_iter,
3071 _Distance __n, _UniformRandomNumberGenerator& __g) {
3072 typedef typename iterator_traits<_PopulationIterator>::iterator_category
3074 typedef typename iterator_traits<_PopulationIterator>::difference_type
3076 static_assert(__is_forward_iterator<_PopulationIterator>::value ||
3077 __is_random_access_iterator<_SampleIterator>::value,
3078 "SampleIterator must meet the requirements of RandomAccessIterator");
3079 typedef typename common_type<_Distance, _Difference>::type _CommonType;
3080 _LIBCPP_ASSERT(__n >= 0, "N must be a positive number.");
3081 return _VSTD::__sample(
3082 __first, __last, __output_iter, _CommonType(__n),
3083 __g, _PopCategory());
3086 #if _LIBCPP_STD_VER > 14
3087 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3088 class _UniformRandomNumberGenerator>
3089 inline _LIBCPP_INLINE_VISIBILITY
3090 _SampleIterator sample(_PopulationIterator __first,
3091 _PopulationIterator __last, _SampleIterator __output_iter,
3092 _Distance __n, _UniformRandomNumberGenerator&& __g) {
3093 return _VSTD::__sample(__first, __last, __output_iter, __n, __g);
3095 #endif // _LIBCPP_STD_VER > 14
3097 template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
3098 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3099 #ifndef _LIBCPP_CXX03_LANG
3100 _UniformRandomNumberGenerator&& __g)
3102 _UniformRandomNumberGenerator& __g)
3105 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3106 typedef uniform_int_distribution<ptrdiff_t> _Dp;
3107 typedef typename _Dp::param_type _Pp;
3108 difference_type __d = __last - __first;
3112 for (--__last, --__d; __first < __last; ++__first, --__d)
3114 difference_type __i = __uid(__g, _Pp(0, __d));
3115 if (__i != difference_type(0))
3116 swap(*__first, *(__first + __i));
3121 template <class _InputIterator, class _Predicate>
3122 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
3123 is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3125 for (; __first != __last; ++__first)
3126 if (!__pred(*__first))
3128 if ( __first == __last )
3131 for (; __first != __last; ++__first)
3132 if (__pred(*__first))
3139 template <class _Predicate, class _ForwardIterator>
3141 __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
3145 if (__first == __last)
3147 if (!__pred(*__first))
3151 for (_ForwardIterator __p = __first; ++__p != __last;)
3155 swap(*__first, *__p);
3162 template <class _Predicate, class _BidirectionalIterator>
3163 _BidirectionalIterator
3164 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3165 bidirectional_iterator_tag)
3171 if (__first == __last)
3173 if (!__pred(*__first))
3179 if (__first == --__last)
3181 } while (!__pred(*__last));
3182 swap(*__first, *__last);
3187 template <class _ForwardIterator, class _Predicate>
3188 inline _LIBCPP_INLINE_VISIBILITY
3190 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3192 return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>
3193 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3198 template <class _InputIterator, class _OutputIterator1,
3199 class _OutputIterator2, class _Predicate>
3200 _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_OutputIterator1, _OutputIterator2>
3201 partition_copy(_InputIterator __first, _InputIterator __last,
3202 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
3205 for (; __first != __last; ++__first)
3207 if (__pred(*__first))
3209 *__out_true = *__first;
3214 *__out_false = *__first;
3218 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
3223 template<class _ForwardIterator, class _Predicate>
3224 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
3225 partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3227 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3228 difference_type __len = _VSTD::distance(__first, __last);
3231 difference_type __l2 = _VSTD::__half_positive(__len);
3232 _ForwardIterator __m = __first;
3233 _VSTD::advance(__m, __l2);
3247 template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
3249 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3250 _Distance __len, _Pair __p, forward_iterator_tag __fit)
3252 // *__first is known to be false
3258 _ForwardIterator __m = __first;
3261 swap(*__first, *__m);
3266 if (__len <= __p.second)
3267 { // The buffer is big enough to use
3268 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3269 __destruct_n __d(0);
3270 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3271 // Move the falses into the temporary buffer, and the trues to the front of the line
3272 // Update __first to always point to the end of the trues
3273 value_type* __t = __p.first;
3274 ::new(__t) value_type(_VSTD::move(*__first));
3275 __d.__incr((value_type*)0);
3277 _ForwardIterator __i = __first;
3278 while (++__i != __last)
3282 *__first = _VSTD::move(*__i);
3287 ::new(__t) value_type(_VSTD::move(*__i));
3288 __d.__incr((value_type*)0);
3292 // All trues now at start of range, all falses in buffer
3293 // Move falses back into range, but don't mess up __first which points to first false
3295 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3296 *__i = _VSTD::move(*__t2);
3297 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3300 // Else not enough buffer, do in place
3302 _ForwardIterator __m = __first;
3303 _Distance __len2 = __len / 2; // __len2 >= 2
3304 _VSTD::advance(__m, __len2);
3305 // recurse on [__first, __m), *__first know to be false
3306 // F?????????????????
3308 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3309 _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
3310 // TTTFFFFF??????????
3312 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3313 _ForwardIterator __m1 = __m;
3314 _ForwardIterator __second_false = __last;
3315 _Distance __len_half = __len - __len2;
3316 while (__pred(*__m1))
3318 if (++__m1 == __last)
3319 goto __second_half_done;
3322 // TTTFFFFFTTTF??????
3324 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
3326 // TTTFFFFFTTTTTFFFFF
3328 return _VSTD::rotate(__first_false, __m, __second_false);
3329 // TTTTTTTTFFFFFFFFFF
3333 struct __return_temporary_buffer
3335 template <class _Tp>
3336 _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}
3339 template <class _Predicate, class _ForwardIterator>
3341 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3342 forward_iterator_tag)
3344 const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment
3345 // Either prove all true and return __first or point to first false
3348 if (__first == __last)
3350 if (!__pred(*__first))
3354 // We now have a reduced range [__first, __last)
3355 // *__first is known to be false
3356 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3357 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3358 difference_type __len = _VSTD::distance(__first, __last);
3359 pair<value_type*, ptrdiff_t> __p(0, 0);
3360 unique_ptr<value_type, __return_temporary_buffer> __h;
3361 if (__len >= __alloc_limit)
3363 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3364 __h.reset(__p.first);
3366 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3367 (__first, __last, __pred, __len, __p, forward_iterator_tag());
3370 template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
3371 _BidirectionalIterator
3372 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3373 _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
3375 // *__first is known to be false
3376 // *__last is known to be true
3380 swap(*__first, *__last);
3385 _BidirectionalIterator __m = __first;
3388 swap(*__first, *__m);
3389 swap(*__m, *__last);
3392 swap(*__m, *__last);
3393 swap(*__first, *__m);
3396 if (__len <= __p.second)
3397 { // The buffer is big enough to use
3398 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3399 __destruct_n __d(0);
3400 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3401 // Move the falses into the temporary buffer, and the trues to the front of the line
3402 // Update __first to always point to the end of the trues
3403 value_type* __t = __p.first;
3404 ::new(__t) value_type(_VSTD::move(*__first));
3405 __d.__incr((value_type*)0);
3407 _BidirectionalIterator __i = __first;
3408 while (++__i != __last)
3412 *__first = _VSTD::move(*__i);
3417 ::new(__t) value_type(_VSTD::move(*__i));
3418 __d.__incr((value_type*)0);
3422 // move *__last, known to be true
3423 *__first = _VSTD::move(*__i);
3425 // All trues now at start of range, all falses in buffer
3426 // Move falses back into range, but don't mess up __first which points to first false
3427 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3428 *__i = _VSTD::move(*__t2);
3429 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3432 // Else not enough buffer, do in place
3434 _BidirectionalIterator __m = __first;
3435 _Distance __len2 = __len / 2; // __len2 >= 2
3436 _VSTD::advance(__m, __len2);
3437 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
3438 // F????????????????T
3440 _BidirectionalIterator __m1 = __m;
3441 _BidirectionalIterator __first_false = __first;
3442 _Distance __len_half = __len2;
3443 while (!__pred(*--__m1))
3445 if (__m1 == __first)
3446 goto __first_half_done;
3449 // F???TFFF?????????T
3451 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3452 __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3454 // TTTFFFFF?????????T
3456 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3458 _BidirectionalIterator __second_false = __last;
3460 __len_half = __len - __len2;
3461 while (__pred(*__m1))
3463 if (++__m1 == __last)
3464 goto __second_half_done;
3467 // TTTFFFFFTTTF?????T
3469 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
3471 // TTTFFFFFTTTTTFFFFF
3473 return _VSTD::rotate(__first_false, __m, __second_false);
3474 // TTTTTTTTFFFFFFFFFF
3478 template <class _Predicate, class _BidirectionalIterator>
3479 _BidirectionalIterator
3480 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3481 bidirectional_iterator_tag)
3483 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3484 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3485 const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment
3486 // Either prove all true and return __first or point to first false
3489 if (__first == __last)
3491 if (!__pred(*__first))
3495 // __first points to first false, everything prior to __first is already set.
3496 // Either prove [__first, __last) is all false and return __first, or point __last to last true
3499 if (__first == --__last)
3501 } while (!__pred(*__last));
3502 // We now have a reduced range [__first, __last]
3503 // *__first is known to be false
3504 // *__last is known to be true
3506 difference_type __len = _VSTD::distance(__first, __last) + 1;
3507 pair<value_type*, ptrdiff_t> __p(0, 0);
3508 unique_ptr<value_type, __return_temporary_buffer> __h;
3509 if (__len >= __alloc_limit)
3511 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3512 __h.reset(__p.first);
3514 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3515 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3518 template <class _ForwardIterator, class _Predicate>
3519 inline _LIBCPP_INLINE_VISIBILITY
3521 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3523 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3524 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3529 template <class _ForwardIterator, class _Compare>
3530 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
3531 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3533 if (__first != __last)
3535 _ForwardIterator __i = __first;
3536 while (++__i != __last)
3538 if (__comp(*__i, *__first))
3546 template<class _ForwardIterator>
3547 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3549 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3551 return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3556 template <class _ForwardIterator, class _Compare>
3557 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3559 is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3561 return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
3564 template<class _ForwardIterator>
3565 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3567 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3569 return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3574 // stable, 2-3 compares, 0-2 swaps
3576 template <class _Compare, class _ForwardIterator>
3578 __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
3581 if (!__c(*__y, *__x)) // if x <= y
3583 if (!__c(*__z, *__y)) // if y <= z
3584 return __r; // x <= y && y <= z
3586 swap(*__y, *__z); // x <= z && y < z
3588 if (__c(*__y, *__x)) // if x > y
3590 swap(*__x, *__y); // x < y && y <= z
3593 return __r; // x <= y && y < z
3595 if (__c(*__z, *__y)) // x > y, if y > z
3597 swap(*__x, *__z); // x < y && y < z
3601 swap(*__x, *__y); // x > y && y <= z
3602 __r = 1; // x < y && x <= z
3603 if (__c(*__z, *__y)) // if y > z
3605 swap(*__y, *__z); // x <= y && y < z
3609 } // x <= y && y <= z
3611 // stable, 3-6 compares, 0-5 swaps
3613 template <class _Compare, class _ForwardIterator>
3615 __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3616 _ForwardIterator __x4, _Compare __c)
3618 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
3619 if (__c(*__x4, *__x3))
3623 if (__c(*__x3, *__x2))
3627 if (__c(*__x2, *__x1))
3637 // stable, 4-10 compares, 0-9 swaps
3639 template <class _Compare, class _ForwardIterator>
3642 __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3643 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
3645 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
3646 if (__c(*__x5, *__x4))
3650 if (__c(*__x4, *__x3))
3654 if (__c(*__x3, *__x2))
3658 if (__c(*__x2, *__x1))
3670 template <class _Compare, class _BirdirectionalIterator>
3672 __selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3674 _BirdirectionalIterator __lm1 = __last;
3675 for (--__lm1; __first != __lm1; ++__first)
3677 _BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator,
3678 typename add_lvalue_reference<_Compare>::type>
3679 (__first, __last, __comp);
3681 swap(*__first, *__i);
3685 template <class _Compare, class _BirdirectionalIterator>
3687 __insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3689 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3690 if (__first != __last)
3692 _BirdirectionalIterator __i = __first;
3693 for (++__i; __i != __last; ++__i)
3695 _BirdirectionalIterator __j = __i;
3696 value_type __t(_VSTD::move(*__j));
3697 for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
3698 *__j = _VSTD::move(*__k);
3699 *__j = _VSTD::move(__t);
3704 template <class _Compare, class _RandomAccessIterator>
3706 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3708 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3709 _RandomAccessIterator __j = __first+2;
3710 __sort3<_Compare>(__first, __first+1, __j, __comp);
3711 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3713 if (__comp(*__i, *__j))
3715 value_type __t(_VSTD::move(*__i));
3716 _RandomAccessIterator __k = __j;
3720 *__j = _VSTD::move(*__k);
3722 } while (__j != __first && __comp(__t, *--__k));
3723 *__j = _VSTD::move(__t);
3729 template <class _Compare, class _RandomAccessIterator>
3731 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3733 switch (__last - __first)
3739 if (__comp(*--__last, *__first))
3740 swap(*__first, *__last);
3743 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3746 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3749 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3752 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3753 _RandomAccessIterator __j = __first+2;
3754 __sort3<_Compare>(__first, __first+1, __j, __comp);
3755 const unsigned __limit = 8;
3756 unsigned __count = 0;
3757 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3759 if (__comp(*__i, *__j))
3761 value_type __t(_VSTD::move(*__i));
3762 _RandomAccessIterator __k = __j;
3766 *__j = _VSTD::move(*__k);
3768 } while (__j != __first && __comp(__t, *--__k));
3769 *__j = _VSTD::move(__t);
3770 if (++__count == __limit)
3771 return ++__i == __last;
3778 template <class _Compare, class _BirdirectionalIterator>
3780 __insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
3781 typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
3783 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3784 if (__first1 != __last1)
3786 __destruct_n __d(0);
3787 unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
3788 value_type* __last2 = __first2;
3789 ::new(__last2) value_type(_VSTD::move(*__first1));
3790 __d.__incr((value_type*)0);
3791 for (++__last2; ++__first1 != __last1; ++__last2)
3793 value_type* __j2 = __last2;
3794 value_type* __i2 = __j2;
3795 if (__comp(*__first1, *--__i2))
3797 ::new(__j2) value_type(_VSTD::move(*__i2));
3798 __d.__incr((value_type*)0);
3799 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2)
3800 *__j2 = _VSTD::move(*__i2);
3801 *__j2 = _VSTD::move(*__first1);
3805 ::new(__j2) value_type(_VSTD::move(*__first1));
3806 __d.__incr((value_type*)0);
3813 template <class _Compare, class _RandomAccessIterator>
3815 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3817 // _Compare is known to be a reference type
3818 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3819 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3820 const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
3821 is_trivially_copy_assignable<value_type>::value ? 30 : 6;
3825 difference_type __len = __last - __first;
3832 if (__comp(*--__last, *__first))
3833 swap(*__first, *__last);
3836 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3839 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3842 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3845 if (__len <= __limit)
3847 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
3851 _RandomAccessIterator __m = __first;
3852 _RandomAccessIterator __lm1 = __last;
3856 difference_type __delta;
3862 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
3868 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
3872 // partition [__first, __m) < *__m and *__m <= [__m, __last)
3873 // (this inhibits tossing elements equivalent to __m around unnecessarily)
3874 _RandomAccessIterator __i = __first;
3875 _RandomAccessIterator __j = __lm1;
3876 // j points beyond range to be tested, *__m is known to be <= *__lm1
3877 // The search going up is known to be guarded but the search coming down isn't.
3878 // Prime the downward search with a guard.
3879 if (!__comp(*__i, *__m)) // if *__first == *__m
3881 // *__first == *__m, *__first doesn't go in first part
3882 // manually guard downward moving __j against __i
3887 // *__first == *__m, *__m <= all other elements
3888 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
3889 ++__i; // __first + 1
3891 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
3896 return; // [__first, __last) all equivalent elements
3897 if (__comp(*__first, *__i))
3907 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
3912 while (!__comp(*__first, *__i))
3914 while (__comp(*__first, *--__j))
3922 // [__first, __i) == *__first and *__first < [__i, __last)
3923 // The first part is sorted, sort the secod part
3924 // _VSTD::__sort<_Compare>(__i, __last, __comp);
3928 if (__comp(*__j, *__m))
3932 break; // found guard for downward moving __j, now use unguarded partition
3936 // It is known that *__i < *__m
3938 // j points beyond range to be tested, *__m is known to be <= *__lm1
3939 // if not yet partitioned...
3942 // known that *(__i - 1) < *__m
3943 // known that __i <= __m
3946 // __m still guards upward moving __i
3947 while (__comp(*__i, *__m))
3949 // It is now known that a guard exists for downward moving __j
3950 while (!__comp(*--__j, *__m))
3956 // It is known that __m != __j
3957 // If __m just moved, follow it
3963 // [__first, __i) < *__m and *__m <= [__i, __last)
3964 if (__i != __m && __comp(*__m, *__i))
3969 // [__first, __i) < *__i and *__i <= [__i+1, __last)
3970 // If we were given a perfect partition, see if insertion sort is quick...
3973 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
3974 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
3990 // sort smaller range with recursive call and larger with tail recursion elimination
3991 if (__i - __first < __last - __i)
3993 _VSTD::__sort<_Compare>(__first, __i, __comp);
3994 // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
3999 _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4000 // _VSTD::__sort<_Compare>(__first, __i, __comp);
4006 // This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
4007 template <class _RandomAccessIterator, class _Compare>
4008 inline _LIBCPP_INLINE_VISIBILITY
4010 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4012 #ifdef _LIBCPP_DEBUG
4013 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4014 __debug_less<_Compare> __c(__comp);
4015 __sort<_Comp_ref>(__first, __last, __c);
4016 #else // _LIBCPP_DEBUG
4017 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4018 __sort<_Comp_ref>(__first, __last, __comp);
4019 #endif // _LIBCPP_DEBUG
4022 template <class _RandomAccessIterator>
4023 inline _LIBCPP_INLINE_VISIBILITY
4025 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4027 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4030 template <class _Tp>
4031 inline _LIBCPP_INLINE_VISIBILITY
4033 sort(_Tp** __first, _Tp** __last)
4035 _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
4038 template <class _Tp>
4039 inline _LIBCPP_INLINE_VISIBILITY
4041 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
4043 _VSTD::sort(__first.base(), __last.base());
4046 template <class _Tp, class _Compare>
4047 inline _LIBCPP_INLINE_VISIBILITY
4049 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
4051 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4052 _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
4055 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
4056 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4057 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4058 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4059 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))
4060 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4061 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&))
4062 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4063 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&))
4064 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4065 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4066 _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>&))
4067 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&))
4068 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&))
4069 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4071 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))
4072 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4073 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4074 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4075 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))
4076 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4077 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&))
4078 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4079 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&))
4080 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4081 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4082 _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>&))
4083 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&))
4084 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&))
4085 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4087 _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>&))
4091 template <class _Compare, class _ForwardIterator, class _Tp>
4092 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
4093 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4095 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4096 difference_type __len = _VSTD::distance(__first, __last);
4099 difference_type __l2 = _VSTD::__half_positive(__len);
4100 _ForwardIterator __m = __first;
4101 _VSTD::advance(__m, __l2);
4102 if (__comp(*__m, __value_))
4113 template <class _ForwardIterator, class _Tp, class _Compare>
4114 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4116 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4118 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4119 return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp);
4122 template <class _ForwardIterator, class _Tp>
4123 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4125 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4127 return _VSTD::lower_bound(__first, __last, __value_,
4128 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4133 template <class _Compare, class _ForwardIterator, class _Tp>
4134 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
4135 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4137 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4138 difference_type __len = _VSTD::distance(__first, __last);
4141 difference_type __l2 = _VSTD::__half_positive(__len);
4142 _ForwardIterator __m = __first;
4143 _VSTD::advance(__m, __l2);
4144 if (__comp(__value_, *__m))
4155 template <class _ForwardIterator, class _Tp, class _Compare>
4156 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4158 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4160 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4161 return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp);
4164 template <class _ForwardIterator, class _Tp>
4165 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4167 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4169 return _VSTD::upper_bound(__first, __last, __value_,
4170 __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
4175 template <class _Compare, class _ForwardIterator, class _Tp>
4176 _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator>
4177 __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4179 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4180 difference_type __len = _VSTD::distance(__first, __last);
4183 difference_type __l2 = _VSTD::__half_positive(__len);
4184 _ForwardIterator __m = __first;
4185 _VSTD::advance(__m, __l2);
4186 if (__comp(*__m, __value_))
4191 else if (__comp(__value_, *__m))
4198 _ForwardIterator __mp1 = __m;
4199 return pair<_ForwardIterator, _ForwardIterator>
4201 __lower_bound<_Compare>(__first, __m, __value_, __comp),
4202 __upper_bound<_Compare>(++__mp1, __last, __value_, __comp)
4206 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4209 template <class _ForwardIterator, class _Tp, class _Compare>
4210 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4211 pair<_ForwardIterator, _ForwardIterator>
4212 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4214 #ifdef _LIBCPP_DEBUG
4215 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4216 __debug_less<_Compare> __c(__comp);
4217 return __equal_range<_Comp_ref>(__first, __last, __value_, __c);
4218 #else // _LIBCPP_DEBUG
4219 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4220 return __equal_range<_Comp_ref>(__first, __last, __value_, __comp);
4221 #endif // _LIBCPP_DEBUG
4224 template <class _ForwardIterator, class _Tp>
4225 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4226 pair<_ForwardIterator, _ForwardIterator>
4227 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4229 return _VSTD::equal_range(__first, __last, __value_,
4230 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4235 template <class _Compare, class _ForwardIterator, class _Tp>
4236 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4238 __binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4240 __first = __lower_bound<_Compare>(__first, __last, __value_, __comp);
4241 return __first != __last && !__comp(__value_, *__first);
4244 template <class _ForwardIterator, class _Tp, class _Compare>
4245 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4247 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4249 #ifdef _LIBCPP_DEBUG
4250 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4251 __debug_less<_Compare> __c(__comp);
4252 return __binary_search<_Comp_ref>(__first, __last, __value_, __c);
4253 #else // _LIBCPP_DEBUG
4254 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4255 return __binary_search<_Comp_ref>(__first, __last, __value_, __comp);
4256 #endif // _LIBCPP_DEBUG
4259 template <class _ForwardIterator, class _Tp>
4260 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4262 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4264 return _VSTD::binary_search(__first, __last, __value_,
4265 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4270 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4272 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4273 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4275 for (; __first1 != __last1; ++__result)
4277 if (__first2 == __last2)
4278 return _VSTD::copy(__first1, __last1, __result);
4279 if (__comp(*__first2, *__first1))
4281 *__result = *__first2;
4286 *__result = *__first1;
4290 return _VSTD::copy(__first2, __last2, __result);
4293 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4294 inline _LIBCPP_INLINE_VISIBILITY
4296 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4297 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4299 #ifdef _LIBCPP_DEBUG
4300 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4301 __debug_less<_Compare> __c(__comp);
4302 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
4303 #else // _LIBCPP_DEBUG
4304 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4305 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4306 #endif // _LIBCPP_DEBUG
4309 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4310 inline _LIBCPP_INLINE_VISIBILITY
4312 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4313 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4315 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
4316 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
4317 return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
4322 template <class _Compare, class _InputIterator1, class _InputIterator2,
4323 class _OutputIterator>
4324 void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
4325 _InputIterator2 __first2, _InputIterator2 __last2,
4326 _OutputIterator __result, _Compare __comp)
4328 for (; __first1 != __last1; ++__result)
4330 if (__first2 == __last2)
4332 _VSTD::move(__first1, __last1, __result);
4336 if (__comp(*__first2, *__first1))
4338 *__result = _VSTD::move(*__first2);
4343 *__result = _VSTD::move(*__first1);
4347 // __first2 through __last2 are already in the right spot.
4350 template <class _Compare, class _BidirectionalIterator>
4352 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4353 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4354 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4355 typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
4357 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4358 __destruct_n __d(0);
4359 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4360 if (__len1 <= __len2)
4362 value_type* __p = __buff;
4363 for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4364 ::new(__p) value_type(_VSTD::move(*__i));
4365 __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);
4369 value_type* __p = __buff;
4370 for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4371 ::new(__p) value_type(_VSTD::move(*__i));
4372 typedef reverse_iterator<_BidirectionalIterator> _RBi;
4373 typedef reverse_iterator<value_type*> _Rv;
4374 __half_inplace_merge(_Rv(__p), _Rv(__buff),
4375 _RBi(__middle), _RBi(__first),
4376 _RBi(__last), __invert<_Compare>(__comp));
4380 template <class _Compare, class _BidirectionalIterator>
4382 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4383 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4384 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4385 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
4387 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4390 // if __middle == __last, we're done
4393 if (__len1 <= __buff_size || __len2 <= __buff_size)
4394 return __buffered_inplace_merge<_Compare>
4395 (__first, __middle, __last, __comp, __len1, __len2, __buff);
4396 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
4397 for (; true; ++__first, (void) --__len1)
4401 if (__comp(*__middle, *__first))
4404 // __first < __middle < __last
4405 // *__first > *__middle
4406 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4408 // [__first, __m1) <= [__middle, __m2)
4409 // [__middle, __m2) < [__m1, __middle)
4410 // [__m1, __middle) <= [__m2, __last)
4411 // and __m1 or __m2 is in the middle of its range
4412 _BidirectionalIterator __m1; // "median" of [__first, __middle)
4413 _BidirectionalIterator __m2; // "median" of [__middle, __last)
4414 difference_type __len11; // distance(__first, __m1)
4415 difference_type __len21; // distance(__middle, __m2)
4416 // binary search smaller range
4417 if (__len1 < __len2)
4418 { // __len >= 1, __len2 >= 2
4419 __len21 = __len2 / 2;
4421 _VSTD::advance(__m2, __len21);
4422 __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4423 __len11 = _VSTD::distance(__first, __m1);
4428 { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
4429 // It is known *__first > *__middle
4430 swap(*__first, *__middle);
4433 // __len1 >= 2, __len2 >= 1
4434 __len11 = __len1 / 2;
4436 _VSTD::advance(__m1, __len11);
4437 __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp);
4438 __len21 = _VSTD::distance(__middle, __m2);
4440 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle)
4441 difference_type __len22 = __len2 - __len21; // distance(__m2, __last)
4442 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4443 // swap middle two partitions
4444 __middle = _VSTD::rotate(__m1, __middle, __m2);
4445 // __len12 and __len21 now have swapped meanings
4446 // merge smaller range with recurisve call and larger with tail recursion elimination
4447 if (__len11 + __len21 < __len12 + __len22)
4449 __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4450 // __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4458 __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4459 // __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4468 template <class _BidirectionalIterator, class _Compare>
4469 inline _LIBCPP_INLINE_VISIBILITY
4471 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4474 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4475 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4476 difference_type __len1 = _VSTD::distance(__first, __middle);
4477 difference_type __len2 = _VSTD::distance(__middle, __last);
4478 difference_type __buf_size = _VSTD::min(__len1, __len2);
4479 pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
4480 unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
4482 #ifdef _LIBCPP_DEBUG
4483 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4484 __debug_less<_Compare> __c(__comp);
4485 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2,
4486 __buf.first, __buf.second);
4487 #else // _LIBCPP_DEBUG
4488 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4489 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4490 __buf.first, __buf.second);
4491 #endif // _LIBCPP_DEBUG
4494 template <class _BidirectionalIterator>
4495 inline _LIBCPP_INLINE_VISIBILITY
4497 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
4499 _VSTD::inplace_merge(__first, __middle, __last,
4500 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4505 template <class _Compare, class _InputIterator1, class _InputIterator2>
4507 __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
4508 _InputIterator2 __first2, _InputIterator2 __last2,
4509 typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
4511 typedef typename iterator_traits<_InputIterator1>::value_type value_type;
4512 __destruct_n __d(0);
4513 unique_ptr<value_type, __destruct_n&> __h(__result, __d);
4514 for (; true; ++__result)
4516 if (__first1 == __last1)
4518 for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0))
4519 ::new (__result) value_type(_VSTD::move(*__first2));
4523 if (__first2 == __last2)
4525 for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0))
4526 ::new (__result) value_type(_VSTD::move(*__first1));
4530 if (__comp(*__first2, *__first1))
4532 ::new (__result) value_type(_VSTD::move(*__first2));
4533 __d.__incr((value_type*)0);
4538 ::new (__result) value_type(_VSTD::move(*__first1));
4539 __d.__incr((value_type*)0);
4545 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4547 __merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
4548 _InputIterator2 __first2, _InputIterator2 __last2,
4549 _OutputIterator __result, _Compare __comp)
4551 for (; __first1 != __last1; ++__result)
4553 if (__first2 == __last2)
4555 for (; __first1 != __last1; ++__first1, ++__result)
4556 *__result = _VSTD::move(*__first1);
4559 if (__comp(*__first2, *__first1))
4561 *__result = _VSTD::move(*__first2);
4566 *__result = _VSTD::move(*__first1);
4570 for (; __first2 != __last2; ++__first2, ++__result)
4571 *__result = _VSTD::move(*__first2);
4574 template <class _Compare, class _RandomAccessIterator>
4576 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4577 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4578 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
4580 template <class _Compare, class _RandomAccessIterator>
4582 __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
4583 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4584 typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
4586 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4592 ::new(__first2) value_type(_VSTD::move(*__first1));
4595 __destruct_n __d(0);
4596 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
4597 if (__comp(*--__last1, *__first1))
4599 ::new(__first2) value_type(_VSTD::move(*__last1));
4600 __d.__incr((value_type*)0);
4602 ::new(__first2) value_type(_VSTD::move(*__first1));
4606 ::new(__first2) value_type(_VSTD::move(*__first1));
4607 __d.__incr((value_type*)0);
4609 ::new(__first2) value_type(_VSTD::move(*__last1));
4616 __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
4619 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4620 _RandomAccessIterator __m = __first1 + __l2;
4621 __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
4622 __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
4623 __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
4626 template <class _Tp>
4627 struct __stable_sort_switch
4629 static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
4632 template <class _Compare, class _RandomAccessIterator>
4634 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4635 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4636 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
4638 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4639 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4646 if (__comp(*--__last, *__first))
4647 swap(*__first, *__last);
4650 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4652 __insertion_sort<_Compare>(__first, __last, __comp);
4655 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4656 _RandomAccessIterator __m = __first + __l2;
4657 if (__len <= __buff_size)
4659 __destruct_n __d(0);
4660 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4661 __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4662 __d.__set(__l2, (value_type*)0);
4663 __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
4664 __d.__set(__len, (value_type*)0);
4665 __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4666 // __merge<_Compare>(move_iterator<value_type*>(__buff),
4667 // move_iterator<value_type*>(__buff + __l2),
4668 // move_iterator<_RandomAccessIterator>(__buff + __l2),
4669 // move_iterator<_RandomAccessIterator>(__buff + __len),
4670 // __first, __comp);
4673 __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4674 __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
4675 __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4678 template <class _RandomAccessIterator, class _Compare>
4679 inline _LIBCPP_INLINE_VISIBILITY
4681 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4683 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4684 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4685 difference_type __len = __last - __first;
4686 pair<value_type*, ptrdiff_t> __buf(0, 0);
4687 unique_ptr<value_type, __return_temporary_buffer> __h;
4688 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4690 __buf = _VSTD::get_temporary_buffer<value_type>(__len);
4691 __h.reset(__buf.first);
4693 #ifdef _LIBCPP_DEBUG
4694 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4695 __debug_less<_Compare> __c(__comp);
4696 __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);
4697 #else // _LIBCPP_DEBUG
4698 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4699 __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4700 #endif // _LIBCPP_DEBUG
4703 template <class _RandomAccessIterator>
4704 inline _LIBCPP_INLINE_VISIBILITY
4706 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4708 _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4713 template <class _RandomAccessIterator, class _Compare>
4714 _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
4715 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4717 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4718 difference_type __len = __last - __first;
4719 difference_type __p = 0;
4720 difference_type __c = 1;
4721 _RandomAccessIterator __pp = __first;
4724 _RandomAccessIterator __cp = __first + __c;
4725 if (__comp(*__pp, *__cp))
4731 if (__comp(*__pp, *__cp))
4740 template<class _RandomAccessIterator>
4741 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4742 _RandomAccessIterator
4743 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4745 return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4750 template <class _RandomAccessIterator, class _Compare>
4751 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4753 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4755 return _VSTD::is_heap_until(__first, __last, __comp) == __last;
4758 template<class _RandomAccessIterator>
4759 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4761 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4763 return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4768 template <class _Compare, class _RandomAccessIterator>
4770 __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4771 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4773 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4776 __len = (__len - 2) / 2;
4777 _RandomAccessIterator __ptr = __first + __len;
4778 if (__comp(*__ptr, *--__last))
4780 value_type __t(_VSTD::move(*__last));
4783 *__last = _VSTD::move(*__ptr);
4787 __len = (__len - 1) / 2;
4788 __ptr = __first + __len;
4789 } while (__comp(*__ptr, __t));
4790 *__last = _VSTD::move(__t);
4795 template <class _RandomAccessIterator, class _Compare>
4796 inline _LIBCPP_INLINE_VISIBILITY
4798 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4800 #ifdef _LIBCPP_DEBUG
4801 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4802 __debug_less<_Compare> __c(__comp);
4803 __sift_up<_Comp_ref>(__first, __last, __c, __last - __first);
4804 #else // _LIBCPP_DEBUG
4805 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4806 __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
4807 #endif // _LIBCPP_DEBUG
4810 template <class _RandomAccessIterator>
4811 inline _LIBCPP_INLINE_VISIBILITY
4813 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4815 _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4820 template <class _Compare, class _RandomAccessIterator>
4822 __sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/,
4824 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4825 _RandomAccessIterator __start)
4827 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4828 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4829 // left-child of __start is at 2 * __start + 1
4830 // right-child of __start is at 2 * __start + 2
4831 difference_type __child = __start - __first;
4833 if (__len < 2 || (__len - 2) / 2 < __child)
4836 __child = 2 * __child + 1;
4837 _RandomAccessIterator __child_i = __first + __child;
4839 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4840 // right-child exists and is greater than left-child
4845 // check if we are in heap-order
4846 if (__comp(*__child_i, *__start))
4847 // we are, __start is larger than it's largest child
4850 value_type __top(_VSTD::move(*__start));
4853 // we are not in heap-order, swap the parent with it's largest child
4854 *__start = _VSTD::move(*__child_i);
4855 __start = __child_i;
4857 if ((__len - 2) / 2 < __child)
4860 // recompute the child based off of the updated parent
4861 __child = 2 * __child + 1;
4862 __child_i = __first + __child;
4864 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4865 // right-child exists and is greater than left-child
4870 // check if we are in heap-order
4871 } while (!__comp(*__child_i, __top));
4872 *__start = _VSTD::move(__top);
4875 template <class _Compare, class _RandomAccessIterator>
4876 inline _LIBCPP_INLINE_VISIBILITY
4878 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4879 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4883 swap(*__first, *--__last);
4884 __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);
4888 template <class _RandomAccessIterator, class _Compare>
4889 inline _LIBCPP_INLINE_VISIBILITY
4891 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4893 #ifdef _LIBCPP_DEBUG
4894 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4895 __debug_less<_Compare> __c(__comp);
4896 __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);
4897 #else // _LIBCPP_DEBUG
4898 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4899 __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
4900 #endif // _LIBCPP_DEBUG
4903 template <class _RandomAccessIterator>
4904 inline _LIBCPP_INLINE_VISIBILITY
4906 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4908 _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4913 template <class _Compare, class _RandomAccessIterator>
4915 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4917 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4918 difference_type __n = __last - __first;
4921 // start from the first parent, there is no need to consider children
4922 for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start)
4924 __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start);
4929 template <class _RandomAccessIterator, class _Compare>
4930 inline _LIBCPP_INLINE_VISIBILITY
4932 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4934 #ifdef _LIBCPP_DEBUG
4935 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4936 __debug_less<_Compare> __c(__comp);
4937 __make_heap<_Comp_ref>(__first, __last, __c);
4938 #else // _LIBCPP_DEBUG
4939 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4940 __make_heap<_Comp_ref>(__first, __last, __comp);
4941 #endif // _LIBCPP_DEBUG
4944 template <class _RandomAccessIterator>
4945 inline _LIBCPP_INLINE_VISIBILITY
4947 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4949 _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4954 template <class _Compare, class _RandomAccessIterator>
4956 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4958 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4959 for (difference_type __n = __last - __first; __n > 1; --__last, --__n)
4960 __pop_heap<_Compare>(__first, __last, __comp, __n);
4963 template <class _RandomAccessIterator, class _Compare>
4964 inline _LIBCPP_INLINE_VISIBILITY
4966 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4968 #ifdef _LIBCPP_DEBUG
4969 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4970 __debug_less<_Compare> __c(__comp);
4971 __sort_heap<_Comp_ref>(__first, __last, __c);
4972 #else // _LIBCPP_DEBUG
4973 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4974 __sort_heap<_Comp_ref>(__first, __last, __comp);
4975 #endif // _LIBCPP_DEBUG
4978 template <class _RandomAccessIterator>
4979 inline _LIBCPP_INLINE_VISIBILITY
4981 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4983 _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4988 template <class _Compare, class _RandomAccessIterator>
4990 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
4993 __make_heap<_Compare>(__first, __middle, __comp);
4994 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
4995 for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
4997 if (__comp(*__i, *__first))
4999 swap(*__i, *__first);
5000 __sift_down<_Compare>(__first, __middle, __comp, __len, __first);
5003 __sort_heap<_Compare>(__first, __middle, __comp);
5006 template <class _RandomAccessIterator, class _Compare>
5007 inline _LIBCPP_INLINE_VISIBILITY
5009 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5012 #ifdef _LIBCPP_DEBUG
5013 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5014 __debug_less<_Compare> __c(__comp);
5015 __partial_sort<_Comp_ref>(__first, __middle, __last, __c);
5016 #else // _LIBCPP_DEBUG
5017 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5018 __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
5019 #endif // _LIBCPP_DEBUG
5022 template <class _RandomAccessIterator>
5023 inline _LIBCPP_INLINE_VISIBILITY
5025 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
5027 _VSTD::partial_sort(__first, __middle, __last,
5028 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5031 // partial_sort_copy
5033 template <class _Compare, class _InputIterator, class _RandomAccessIterator>
5034 _RandomAccessIterator
5035 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
5036 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5038 _RandomAccessIterator __r = __result_first;
5039 if (__r != __result_last)
5041 for (; __first != __last && __r != __result_last; (void) ++__first, ++__r)
5043 __make_heap<_Compare>(__result_first, __r, __comp);
5044 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
5045 for (; __first != __last; ++__first)
5046 if (__comp(*__first, *__result_first))
5048 *__result_first = *__first;
5049 __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first);
5051 __sort_heap<_Compare>(__result_first, __r, __comp);
5056 template <class _InputIterator, class _RandomAccessIterator, class _Compare>
5057 inline _LIBCPP_INLINE_VISIBILITY
5058 _RandomAccessIterator
5059 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5060 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5062 #ifdef _LIBCPP_DEBUG
5063 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5064 __debug_less<_Compare> __c(__comp);
5065 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);
5066 #else // _LIBCPP_DEBUG
5067 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5068 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
5069 #endif // _LIBCPP_DEBUG
5072 template <class _InputIterator, class _RandomAccessIterator>
5073 inline _LIBCPP_INLINE_VISIBILITY
5074 _RandomAccessIterator
5075 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5076 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
5078 return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
5079 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5084 template <class _Compare, class _RandomAccessIterator>
5086 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5088 // _Compare is known to be a reference type
5089 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5090 const difference_type __limit = 7;
5094 if (__nth == __last)
5096 difference_type __len = __last - __first;
5103 if (__comp(*--__last, *__first))
5104 swap(*__first, *__last);
5108 _RandomAccessIterator __m = __first;
5109 _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
5113 if (__len <= __limit)
5115 __selection_sort<_Compare>(__first, __last, __comp);
5118 // __len > __limit >= 3
5119 _RandomAccessIterator __m = __first + __len/2;
5120 _RandomAccessIterator __lm1 = __last;
5121 unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
5123 // partition [__first, __m) < *__m and *__m <= [__m, __last)
5124 // (this inhibits tossing elements equivalent to __m around unnecessarily)
5125 _RandomAccessIterator __i = __first;
5126 _RandomAccessIterator __j = __lm1;
5127 // j points beyond range to be tested, *__lm1 is known to be <= *__m
5128 // The search going up is known to be guarded but the search coming down isn't.
5129 // Prime the downward search with a guard.
5130 if (!__comp(*__i, *__m)) // if *__first == *__m
5132 // *__first == *__m, *__first doesn't go in first part
5133 // manually guard downward moving __j against __i
5138 // *__first == *__m, *__m <= all other elements
5139 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
5140 ++__i; // __first + 1
5142 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
5147 return; // [__first, __last) all equivalent elements
5148 if (__comp(*__first, *__i))
5158 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
5163 while (!__comp(*__first, *__i))
5165 while (__comp(*__first, *--__j))
5173 // [__first, __i) == *__first and *__first < [__i, __last)
5174 // The first part is sorted,
5177 // __nth_element the secod part
5178 // __nth_element<_Compare>(__i, __nth, __last, __comp);
5182 if (__comp(*__j, *__m))
5186 break; // found guard for downward moving __j, now use unguarded partition
5191 // j points beyond range to be tested, *__lm1 is known to be <= *__m
5192 // if not yet partitioned...
5195 // known that *(__i - 1) < *__m
5198 // __m still guards upward moving __i
5199 while (__comp(*__i, *__m))
5201 // It is now known that a guard exists for downward moving __j
5202 while (!__comp(*--__j, *__m))
5208 // It is known that __m != __j
5209 // If __m just moved, follow it
5215 // [__first, __i) < *__m and *__m <= [__i, __last)
5216 if (__i != __m && __comp(*__m, *__i))
5221 // [__first, __i) < *__i and *__i <= [__i+1, __last)
5226 // We were given a perfectly partitioned sequence. Coincidence?
5229 // Check for [__first, __i) already sorted
5230 __j = __m = __first;
5231 while (++__j != __i)
5233 if (__comp(*__j, *__m))
5234 // not yet sorted, so sort
5238 // [__first, __i) sorted
5243 // Check for [__i, __last) already sorted
5245 while (++__j != __last)
5247 if (__comp(*__j, *__m))
5248 // not yet sorted, so sort
5252 // [__i, __last) sorted
5257 // __nth_element on range containing __nth
5260 // __nth_element<_Compare>(__first, __nth, __i, __comp);
5265 // __nth_element<_Compare>(__i+1, __nth, __last, __comp);
5271 template <class _RandomAccessIterator, class _Compare>
5272 inline _LIBCPP_INLINE_VISIBILITY
5274 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5276 #ifdef _LIBCPP_DEBUG
5277 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5278 __debug_less<_Compare> __c(__comp);
5279 __nth_element<_Comp_ref>(__first, __nth, __last, __c);
5280 #else // _LIBCPP_DEBUG
5281 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5282 __nth_element<_Comp_ref>(__first, __nth, __last, __comp);
5283 #endif // _LIBCPP_DEBUG
5286 template <class _RandomAccessIterator>
5287 inline _LIBCPP_INLINE_VISIBILITY
5289 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
5291 _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5296 template <class _Compare, class _InputIterator1, class _InputIterator2>
5297 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
5298 __includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5301 for (; __first2 != __last2; ++__first1)
5303 if (__first1 == __last1 || __comp(*__first2, *__first1))
5305 if (!__comp(*__first1, *__first2))
5311 template <class _InputIterator1, class _InputIterator2, class _Compare>
5312 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5314 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5317 #ifdef _LIBCPP_DEBUG
5318 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5319 __debug_less<_Compare> __c(__comp);
5320 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5321 #else // _LIBCPP_DEBUG
5322 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5323 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5324 #endif // _LIBCPP_DEBUG
5327 template <class _InputIterator1, class _InputIterator2>
5328 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5330 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
5332 return _VSTD::includes(__first1, __last1, __first2, __last2,
5333 __less<typename iterator_traits<_InputIterator1>::value_type,
5334 typename iterator_traits<_InputIterator2>::value_type>());
5339 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5341 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5342 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5344 for (; __first1 != __last1; ++__result)
5346 if (__first2 == __last2)
5347 return _VSTD::copy(__first1, __last1, __result);
5348 if (__comp(*__first2, *__first1))
5350 *__result = *__first2;
5355 if (!__comp(*__first1, *__first2))
5357 *__result = *__first1;
5361 return _VSTD::copy(__first2, __last2, __result);
5364 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5365 inline _LIBCPP_INLINE_VISIBILITY
5367 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5368 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5370 #ifdef _LIBCPP_DEBUG
5371 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5372 __debug_less<_Compare> __c(__comp);
5373 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5374 #else // _LIBCPP_DEBUG
5375 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5376 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5377 #endif // _LIBCPP_DEBUG
5380 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5381 inline _LIBCPP_INLINE_VISIBILITY
5383 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5384 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5386 return _VSTD::set_union(__first1, __last1, __first2, __last2, __result,
5387 __less<typename iterator_traits<_InputIterator1>::value_type,
5388 typename iterator_traits<_InputIterator2>::value_type>());
5393 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5394 _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
5395 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5396 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5398 while (__first1 != __last1 && __first2 != __last2)
5400 if (__comp(*__first1, *__first2))
5404 if (!__comp(*__first2, *__first1))
5406 *__result = *__first1;
5416 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5417 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5419 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5420 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5422 #ifdef _LIBCPP_DEBUG
5423 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5424 __debug_less<_Compare> __c(__comp);
5425 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5426 #else // _LIBCPP_DEBUG
5427 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5428 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5429 #endif // _LIBCPP_DEBUG
5432 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5433 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5435 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5436 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5438 return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result,
5439 __less<typename iterator_traits<_InputIterator1>::value_type,
5440 typename iterator_traits<_InputIterator2>::value_type>());
5445 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5447 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5448 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5450 while (__first1 != __last1)
5452 if (__first2 == __last2)
5453 return _VSTD::copy(__first1, __last1, __result);
5454 if (__comp(*__first1, *__first2))
5456 *__result = *__first1;
5462 if (!__comp(*__first2, *__first1))
5470 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5471 inline _LIBCPP_INLINE_VISIBILITY
5473 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5474 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5476 #ifdef _LIBCPP_DEBUG
5477 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5478 __debug_less<_Compare> __c(__comp);
5479 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5480 #else // _LIBCPP_DEBUG
5481 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5482 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5483 #endif // _LIBCPP_DEBUG
5486 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5487 inline _LIBCPP_INLINE_VISIBILITY
5489 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5490 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5492 return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result,
5493 __less<typename iterator_traits<_InputIterator1>::value_type,
5494 typename iterator_traits<_InputIterator2>::value_type>());
5497 // set_symmetric_difference
5499 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5501 __set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5502 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5504 while (__first1 != __last1)
5506 if (__first2 == __last2)
5507 return _VSTD::copy(__first1, __last1, __result);
5508 if (__comp(*__first1, *__first2))
5510 *__result = *__first1;
5516 if (__comp(*__first2, *__first1))
5518 *__result = *__first2;
5526 return _VSTD::copy(__first2, __last2, __result);
5529 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5530 inline _LIBCPP_INLINE_VISIBILITY
5532 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5533 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5535 #ifdef _LIBCPP_DEBUG
5536 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5537 __debug_less<_Compare> __c(__comp);
5538 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5539 #else // _LIBCPP_DEBUG
5540 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5541 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5542 #endif // _LIBCPP_DEBUG
5545 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5546 inline _LIBCPP_INLINE_VISIBILITY
5548 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5549 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5551 return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
5552 __less<typename iterator_traits<_InputIterator1>::value_type,
5553 typename iterator_traits<_InputIterator2>::value_type>());
5556 // lexicographical_compare
5558 template <class _Compare, class _InputIterator1, class _InputIterator2>
5559 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
5560 __lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5561 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5563 for (; __first2 != __last2; ++__first1, (void) ++__first2)
5565 if (__first1 == __last1 || __comp(*__first1, *__first2))
5567 if (__comp(*__first2, *__first1))
5573 template <class _InputIterator1, class _InputIterator2, class _Compare>
5574 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5576 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5577 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5579 #ifdef _LIBCPP_DEBUG
5580 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5581 __debug_less<_Compare> __c(__comp);
5582 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5583 #else // _LIBCPP_DEBUG
5584 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5585 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5586 #endif // _LIBCPP_DEBUG
5589 template <class _InputIterator1, class _InputIterator2>
5590 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5592 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5593 _InputIterator2 __first2, _InputIterator2 __last2)
5595 return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,
5596 __less<typename iterator_traits<_InputIterator1>::value_type,
5597 typename iterator_traits<_InputIterator2>::value_type>());
5602 template <class _Compare, class _BidirectionalIterator>
5604 __next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5606 _BidirectionalIterator __i = __last;
5607 if (__first == __last || __first == --__i)
5611 _BidirectionalIterator __ip1 = __i;
5612 if (__comp(*--__i, *__ip1))
5614 _BidirectionalIterator __j = __last;
5615 while (!__comp(*__i, *--__j))
5618 _VSTD::reverse(__ip1, __last);
5623 _VSTD::reverse(__first, __last);
5629 template <class _BidirectionalIterator, class _Compare>
5630 inline _LIBCPP_INLINE_VISIBILITY
5632 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5634 #ifdef _LIBCPP_DEBUG
5635 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5636 __debug_less<_Compare> __c(__comp);
5637 return __next_permutation<_Comp_ref>(__first, __last, __c);
5638 #else // _LIBCPP_DEBUG
5639 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5640 return __next_permutation<_Comp_ref>(__first, __last, __comp);
5641 #endif // _LIBCPP_DEBUG
5644 template <class _BidirectionalIterator>
5645 inline _LIBCPP_INLINE_VISIBILITY
5647 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5649 return _VSTD::next_permutation(__first, __last,
5650 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5655 template <class _Compare, class _BidirectionalIterator>
5657 __prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5659 _BidirectionalIterator __i = __last;
5660 if (__first == __last || __first == --__i)
5664 _BidirectionalIterator __ip1 = __i;
5665 if (__comp(*__ip1, *--__i))
5667 _BidirectionalIterator __j = __last;
5668 while (!__comp(*--__j, *__i))
5671 _VSTD::reverse(__ip1, __last);
5676 _VSTD::reverse(__first, __last);
5682 template <class _BidirectionalIterator, class _Compare>
5683 inline _LIBCPP_INLINE_VISIBILITY
5685 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5687 #ifdef _LIBCPP_DEBUG
5688 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5689 __debug_less<_Compare> __c(__comp);
5690 return __prev_permutation<_Comp_ref>(__first, __last, __c);
5691 #else // _LIBCPP_DEBUG
5692 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5693 return __prev_permutation<_Comp_ref>(__first, __last, __comp);
5694 #endif // _LIBCPP_DEBUG
5697 template <class _BidirectionalIterator>
5698 inline _LIBCPP_INLINE_VISIBILITY
5700 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5702 return _VSTD::prev_permutation(__first, __last,
5703 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5706 _LIBCPP_END_NAMESPACE_STD
5710 #endif // _LIBCPP_ALGORITHM