1// -*- C++ -*-
2//===-------------------------- algorithm ---------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_ALGORITHM
11#define _LIBCPP_ALGORITHM
12
13/*
14 algorithm synopsis
15
16#include <initializer_list>
17
18namespace std
19{
20
21template <class InputIterator, class Predicate>
22 constexpr bool // constexpr in C++20
23 all_of(InputIterator first, InputIterator last, Predicate pred);
24
25template <class InputIterator, class Predicate>
26 constexpr bool // constexpr in C++20
27 any_of(InputIterator first, InputIterator last, Predicate pred);
28
29template <class InputIterator, class Predicate>
30 constexpr bool // constexpr in C++20
31 none_of(InputIterator first, InputIterator last, Predicate pred);
32
33template <class InputIterator, class Function>
34 constexpr Function // constexpr in C++20
35 for_each(InputIterator first, InputIterator last, Function f);
36
37template<class InputIterator, class Size, class Function>
38 constexpr InputIterator // constexpr in C++20
39 for_each_n(InputIterator first, Size n, Function f); // C++17
40
41template <class InputIterator, class T>
42 constexpr InputIterator // constexpr in C++20
43 find(InputIterator first, InputIterator last, const T& value);
44
45template <class InputIterator, class Predicate>
46 constexpr InputIterator // constexpr in C++20
47 find_if(InputIterator first, InputIterator last, Predicate pred);
48
49template<class InputIterator, class Predicate>
50 InputIterator // constexpr in C++20
51 find_if_not(InputIterator first, InputIterator last, Predicate pred);
52
53template <class ForwardIterator1, class ForwardIterator2>
54 ForwardIterator1 // constexpr in C++20
55 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
56 ForwardIterator2 first2, ForwardIterator2 last2);
57
58template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
59 ForwardIterator1 // constexpr in C++20
60 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
61 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
62
63template <class ForwardIterator1, class ForwardIterator2>
64 constexpr ForwardIterator1 // constexpr in C++20
65 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
66 ForwardIterator2 first2, ForwardIterator2 last2);
67
68template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
69 constexpr ForwardIterator1 // constexpr in C++20
70 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
71 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
72
73template <class ForwardIterator>
74 constexpr ForwardIterator // constexpr in C++20
75 adjacent_find(ForwardIterator first, ForwardIterator last);
76
77template <class ForwardIterator, class BinaryPredicate>
78 constexpr ForwardIterator // constexpr in C++20
79 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
80
81template <class InputIterator, class T>
82 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20
83 count(InputIterator first, InputIterator last, const T& value);
84
85template <class InputIterator, class Predicate>
86 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20
87 count_if(InputIterator first, InputIterator last, Predicate pred);
88
89template <class InputIterator1, class InputIterator2>
90 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
91 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
92
93template <class InputIterator1, class InputIterator2>
94 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
95 mismatch(InputIterator1 first1, InputIterator1 last1,
96 InputIterator2 first2, InputIterator2 last2); // **C++14**
97
98template <class InputIterator1, class InputIterator2, class BinaryPredicate>
99 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
100 mismatch(InputIterator1 first1, InputIterator1 last1,
101 InputIterator2 first2, BinaryPredicate pred);
102
103template <class InputIterator1, class InputIterator2, class BinaryPredicate>
104 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
105 mismatch(InputIterator1 first1, InputIterator1 last1,
106 InputIterator2 first2, InputIterator2 last2,
107 BinaryPredicate pred); // **C++14**
108
109template <class InputIterator1, class InputIterator2>
110 constexpr bool // constexpr in C++20
111 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
112
113template <class InputIterator1, class InputIterator2>
114 constexpr bool // constexpr in C++20
115 equal(InputIterator1 first1, InputIterator1 last1,
116 InputIterator2 first2, InputIterator2 last2); // **C++14**
117
118template <class InputIterator1, class InputIterator2, class BinaryPredicate>
119 constexpr bool // constexpr in C++20
120 equal(InputIterator1 first1, InputIterator1 last1,
121 InputIterator2 first2, BinaryPredicate pred);
122
123template <class InputIterator1, class InputIterator2, class BinaryPredicate>
124 constexpr bool // constexpr in C++20
125 equal(InputIterator1 first1, InputIterator1 last1,
126 InputIterator2 first2, InputIterator2 last2,
127 BinaryPredicate pred); // **C++14**
128
129template<class ForwardIterator1, class ForwardIterator2>
130 constexpr bool // constexpr in C++20
131 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
132 ForwardIterator2 first2);
133
134template<class ForwardIterator1, class ForwardIterator2>
135 constexpr bool // constexpr in C++20
136 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
137 ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**
138
139template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
140 constexpr bool // constexpr in C++20
141 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
142 ForwardIterator2 first2, BinaryPredicate pred);
143
144template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
145 constexpr bool // constexpr in C++20
146 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
147 ForwardIterator2 first2, ForwardIterator2 last2,
148 BinaryPredicate pred); // **C++14**
149
150template <class ForwardIterator1, class ForwardIterator2>
151 constexpr ForwardIterator1 // constexpr in C++20
152 search(ForwardIterator1 first1, ForwardIterator1 last1,
153 ForwardIterator2 first2, ForwardIterator2 last2);
154
155template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
156 constexpr ForwardIterator1 // constexpr in C++20
157 search(ForwardIterator1 first1, ForwardIterator1 last1,
158 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
159
160template <class ForwardIterator, class Size, class T>
161 constexpr ForwardIterator // constexpr in C++20
162 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
163
164template <class ForwardIterator, class Size, class T, class BinaryPredicate>
165 constexpr ForwardIterator // constexpr in C++20
166 search_n(ForwardIterator first, ForwardIterator last,
167 Size count, const T& value, BinaryPredicate pred);
168
169template <class InputIterator, class OutputIterator>
170 OutputIterator
171 copy(InputIterator first, InputIterator last, OutputIterator result);
172
173template<class InputIterator, class OutputIterator, class Predicate>
174 OutputIterator
175 copy_if(InputIterator first, InputIterator last,
176 OutputIterator result, Predicate pred);
177
178template<class InputIterator, class Size, class OutputIterator>
179 OutputIterator
180 copy_n(InputIterator first, Size n, OutputIterator result);
181
182template <class BidirectionalIterator1, class BidirectionalIterator2>
183 BidirectionalIterator2
184 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
185 BidirectionalIterator2 result);
186
187template <class ForwardIterator1, class ForwardIterator2>
188 ForwardIterator2
189 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
190
191template <class ForwardIterator1, class ForwardIterator2>
192 void
193 iter_swap(ForwardIterator1 a, ForwardIterator2 b);
194
195template <class InputIterator, class OutputIterator, class UnaryOperation>
196 constexpr OutputIterator // constexpr in C++20
197 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
198
199template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
200 constexpr OutputIterator // constexpr in C++20
201 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
202 OutputIterator result, BinaryOperation binary_op);
203
204template <class ForwardIterator, class T>
205 constexpr void // constexpr in C++20
206 replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
207
208template <class ForwardIterator, class Predicate, class T>
209 constexpr void // constexpr in C++20
210 replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
211
212template <class InputIterator, class OutputIterator, class T>
213 constexpr OutputIterator // constexpr in C++20
214 replace_copy(InputIterator first, InputIterator last, OutputIterator result,
215 const T& old_value, const T& new_value);
216
217template <class InputIterator, class OutputIterator, class Predicate, class T>
218 constexpr OutputIterator // constexpr in C++20
219 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
220
221template <class ForwardIterator, class T>
222 constexpr void // constexpr in C++20
223 fill(ForwardIterator first, ForwardIterator last, const T& value);
224
225template <class OutputIterator, class Size, class T>
226 constexpr OutputIterator // constexpr in C++20
227 fill_n(OutputIterator first, Size n, const T& value);
228
229template <class ForwardIterator, class Generator>
230 constexpr void // constexpr in C++20
231 generate(ForwardIterator first, ForwardIterator last, Generator gen);
232
233template <class OutputIterator, class Size, class Generator>
234 constexpr OutputIterator // constexpr in C++20
235 generate_n(OutputIterator first, Size n, Generator gen);
236
237template <class ForwardIterator, class T>
238 constexpr ForwardIterator // constexpr in C++20
239 remove(ForwardIterator first, ForwardIterator last, const T& value);
240
241template <class ForwardIterator, class Predicate>
242 constexpr ForwardIterator // constexpr in C++20
243 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
244
245template <class InputIterator, class OutputIterator, class T>
246 constexpr OutputIterator // constexpr in C++20
247 remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
248
249template <class InputIterator, class OutputIterator, class Predicate>
250 constexpr OutputIterator // constexpr in C++20
251 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
252
253template <class ForwardIterator>
254 ForwardIterator
255 unique(ForwardIterator first, ForwardIterator last);
256
257template <class ForwardIterator, class BinaryPredicate>
258 ForwardIterator
259 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
260
261template <class InputIterator, class OutputIterator>
262 OutputIterator
263 unique_copy(InputIterator first, InputIterator last, OutputIterator result);
264
265template <class InputIterator, class OutputIterator, class BinaryPredicate>
266 OutputIterator
267 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
268
269template <class BidirectionalIterator>
270 void
271 reverse(BidirectionalIterator first, BidirectionalIterator last);
272
273template <class BidirectionalIterator, class OutputIterator>
274 constexpr OutputIterator // constexpr in C++20
275 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
276
277template <class ForwardIterator>
278 ForwardIterator
279 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
280
281template <class ForwardIterator, class OutputIterator>
282 OutputIterator
283 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
284
285template <class RandomAccessIterator>
286 void
287 random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17
288
289template <class RandomAccessIterator, class RandomNumberGenerator>
290 void
291 random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
292 RandomNumberGenerator& rand); // deprecated in C++14, removed in C++17
293
294template<class PopulationIterator, class SampleIterator,
295 class Distance, class UniformRandomBitGenerator>
296 SampleIterator sample(PopulationIterator first, PopulationIterator last,
297 SampleIterator out, Distance n,
298 UniformRandomBitGenerator&& g); // C++17
299
300template<class RandomAccessIterator, class UniformRandomNumberGenerator>
301 void shuffle(RandomAccessIterator first, RandomAccessIterator last,
302 UniformRandomNumberGenerator&& g);
303
304template <class InputIterator, class Predicate>
305 constexpr bool // constexpr in C++20
306 is_partitioned(InputIterator first, InputIterator last, Predicate pred);
307
308template <class ForwardIterator, class Predicate>
309 ForwardIterator
310 partition(ForwardIterator first, ForwardIterator last, Predicate pred);
311
312template <class InputIterator, class OutputIterator1,
313 class OutputIterator2, class Predicate>
314 constexpr pair<OutputIterator1, OutputIterator2> // constexpr in C++20
315 partition_copy(InputIterator first, InputIterator last,
316 OutputIterator1 out_true, OutputIterator2 out_false,
317 Predicate pred);
318
319template <class ForwardIterator, class Predicate>
320 ForwardIterator
321 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
322
323template<class ForwardIterator, class Predicate>
324 constexpr ForwardIterator // constexpr in C++20
325 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
326
327template <class ForwardIterator>
328 constexpr bool // constexpr in C++20
329 is_sorted(ForwardIterator first, ForwardIterator last);
330
331template <class ForwardIterator, class Compare>
332 bool
333 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
334
335template<class ForwardIterator>
336 constexpr ForwardIterator // constexpr in C++20
337 is_sorted_until(ForwardIterator first, ForwardIterator last);
338
339template <class ForwardIterator, class Compare>
340 constexpr ForwardIterator // constexpr in C++20
341 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
342
343template <class RandomAccessIterator>
344 void
345 sort(RandomAccessIterator first, RandomAccessIterator last);
346
347template <class RandomAccessIterator, class Compare>
348 void
349 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
350
351template <class RandomAccessIterator>
352 void
353 stable_sort(RandomAccessIterator first, RandomAccessIterator last);
354
355template <class RandomAccessIterator, class Compare>
356 void
357 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
358
359template <class RandomAccessIterator>
360 void
361 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
362
363template <class RandomAccessIterator, class Compare>
364 void
365 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
366
367template <class InputIterator, class RandomAccessIterator>
368 RandomAccessIterator
369 partial_sort_copy(InputIterator first, InputIterator last,
370 RandomAccessIterator result_first, RandomAccessIterator result_last);
371
372template <class InputIterator, class RandomAccessIterator, class Compare>
373 RandomAccessIterator
374 partial_sort_copy(InputIterator first, InputIterator last,
375 RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
376
377template <class RandomAccessIterator>
378 void
379 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
380
381template <class RandomAccessIterator, class Compare>
382 void
383 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
384
385template <class ForwardIterator, class T>
386 constexpr ForwardIterator // constexpr in C++20
387 lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
388
389template <class ForwardIterator, class T, class Compare>
390 constexpr ForwardIterator // constexpr in C++20
391 lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
392
393template <class ForwardIterator, class T>
394 constexpr ForwardIterator // constexpr in C++20
395 upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
396
397template <class ForwardIterator, class T, class Compare>
398 constexpr ForwardIterator // constexpr in C++20
399 upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
400
401template <class ForwardIterator, class T>
402 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20
403 equal_range(ForwardIterator first, ForwardIterator last, const T& value);
404
405template <class ForwardIterator, class T, class Compare>
406 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20
407 equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
408
409template <class ForwardIterator, class T>
410 constexpr bool // constexpr in C++20
411 binary_search(ForwardIterator first, ForwardIterator last, const T& value);
412
413template <class ForwardIterator, class T, class Compare>
414 constexpr bool // constexpr in C++20
415 binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
416
417template <class InputIterator1, class InputIterator2, class OutputIterator>
418 OutputIterator
419 merge(InputIterator1 first1, InputIterator1 last1,
420 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
421
422template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
423 OutputIterator
424 merge(InputIterator1 first1, InputIterator1 last1,
425 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
426
427template <class BidirectionalIterator>
428 void
429 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
430
431template <class BidirectionalIterator, class Compare>
432 void
433 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
434
435template <class InputIterator1, class InputIterator2>
436 constexpr bool // constexpr in C++20
437 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
438
439template <class InputIterator1, class InputIterator2, class Compare>
440 constexpr bool // constexpr in C++20
441 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
442
443template <class InputIterator1, class InputIterator2, class OutputIterator>
444 OutputIterator
445 set_union(InputIterator1 first1, InputIterator1 last1,
446 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
447
448template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
449 OutputIterator
450 set_union(InputIterator1 first1, InputIterator1 last1,
451 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
452
453template <class InputIterator1, class InputIterator2, class OutputIterator>
454 constexpr OutputIterator // constexpr in C++20
455 set_intersection(InputIterator1 first1, InputIterator1 last1,
456 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
457
458template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
459 constexpr OutputIterator // constexpr in C++20
460 set_intersection(InputIterator1 first1, InputIterator1 last1,
461 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
462
463template <class InputIterator1, class InputIterator2, class OutputIterator>
464 OutputIterator
465 set_difference(InputIterator1 first1, InputIterator1 last1,
466 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
467
468template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
469 OutputIterator
470 set_difference(InputIterator1 first1, InputIterator1 last1,
471 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
472
473template <class InputIterator1, class InputIterator2, class OutputIterator>
474 OutputIterator
475 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
476 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
477
478template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
479 OutputIterator
480 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
481 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
482
483template <class RandomAccessIterator>
484 void
485 push_heap(RandomAccessIterator first, RandomAccessIterator last);
486
487template <class RandomAccessIterator, class Compare>
488 void
489 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
490
491template <class RandomAccessIterator>
492 void
493 pop_heap(RandomAccessIterator first, RandomAccessIterator last);
494
495template <class RandomAccessIterator, class Compare>
496 void
497 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
498
499template <class RandomAccessIterator>
500 void
501 make_heap(RandomAccessIterator first, RandomAccessIterator last);
502
503template <class RandomAccessIterator, class Compare>
504 void
505 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
506
507template <class RandomAccessIterator>
508 void
509 sort_heap(RandomAccessIterator first, RandomAccessIterator last);
510
511template <class RandomAccessIterator, class Compare>
512 void
513 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
514
515template <class RandomAccessIterator>
516 constexpr bool // constexpr in C++20
517 is_heap(RandomAccessIterator first, RandomAccessiterator last);
518
519template <class RandomAccessIterator, class Compare>
520 constexpr bool // constexpr in C++20
521 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
522
523template <class RandomAccessIterator>
524 constexpr RandomAccessIterator // constexpr in C++20
525 is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
526
527template <class RandomAccessIterator, class Compare>
528 constexpr RandomAccessIterator // constexpr in C++20
529 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
530
531template <class ForwardIterator>
532 ForwardIterator
533 min_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14
534
535template <class ForwardIterator, class Compare>
536 ForwardIterator
537 min_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14
538
539template <class T>
540 const T&
541 min(const T& a, const T& b); // constexpr in C++14
542
543template <class T, class Compare>
544 const T&
545 min(const T& a, const T& b, Compare comp); // constexpr in C++14
546
547template<class T>
548 T
549 min(initializer_list<T> t); // constexpr in C++14
550
551template<class T, class Compare>
552 T
553 min(initializer_list<T> t, Compare comp); // constexpr in C++14
554
555template<class T>
556 constexpr const T& clamp( const T& v, const T& lo, const T& hi ); // C++17
557
558template<class T, class Compare>
559 constexpr const T& clamp( const T& v, const T& lo, const T& hi, Compare comp ); // C++17
560
561template <class ForwardIterator>
562 ForwardIterator
563 max_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14
564
565template <class ForwardIterator, class Compare>
566 ForwardIterator
567 max_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14
568
569template <class T>
570 const T&
571 max(const T& a, const T& b); // constexpr in C++14
572
573template <class T, class Compare>
574 const T&
575 max(const T& a, const T& b, Compare comp); // constexpr in C++14
576
577template<class T>
578 T
579 max(initializer_list<T> t); // constexpr in C++14
580
581template<class T, class Compare>
582 T
583 max(initializer_list<T> t, Compare comp); // constexpr in C++14
584
585template<class ForwardIterator>
586 pair<ForwardIterator, ForwardIterator>
587 minmax_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14
588
589template<class ForwardIterator, class Compare>
590 pair<ForwardIterator, ForwardIterator>
591 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14
592
593template<class T>
594 pair<const T&, const T&>
595 minmax(const T& a, const T& b); // constexpr in C++14
596
597template<class T, class Compare>
598 pair<const T&, const T&>
599 minmax(const T& a, const T& b, Compare comp); // constexpr in C++14
600
601template<class T>
602 pair<T, T>
603 minmax(initializer_list<T> t); // constexpr in C++14
604
605template<class T, class Compare>
606 pair<T, T>
607 minmax(initializer_list<T> t, Compare comp); // constexpr in C++14
608
609template <class InputIterator1, class InputIterator2>
610 constexpr bool // constexpr in C++20
611 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
612
613template <class InputIterator1, class InputIterator2, class Compare>
614 constexpr bool // constexpr in C++20
615 lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
616 InputIterator2 first2, InputIterator2 last2, Compare comp);
617
618template <class BidirectionalIterator>
619 bool
620 next_permutation(BidirectionalIterator first, BidirectionalIterator last);
621
622template <class BidirectionalIterator, class Compare>
623 bool
624 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
625
626template <class BidirectionalIterator>
627 bool
628 prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
629
630template <class BidirectionalIterator, class Compare>
631 bool
632 prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
633
634} // std
635
636*/
637
638#include <__config>
639#include <initializer_list>
640#include <type_traits>
641#include <cstring>
642#include <utility> // needed to provide swap_ranges.
643#include <memory>
644#include <functional>
645#include <iterator>
646#include <cstddef>
647#include <bit>
648#include <version>
649
650#include <__debug>
651
652#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
653#pragma GCC system_header
654#endif
655
656_LIBCPP_PUSH_MACROS
657#include <__undef_macros>
658
659
660_LIBCPP_BEGIN_NAMESPACE_STD
661
662// I'd like to replace these with _VSTD::equal_to<void>, but can't because:
663// * That only works with C++14 and later, and
664// * We haven't included <functional> here.
665template <class _T1, class _T2 = _T1>
666struct __equal_to
667{
668 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
669 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;}
670 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;}
671 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;}
672};
673
674template <class _T1>
675struct __equal_to<_T1, _T1>
676{
677 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
678 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
679};
680
681template <class _T1>
682struct __equal_to<const _T1, _T1>
683{
684 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
685 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
686};
687
688template <class _T1>
689struct __equal_to<_T1, const _T1>
690{
691 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
692 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
693};
694
695template <class _T1, class _T2 = _T1>
696struct __less
697{
698 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
699 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
700
701 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
702 bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;}
703
704 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
705 bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;}
706
707 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
708 bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;}
709};
710
711template <class _T1>
712struct __less<_T1, _T1>
713{
714 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
715 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
716};
717
718template <class _T1>
719struct __less<const _T1, _T1>
720{
721 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
722 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
723};
724
725template <class _T1>
726struct __less<_T1, const _T1>
727{
728 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
729 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
730};
731
732template <class _Predicate>
733class __invert // invert the sense of a comparison
734{
735private:
736 _Predicate __p_;
737public:
738 _LIBCPP_INLINE_VISIBILITY __invert() {}
739
740 _LIBCPP_INLINE_VISIBILITY
741 explicit __invert(_Predicate __p) : __p_(__p) {}
742
743 template <class _T1>
744 _LIBCPP_INLINE_VISIBILITY
745 bool operator()(const _T1& __x) {return !__p_(__x);}
746
747 template <class _T1, class _T2>
748 _LIBCPP_INLINE_VISIBILITY
749 bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);}
750};
751
752// Perform division by two quickly for positive integers (llvm.org/PR39129)
753
754template <typename _Integral>
755_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
756typename enable_if
757<
758 is_integral<_Integral>::value,
759 _Integral
760>::type
761__half_positive(_Integral __value)
762{
763 return static_cast<_Integral>(static_cast<typename make_unsigned<_Integral>::type>(__value) / 2);
764}
765
766template <typename _Tp>
767_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
768typename enable_if
769<
770 !is_integral<_Tp>::value,
771 _Tp
772>::type
773__half_positive(_Tp __value)
774{
775 return __value / 2;
776}
777
778#ifdef _LIBCPP_DEBUG
779
780template <class _Compare>
781struct __debug_less
782{
783 _Compare __comp_;
784 __debug_less(_Compare& __c) : __comp_(__c) {}
785
786 template <class _Tp, class _Up>
787 bool operator()(_Tp& __x, _Up& __y)
788 {
789 bool __r = __comp_(__x, __y);
790 if (__r)
791 __do_compare_assert(0, __y, __x);
792 return __r;
793 }
794
795 template <class _LHS, class _RHS>
796 inline _LIBCPP_INLINE_VISIBILITY
797 decltype((void)_VSTD::declval<_Compare&>()(
798 _VSTD::declval<_LHS &>(), _VSTD::declval<_RHS &>()))
799 __do_compare_assert(int, _LHS & __l, _RHS & __r) {
800 _LIBCPP_ASSERT(!__comp_(__l, __r),
801 "Comparator does not induce a strict weak ordering");
802 }
803
804 template <class _LHS, class _RHS>
805 inline _LIBCPP_INLINE_VISIBILITY
806 void __do_compare_assert(long, _LHS &, _RHS &) {}
807};
808
809#endif // _LIBCPP_DEBUG
810
811// all_of
812
813template <class _InputIterator, class _Predicate>
814_LIBCPP_NODISCARD_EXT inline
815_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
816bool
817all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
818{
819 for (; __first != __last; ++__first)
820 if (!__pred(*__first))
821 return false;
822 return true;
823}
824
825// any_of
826
827template <class _InputIterator, class _Predicate>
828_LIBCPP_NODISCARD_EXT inline
829_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
830bool
831any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
832{
833 for (; __first != __last; ++__first)
834 if (__pred(*__first))
835 return true;
836 return false;
837}
838
839// none_of
840
841template <class _InputIterator, class _Predicate>
842_LIBCPP_NODISCARD_EXT inline
843_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
844bool
845none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
846{
847 for (; __first != __last; ++__first)
848 if (__pred(*__first))
849 return false;
850 return true;
851}
852
853// for_each
854
855template <class _InputIterator, class _Function>
856inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
857_Function
858for_each(_InputIterator __first, _InputIterator __last, _Function __f)
859{
860 for (; __first != __last; ++__first)
861 __f(*__first);
862 return __f;
863}
864
865#if _LIBCPP_STD_VER > 14
866// for_each_n
867
868template <class _InputIterator, class _Size, class _Function>
869inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
870_InputIterator
871for_each_n(_InputIterator __first, _Size __orig_n, _Function __f)
872{
873 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
874 _IntegralSize __n = __orig_n;
875 while (__n > 0)
876 {
877 __f(*__first);
878 ++__first;
879 --__n;
880 }
881 return __first;
882}
883#endif
884
885// find
886
887template <class _InputIterator, class _Tp>
888_LIBCPP_NODISCARD_EXT inline
889_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
890_InputIterator
891find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
892{
893 for (; __first != __last; ++__first)
894 if (*__first == __value_)
895 break;
896 return __first;
897}
898
899// find_if
900
901template <class _InputIterator, class _Predicate>
902_LIBCPP_NODISCARD_EXT inline
903_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
904_InputIterator
905find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
906{
907 for (; __first != __last; ++__first)
908 if (__pred(*__first))
909 break;
910 return __first;
911}
912
913// find_if_not
914
915template<class _InputIterator, class _Predicate>
916_LIBCPP_NODISCARD_EXT inline
917_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
918_InputIterator
919find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
920{
921 for (; __first != __last; ++__first)
922 if (!__pred(*__first))
923 break;
924 return __first;
925}
926
927// find_end
928
929template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
930_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1
931__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
932 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
933 forward_iterator_tag, forward_iterator_tag)
934{
935 // modeled after search algorithm
936 _ForwardIterator1 __r = __last1; // __last1 is the "default" answer
937 if (__first2 == __last2)
938 return __r;
939 while (true)
940 {
941 while (true)
942 {
943 if (__first1 == __last1) // if source exhausted return last correct answer
944 return __r; // (or __last1 if never found)
945 if (__pred(*__first1, *__first2))
946 break;
947 ++__first1;
948 }
949 // *__first1 matches *__first2, now match elements after here
950 _ForwardIterator1 __m1 = __first1;
951 _ForwardIterator2 __m2 = __first2;
952 while (true)
953 {
954 if (++__m2 == __last2)
955 { // Pattern exhaused, record answer and search for another one
956 __r = __first1;
957 ++__first1;
958 break;
959 }
960 if (++__m1 == __last1) // Source exhausted, return last answer
961 return __r;
962 if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first
963 {
964 ++__first1;
965 break;
966 } // else there is a match, check next elements
967 }
968 }
969}
970
971template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2>
972_LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator1
973__find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,
974 _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred,
975 bidirectional_iterator_tag, bidirectional_iterator_tag)
976{
977 // modeled after search algorithm (in reverse)
978 if (__first2 == __last2)
979 return __last1; // Everything matches an empty sequence
980 _BidirectionalIterator1 __l1 = __last1;
981 _BidirectionalIterator2 __l2 = __last2;
982 --__l2;
983 while (true)
984 {
985 // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks
986 while (true)
987 {
988 if (__first1 == __l1) // return __last1 if no element matches *__first2
989 return __last1;
990 if (__pred(*--__l1, *__l2))
991 break;
992 }
993 // *__l1 matches *__l2, now match elements before here
994 _BidirectionalIterator1 __m1 = __l1;
995 _BidirectionalIterator2 __m2 = __l2;
996 while (true)
997 {
998 if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern)
999 return __m1;
1000 if (__m1 == __first1) // Otherwise if source exhaused, pattern not found
1001 return __last1;
1002 if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1
1003 {
1004 break;
1005 } // else there is a match, check next elements
1006 }
1007 }
1008}
1009
1010template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1011_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1
1012__find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1013 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1014 random_access_iterator_tag, random_access_iterator_tag)
1015{
1016 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern
1017 typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;
1018 if (__len2 == 0)
1019 return __last1;
1020 typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;
1021 if (__len1 < __len2)
1022 return __last1;
1023 const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here
1024 _RandomAccessIterator1 __l1 = __last1;
1025 _RandomAccessIterator2 __l2 = __last2;
1026 --__l2;
1027 while (true)
1028 {
1029 while (true)
1030 {
1031 if (__s == __l1)
1032 return __last1;
1033 if (__pred(*--__l1, *__l2))
1034 break;
1035 }
1036 _RandomAccessIterator1 __m1 = __l1;
1037 _RandomAccessIterator2 __m2 = __l2;
1038 while (true)
1039 {
1040 if (__m2 == __first2)
1041 return __m1;
1042 // no need to check range on __m1 because __s guarantees we have enough source
1043 if (!__pred(*--__m1, *--__m2))
1044 {
1045 break;
1046 }
1047 }
1048 }
1049}
1050
1051template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1052_LIBCPP_NODISCARD_EXT inline
1053_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1054_ForwardIterator1
1055find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1056 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1057{
1058 return _VSTD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type>
1059 (__first1, __last1, __first2, __last2, __pred,
1060 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1061 typename iterator_traits<_ForwardIterator2>::iterator_category());
1062}
1063
1064template <class _ForwardIterator1, class _ForwardIterator2>
1065_LIBCPP_NODISCARD_EXT inline
1066_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1067_ForwardIterator1
1068find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1069 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1070{
1071 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1072 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1073 return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1074}
1075
1076// find_first_of
1077
1078template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1079_LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator1
1080__find_first_of_ce(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1081 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1082{
1083 for (; __first1 != __last1; ++__first1)
1084 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1085 if (__pred(*__first1, *__j))
1086 return __first1;
1087 return __last1;
1088}
1089
1090
1091template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1092_LIBCPP_NODISCARD_EXT inline
1093_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1094_ForwardIterator1
1095find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1096 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1097{
1098 return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred);
1099}
1100
1101template <class _ForwardIterator1, class _ForwardIterator2>
1102_LIBCPP_NODISCARD_EXT inline
1103_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1104_ForwardIterator1
1105find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1106 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1107{
1108 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1109 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1110 return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1111}
1112
1113// adjacent_find
1114
1115template <class _ForwardIterator, class _BinaryPredicate>
1116_LIBCPP_NODISCARD_EXT inline
1117_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1118_ForwardIterator
1119adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
1120{
1121 if (__first != __last)
1122 {
1123 _ForwardIterator __i = __first;
1124 while (++__i != __last)
1125 {
1126 if (__pred(*__first, *__i))
1127 return __first;
1128 __first = __i;
1129 }
1130 }
1131 return __last;
1132}
1133
1134template <class _ForwardIterator>
1135_LIBCPP_NODISCARD_EXT inline
1136_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1137_ForwardIterator
1138adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
1139{
1140 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1141 return _VSTD::adjacent_find(__first, __last, __equal_to<__v>());
1142}
1143
1144// count
1145
1146template <class _InputIterator, class _Tp>
1147_LIBCPP_NODISCARD_EXT inline
1148_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1149typename iterator_traits<_InputIterator>::difference_type
1150count(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
1151{
1152 typename iterator_traits<_InputIterator>::difference_type __r(0);
1153 for (; __first != __last; ++__first)
1154 if (*__first == __value_)
1155 ++__r;
1156 return __r;
1157}
1158
1159// count_if
1160
1161template <class _InputIterator, class _Predicate>
1162_LIBCPP_NODISCARD_EXT inline
1163_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1164typename iterator_traits<_InputIterator>::difference_type
1165count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
1166{
1167 typename iterator_traits<_InputIterator>::difference_type __r(0);
1168 for (; __first != __last; ++__first)
1169 if (__pred(*__first))
1170 ++__r;
1171 return __r;
1172}
1173
1174// mismatch
1175
1176template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1177_LIBCPP_NODISCARD_EXT inline
1178_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1179pair<_InputIterator1, _InputIterator2>
1180mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1181 _InputIterator2 __first2, _BinaryPredicate __pred)
1182{
1183 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1184 if (!__pred(*__first1, *__first2))
1185 break;
1186 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1187}
1188
1189template <class _InputIterator1, class _InputIterator2>
1190_LIBCPP_NODISCARD_EXT inline
1191_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1192pair<_InputIterator1, _InputIterator2>
1193mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1194{
1195 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1196 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1197 return _VSTD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1198}
1199
1200#if _LIBCPP_STD_VER > 11
1201template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1202_LIBCPP_NODISCARD_EXT inline
1203_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1204pair<_InputIterator1, _InputIterator2>
1205mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1206 _InputIterator2 __first2, _InputIterator2 __last2,
1207 _BinaryPredicate __pred)
1208{
1209 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1210 if (!__pred(*__first1, *__first2))
1211 break;
1212 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1213}
1214
1215template <class _InputIterator1, class _InputIterator2>
1216_LIBCPP_NODISCARD_EXT inline
1217_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1218pair<_InputIterator1, _InputIterator2>
1219mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1220 _InputIterator2 __first2, _InputIterator2 __last2)
1221{
1222 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1223 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1224 return _VSTD::mismatch(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1225}
1226#endif
1227
1228// equal
1229
1230template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1231_LIBCPP_NODISCARD_EXT inline
1232_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1233bool
1234equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred)
1235{
1236 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1237 if (!__pred(*__first1, *__first2))
1238 return false;
1239 return true;
1240}
1241
1242template <class _InputIterator1, class _InputIterator2>
1243_LIBCPP_NODISCARD_EXT inline
1244_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1245bool
1246equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1247{
1248 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1249 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1250 return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1251}
1252
1253#if _LIBCPP_STD_VER > 11
1254template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2>
1255inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1256bool
1257__equal(_InputIterator1 __first1, _InputIterator1 __last1,
1258 _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred,
1259 input_iterator_tag, input_iterator_tag )
1260{
1261 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1262 if (!__pred(*__first1, *__first2))
1263 return false;
1264 return __first1 == __last1 && __first2 == __last2;
1265}
1266
1267template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1268inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1269bool
1270__equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
1271 _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
1272 random_access_iterator_tag, random_access_iterator_tag )
1273{
1274 if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
1275 return false;
1276 return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2,
1277 typename add_lvalue_reference<_BinaryPredicate>::type>
1278 (__first1, __last1, __first2, __pred );
1279}
1280
1281template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1282_LIBCPP_NODISCARD_EXT inline
1283_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1284bool
1285equal(_InputIterator1 __first1, _InputIterator1 __last1,
1286 _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred )
1287{
1288 return _VSTD::__equal<typename add_lvalue_reference<_BinaryPredicate>::type>
1289 (__first1, __last1, __first2, __last2, __pred,
1290 typename iterator_traits<_InputIterator1>::iterator_category(),
1291 typename iterator_traits<_InputIterator2>::iterator_category());
1292}
1293
1294template <class _InputIterator1, class _InputIterator2>
1295_LIBCPP_NODISCARD_EXT inline
1296_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1297bool
1298equal(_InputIterator1 __first1, _InputIterator1 __last1,
1299 _InputIterator2 __first2, _InputIterator2 __last2)
1300{
1301 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1302 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1303 return _VSTD::__equal(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(),
1304 typename iterator_traits<_InputIterator1>::iterator_category(),
1305 typename iterator_traits<_InputIterator2>::iterator_category());
1306}
1307#endif
1308
1309// is_permutation
1310
1311template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1312_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
1313is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1314 _ForwardIterator2 __first2, _BinaryPredicate __pred)
1315{
1316// shorten sequences as much as possible by lopping of any equal prefix
1317 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1318 if (!__pred(*__first1, *__first2))
1319 break;
1320 if (__first1 == __last1)
1321 return true;
1322
1323// __first1 != __last1 && *__first1 != *__first2
1324 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1325 _D1 __l1 = _VSTD::distance(__first1, __last1);
1326 if (__l1 == _D1(1))
1327 return false;
1328 _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1);
1329 // For each element in [f1, l1) see if there are the same number of
1330 // equal elements in [f2, l2)
1331 for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
1332 {
1333 // Have we already counted the number of *__i in [f1, l1)?
1334 _ForwardIterator1 __match = __first1;
1335 for (; __match != __i; ++__match)
1336 if (__pred(*__match, *__i))
1337 break;
1338 if (__match == __i) {
1339 // Count number of *__i in [f2, l2)
1340 _D1 __c2 = 0;
1341 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1342 if (__pred(*__i, *__j))
1343 ++__c2;
1344 if (__c2 == 0)
1345 return false;
1346 // Count number of *__i in [__i, l1) (we can start with 1)
1347 _D1 __c1 = 1;
1348 for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
1349 if (__pred(*__i, *__j))
1350 ++__c1;
1351 if (__c1 != __c2)
1352 return false;
1353 }
1354 }
1355 return true;
1356}
1357
1358template<class _ForwardIterator1, class _ForwardIterator2>
1359_LIBCPP_NODISCARD_EXT inline
1360_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1361bool
1362is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1363 _ForwardIterator2 __first2)
1364{
1365 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1366 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1367 return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1368}
1369
1370#if _LIBCPP_STD_VER > 11
1371template<class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
1372_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
1373__is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1374 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1375 _BinaryPredicate __pred,
1376 forward_iterator_tag, forward_iterator_tag )
1377{
1378// shorten sequences as much as possible by lopping of any equal prefix
1379 for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2)
1380 if (!__pred(*__first1, *__first2))
1381 break;
1382 if (__first1 == __last1)
1383 return __first2 == __last2;
1384 else if (__first2 == __last2)
1385 return false;
1386
1387 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1;
1388 _D1 __l1 = _VSTD::distance(__first1, __last1);
1389
1390 typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2;
1391 _D2 __l2 = _VSTD::distance(__first2, __last2);
1392 if (__l1 != __l2)
1393 return false;
1394
1395 // For each element in [f1, l1) see if there are the same number of
1396 // equal elements in [f2, l2)
1397 for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
1398 {
1399 // Have we already counted the number of *__i in [f1, l1)?
1400 _ForwardIterator1 __match = __first1;
1401 for (; __match != __i; ++__match)
1402 if (__pred(*__match, *__i))
1403 break;
1404 if (__match == __i) {
1405 // Count number of *__i in [f2, l2)
1406 _D1 __c2 = 0;
1407 for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
1408 if (__pred(*__i, *__j))
1409 ++__c2;
1410 if (__c2 == 0)
1411 return false;
1412 // Count number of *__i in [__i, l1) (we can start with 1)
1413 _D1 __c1 = 1;
1414 for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j)
1415 if (__pred(*__i, *__j))
1416 ++__c1;
1417 if (__c1 != __c2)
1418 return false;
1419 }
1420 }
1421 return true;
1422}
1423
1424template<class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1425_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
1426__is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1,
1427 _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2,
1428 _BinaryPredicate __pred,
1429 random_access_iterator_tag, random_access_iterator_tag )
1430{
1431 if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
1432 return false;
1433 return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2,
1434 typename add_lvalue_reference<_BinaryPredicate>::type>
1435 (__first1, __last1, __first2, __pred );
1436}
1437
1438template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1439_LIBCPP_NODISCARD_EXT inline
1440_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1441bool
1442is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1443 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1444 _BinaryPredicate __pred )
1445{
1446 return _VSTD::__is_permutation<typename add_lvalue_reference<_BinaryPredicate>::type>
1447 (__first1, __last1, __first2, __last2, __pred,
1448 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1449 typename iterator_traits<_ForwardIterator2>::iterator_category());
1450}
1451
1452template<class _ForwardIterator1, class _ForwardIterator2>
1453_LIBCPP_NODISCARD_EXT inline
1454_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1455bool
1456is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1457 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1458{
1459 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1460 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1461 return _VSTD::__is_permutation(__first1, __last1, __first2, __last2,
1462 __equal_to<__v1, __v2>(),
1463 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1464 typename iterator_traits<_ForwardIterator2>::iterator_category());
1465}
1466#endif
1467
1468// search
1469// __search is in <functional>
1470
1471template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1472_LIBCPP_NODISCARD_EXT inline
1473_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1474_ForwardIterator1
1475search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1476 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1477{
1478 return _VSTD::__search<typename add_lvalue_reference<_BinaryPredicate>::type>
1479 (__first1, __last1, __first2, __last2, __pred,
1480 typename iterator_traits<_ForwardIterator1>::iterator_category(),
1481 typename iterator_traits<_ForwardIterator2>::iterator_category())
1482 .first;
1483}
1484
1485template <class _ForwardIterator1, class _ForwardIterator2>
1486_LIBCPP_NODISCARD_EXT inline
1487_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1488_ForwardIterator1
1489search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1490 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1491{
1492 typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;
1493 typedef typename iterator_traits<_ForwardIterator2>::value_type __v2;
1494 return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
1495}
1496
1497
1498#if _LIBCPP_STD_VER > 14
1499template <class _ForwardIterator, class _Searcher>
1500_LIBCPP_NODISCARD_EXT _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1501_ForwardIterator search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher &__s)
1502{ return __s(__f, __l).first; }
1503#endif
1504
1505// search_n
1506
1507template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp>
1508_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
1509__search_n(_ForwardIterator __first, _ForwardIterator __last,
1510 _Size __count, const _Tp& __value_, _BinaryPredicate __pred, forward_iterator_tag)
1511{
1512 if (__count <= 0)
1513 return __first;
1514 while (true)
1515 {
1516 // Find first element in sequence that matchs __value_, with a mininum of loop checks
1517 while (true)
1518 {
1519 if (__first == __last) // return __last if no element matches __value_
1520 return __last;
1521 if (__pred(*__first, __value_))
1522 break;
1523 ++__first;
1524 }
1525 // *__first matches __value_, now match elements after here
1526 _ForwardIterator __m = __first;
1527 _Size __c(0);
1528 while (true)
1529 {
1530 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1531 return __first;
1532 if (++__m == __last) // Otherwise if source exhaused, pattern not found
1533 return __last;
1534 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1535 {
1536 __first = __m;
1537 ++__first;
1538 break;
1539 } // else there is a match, check next elements
1540 }
1541 }
1542}
1543
1544template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp>
1545_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
1546__search_n(_RandomAccessIterator __first, _RandomAccessIterator __last,
1547 _Size __count, const _Tp& __value_, _BinaryPredicate __pred, random_access_iterator_tag)
1548{
1549 if (__count <= 0)
1550 return __first;
1551 _Size __len = static_cast<_Size>(__last - __first);
1552 if (__len < __count)
1553 return __last;
1554 const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here
1555 while (true)
1556 {
1557 // Find first element in sequence that matchs __value_, with a mininum of loop checks
1558 while (true)
1559 {
1560 if (__first >= __s) // return __last if no element matches __value_
1561 return __last;
1562 if (__pred(*__first, __value_))
1563 break;
1564 ++__first;
1565 }
1566 // *__first matches __value_, now match elements after here
1567 _RandomAccessIterator __m = __first;
1568 _Size __c(0);
1569 while (true)
1570 {
1571 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1572 return __first;
1573 ++__m; // no need to check range on __m because __s guarantees we have enough source
1574 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1575 {
1576 __first = __m;
1577 ++__first;
1578 break;
1579 } // else there is a match, check next elements
1580 }
1581 }
1582}
1583
1584template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
1585_LIBCPP_NODISCARD_EXT inline
1586_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1587_ForwardIterator
1588search_n(_ForwardIterator __first, _ForwardIterator __last,
1589 _Size __count, const _Tp& __value_, _BinaryPredicate __pred)
1590{
1591 return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>
1592 (__first, __last, __convert_to_integral(__count), __value_, __pred,
1593 typename iterator_traits<_ForwardIterator>::iterator_category());
1594}
1595
1596template <class _ForwardIterator, class _Size, class _Tp>
1597_LIBCPP_NODISCARD_EXT inline
1598_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1599_ForwardIterator
1600search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
1601{
1602 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1603 return _VSTD::search_n(__first, __last, __convert_to_integral(__count),
1604 __value_, __equal_to<__v, _Tp>());
1605}
1606
1607// copy
1608template <class _Iter>
1609inline _LIBCPP_INLINE_VISIBILITY
1610_Iter
1611__unwrap_iter(_Iter __i)
1612{
1613 return __i;
1614}
1615
1616template <class _Tp>
1617inline _LIBCPP_INLINE_VISIBILITY
1618typename enable_if
1619<
1620 is_trivially_copy_assignable<_Tp>::value,
1621 _Tp*
1622>::type
1623__unwrap_iter(move_iterator<_Tp*> __i)
1624{
1625 return __i.base();
1626}
1627
1628#if _LIBCPP_DEBUG_LEVEL < 2
1629
1630template <class _Tp>
1631inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
1632typename enable_if
1633<
1634 is_trivially_copy_assignable<_Tp>::value,
1635 _Tp*
1636>::type
1637__unwrap_iter(__wrap_iter<_Tp*> __i)
1638{
1639 return __i.base();
1640}
1641
1642template <class _Tp>
1643inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
1644typename enable_if
1645<
1646 is_trivially_copy_assignable<_Tp>::value,
1647 const _Tp*
1648>::type
1649__unwrap_iter(__wrap_iter<const _Tp*> __i)
1650{
1651 return __i.base();
1652}
1653
1654#else
1655
1656template <class _Tp>
1657inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
1658typename enable_if
1659<
1660 is_trivially_copy_assignable<_Tp>::value,
1661 __wrap_iter<_Tp*>
1662>::type
1663__unwrap_iter(__wrap_iter<_Tp*> __i)
1664{
1665 return __i;
1666}
1667
1668#endif // _LIBCPP_DEBUG_LEVEL < 2
1669
1670template <class _InputIterator, class _OutputIterator>
1671inline _LIBCPP_INLINE_VISIBILITY
1672_OutputIterator
1673__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1674{
1675 for (; __first != __last; ++__first, (void) ++__result)
1676 *__result = *__first;
1677 return __result;
1678}
1679
1680template <class _Tp, class _Up>
1681inline _LIBCPP_INLINE_VISIBILITY
1682typename enable_if
1683<
1684 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1685 is_trivially_copy_assignable<_Up>::value,
1686 _Up*
1687>::type
1688__copy(_Tp* __first, _Tp* __last, _Up* __result)
1689{
1690 const size_t __n = static_cast<size_t>(__last - __first);
1691 if (__n > 0)
1692 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1693 return __result + __n;
1694}
1695
1696template <class _InputIterator, class _OutputIterator>
1697inline _LIBCPP_INLINE_VISIBILITY
1698_OutputIterator
1699copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1700{
1701 return _VSTD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1702}
1703
1704// copy_backward
1705
1706template <class _BidirectionalIterator, class _OutputIterator>
1707inline _LIBCPP_INLINE_VISIBILITY
1708_OutputIterator
1709__copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
1710{
1711 while (__first != __last)
1712 *--__result = *--__last;
1713 return __result;
1714}
1715
1716template <class _Tp, class _Up>
1717inline _LIBCPP_INLINE_VISIBILITY
1718typename enable_if
1719<
1720 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1721 is_trivially_copy_assignable<_Up>::value,
1722 _Up*
1723>::type
1724__copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
1725{
1726 const size_t __n = static_cast<size_t>(__last - __first);
1727 if (__n > 0)
1728 {
1729 __result -= __n;
1730 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1731 }
1732 return __result;
1733}
1734
1735template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1736inline _LIBCPP_INLINE_VISIBILITY
1737_BidirectionalIterator2
1738copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1739 _BidirectionalIterator2 __result)
1740{
1741 return _VSTD::__copy_backward(__unwrap_iter(__first),
1742 __unwrap_iter(__last),
1743 __unwrap_iter(__result));
1744}
1745
1746// copy_if
1747
1748template<class _InputIterator, class _OutputIterator, class _Predicate>
1749inline _LIBCPP_INLINE_VISIBILITY
1750_OutputIterator
1751copy_if(_InputIterator __first, _InputIterator __last,
1752 _OutputIterator __result, _Predicate __pred)
1753{
1754 for (; __first != __last; ++__first)
1755 {
1756 if (__pred(*__first))
1757 {
1758 *__result = *__first;
1759 ++__result;
1760 }
1761 }
1762 return __result;
1763}
1764
1765// copy_n
1766
1767template<class _InputIterator, class _Size, class _OutputIterator>
1768inline _LIBCPP_INLINE_VISIBILITY
1769typename enable_if
1770<
1771 __is_input_iterator<_InputIterator>::value &&
1772 !__is_random_access_iterator<_InputIterator>::value,
1773 _OutputIterator
1774>::type
1775copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1776{
1777 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
1778 _IntegralSize __n = __orig_n;
1779 if (__n > 0)
1780 {
1781 *__result = *__first;
1782 ++__result;
1783 for (--__n; __n > 0; --__n)
1784 {
1785 ++__first;
1786 *__result = *__first;
1787 ++__result;
1788 }
1789 }
1790 return __result;
1791}
1792
1793template<class _InputIterator, class _Size, class _OutputIterator>
1794inline _LIBCPP_INLINE_VISIBILITY
1795typename enable_if
1796<
1797 __is_random_access_iterator<_InputIterator>::value,
1798 _OutputIterator
1799>::type
1800copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1801{
1802 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
1803 _IntegralSize __n = __orig_n;
1804 return _VSTD::copy(__first, __first + __n, __result);
1805}
1806
1807// move
1808
1809template <class _InputIterator, class _OutputIterator>
1810inline _LIBCPP_INLINE_VISIBILITY
1811_OutputIterator
1812__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1813{
1814 for (; __first != __last; ++__first, (void) ++__result)
1815 *__result = _VSTD::move(*__first);
1816 return __result;
1817}
1818
1819template <class _Tp, class _Up>
1820inline _LIBCPP_INLINE_VISIBILITY
1821typename enable_if
1822<
1823 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1824 is_trivially_copy_assignable<_Up>::value,
1825 _Up*
1826>::type
1827__move(_Tp* __first, _Tp* __last, _Up* __result)
1828{
1829 const size_t __n = static_cast<size_t>(__last - __first);
1830 if (__n > 0)
1831 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1832 return __result + __n;
1833}
1834
1835template <class _InputIterator, class _OutputIterator>
1836inline _LIBCPP_INLINE_VISIBILITY
1837_OutputIterator
1838move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1839{
1840 return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1841}
1842
1843// move_backward
1844
1845template <class _InputIterator, class _OutputIterator>
1846inline _LIBCPP_INLINE_VISIBILITY
1847_OutputIterator
1848__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1849{
1850 while (__first != __last)
1851 *--__result = _VSTD::move(*--__last);
1852 return __result;
1853}
1854
1855template <class _Tp, class _Up>
1856inline _LIBCPP_INLINE_VISIBILITY
1857typename enable_if
1858<
1859 is_same<typename remove_const<_Tp>::type, _Up>::value &&
1860 is_trivially_copy_assignable<_Up>::value,
1861 _Up*
1862>::type
1863__move_backward(_Tp* __first, _Tp* __last, _Up* __result)
1864{
1865 const size_t __n = static_cast<size_t>(__last - __first);
1866 if (__n > 0)
1867 {
1868 __result -= __n;
1869 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1870 }
1871 return __result;
1872}
1873
1874template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1875inline _LIBCPP_INLINE_VISIBILITY
1876_BidirectionalIterator2
1877move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1878 _BidirectionalIterator2 __result)
1879{
1880 return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1881}
1882
1883// iter_swap
1884
1885// moved to <type_traits> for better swap / noexcept support
1886
1887// transform
1888
1889template <class _InputIterator, class _OutputIterator, class _UnaryOperation>
1890inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1891_OutputIterator
1892transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op)
1893{
1894 for (; __first != __last; ++__first, (void) ++__result)
1895 *__result = __op(*__first);
1896 return __result;
1897}
1898
1899template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation>
1900inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1901_OutputIterator
1902transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
1903 _OutputIterator __result, _BinaryOperation __binary_op)
1904{
1905 for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result)
1906 *__result = __binary_op(*__first1, *__first2);
1907 return __result;
1908}
1909
1910// replace
1911
1912template <class _ForwardIterator, class _Tp>
1913inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1914void
1915replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value)
1916{
1917 for (; __first != __last; ++__first)
1918 if (*__first == __old_value)
1919 *__first = __new_value;
1920}
1921
1922// replace_if
1923
1924template <class _ForwardIterator, class _Predicate, class _Tp>
1925inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1926void
1927replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value)
1928{
1929 for (; __first != __last; ++__first)
1930 if (__pred(*__first))
1931 *__first = __new_value;
1932}
1933
1934// replace_copy
1935
1936template <class _InputIterator, class _OutputIterator, class _Tp>
1937inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1938_OutputIterator
1939replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1940 const _Tp& __old_value, const _Tp& __new_value)
1941{
1942 for (; __first != __last; ++__first, (void) ++__result)
1943 if (*__first == __old_value)
1944 *__result = __new_value;
1945 else
1946 *__result = *__first;
1947 return __result;
1948}
1949
1950// replace_copy_if
1951
1952template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp>
1953inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1954_OutputIterator
1955replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1956 _Predicate __pred, const _Tp& __new_value)
1957{
1958 for (; __first != __last; ++__first, (void) ++__result)
1959 if (__pred(*__first))
1960 *__result = __new_value;
1961 else
1962 *__result = *__first;
1963 return __result;
1964}
1965
1966// fill_n
1967
1968template <class _OutputIterator, class _Size, class _Tp>
1969inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1970_OutputIterator
1971__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
1972{
1973 for (; __n > 0; ++__first, (void) --__n)
1974 *__first = __value_;
1975 return __first;
1976}
1977
1978template <class _OutputIterator, class _Size, class _Tp>
1979inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1980_OutputIterator
1981fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
1982{
1983 return _VSTD::__fill_n(__first, __convert_to_integral(__n), __value_);
1984}
1985
1986// fill
1987
1988template <class _ForwardIterator, class _Tp>
1989inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1990void
1991__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
1992{
1993 for (; __first != __last; ++__first)
1994 *__first = __value_;
1995}
1996
1997template <class _RandomAccessIterator, class _Tp>
1998inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1999void
2000__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag)
2001{
2002 _VSTD::fill_n(__first, __last - __first, __value_);
2003}
2004
2005template <class _ForwardIterator, class _Tp>
2006inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2007void
2008fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2009{
2010 _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category());
2011}
2012
2013// generate
2014
2015template <class _ForwardIterator, class _Generator>
2016inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2017void
2018generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
2019{
2020 for (; __first != __last; ++__first)
2021 *__first = __gen();
2022}
2023
2024// generate_n
2025
2026template <class _OutputIterator, class _Size, class _Generator>
2027inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2028_OutputIterator
2029generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen)
2030{
2031 typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
2032 _IntegralSize __n = __orig_n;
2033 for (; __n > 0; ++__first, (void) --__n)
2034 *__first = __gen();
2035 return __first;
2036}
2037
2038// remove
2039
2040template <class _ForwardIterator, class _Tp>
2041_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
2042remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2043{
2044 __first = _VSTD::find(__first, __last, __value_);
2045 if (__first != __last)
2046 {
2047 _ForwardIterator __i = __first;
2048 while (++__i != __last)
2049 {
2050 if (!(*__i == __value_))
2051 {
2052 *__first = _VSTD::move(*__i);
2053 ++__first;
2054 }
2055 }
2056 }
2057 return __first;
2058}
2059
2060// remove_if
2061
2062template <class _ForwardIterator, class _Predicate>
2063_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
2064remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2065{
2066 __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
2067 (__first, __last, __pred);
2068 if (__first != __last)
2069 {
2070 _ForwardIterator __i = __first;
2071 while (++__i != __last)
2072 {
2073 if (!__pred(*__i))
2074 {
2075 *__first = _VSTD::move(*__i);
2076 ++__first;
2077 }
2078 }
2079 }
2080 return __first;
2081}
2082
2083// remove_copy
2084
2085template <class _InputIterator, class _OutputIterator, class _Tp>
2086inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2087_OutputIterator
2088remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_)
2089{
2090 for (; __first != __last; ++__first)
2091 {
2092 if (!(*__first == __value_))
2093 {
2094 *__result = *__first;
2095 ++__result;
2096 }
2097 }
2098 return __result;
2099}
2100
2101// remove_copy_if
2102
2103template <class _InputIterator, class _OutputIterator, class _Predicate>
2104inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2105_OutputIterator
2106remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
2107{
2108 for (; __first != __last; ++__first)
2109 {
2110 if (!__pred(*__first))
2111 {
2112 *__result = *__first;
2113 ++__result;
2114 }
2115 }
2116 return __result;
2117}
2118
2119// unique
2120
2121template <class _ForwardIterator, class _BinaryPredicate>
2122_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
2123unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
2124{
2125 __first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type>
2126 (__first, __last, __pred);
2127 if (__first != __last)
2128 {
2129 // ... a a ? ...
2130 // f i
2131 _ForwardIterator __i = __first;
2132 for (++__i; ++__i != __last;)
2133 if (!__pred(*__first, *__i))
2134 *++__first = _VSTD::move(*__i);
2135 ++__first;
2136 }
2137 return __first;
2138}
2139
2140template <class _ForwardIterator>
2141_LIBCPP_NODISCARD_EXT inline
2142_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2143_ForwardIterator
2144unique(_ForwardIterator __first, _ForwardIterator __last)
2145{
2146 typedef typename iterator_traits<_ForwardIterator>::value_type __v;
2147 return _VSTD::unique(__first, __last, __equal_to<__v>());
2148}
2149
2150// unique_copy
2151
2152template <class _BinaryPredicate, class _InputIterator, class _OutputIterator>
2153_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
2154__unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2155 input_iterator_tag, output_iterator_tag)
2156{
2157 if (__first != __last)
2158 {
2159 typename iterator_traits<_InputIterator>::value_type __t(*__first);
2160 *__result = __t;
2161 ++__result;
2162 while (++__first != __last)
2163 {
2164 if (!__pred(__t, *__first))
2165 {
2166 __t = *__first;
2167 *__result = __t;
2168 ++__result;
2169 }
2170 }
2171 }
2172 return __result;
2173}
2174
2175template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator>
2176_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
2177__unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2178 forward_iterator_tag, output_iterator_tag)
2179{
2180 if (__first != __last)
2181 {
2182 _ForwardIterator __i = __first;
2183 *__result = *__i;
2184 ++__result;
2185 while (++__first != __last)
2186 {
2187 if (!__pred(*__i, *__first))
2188 {
2189 *__result = *__first;
2190 ++__result;
2191 __i = __first;
2192 }
2193 }
2194 }
2195 return __result;
2196}
2197
2198template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator>
2199_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
2200__unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred,
2201 input_iterator_tag, forward_iterator_tag)
2202{
2203 if (__first != __last)
2204 {
2205 *__result = *__first;
2206 while (++__first != __last)
2207 if (!__pred(*__result, *__first))
2208 *++__result = *__first;
2209 ++__result;
2210 }
2211 return __result;
2212}
2213
2214template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
2215inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2216_OutputIterator
2217unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred)
2218{
2219 return _VSTD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type>
2220 (__first, __last, __result, __pred,
2221 typename iterator_traits<_InputIterator>::iterator_category(),
2222 typename iterator_traits<_OutputIterator>::iterator_category());
2223}
2224
2225template <class _InputIterator, class _OutputIterator>
2226inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2227_OutputIterator
2228unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
2229{
2230 typedef typename iterator_traits<_InputIterator>::value_type __v;
2231 return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());
2232}
2233
2234// reverse
2235
2236template <class _BidirectionalIterator>
2237inline _LIBCPP_INLINE_VISIBILITY
2238void
2239__reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
2240{
2241 while (__first != __last)
2242 {
2243 if (__first == --__last)
2244 break;
2245 _VSTD::iter_swap(__first, __last);
2246 ++__first;
2247 }
2248}
2249
2250template <class _RandomAccessIterator>
2251inline _LIBCPP_INLINE_VISIBILITY
2252void
2253__reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
2254{
2255 if (__first != __last)
2256 for (; __first < --__last; ++__first)
2257 _VSTD::iter_swap(__first, __last);
2258}
2259
2260template <class _BidirectionalIterator>
2261inline _LIBCPP_INLINE_VISIBILITY
2262void
2263reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
2264{
2265 _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());
2266}
2267
2268// reverse_copy
2269
2270template <class _BidirectionalIterator, class _OutputIterator>
2271inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2272_OutputIterator
2273reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
2274{
2275 for (; __first != __last; ++__result)
2276 *__result = *--__last;
2277 return __result;
2278}
2279
2280// rotate
2281
2282template <class _ForwardIterator>
2283_ForwardIterator
2284__rotate_left(_ForwardIterator __first, _ForwardIterator __last)
2285{
2286 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2287 value_type __tmp = _VSTD::move(*__first);
2288 _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
2289 *__lm1 = _VSTD::move(__tmp);
2290 return __lm1;
2291}
2292
2293template <class _BidirectionalIterator>
2294_BidirectionalIterator
2295__rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
2296{
2297 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
2298 _BidirectionalIterator __lm1 = _VSTD::prev(__last);
2299 value_type __tmp = _VSTD::move(*__lm1);
2300 _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
2301 *__first = _VSTD::move(__tmp);
2302 return __fp1;
2303}
2304
2305template <class _ForwardIterator>
2306_ForwardIterator
2307__rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2308{
2309 _ForwardIterator __i = __middle;
2310 while (true)
2311 {
2312 swap(*__first, *__i);
2313 ++__first;
2314 if (++__i == __last)
2315 break;
2316 if (__first == __middle)
2317 __middle = __i;
2318 }
2319 _ForwardIterator __r = __first;
2320 if (__first != __middle)
2321 {
2322 __i = __middle;
2323 while (true)
2324 {
2325 swap(*__first, *__i);
2326 ++__first;
2327 if (++__i == __last)
2328 {
2329 if (__first == __middle)
2330 break;
2331 __i = __middle;
2332 }
2333 else if (__first == __middle)
2334 __middle = __i;
2335 }
2336 }
2337 return __r;
2338}
2339
2340template<typename _Integral>
2341inline _LIBCPP_INLINE_VISIBILITY
2342_Integral
2343__algo_gcd(_Integral __x, _Integral __y)
2344{
2345 do
2346 {
2347 _Integral __t = __x % __y;
2348 __x = __y;
2349 __y = __t;
2350 } while (__y);
2351 return __x;
2352}
2353
2354template<typename _RandomAccessIterator>
2355_RandomAccessIterator
2356__rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
2357{
2358 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2359 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
2360
2361 const difference_type __m1 = __middle - __first;
2362 const difference_type __m2 = __last - __middle;
2363 if (__m1 == __m2)
2364 {
2365 _VSTD::swap_ranges(__first, __middle, __middle);
2366 return __middle;
2367 }
2368 const difference_type __g = _VSTD::__algo_gcd(__m1, __m2);
2369 for (_RandomAccessIterator __p = __first + __g; __p != __first;)
2370 {
2371 value_type __t(_VSTD::move(*--__p));
2372 _RandomAccessIterator __p1 = __p;
2373 _RandomAccessIterator __p2 = __p1 + __m1;
2374 do
2375 {
2376 *__p1 = _VSTD::move(*__p2);
2377 __p1 = __p2;
2378 const difference_type __d = __last - __p2;
2379 if (__m1 < __d)
2380 __p2 += __m1;
2381 else
2382 __p2 = __first + (__m1 - __d);
2383 } while (__p2 != __p);
2384 *__p1 = _VSTD::move(__t);
2385 }
2386 return __first + __m2;
2387}
2388
2389template <class _ForwardIterator>
2390inline _LIBCPP_INLINE_VISIBILITY
2391_ForwardIterator
2392__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
2393 _VSTD::forward_iterator_tag)
2394{
2395 typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type;
2396 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2397 {
2398 if (_VSTD::next(__first) == __middle)
2399 return _VSTD::__rotate_left(__first, __last);
2400 }
2401 return _VSTD::__rotate_forward(__first, __middle, __last);
2402}
2403
2404template <class _BidirectionalIterator>
2405inline _LIBCPP_INLINE_VISIBILITY
2406_BidirectionalIterator
2407__rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
2408 _VSTD::bidirectional_iterator_tag)
2409{
2410 typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type;
2411 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2412 {
2413 if (_VSTD::next(__first) == __middle)
2414 return _VSTD::__rotate_left(__first, __last);
2415 if (_VSTD::next(__middle) == __last)
2416 return _VSTD::__rotate_right(__first, __last);
2417 }
2418 return _VSTD::__rotate_forward(__first, __middle, __last);
2419}
2420
2421template <class _RandomAccessIterator>
2422inline _LIBCPP_INLINE_VISIBILITY
2423_RandomAccessIterator
2424__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
2425 _VSTD::random_access_iterator_tag)
2426{
2427 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
2428 if (_VSTD::is_trivially_move_assignable<value_type>::value)
2429 {
2430 if (_VSTD::next(__first) == __middle)
2431 return _VSTD::__rotate_left(__first, __last);
2432 if (_VSTD::next(__middle) == __last)
2433 return _VSTD::__rotate_right(__first, __last);
2434 return _VSTD::__rotate_gcd(__first, __middle, __last);
2435 }
2436 return _VSTD::__rotate_forward(__first, __middle, __last);
2437}
2438
2439template <class _ForwardIterator>
2440inline _LIBCPP_INLINE_VISIBILITY
2441_ForwardIterator
2442rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2443{
2444 if (__first == __middle)
2445 return __last;
2446 if (__middle == __last)
2447 return __first;
2448 return _VSTD::__rotate(__first, __middle, __last,
2449 typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());
2450}
2451
2452// rotate_copy
2453
2454template <class _ForwardIterator, class _OutputIterator>
2455inline _LIBCPP_INLINE_VISIBILITY
2456_OutputIterator
2457rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
2458{
2459 return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));
2460}
2461
2462// min_element
2463
2464template <class _ForwardIterator, class _Compare>
2465_LIBCPP_NODISCARD_EXT inline
2466_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2467_ForwardIterator
2468min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2469{
2470 static_assert(__is_forward_iterator<_ForwardIterator>::value,
2471 "std::min_element requires a ForwardIterator");
2472 if (__first != __last)
2473 {
2474 _ForwardIterator __i = __first;
2475 while (++__i != __last)
2476 if (__comp(*__i, *__first))
2477 __first = __i;
2478 }
2479 return __first;
2480}
2481
2482template <class _ForwardIterator>
2483_LIBCPP_NODISCARD_EXT inline
2484_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2485_ForwardIterator
2486min_element(_ForwardIterator __first, _ForwardIterator __last)
2487{
2488 return _VSTD::min_element(__first, __last,
2489 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2490}
2491
2492// min
2493
2494template <class _Tp, class _Compare>
2495_LIBCPP_NODISCARD_EXT inline
2496_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2497const _Tp&
2498min(const _Tp& __a, const _Tp& __b, _Compare __comp)
2499{
2500 return __comp(__b, __a) ? __b : __a;
2501}
2502
2503template <class _Tp>
2504_LIBCPP_NODISCARD_EXT inline
2505_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2506const _Tp&
2507min(const _Tp& __a, const _Tp& __b)
2508{
2509 return _VSTD::min(__a, __b, __less<_Tp>());
2510}
2511
2512#ifndef _LIBCPP_CXX03_LANG
2513
2514template<class _Tp, class _Compare>
2515_LIBCPP_NODISCARD_EXT inline
2516_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2517_Tp
2518min(initializer_list<_Tp> __t, _Compare __comp)
2519{
2520 return *_VSTD::min_element(__t.begin(), __t.end(), __comp);
2521}
2522
2523template<class _Tp>
2524_LIBCPP_NODISCARD_EXT inline
2525_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2526_Tp
2527min(initializer_list<_Tp> __t)
2528{
2529 return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>());
2530}
2531
2532#endif // _LIBCPP_CXX03_LANG
2533
2534// max_element
2535
2536template <class _ForwardIterator, class _Compare>
2537_LIBCPP_NODISCARD_EXT inline
2538_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2539_ForwardIterator
2540max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2541{
2542 static_assert(__is_forward_iterator<_ForwardIterator>::value,
2543 "std::max_element requires a ForwardIterator");
2544 if (__first != __last)
2545 {
2546 _ForwardIterator __i = __first;
2547 while (++__i != __last)
2548 if (__comp(*__first, *__i))
2549 __first = __i;
2550 }
2551 return __first;
2552}
2553
2554
2555template <class _ForwardIterator>
2556_LIBCPP_NODISCARD_EXT inline
2557_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2558_ForwardIterator
2559max_element(_ForwardIterator __first, _ForwardIterator __last)
2560{
2561 return _VSTD::max_element(__first, __last,
2562 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2563}
2564
2565// max
2566
2567template <class _Tp, class _Compare>
2568_LIBCPP_NODISCARD_EXT inline
2569_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2570const _Tp&
2571max(const _Tp& __a, const _Tp& __b, _Compare __comp)
2572{
2573 return __comp(__a, __b) ? __b : __a;
2574}
2575
2576template <class _Tp>
2577_LIBCPP_NODISCARD_EXT inline
2578_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2579const _Tp&
2580max(const _Tp& __a, const _Tp& __b)
2581{
2582 return _VSTD::max(__a, __b, __less<_Tp>());
2583}
2584
2585#ifndef _LIBCPP_CXX03_LANG
2586
2587template<class _Tp, class _Compare>
2588_LIBCPP_NODISCARD_EXT inline
2589_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2590_Tp
2591max(initializer_list<_Tp> __t, _Compare __comp)
2592{
2593 return *_VSTD::max_element(__t.begin(), __t.end(), __comp);
2594}
2595
2596template<class _Tp>
2597_LIBCPP_NODISCARD_EXT inline
2598_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2599_Tp
2600max(initializer_list<_Tp> __t)
2601{
2602 return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>());
2603}
2604
2605#endif // _LIBCPP_CXX03_LANG
2606
2607#if _LIBCPP_STD_VER > 14
2608// clamp
2609template<class _Tp, class _Compare>
2610_LIBCPP_NODISCARD_EXT inline
2611_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
2612const _Tp&
2613clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
2614{
2615 _LIBCPP_ASSERT(!__comp(__hi, __lo), "Bad bounds passed to std::clamp");
2616 return __comp(__v, __lo) ? __lo : __comp(__hi, __v) ? __hi : __v;
2617
2618}
2619
2620template<class _Tp>
2621_LIBCPP_NODISCARD_EXT inline
2622_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
2623const _Tp&
2624clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi)
2625{
2626 return _VSTD::clamp(__v, __lo, __hi, __less<_Tp>());
2627}
2628#endif
2629
2630// minmax_element
2631
2632template <class _ForwardIterator, class _Compare>
2633_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX11
2634std::pair<_ForwardIterator, _ForwardIterator>
2635minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2636{
2637 static_assert(__is_forward_iterator<_ForwardIterator>::value,
2638 "std::minmax_element requires a ForwardIterator");
2639 std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);
2640 if (__first != __last)
2641 {
2642 if (++__first != __last)
2643 {
2644 if (__comp(*__first, *__result.first))
2645 __result.first = __first;
2646 else
2647 __result.second = __first;
2648 while (++__first != __last)
2649 {
2650 _ForwardIterator __i = __first;
2651 if (++__first == __last)
2652 {
2653 if (__comp(*__i, *__result.first))
2654 __result.first = __i;
2655 else if (!__comp(*__i, *__result.second))
2656 __result.second = __i;
2657 break;
2658 }
2659 else
2660 {
2661 if (__comp(*__first, *__i))
2662 {
2663 if (__comp(*__first, *__result.first))
2664 __result.first = __first;
2665 if (!__comp(*__i, *__result.second))
2666 __result.second = __i;
2667 }
2668 else
2669 {
2670 if (__comp(*__i, *__result.first))
2671 __result.first = __i;
2672 if (!__comp(*__first, *__result.second))
2673 __result.second = __first;
2674 }
2675 }
2676 }
2677 }
2678 }
2679 return __result;
2680}
2681
2682template <class _ForwardIterator>
2683_LIBCPP_NODISCARD_EXT inline
2684_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2685std::pair<_ForwardIterator, _ForwardIterator>
2686minmax_element(_ForwardIterator __first, _ForwardIterator __last)
2687{
2688 return _VSTD::minmax_element(__first, __last,
2689 __less<typename iterator_traits<_ForwardIterator>::value_type>());
2690}
2691
2692// minmax
2693
2694template<class _Tp, class _Compare>
2695_LIBCPP_NODISCARD_EXT inline
2696_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2697pair<const _Tp&, const _Tp&>
2698minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
2699{
2700 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) :
2701 pair<const _Tp&, const _Tp&>(__a, __b);
2702}
2703
2704template<class _Tp>
2705_LIBCPP_NODISCARD_EXT inline
2706_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2707pair<const _Tp&, const _Tp&>
2708minmax(const _Tp& __a, const _Tp& __b)
2709{
2710 return _VSTD::minmax(__a, __b, __less<_Tp>());
2711}
2712
2713#ifndef _LIBCPP_CXX03_LANG
2714
2715template<class _Tp, class _Compare>
2716_LIBCPP_NODISCARD_EXT inline
2717_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2718pair<_Tp, _Tp>
2719minmax(initializer_list<_Tp> __t, _Compare __comp)
2720{
2721 typedef typename initializer_list<_Tp>::const_iterator _Iter;
2722 _Iter __first = __t.begin();
2723 _Iter __last = __t.end();
2724 std::pair<_Tp, _Tp> __result(*__first, *__first);
2725
2726 ++__first;
2727 if (__t.size() % 2 == 0)
2728 {
2729 if (__comp(*__first, __result.first))
2730 __result.first = *__first;
2731 else
2732 __result.second = *__first;
2733 ++__first;
2734 }
2735
2736 while (__first != __last)
2737 {
2738 _Tp __prev = *__first++;
2739 if (__comp(*__first, __prev)) {
2740 if ( __comp(*__first, __result.first)) __result.first = *__first;
2741 if (!__comp(__prev, __result.second)) __result.second = __prev;
2742 }
2743 else {
2744 if ( __comp(__prev, __result.first)) __result.first = __prev;
2745 if (!__comp(*__first, __result.second)) __result.second = *__first;
2746 }
2747
2748 __first++;
2749 }
2750 return __result;
2751}
2752
2753template<class _Tp>
2754_LIBCPP_NODISCARD_EXT inline
2755_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2756pair<_Tp, _Tp>
2757minmax(initializer_list<_Tp> __t)
2758{
2759 return _VSTD::minmax(__t, __less<_Tp>());
2760}
2761
2762#endif // _LIBCPP_CXX03_LANG
2763
2764// random_shuffle
2765
2766// __independent_bits_engine
2767
2768template <unsigned long long _Xp, size_t _Rp>
2769struct __log2_imp
2770{
2771 static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp
2772 : __log2_imp<_Xp, _Rp - 1>::value;
2773};
2774
2775template <unsigned long long _Xp>
2776struct __log2_imp<_Xp, 0>
2777{
2778 static const size_t value = 0;
2779};
2780
2781template <size_t _Rp>
2782struct __log2_imp<0, _Rp>
2783{
2784 static const size_t value = _Rp + 1;
2785};
2786
2787template <class _UIntType, _UIntType _Xp>
2788struct __log2
2789{
2790 static const size_t value = __log2_imp<_Xp,
2791 sizeof(_UIntType) * __CHAR_BIT__ - 1>::value;
2792};
2793
2794template<class _Engine, class _UIntType>
2795class __independent_bits_engine
2796{
2797public:
2798 // types
2799 typedef _UIntType result_type;
2800
2801private:
2802 typedef typename _Engine::result_type _Engine_result_type;
2803 typedef typename conditional
2804 <
2805 sizeof(_Engine_result_type) <= sizeof(result_type),
2806 result_type,
2807 _Engine_result_type
2808 >::type _Working_result_type;
2809
2810 _Engine& __e_;
2811 size_t __w_;
2812 size_t __w0_;
2813 size_t __n_;
2814 size_t __n0_;
2815 _Working_result_type __y0_;
2816 _Working_result_type __y1_;
2817 _Engine_result_type __mask0_;
2818 _Engine_result_type __mask1_;
2819
2820#ifdef _LIBCPP_CXX03_LANG
2821 static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
2822 + _Working_result_type(1);
2823#else
2824 static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()
2825 + _Working_result_type(1);
2826#endif
2827 static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value;
2828 static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits;
2829 static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
2830
2831public:
2832 // constructors and seeding functions
2833 __independent_bits_engine(_Engine& __e, size_t __w);
2834
2835 // generating functions
2836 result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
2837
2838private:
2839 result_type __eval(false_type);
2840 result_type __eval(true_type);
2841};
2842
2843template<class _Engine, class _UIntType>
2844__independent_bits_engine<_Engine, _UIntType>
2845 ::__independent_bits_engine(_Engine& __e, size_t __w)
2846 : __e_(__e),
2847 __w_(__w)
2848{
2849 __n_ = __w_ / __m + (__w_ % __m != 0);
2850 __w0_ = __w_ / __n_;
2851 if (_Rp == 0)
2852 __y0_ = _Rp;
2853 else if (__w0_ < _WDt)
2854 __y0_ = (_Rp >> __w0_) << __w0_;
2855 else
2856 __y0_ = 0;
2857 if (_Rp - __y0_ > __y0_ / __n_)
2858 {
2859 ++__n_;
2860 __w0_ = __w_ / __n_;
2861 if (__w0_ < _WDt)
2862 __y0_ = (_Rp >> __w0_) << __w0_;
2863 else
2864 __y0_ = 0;
2865 }
2866 __n0_ = __n_ - __w_ % __n_;
2867 if (__w0_ < _WDt - 1)
2868 __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1);
2869 else
2870 __y1_ = 0;
2871 __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :
2872 _Engine_result_type(0);
2873 __mask1_ = __w0_ < _EDt - 1 ?
2874 _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :
2875 _Engine_result_type(~0);
2876}
2877
2878template<class _Engine, class _UIntType>
2879inline
2880_UIntType
2881__independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
2882{
2883 return static_cast<result_type>(__e_() & __mask0_);
2884}
2885
2886template<class _Engine, class _UIntType>
2887_UIntType
2888__independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
2889{
2890 const size_t _WRt = numeric_limits<result_type>::digits;
2891 result_type _Sp = 0;
2892 for (size_t __k = 0; __k < __n0_; ++__k)
2893 {
2894 _Engine_result_type __u;
2895 do
2896 {
2897 __u = __e_() - _Engine::min();
2898 } while (__u >= __y0_);
2899 if (__w0_ < _WRt)
2900 _Sp <<= __w0_;
2901 else
2902 _Sp = 0;
2903 _Sp += __u & __mask0_;
2904 }
2905 for (size_t __k = __n0_; __k < __n_; ++__k)
2906 {
2907 _Engine_result_type __u;
2908 do
2909 {
2910 __u = __e_() - _Engine::min();
2911 } while (__u >= __y1_);
2912 if (__w0_ < _WRt - 1)
2913 _Sp <<= __w0_ + 1;
2914 else
2915 _Sp = 0;
2916 _Sp += __u & __mask1_;
2917 }
2918 return _Sp;
2919}
2920
2921// uniform_int_distribution
2922
2923template<class _IntType = int>
2924class uniform_int_distribution
2925{
2926public:
2927 // types
2928 typedef _IntType result_type;
2929
2930 class param_type
2931 {
2932 result_type __a_;
2933 result_type __b_;
2934 public:
2935 typedef uniform_int_distribution distribution_type;
2936
2937 explicit param_type(result_type __a = 0,
2938 result_type __b = numeric_limits<result_type>::max())
2939 : __a_(__a), __b_(__b) {}
2940
2941 result_type a() const {return __a_;}
2942 result_type b() const {return __b_;}
2943
2944 friend bool operator==(const param_type& __x, const param_type& __y)
2945 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
2946 friend bool operator!=(const param_type& __x, const param_type& __y)
2947 {return !(__x == __y);}
2948 };
2949
2950private:
2951 param_type __p_;
2952
2953public:
2954 // constructors and reset functions
2955 explicit uniform_int_distribution(result_type __a = 0,
2956 result_type __b = numeric_limits<result_type>::max())
2957 : __p_(param_type(__a, __b)) {}
2958 explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
2959 void reset() {}
2960
2961 // generating functions
2962 template<class _URNG> result_type operator()(_URNG& __g)
2963 {return (*this)(__g, __p_);}
2964 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
2965
2966 // property functions
2967 result_type a() const {return __p_.a();}
2968 result_type b() const {return __p_.b();}
2969
2970 param_type param() const {return __p_;}
2971 void param(const param_type& __p) {__p_ = __p;}
2972
2973 result_type min() const {return a();}
2974 result_type max() const {return b();}
2975
2976 friend bool operator==(const uniform_int_distribution& __x,
2977 const uniform_int_distribution& __y)
2978 {return __x.__p_ == __y.__p_;}
2979 friend bool operator!=(const uniform_int_distribution& __x,
2980 const uniform_int_distribution& __y)
2981 {return !(__x == __y);}
2982};
2983
2984template<class _IntType>
2985template<class _URNG>
2986typename uniform_int_distribution<_IntType>::result_type
2987uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
2988_LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
2989{
2990 typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
2991 uint32_t, uint64_t>::type _UIntType;
2992 const _UIntType _Rp = _UIntType(__p.b()) - _UIntType(__p.a()) + _UIntType(1);
2993 if (_Rp == 1)
2994 return __p.a();
2995 const size_t _Dt = numeric_limits<_UIntType>::digits;
2996 typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
2997 if (_Rp == 0)
2998 return static_cast<result_type>(_Eng(__g, _Dt)());
2999 size_t __w = _Dt - __clz(_Rp) - 1;
3000 if ((_Rp & (std::numeric_limits<_UIntType>::max() >> (_Dt - __w))) != 0)
3001 ++__w;
3002 _Eng __e(__g, __w);
3003 _UIntType __u;
3004 do
3005 {
3006 __u = __e();
3007 } while (__u >= _Rp);
3008 return static_cast<result_type>(__u + __p.a());
3009}
3010
3011#if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \
3012 || defined(_LIBCPP_BUILDING_LIBRARY)
3013class _LIBCPP_TYPE_VIS __rs_default;
3014
3015_LIBCPP_FUNC_VIS __rs_default __rs_get();
3016
3017class _LIBCPP_TYPE_VIS __rs_default
3018{
3019 static unsigned __c_;
3020
3021 __rs_default();
3022public:
3023 typedef uint_fast32_t result_type;
3024
3025 static const result_type _Min = 0;
3026 static const result_type _Max = 0xFFFFFFFF;
3027
3028 __rs_default(const __rs_default&);
3029 ~__rs_default();
3030
3031 result_type operator()();
3032
3033 static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
3034 static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
3035
3036 friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
3037};
3038
3039_LIBCPP_FUNC_VIS __rs_default __rs_get();
3040
3041template <class _RandomAccessIterator>
3042_LIBCPP_DEPRECATED_IN_CXX14 void
3043random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
3044{
3045 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3046 typedef uniform_int_distribution<ptrdiff_t> _Dp;
3047 typedef typename _Dp::param_type _Pp;
3048 difference_type __d = __last - __first;
3049 if (__d > 1)
3050 {
3051 _Dp __uid;
3052 __rs_default __g = __rs_get();
3053 for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
3054 {
3055 difference_type __i = __uid(__g, _Pp(0, __d));
3056 if (__i != difference_type(0))
3057 swap(*__first, *(__first + __i));
3058 }
3059 }
3060}
3061
3062template <class _RandomAccessIterator, class _RandomNumberGenerator>
3063_LIBCPP_DEPRECATED_IN_CXX14 void
3064random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3065#ifndef _LIBCPP_CXX03_LANG
3066 _RandomNumberGenerator&& __rand)
3067#else
3068 _RandomNumberGenerator& __rand)
3069#endif
3070{
3071 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3072 difference_type __d = __last - __first;
3073 if (__d > 1)
3074 {
3075 for (--__last; __first < __last; ++__first, (void) --__d)
3076 {
3077 difference_type __i = __rand(__d);
3078 if (__i != difference_type(0))
3079 swap(*__first, *(__first + __i));
3080 }
3081 }
3082}
3083#endif
3084
3085template <class _PopulationIterator, class _SampleIterator, class _Distance,
3086 class _UniformRandomNumberGenerator>
3087_LIBCPP_INLINE_VISIBILITY
3088_SampleIterator __sample(_PopulationIterator __first,
3089 _PopulationIterator __last, _SampleIterator __output_iter,
3090 _Distance __n,
3091 _UniformRandomNumberGenerator & __g,
3092 input_iterator_tag) {
3093
3094 _Distance __k = 0;
3095 for (; __first != __last && __k < __n; ++__first, (void)++__k)
3096 __output_iter[__k] = *__first;
3097 _Distance __sz = __k;
3098 for (; __first != __last; ++__first, (void)++__k) {
3099 _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g);
3100 if (__r < __sz)
3101 __output_iter[__r] = *__first;
3102 }
3103 return __output_iter + _VSTD::min(__n, __k);
3104}
3105
3106template <class _PopulationIterator, class _SampleIterator, class _Distance,
3107 class _UniformRandomNumberGenerator>
3108_LIBCPP_INLINE_VISIBILITY
3109_SampleIterator __sample(_PopulationIterator __first,
3110 _PopulationIterator __last, _SampleIterator __output_iter,
3111 _Distance __n,
3112 _UniformRandomNumberGenerator& __g,
3113 forward_iterator_tag) {
3114 _Distance __unsampled_sz = _VSTD::distance(__first, __last);
3115 for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
3116 _Distance __r =
3117 _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g);
3118 if (__r < __n) {
3119 *__output_iter++ = *__first;
3120 --__n;
3121 }
3122 }
3123 return __output_iter;
3124}
3125
3126template <class _PopulationIterator, class _SampleIterator, class _Distance,
3127 class _UniformRandomNumberGenerator>
3128_LIBCPP_INLINE_VISIBILITY
3129_SampleIterator __sample(_PopulationIterator __first,
3130 _PopulationIterator __last, _SampleIterator __output_iter,
3131 _Distance __n, _UniformRandomNumberGenerator& __g) {
3132 typedef typename iterator_traits<_PopulationIterator>::iterator_category
3133 _PopCategory;
3134 typedef typename iterator_traits<_PopulationIterator>::difference_type
3135 _Difference;
3136 static_assert(__is_forward_iterator<_PopulationIterator>::value ||
3137 __is_random_access_iterator<_SampleIterator>::value,
3138 "SampleIterator must meet the requirements of RandomAccessIterator");
3139 typedef typename common_type<_Distance, _Difference>::type _CommonType;
3140 _LIBCPP_ASSERT(__n >= 0, "N must be a positive number.");
3141 return _VSTD::__sample(
3142 __first, __last, __output_iter, _CommonType(__n),
3143 __g, _PopCategory());
3144}
3145
3146#if _LIBCPP_STD_VER > 14
3147template <class _PopulationIterator, class _SampleIterator, class _Distance,
3148 class _UniformRandomNumberGenerator>
3149inline _LIBCPP_INLINE_VISIBILITY
3150_SampleIterator sample(_PopulationIterator __first,
3151 _PopulationIterator __last, _SampleIterator __output_iter,
3152 _Distance __n, _UniformRandomNumberGenerator&& __g) {
3153 return _VSTD::__sample(__first, __last, __output_iter, __n, __g);
3154}
3155#endif // _LIBCPP_STD_VER > 14
3156
3157template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
3158 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3159#ifndef _LIBCPP_CXX03_LANG
3160 _UniformRandomNumberGenerator&& __g)
3161#else
3162 _UniformRandomNumberGenerator& __g)
3163#endif
3164{
3165 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3166 typedef uniform_int_distribution<ptrdiff_t> _Dp;
3167 typedef typename _Dp::param_type _Pp;
3168 difference_type __d = __last - __first;
3169 if (__d > 1)
3170 {
3171 _Dp __uid;
3172 for (--__last, --__d; __first < __last; ++__first, --__d)
3173 {
3174 difference_type __i = __uid(__g, _Pp(0, __d));
3175 if (__i != difference_type(0))
3176 swap(*__first, *(__first + __i));
3177 }
3178 }
3179}
3180
3181template <class _InputIterator, class _Predicate>
3182_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
3183is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3184{
3185 for (; __first != __last; ++__first)
3186 if (!__pred(*__first))
3187 break;
3188 if ( __first == __last )
3189 return true;
3190 ++__first;
3191 for (; __first != __last; ++__first)
3192 if (__pred(*__first))
3193 return false;
3194 return true;
3195}
3196
3197// partition
3198
3199template <class _Predicate, class _ForwardIterator>
3200_ForwardIterator
3201__partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
3202{
3203 while (true)
3204 {
3205 if (__first == __last)
3206 return __first;
3207 if (!__pred(*__first))
3208 break;
3209 ++__first;
3210 }
3211 for (_ForwardIterator __p = __first; ++__p != __last;)
3212 {
3213 if (__pred(*__p))
3214 {
3215 swap(*__first, *__p);
3216 ++__first;
3217 }
3218 }
3219 return __first;
3220}
3221
3222template <class _Predicate, class _BidirectionalIterator>
3223_BidirectionalIterator
3224__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3225 bidirectional_iterator_tag)
3226{
3227 while (true)
3228 {
3229 while (true)
3230 {
3231 if (__first == __last)
3232 return __first;
3233 if (!__pred(*__first))
3234 break;
3235 ++__first;
3236 }
3237 do
3238 {
3239 if (__first == --__last)
3240 return __first;
3241 } while (!__pred(*__last));
3242 swap(*__first, *__last);
3243 ++__first;
3244 }
3245}
3246
3247template <class _ForwardIterator, class _Predicate>
3248inline _LIBCPP_INLINE_VISIBILITY
3249_ForwardIterator
3250partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3251{
3252 return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>
3253 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3254}
3255
3256// partition_copy
3257
3258template <class _InputIterator, class _OutputIterator1,
3259 class _OutputIterator2, class _Predicate>
3260_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_OutputIterator1, _OutputIterator2>
3261partition_copy(_InputIterator __first, _InputIterator __last,
3262 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
3263 _Predicate __pred)
3264{
3265 for (; __first != __last; ++__first)
3266 {
3267 if (__pred(*__first))
3268 {
3269 *__out_true = *__first;
3270 ++__out_true;
3271 }
3272 else
3273 {
3274 *__out_false = *__first;
3275 ++__out_false;
3276 }
3277 }
3278 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
3279}
3280
3281// partition_point
3282
3283template<class _ForwardIterator, class _Predicate>
3284_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
3285partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3286{
3287 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3288 difference_type __len = _VSTD::distance(__first, __last);
3289 while (__len != 0)
3290 {
3291 difference_type __l2 = _VSTD::__half_positive(__len);
3292 _ForwardIterator __m = __first;
3293 _VSTD::advance(__m, __l2);
3294 if (__pred(*__m))
3295 {
3296 __first = ++__m;
3297 __len -= __l2 + 1;
3298 }
3299 else
3300 __len = __l2;
3301 }
3302 return __first;
3303}
3304
3305// stable_partition
3306
3307template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
3308_ForwardIterator
3309__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3310 _Distance __len, _Pair __p, forward_iterator_tag __fit)
3311{
3312 // *__first is known to be false
3313 // __len >= 1
3314 if (__len == 1)
3315 return __first;
3316 if (__len == 2)
3317 {
3318 _ForwardIterator __m = __first;
3319 if (__pred(*++__m))
3320 {
3321 swap(*__first, *__m);
3322 return __m;
3323 }
3324 return __first;
3325 }
3326 if (__len <= __p.second)
3327 { // The buffer is big enough to use
3328 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3329 __destruct_n __d(0);
3330 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3331 // Move the falses into the temporary buffer, and the trues to the front of the line
3332 // Update __first to always point to the end of the trues
3333 value_type* __t = __p.first;
3334 ::new(__t) value_type(_VSTD::move(*__first));
3335 __d.__incr((value_type*)0);
3336 ++__t;
3337 _ForwardIterator __i = __first;
3338 while (++__i != __last)
3339 {
3340 if (__pred(*__i))
3341 {
3342 *__first = _VSTD::move(*__i);
3343 ++__first;
3344 }
3345 else
3346 {
3347 ::new(__t) value_type(_VSTD::move(*__i));
3348 __d.__incr((value_type*)0);
3349 ++__t;
3350 }
3351 }
3352 // All trues now at start of range, all falses in buffer
3353 // Move falses back into range, but don't mess up __first which points to first false
3354 __i = __first;
3355 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3356 *__i = _VSTD::move(*__t2);
3357 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3358 return __first;
3359 }
3360 // Else not enough buffer, do in place
3361 // __len >= 3
3362 _ForwardIterator __m = __first;
3363 _Distance __len2 = __len / 2; // __len2 >= 2
3364 _VSTD::advance(__m, __len2);
3365 // recurse on [__first, __m), *__first know to be false
3366 // F?????????????????
3367 // f m l
3368 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3369 _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
3370 // TTTFFFFF??????????
3371 // f ff m l
3372 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3373 _ForwardIterator __m1 = __m;
3374 _ForwardIterator __second_false = __last;
3375 _Distance __len_half = __len - __len2;
3376 while (__pred(*__m1))
3377 {
3378 if (++__m1 == __last)
3379 goto __second_half_done;
3380 --__len_half;
3381 }
3382 // TTTFFFFFTTTF??????
3383 // f ff m m1 l
3384 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
3385__second_half_done:
3386 // TTTFFFFFTTTTTFFFFF
3387 // f ff m sf l
3388 return _VSTD::rotate(__first_false, __m, __second_false);
3389 // TTTTTTTTFFFFFFFFFF
3390 // |
3391}
3392
3393struct __return_temporary_buffer
3394{
3395 template <class _Tp>
3396 _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}
3397};
3398
3399template <class _Predicate, class _ForwardIterator>
3400_ForwardIterator
3401__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3402 forward_iterator_tag)
3403{
3404 const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment
3405 // Either prove all true and return __first or point to first false
3406 while (true)
3407 {
3408 if (__first == __last)
3409 return __first;
3410 if (!__pred(*__first))
3411 break;
3412 ++__first;
3413 }
3414 // We now have a reduced range [__first, __last)
3415 // *__first is known to be false
3416 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3417 typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3418 difference_type __len = _VSTD::distance(__first, __last);
3419 pair<value_type*, ptrdiff_t> __p(0, 0);
3420 unique_ptr<value_type, __return_temporary_buffer> __h;
3421 if (__len >= __alloc_limit)
3422 {
3423 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3424 __h.reset(__p.first);
3425 }
3426 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3427 (__first, __last, __pred, __len, __p, forward_iterator_tag());
3428}
3429
3430template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
3431_BidirectionalIterator
3432__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3433 _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
3434{
3435 // *__first is known to be false
3436 // *__last is known to be true
3437 // __len >= 2
3438 if (__len == 2)
3439 {
3440 swap(*__first, *__last);
3441 return __last;
3442 }
3443 if (__len == 3)
3444 {
3445 _BidirectionalIterator __m = __first;
3446 if (__pred(*++__m))
3447 {
3448 swap(*__first, *__m);
3449 swap(*__m, *__last);
3450 return __last;
3451 }
3452 swap(*__m, *__last);
3453 swap(*__first, *__m);
3454 return __m;
3455 }
3456 if (__len <= __p.second)
3457 { // The buffer is big enough to use
3458 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3459 __destruct_n __d(0);
3460 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3461 // Move the falses into the temporary buffer, and the trues to the front of the line
3462 // Update __first to always point to the end of the trues
3463 value_type* __t = __p.first;
3464 ::new(__t) value_type(_VSTD::move(*__first));
3465 __d.__incr((value_type*)0);
3466 ++__t;
3467 _BidirectionalIterator __i = __first;
3468 while (++__i != __last)
3469 {
3470 if (__pred(*__i))
3471 {
3472 *__first = _VSTD::move(*__i);
3473 ++__first;
3474 }
3475 else
3476 {
3477 ::new(__t) value_type(_VSTD::move(*__i));
3478 __d.__incr((value_type*)0);
3479 ++__t;
3480 }
3481 }
3482 // move *__last, known to be true
3483 *__first = _VSTD::move(*__i);
3484 __i = ++__first;
3485 // All trues now at start of range, all falses in buffer
3486 // Move falses back into range, but don't mess up __first which points to first false
3487 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3488 *__i = _VSTD::move(*__t2);
3489 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3490 return __first;
3491 }
3492 // Else not enough buffer, do in place
3493 // __len >= 4
3494 _BidirectionalIterator __m = __first;
3495 _Distance __len2 = __len / 2; // __len2 >= 2
3496 _VSTD::advance(__m, __len2);
3497 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
3498 // F????????????????T
3499 // f m l
3500 _BidirectionalIterator __m1 = __m;
3501 _BidirectionalIterator __first_false = __first;
3502 _Distance __len_half = __len2;
3503 while (!__pred(*--__m1))
3504 {
3505 if (__m1 == __first)
3506 goto __first_half_done;
3507 --__len_half;
3508 }
3509 // F???TFFF?????????T
3510 // f m1 m l
3511 typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3512 __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3513__first_half_done:
3514 // TTTFFFFF?????????T
3515 // f ff m l
3516 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3517 __m1 = __m;
3518 _BidirectionalIterator __second_false = __last;
3519 ++__second_false;
3520 __len_half = __len - __len2;
3521 while (__pred(*__m1))
3522 {
3523 if (++__m1 == __last)
3524 goto __second_half_done;
3525 --__len_half;
3526 }
3527 // TTTFFFFFTTTF?????T
3528 // f ff m m1 l
3529 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
3530__second_half_done:
3531 // TTTFFFFFTTTTTFFFFF
3532 // f ff m sf l
3533 return _VSTD::rotate(__first_false, __m, __second_false);
3534 // TTTTTTTTFFFFFFFFFF
3535 // |
3536}
3537
3538template <class _Predicate, class _BidirectionalIterator>
3539_BidirectionalIterator
3540__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3541 bidirectional_iterator_tag)
3542{
3543 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3544 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3545 const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment
3546 // Either prove all true and return __first or point to first false
3547 while (true)
3548 {
3549 if (__first == __last)
3550 return __first;
3551 if (!__pred(*__first))
3552 break;
3553 ++__first;
3554 }
3555 // __first points to first false, everything prior to __first is already set.
3556 // Either prove [__first, __last) is all false and return __first, or point __last to last true
3557 do
3558 {
3559 if (__first == --__last)
3560 return __first;
3561 } while (!__pred(*__last));
3562 // We now have a reduced range [__first, __last]
3563 // *__first is known to be false
3564 // *__last is known to be true
3565 // __len >= 2
3566 difference_type __len = _VSTD::distance(__first, __last) + 1;
3567 pair<value_type*, ptrdiff_t> __p(0, 0);
3568 unique_ptr<value_type, __return_temporary_buffer> __h;
3569 if (__len >= __alloc_limit)
3570 {
3571 __p = _VSTD::get_temporary_buffer<value_type>(__len);
3572 __h.reset(__p.first);
3573 }
3574 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3575 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3576}
3577
3578template <class _ForwardIterator, class _Predicate>
3579inline _LIBCPP_INLINE_VISIBILITY
3580_ForwardIterator
3581stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3582{
3583 return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3584 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3585}
3586
3587// is_sorted_until
3588
3589template <class _ForwardIterator, class _Compare>
3590_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
3591is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3592{
3593 if (__first != __last)
3594 {
3595 _ForwardIterator __i = __first;
3596 while (++__i != __last)
3597 {
3598 if (__comp(*__i, *__first))
3599 return __i;
3600 __first = __i;
3601 }
3602 }
3603 return __last;
3604}
3605
3606template<class _ForwardIterator>
3607_LIBCPP_NODISCARD_EXT inline
3608_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3609_ForwardIterator
3610is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3611{
3612 return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3613}
3614
3615// is_sorted
3616
3617template <class _ForwardIterator, class _Compare>
3618_LIBCPP_NODISCARD_EXT inline
3619_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3620bool
3621is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3622{
3623 return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
3624}
3625
3626template<class _ForwardIterator>
3627_LIBCPP_NODISCARD_EXT inline
3628_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3629bool
3630is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3631{
3632 return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3633}
3634
3635// sort
3636
3637// stable, 2-3 compares, 0-2 swaps
3638
3639template <class _Compare, class _ForwardIterator>
3640unsigned
3641__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
3642{
3643 unsigned __r = 0;
3644 if (!__c(*__y, *__x)) // if x <= y
3645 {
3646 if (!__c(*__z, *__y)) // if y <= z
3647 return __r; // x <= y && y <= z
3648 // x <= y && y > z
3649 swap(*__y, *__z); // x <= z && y < z
3650 __r = 1;
3651 if (__c(*__y, *__x)) // if x > y
3652 {
3653 swap(*__x, *__y); // x < y && y <= z
3654 __r = 2;
3655 }
3656 return __r; // x <= y && y < z
3657 }
3658 if (__c(*__z, *__y)) // x > y, if y > z
3659 {
3660 swap(*__x, *__z); // x < y && y < z
3661 __r = 1;
3662 return __r;
3663 }
3664 swap(*__x, *__y); // x > y && y <= z
3665 __r = 1; // x < y && x <= z
3666 if (__c(*__z, *__y)) // if y > z
3667 {
3668 swap(*__y, *__z); // x <= y && y < z
3669 __r = 2;
3670 }
3671 return __r;
3672} // x <= y && y <= z
3673
3674// stable, 3-6 compares, 0-5 swaps
3675
3676template <class _Compare, class _ForwardIterator>
3677unsigned
3678__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3679 _ForwardIterator __x4, _Compare __c)
3680{
3681 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
3682 if (__c(*__x4, *__x3))
3683 {
3684 swap(*__x3, *__x4);
3685 ++__r;
3686 if (__c(*__x3, *__x2))
3687 {
3688 swap(*__x2, *__x3);
3689 ++__r;
3690 if (__c(*__x2, *__x1))
3691 {
3692 swap(*__x1, *__x2);
3693 ++__r;
3694 }
3695 }
3696 }
3697 return __r;
3698}
3699
3700// stable, 4-10 compares, 0-9 swaps
3701
3702template <class _Compare, class _ForwardIterator>
3703_LIBCPP_HIDDEN
3704unsigned
3705__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3706 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
3707{
3708 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
3709 if (__c(*__x5, *__x4))
3710 {
3711 swap(*__x4, *__x5);
3712 ++__r;
3713 if (__c(*__x4, *__x3))
3714 {
3715 swap(*__x3, *__x4);
3716 ++__r;
3717 if (__c(*__x3, *__x2))
3718 {
3719 swap(*__x2, *__x3);
3720 ++__r;
3721 if (__c(*__x2, *__x1))
3722 {
3723 swap(*__x1, *__x2);
3724 ++__r;
3725 }
3726 }
3727 }
3728 }
3729 return __r;
3730}
3731
3732// Assumes size > 0
3733template <class _Compare, class _BirdirectionalIterator>
3734void
3735__selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3736{
3737 _BirdirectionalIterator __lm1 = __last;
3738 for (--__lm1; __first != __lm1; ++__first)
3739 {
3740 _BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator,
3741 typename add_lvalue_reference<_Compare>::type>
3742 (__first, __last, __comp);
3743 if (__i != __first)
3744 swap(*__first, *__i);
3745 }
3746}
3747
3748template <class _Compare, class _BirdirectionalIterator>
3749void
3750__insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3751{
3752 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3753 if (__first != __last)
3754 {
3755 _BirdirectionalIterator __i = __first;
3756 for (++__i; __i != __last; ++__i)
3757 {
3758 _BirdirectionalIterator __j = __i;
3759 value_type __t(_VSTD::move(*__j));
3760 for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
3761 *__j = _VSTD::move(*__k);
3762 *__j = _VSTD::move(__t);
3763 }
3764 }
3765}
3766
3767template <class _Compare, class _RandomAccessIterator>
3768void
3769__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3770{
3771 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3772 _RandomAccessIterator __j = __first+2;
3773 __sort3<_Compare>(__first, __first+1, __j, __comp);
3774 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3775 {
3776 if (__comp(*__i, *__j))
3777 {
3778 value_type __t(_VSTD::move(*__i));
3779 _RandomAccessIterator __k = __j;
3780 __j = __i;
3781 do
3782 {
3783 *__j = _VSTD::move(*__k);
3784 __j = __k;
3785 } while (__j != __first && __comp(__t, *--__k));
3786 *__j = _VSTD::move(__t);
3787 }
3788 __j = __i;
3789 }
3790}
3791
3792template <class _Compare, class _RandomAccessIterator>
3793bool
3794__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3795{
3796 switch (__last - __first)
3797 {
3798 case 0:
3799 case 1:
3800 return true;
3801 case 2:
3802 if (__comp(*--__last, *__first))
3803 swap(*__first, *__last);
3804 return true;
3805 case 3:
3806 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3807 return true;
3808 case 4:
3809 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3810 return true;
3811 case 5:
3812 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3813 return true;
3814 }
3815 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3816 _RandomAccessIterator __j = __first+2;
3817 __sort3<_Compare>(__first, __first+1, __j, __comp);
3818 const unsigned __limit = 8;
3819 unsigned __count = 0;
3820 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3821 {
3822 if (__comp(*__i, *__j))
3823 {
3824 value_type __t(_VSTD::move(*__i));
3825 _RandomAccessIterator __k = __j;
3826 __j = __i;
3827 do
3828 {
3829 *__j = _VSTD::move(*__k);
3830 __j = __k;
3831 } while (__j != __first && __comp(__t, *--__k));
3832 *__j = _VSTD::move(__t);
3833 if (++__count == __limit)
3834 return ++__i == __last;
3835 }
3836 __j = __i;
3837 }
3838 return true;
3839}
3840
3841template <class _Compare, class _BirdirectionalIterator>
3842void
3843__insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
3844 typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
3845{
3846 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3847 if (__first1 != __last1)
3848 {
3849 __destruct_n __d(0);
3850 unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
3851 value_type* __last2 = __first2;
3852 ::new(__last2) value_type(_VSTD::move(*__first1));
3853 __d.__incr((value_type*)0);
3854 for (++__last2; ++__first1 != __last1; ++__last2)
3855 {
3856 value_type* __j2 = __last2;
3857 value_type* __i2 = __j2;
3858 if (__comp(*__first1, *--__i2))
3859 {
3860 ::new(__j2) value_type(_VSTD::move(*__i2));
3861 __d.__incr((value_type*)0);
3862 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2)
3863 *__j2 = _VSTD::move(*__i2);
3864 *__j2 = _VSTD::move(*__first1);
3865 }
3866 else
3867 {
3868 ::new(__j2) value_type(_VSTD::move(*__first1));
3869 __d.__incr((value_type*)0);
3870 }
3871 }
3872 __h.release();
3873 }
3874}
3875
3876template <class _Compare, class _RandomAccessIterator>
3877void
3878__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3879{
3880 // _Compare is known to be a reference type
3881 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3882 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3883 const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
3884 is_trivially_copy_assignable<value_type>::value ? 30 : 6;
3885 while (true)
3886 {
3887 __restart:
3888 difference_type __len = __last - __first;
3889 switch (__len)
3890 {
3891 case 0:
3892 case 1:
3893 return;
3894 case 2:
3895 if (__comp(*--__last, *__first))
3896 swap(*__first, *__last);
3897 return;
3898 case 3:
3899 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3900 return;
3901 case 4:
3902 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3903 return;
3904 case 5:
3905 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3906 return;
3907 }
3908 if (__len <= __limit)
3909 {
3910 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
3911 return;
3912 }
3913 // __len > 5
3914 _RandomAccessIterator __m = __first;
3915 _RandomAccessIterator __lm1 = __last;
3916 --__lm1;
3917 unsigned __n_swaps;
3918 {
3919 difference_type __delta;
3920 if (__len >= 1000)
3921 {
3922 __delta = __len/2;
3923 __m += __delta;
3924 __delta /= 2;
3925 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
3926 }
3927 else
3928 {
3929 __delta = __len/2;
3930 __m += __delta;
3931 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
3932 }
3933 }
3934 // *__m is median
3935 // partition [__first, __m) < *__m and *__m <= [__m, __last)
3936 // (this inhibits tossing elements equivalent to __m around unnecessarily)
3937 _RandomAccessIterator __i = __first;
3938 _RandomAccessIterator __j = __lm1;
3939 // j points beyond range to be tested, *__m is known to be <= *__lm1
3940 // The search going up is known to be guarded but the search coming down isn't.
3941 // Prime the downward search with a guard.
3942 if (!__comp(*__i, *__m)) // if *__first == *__m
3943 {
3944 // *__first == *__m, *__first doesn't go in first part
3945 // manually guard downward moving __j against __i
3946 while (true)
3947 {
3948 if (__i == --__j)
3949 {
3950 // *__first == *__m, *__m <= all other elements
3951 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
3952 ++__i; // __first + 1
3953 __j = __last;
3954 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
3955 {
3956 while (true)
3957 {
3958 if (__i == __j)
3959 return; // [__first, __last) all equivalent elements
3960 if (__comp(*__first, *__i))
3961 {
3962 swap(*__i, *__j);
3963 ++__n_swaps;
3964 ++__i;
3965 break;
3966 }
3967 ++__i;
3968 }
3969 }
3970 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
3971 if (__i == __j)
3972 return;
3973 while (true)
3974 {
3975 while (!__comp(*__first, *__i))
3976 ++__i;
3977 while (__comp(*__first, *--__j))
3978 ;
3979 if (__i >= __j)
3980 break;
3981 swap(*__i, *__j);
3982 ++__n_swaps;
3983 ++__i;
3984 }
3985 // [__first, __i) == *__first and *__first < [__i, __last)
3986 // The first part is sorted, sort the secod part
3987 // _VSTD::__sort<_Compare>(__i, __last, __comp);
3988 __first = __i;
3989 goto __restart;
3990 }
3991 if (__comp(*__j, *__m))
3992 {
3993 swap(*__i, *__j);
3994 ++__n_swaps;
3995 break; // found guard for downward moving __j, now use unguarded partition
3996 }
3997 }
3998 }
3999 // It is known that *__i < *__m
4000 ++__i;
4001 // j points beyond range to be tested, *__m is known to be <= *__lm1
4002 // if not yet partitioned...
4003 if (__i < __j)
4004 {
4005 // known that *(__i - 1) < *__m
4006 // known that __i <= __m
4007 while (true)
4008 {
4009 // __m still guards upward moving __i
4010 while (__comp(*__i, *__m))
4011 ++__i;
4012 // It is now known that a guard exists for downward moving __j
4013 while (!__comp(*--__j, *__m))
4014 ;
4015 if (__i > __j)
4016 break;
4017 swap(*__i, *__j);
4018 ++__n_swaps;
4019 // It is known that __m != __j
4020 // If __m just moved, follow it
4021 if (__m == __i)
4022 __m = __j;
4023 ++__i;
4024 }
4025 }
4026 // [__first, __i) < *__m and *__m <= [__i, __last)
4027 if (__i != __m && __comp(*__m, *__i))
4028 {
4029 swap(*__i, *__m);
4030 ++__n_swaps;
4031 }
4032 // [__first, __i) < *__i and *__i <= [__i+1, __last)
4033 // If we were given a perfect partition, see if insertion sort is quick...
4034 if (__n_swaps == 0)
4035 {
4036 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
4037 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
4038 {
4039 if (__fs)
4040 return;
4041 __last = __i;
4042 continue;
4043 }
4044 else
4045 {
4046 if (__fs)
4047 {
4048 __first = ++__i;
4049 continue;
4050 }
4051 }
4052 }
4053 // sort smaller range with recursive call and larger with tail recursion elimination
4054 if (__i - __first < __last - __i)
4055 {
4056 _VSTD::__sort<_Compare>(__first, __i, __comp);
4057 // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4058 __first = ++__i;
4059 }
4060 else
4061 {
4062 _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4063 // _VSTD::__sort<_Compare>(__first, __i, __comp);
4064 __last = __i;
4065 }
4066 }
4067}
4068
4069// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
4070template <class _RandomAccessIterator, class _Compare>
4071inline _LIBCPP_INLINE_VISIBILITY
4072void
4073sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4074{
4075#ifdef _LIBCPP_DEBUG
4076 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4077 __debug_less<_Compare> __c(__comp);
4078 __sort<_Comp_ref>(__first, __last, __c);
4079#else // _LIBCPP_DEBUG
4080 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4081 __sort<_Comp_ref>(__first, __last, __comp);
4082#endif // _LIBCPP_DEBUG
4083}
4084
4085template <class _RandomAccessIterator>
4086inline _LIBCPP_INLINE_VISIBILITY
4087void
4088sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4089{
4090 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4091}
4092
4093template <class _Tp>
4094inline _LIBCPP_INLINE_VISIBILITY
4095void
4096sort(_Tp** __first, _Tp** __last)
4097{
4098 _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
4099}
4100
4101template <class _Tp>
4102inline _LIBCPP_INLINE_VISIBILITY
4103void
4104sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
4105{
4106 _VSTD::sort(__first.base(), __last.base());
4107}
4108
4109template <class _Tp, class _Compare>
4110inline _LIBCPP_INLINE_VISIBILITY
4111void
4112sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
4113{
4114 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4115 _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
4116}
4117
4118_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
4119_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4120_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4121_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4122_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))
4123_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4124_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&))
4125_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4126_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&))
4127_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4128_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4129_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>&))
4130_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&))
4131_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&))
4132_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4133
4134_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))
4135_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4136_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4137_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4138_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))
4139_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4140_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&))
4141_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4142_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&))
4143_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4144_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4145_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>&))
4146_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&))
4147_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&))
4148_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4149
4150_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>&))
4151
4152// lower_bound
4153
4154template <class _Compare, class _ForwardIterator, class _Tp>
4155_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
4156__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4157{
4158 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4159 difference_type __len = _VSTD::distance(__first, __last);
4160 while (__len != 0)
4161 {
4162 difference_type __l2 = _VSTD::__half_positive(__len);
4163 _ForwardIterator __m = __first;
4164 _VSTD::advance(__m, __l2);
4165 if (__comp(*__m, __value_))
4166 {
4167 __first = ++__m;
4168 __len -= __l2 + 1;
4169 }
4170 else
4171 __len = __l2;
4172 }
4173 return __first;
4174}
4175
4176template <class _ForwardIterator, class _Tp, class _Compare>
4177_LIBCPP_NODISCARD_EXT inline
4178_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4179_ForwardIterator
4180lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4181{
4182 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4183 return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp);
4184}
4185
4186template <class _ForwardIterator, class _Tp>
4187_LIBCPP_NODISCARD_EXT inline
4188_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4189_ForwardIterator
4190lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4191{
4192 return _VSTD::lower_bound(__first, __last, __value_,
4193 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4194}
4195
4196// upper_bound
4197
4198template <class _Compare, class _ForwardIterator, class _Tp>
4199_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
4200__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4201{
4202 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4203 difference_type __len = _VSTD::distance(__first, __last);
4204 while (__len != 0)
4205 {
4206 difference_type __l2 = _VSTD::__half_positive(__len);
4207 _ForwardIterator __m = __first;
4208 _VSTD::advance(__m, __l2);
4209 if (__comp(__value_, *__m))
4210 __len = __l2;
4211 else
4212 {
4213 __first = ++__m;
4214 __len -= __l2 + 1;
4215 }
4216 }
4217 return __first;
4218}
4219
4220template <class _ForwardIterator, class _Tp, class _Compare>
4221_LIBCPP_NODISCARD_EXT inline
4222_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4223_ForwardIterator
4224upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4225{
4226 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4227 return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp);
4228}
4229
4230template <class _ForwardIterator, class _Tp>
4231_LIBCPP_NODISCARD_EXT inline
4232_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4233_ForwardIterator
4234upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4235{
4236 return _VSTD::upper_bound(__first, __last, __value_,
4237 __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
4238}
4239
4240// equal_range
4241
4242template <class _Compare, class _ForwardIterator, class _Tp>
4243_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator>
4244__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4245{
4246 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4247 difference_type __len = _VSTD::distance(__first, __last);
4248 while (__len != 0)
4249 {
4250 difference_type __l2 = _VSTD::__half_positive(__len);
4251 _ForwardIterator __m = __first;
4252 _VSTD::advance(__m, __l2);
4253 if (__comp(*__m, __value_))
4254 {
4255 __first = ++__m;
4256 __len -= __l2 + 1;
4257 }
4258 else if (__comp(__value_, *__m))
4259 {
4260 __last = __m;
4261 __len = __l2;
4262 }
4263 else
4264 {
4265 _ForwardIterator __mp1 = __m;
4266 return pair<_ForwardIterator, _ForwardIterator>
4267 (
4268 __lower_bound<_Compare>(__first, __m, __value_, __comp),
4269 __upper_bound<_Compare>(++__mp1, __last, __value_, __comp)
4270 );
4271 }
4272 }
4273 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4274}
4275
4276template <class _ForwardIterator, class _Tp, class _Compare>
4277_LIBCPP_NODISCARD_EXT inline
4278_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4279pair<_ForwardIterator, _ForwardIterator>
4280equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4281{
4282#ifdef _LIBCPP_DEBUG
4283 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4284 __debug_less<_Compare> __c(__comp);
4285 return __equal_range<_Comp_ref>(__first, __last, __value_, __c);
4286#else // _LIBCPP_DEBUG
4287 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4288 return __equal_range<_Comp_ref>(__first, __last, __value_, __comp);
4289#endif // _LIBCPP_DEBUG
4290}
4291
4292template <class _ForwardIterator, class _Tp>
4293_LIBCPP_NODISCARD_EXT inline
4294_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4295pair<_ForwardIterator, _ForwardIterator>
4296equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4297{
4298 return _VSTD::equal_range(__first, __last, __value_,
4299 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4300}
4301
4302// binary_search
4303
4304template <class _Compare, class _ForwardIterator, class _Tp>
4305inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4306bool
4307__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4308{
4309 __first = __lower_bound<_Compare>(__first, __last, __value_, __comp);
4310 return __first != __last && !__comp(__value_, *__first);
4311}
4312
4313template <class _ForwardIterator, class _Tp, class _Compare>
4314_LIBCPP_NODISCARD_EXT inline
4315_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4316bool
4317binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4318{
4319#ifdef _LIBCPP_DEBUG
4320 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4321 __debug_less<_Compare> __c(__comp);
4322 return __binary_search<_Comp_ref>(__first, __last, __value_, __c);
4323#else // _LIBCPP_DEBUG
4324 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4325 return __binary_search<_Comp_ref>(__first, __last, __value_, __comp);
4326#endif // _LIBCPP_DEBUG
4327}
4328
4329template <class _ForwardIterator, class _Tp>
4330_LIBCPP_NODISCARD_EXT inline
4331_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4332bool
4333binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4334{
4335 return _VSTD::binary_search(__first, __last, __value_,
4336 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4337}
4338
4339// merge
4340
4341template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4342_OutputIterator
4343__merge(_InputIterator1 __first1, _InputIterator1 __last1,
4344 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4345{
4346 for (; __first1 != __last1; ++__result)
4347 {
4348 if (__first2 == __last2)
4349 return _VSTD::copy(__first1, __last1, __result);
4350 if (__comp(*__first2, *__first1))
4351 {
4352 *__result = *__first2;
4353 ++__first2;
4354 }
4355 else
4356 {
4357 *__result = *__first1;
4358 ++__first1;
4359 }
4360 }
4361 return _VSTD::copy(__first2, __last2, __result);
4362}
4363
4364template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4365inline _LIBCPP_INLINE_VISIBILITY
4366_OutputIterator
4367merge(_InputIterator1 __first1, _InputIterator1 __last1,
4368 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4369{
4370#ifdef _LIBCPP_DEBUG
4371 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4372 __debug_less<_Compare> __c(__comp);
4373 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
4374#else // _LIBCPP_DEBUG
4375 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4376 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4377#endif // _LIBCPP_DEBUG
4378}
4379
4380template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4381inline _LIBCPP_INLINE_VISIBILITY
4382_OutputIterator
4383merge(_InputIterator1 __first1, _InputIterator1 __last1,
4384 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4385{
4386 typedef typename iterator_traits<_InputIterator1>::value_type __v1;
4387 typedef typename iterator_traits<_InputIterator2>::value_type __v2;
4388 return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
4389}
4390
4391// inplace_merge
4392
4393template <class _Compare, class _InputIterator1, class _InputIterator2,
4394 class _OutputIterator>
4395void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
4396 _InputIterator2 __first2, _InputIterator2 __last2,
4397 _OutputIterator __result, _Compare __comp)
4398{
4399 for (; __first1 != __last1; ++__result)
4400 {
4401 if (__first2 == __last2)
4402 {
4403 _VSTD::move(__first1, __last1, __result);
4404 return;
4405 }
4406
4407 if (__comp(*__first2, *__first1))
4408 {
4409 *__result = _VSTD::move(*__first2);
4410 ++__first2;
4411 }
4412 else
4413 {
4414 *__result = _VSTD::move(*__first1);
4415 ++__first1;
4416 }
4417 }
4418 // __first2 through __last2 are already in the right spot.
4419}
4420
4421template <class _Compare, class _BidirectionalIterator>
4422void
4423__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4424 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4425 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4426 typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
4427{
4428 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4429 __destruct_n __d(0);
4430 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4431 if (__len1 <= __len2)
4432 {
4433 value_type* __p = __buff;
4434 for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4435 ::new(__p) value_type(_VSTD::move(*__i));
4436 __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);
4437 }
4438 else
4439 {
4440 value_type* __p = __buff;
4441 for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4442 ::new(__p) value_type(_VSTD::move(*__i));
4443 typedef reverse_iterator<_BidirectionalIterator> _RBi;
4444 typedef reverse_iterator<value_type*> _Rv;
4445 __half_inplace_merge(_Rv(__p), _Rv(__buff),
4446 _RBi(__middle), _RBi(__first),
4447 _RBi(__last), __invert<_Compare>(__comp));
4448 }
4449}
4450
4451template <class _Compare, class _BidirectionalIterator>
4452void
4453__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4454 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4455 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4456 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
4457{
4458 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4459 while (true)
4460 {
4461 // if __middle == __last, we're done
4462 if (__len2 == 0)
4463 return;
4464 if (__len1 <= __buff_size || __len2 <= __buff_size)
4465 return __buffered_inplace_merge<_Compare>
4466 (__first, __middle, __last, __comp, __len1, __len2, __buff);
4467 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
4468 for (; true; ++__first, (void) --__len1)
4469 {
4470 if (__len1 == 0)
4471 return;
4472 if (__comp(*__middle, *__first))
4473 break;
4474 }
4475 // __first < __middle < __last
4476 // *__first > *__middle
4477 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4478 // all elements in:
4479 // [__first, __m1) <= [__middle, __m2)
4480 // [__middle, __m2) < [__m1, __middle)
4481 // [__m1, __middle) <= [__m2, __last)
4482 // and __m1 or __m2 is in the middle of its range
4483 _BidirectionalIterator __m1; // "median" of [__first, __middle)
4484 _BidirectionalIterator __m2; // "median" of [__middle, __last)
4485 difference_type __len11; // distance(__first, __m1)
4486 difference_type __len21; // distance(__middle, __m2)
4487 // binary search smaller range
4488 if (__len1 < __len2)
4489 { // __len >= 1, __len2 >= 2
4490 __len21 = __len2 / 2;
4491 __m2 = __middle;
4492 _VSTD::advance(__m2, __len21);
4493 __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4494 __len11 = _VSTD::distance(__first, __m1);
4495 }
4496 else
4497 {
4498 if (__len1 == 1)
4499 { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
4500 // It is known *__first > *__middle
4501 swap(*__first, *__middle);
4502 return;
4503 }
4504 // __len1 >= 2, __len2 >= 1
4505 __len11 = __len1 / 2;
4506 __m1 = __first;
4507 _VSTD::advance(__m1, __len11);
4508 __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp);
4509 __len21 = _VSTD::distance(__middle, __m2);
4510 }
4511 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle)
4512 difference_type __len22 = __len2 - __len21; // distance(__m2, __last)
4513 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4514 // swap middle two partitions
4515 __middle = _VSTD::rotate(__m1, __middle, __m2);
4516 // __len12 and __len21 now have swapped meanings
4517 // merge smaller range with recurisve call and larger with tail recursion elimination
4518 if (__len11 + __len21 < __len12 + __len22)
4519 {
4520 __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4521// __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4522 __first = __middle;
4523 __middle = __m2;
4524 __len1 = __len12;
4525 __len2 = __len22;
4526 }
4527 else
4528 {
4529 __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4530// __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4531 __last = __middle;
4532 __middle = __m1;
4533 __len1 = __len11;
4534 __len2 = __len21;
4535 }
4536 }
4537}
4538
4539template <class _BidirectionalIterator, class _Compare>
4540inline _LIBCPP_INLINE_VISIBILITY
4541void
4542inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4543 _Compare __comp)
4544{
4545 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4546 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4547 difference_type __len1 = _VSTD::distance(__first, __middle);
4548 difference_type __len2 = _VSTD::distance(__middle, __last);
4549 difference_type __buf_size = _VSTD::min(__len1, __len2);
4550 pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
4551 unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
4552
4553#ifdef _LIBCPP_DEBUG
4554 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4555 __debug_less<_Compare> __c(__comp);
4556 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2,
4557 __buf.first, __buf.second);
4558#else // _LIBCPP_DEBUG
4559 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4560 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4561 __buf.first, __buf.second);
4562#endif // _LIBCPP_DEBUG
4563}
4564
4565template <class _BidirectionalIterator>
4566inline _LIBCPP_INLINE_VISIBILITY
4567void
4568inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
4569{
4570 _VSTD::inplace_merge(__first, __middle, __last,
4571 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4572}
4573
4574// stable_sort
4575
4576template <class _Compare, class _InputIterator1, class _InputIterator2>
4577void
4578__merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
4579 _InputIterator2 __first2, _InputIterator2 __last2,
4580 typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
4581{
4582 typedef typename iterator_traits<_InputIterator1>::value_type value_type;
4583 __destruct_n __d(0);
4584 unique_ptr<value_type, __destruct_n&> __h(__result, __d);
4585 for (; true; ++__result)
4586 {
4587 if (__first1 == __last1)
4588 {
4589 for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0))
4590 ::new (__result) value_type(_VSTD::move(*__first2));
4591 __h.release();
4592 return;
4593 }
4594 if (__first2 == __last2)
4595 {
4596 for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0))
4597 ::new (__result) value_type(_VSTD::move(*__first1));
4598 __h.release();
4599 return;
4600 }
4601 if (__comp(*__first2, *__first1))
4602 {
4603 ::new (__result) value_type(_VSTD::move(*__first2));
4604 __d.__incr((value_type*)0);
4605 ++__first2;
4606 }
4607 else
4608 {
4609 ::new (__result) value_type(_VSTD::move(*__first1));
4610 __d.__incr((value_type*)0);
4611 ++__first1;
4612 }
4613 }
4614}
4615
4616template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4617void
4618__merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
4619 _InputIterator2 __first2, _InputIterator2 __last2,
4620 _OutputIterator __result, _Compare __comp)
4621{
4622 for (; __first1 != __last1; ++__result)
4623 {
4624 if (__first2 == __last2)
4625 {
4626 for (; __first1 != __last1; ++__first1, ++__result)
4627 *__result = _VSTD::move(*__first1);
4628 return;
4629 }
4630 if (__comp(*__first2, *__first1))
4631 {
4632 *__result = _VSTD::move(*__first2);
4633 ++__first2;
4634 }
4635 else
4636 {
4637 *__result = _VSTD::move(*__first1);
4638 ++__first1;
4639 }
4640 }
4641 for (; __first2 != __last2; ++__first2, ++__result)
4642 *__result = _VSTD::move(*__first2);
4643}
4644
4645template <class _Compare, class _RandomAccessIterator>
4646void
4647__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4648 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4649 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
4650
4651template <class _Compare, class _RandomAccessIterator>
4652void
4653__stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
4654 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4655 typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
4656{
4657 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4658 switch (__len)
4659 {
4660 case 0:
4661 return;
4662 case 1:
4663 ::new(__first2) value_type(_VSTD::move(*__first1));
4664 return;
4665 case 2:
4666 __destruct_n __d(0);
4667 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
4668 if (__comp(*--__last1, *__first1))
4669 {
4670 ::new(__first2) value_type(_VSTD::move(*__last1));
4671 __d.__incr((value_type*)0);
4672 ++__first2;
4673 ::new(__first2) value_type(_VSTD::move(*__first1));
4674 }
4675 else
4676 {
4677 ::new(__first2) value_type(_VSTD::move(*__first1));
4678 __d.__incr((value_type*)0);
4679 ++__first2;
4680 ::new(__first2) value_type(_VSTD::move(*__last1));
4681 }
4682 __h2.release();
4683 return;
4684 }
4685 if (__len <= 8)
4686 {
4687 __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
4688 return;
4689 }
4690 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4691 _RandomAccessIterator __m = __first1 + __l2;
4692 __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
4693 __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
4694 __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
4695}
4696
4697template <class _Tp>
4698struct __stable_sort_switch
4699{
4700 static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
4701};
4702
4703template <class _Compare, class _RandomAccessIterator>
4704void
4705__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4706 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4707 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
4708{
4709 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4710 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4711 switch (__len)
4712 {
4713 case 0:
4714 case 1:
4715 return;
4716 case 2:
4717 if (__comp(*--__last, *__first))
4718 swap(*__first, *__last);
4719 return;
4720 }
4721 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4722 {
4723 __insertion_sort<_Compare>(__first, __last, __comp);
4724 return;
4725 }
4726 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4727 _RandomAccessIterator __m = __first + __l2;
4728 if (__len <= __buff_size)
4729 {
4730 __destruct_n __d(0);
4731 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4732 __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4733 __d.__set(__l2, (value_type*)0);
4734 __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
4735 __d.__set(__len, (value_type*)0);
4736 __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4737// __merge<_Compare>(move_iterator<value_type*>(__buff),
4738// move_iterator<value_type*>(__buff + __l2),
4739// move_iterator<_RandomAccessIterator>(__buff + __l2),
4740// move_iterator<_RandomAccessIterator>(__buff + __len),
4741// __first, __comp);
4742 return;
4743 }
4744 __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4745 __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
4746 __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4747}
4748
4749template <class _RandomAccessIterator, class _Compare>
4750inline _LIBCPP_INLINE_VISIBILITY
4751void
4752stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4753{
4754 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4755 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4756 difference_type __len = __last - __first;
4757 pair<value_type*, ptrdiff_t> __buf(0, 0);
4758 unique_ptr<value_type, __return_temporary_buffer> __h;
4759 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4760 {
4761 __buf = _VSTD::get_temporary_buffer<value_type>(__len);
4762 __h.reset(__buf.first);
4763 }
4764#ifdef _LIBCPP_DEBUG
4765 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4766 __debug_less<_Compare> __c(__comp);
4767 __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);
4768#else // _LIBCPP_DEBUG
4769 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4770 __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4771#endif // _LIBCPP_DEBUG
4772}
4773
4774template <class _RandomAccessIterator>
4775inline _LIBCPP_INLINE_VISIBILITY
4776void
4777stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4778{
4779 _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4780}
4781
4782// is_heap_until
4783
4784template <class _RandomAccessIterator, class _Compare>
4785_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
4786is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4787{
4788 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4789 difference_type __len = __last - __first;
4790 difference_type __p = 0;
4791 difference_type __c = 1;
4792 _RandomAccessIterator __pp = __first;
4793 while (__c < __len)
4794 {
4795 _RandomAccessIterator __cp = __first + __c;
4796 if (__comp(*__pp, *__cp))
4797 return __cp;
4798 ++__c;
4799 ++__cp;
4800 if (__c == __len)
4801 return __last;
4802 if (__comp(*__pp, *__cp))
4803 return __cp;
4804 ++__p;
4805 ++__pp;
4806 __c = 2 * __p + 1;
4807 }
4808 return __last;
4809}
4810
4811template<class _RandomAccessIterator>
4812_LIBCPP_NODISCARD_EXT inline
4813_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4814_RandomAccessIterator
4815is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4816{
4817 return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4818}
4819
4820// is_heap
4821
4822template <class _RandomAccessIterator, class _Compare>
4823_LIBCPP_NODISCARD_EXT inline
4824_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4825bool
4826is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4827{
4828 return _VSTD::is_heap_until(__first, __last, __comp) == __last;
4829}
4830
4831template<class _RandomAccessIterator>
4832_LIBCPP_NODISCARD_EXT inline
4833_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4834bool
4835is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4836{
4837 return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4838}
4839
4840// push_heap
4841
4842template <class _Compare, class _RandomAccessIterator>
4843void
4844__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4845 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4846{
4847 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4848 if (__len > 1)
4849 {
4850 __len = (__len - 2) / 2;
4851 _RandomAccessIterator __ptr = __first + __len;
4852 if (__comp(*__ptr, *--__last))
4853 {
4854 value_type __t(_VSTD::move(*__last));
4855 do
4856 {
4857 *__last = _VSTD::move(*__ptr);
4858 __last = __ptr;
4859 if (__len == 0)
4860 break;
4861 __len = (__len - 1) / 2;
4862 __ptr = __first + __len;
4863 } while (__comp(*__ptr, __t));
4864 *__last = _VSTD::move(__t);
4865 }
4866 }
4867}
4868
4869template <class _RandomAccessIterator, class _Compare>
4870inline _LIBCPP_INLINE_VISIBILITY
4871void
4872push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4873{
4874#ifdef _LIBCPP_DEBUG
4875 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4876 __debug_less<_Compare> __c(__comp);
4877 __sift_up<_Comp_ref>(__first, __last, __c, __last - __first);
4878#else // _LIBCPP_DEBUG
4879 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4880 __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
4881#endif // _LIBCPP_DEBUG
4882}
4883
4884template <class _RandomAccessIterator>
4885inline _LIBCPP_INLINE_VISIBILITY
4886void
4887push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4888{
4889 _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4890}
4891
4892// pop_heap
4893
4894template <class _Compare, class _RandomAccessIterator>
4895void
4896__sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/,
4897 _Compare __comp,
4898 typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4899 _RandomAccessIterator __start)
4900{
4901 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4902 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4903 // left-child of __start is at 2 * __start + 1
4904 // right-child of __start is at 2 * __start + 2
4905 difference_type __child = __start - __first;
4906
4907 if (__len < 2 || (__len - 2) / 2 < __child)
4908 return;
4909
4910 __child = 2 * __child + 1;
4911 _RandomAccessIterator __child_i = __first + __child;
4912
4913 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4914 // right-child exists and is greater than left-child
4915 ++__child_i;
4916 ++__child;
4917 }
4918
4919 // check if we are in heap-order
4920 if (__comp(*__child_i, *__start))
4921 // we are, __start is larger than it's largest child
4922 return;
4923
4924 value_type __top(_VSTD::move(*__start));
4925 do
4926 {
4927 // we are not in heap-order, swap the parent with it's largest child
4928 *__start = _VSTD::move(*__child_i);
4929 __start = __child_i;
4930
4931 if ((__len - 2) / 2 < __child)
4932 break;
4933
4934 // recompute the child based off of the updated parent
4935 __child = 2 * __child + 1;
4936 __child_i = __first + __child;
4937
4938 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4939 // right-child exists and is greater than left-child
4940 ++__child_i;
4941 ++__child;
4942 }
4943
4944 // check if we are in heap-order
4945 } while (!__comp(*__child_i, __top));
4946 *__start = _VSTD::move(__top);
4947}
4948
4949template <class _Compare, class _RandomAccessIterator>
4950inline _LIBCPP_INLINE_VISIBILITY
4951void
4952__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4953 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4954{
4955 if (__len > 1)
4956 {
4957 swap(*__first, *--__last);
4958 __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);
4959 }
4960}
4961
4962template <class _RandomAccessIterator, class _Compare>
4963inline _LIBCPP_INLINE_VISIBILITY
4964void
4965pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4966{
4967#ifdef _LIBCPP_DEBUG
4968 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4969 __debug_less<_Compare> __c(__comp);
4970 __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);
4971#else // _LIBCPP_DEBUG
4972 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4973 __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
4974#endif // _LIBCPP_DEBUG
4975}
4976
4977template <class _RandomAccessIterator>
4978inline _LIBCPP_INLINE_VISIBILITY
4979void
4980pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4981{
4982 _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4983}
4984
4985// make_heap
4986
4987template <class _Compare, class _RandomAccessIterator>
4988void
4989__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4990{
4991 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4992 difference_type __n = __last - __first;
4993 if (__n > 1)
4994 {
4995 // start from the first parent, there is no need to consider children
4996 for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start)
4997 {
4998 __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start);
4999 }
5000 }
5001}
5002
5003template <class _RandomAccessIterator, class _Compare>
5004inline _LIBCPP_INLINE_VISIBILITY
5005void
5006make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5007{
5008#ifdef _LIBCPP_DEBUG
5009 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5010 __debug_less<_Compare> __c(__comp);
5011 __make_heap<_Comp_ref>(__first, __last, __c);
5012#else // _LIBCPP_DEBUG
5013 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5014 __make_heap<_Comp_ref>(__first, __last, __comp);
5015#endif // _LIBCPP_DEBUG
5016}
5017
5018template <class _RandomAccessIterator>
5019inline _LIBCPP_INLINE_VISIBILITY
5020void
5021make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5022{
5023 _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5024}
5025
5026// sort_heap
5027
5028template <class _Compare, class _RandomAccessIterator>
5029void
5030__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5031{
5032 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5033 for (difference_type __n = __last - __first; __n > 1; --__last, --__n)
5034 __pop_heap<_Compare>(__first, __last, __comp, __n);
5035}
5036
5037template <class _RandomAccessIterator, class _Compare>
5038inline _LIBCPP_INLINE_VISIBILITY
5039void
5040sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5041{
5042#ifdef _LIBCPP_DEBUG
5043 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5044 __debug_less<_Compare> __c(__comp);
5045 __sort_heap<_Comp_ref>(__first, __last, __c);
5046#else // _LIBCPP_DEBUG
5047 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5048 __sort_heap<_Comp_ref>(__first, __last, __comp);
5049#endif // _LIBCPP_DEBUG
5050}
5051
5052template <class _RandomAccessIterator>
5053inline _LIBCPP_INLINE_VISIBILITY
5054void
5055sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5056{
5057 _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5058}
5059
5060// partial_sort
5061
5062template <class _Compare, class _RandomAccessIterator>
5063void
5064__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5065 _Compare __comp)
5066{
5067 __make_heap<_Compare>(__first, __middle, __comp);
5068 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
5069 for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
5070 {
5071 if (__comp(*__i, *__first))
5072 {
5073 swap(*__i, *__first);
5074 __sift_down<_Compare>(__first, __middle, __comp, __len, __first);
5075 }
5076 }
5077 __sort_heap<_Compare>(__first, __middle, __comp);
5078}
5079
5080template <class _RandomAccessIterator, class _Compare>
5081inline _LIBCPP_INLINE_VISIBILITY
5082void
5083partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5084 _Compare __comp)
5085{
5086#ifdef _LIBCPP_DEBUG
5087 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5088 __debug_less<_Compare> __c(__comp);
5089 __partial_sort<_Comp_ref>(__first, __middle, __last, __c);
5090#else // _LIBCPP_DEBUG
5091 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5092 __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
5093#endif // _LIBCPP_DEBUG
5094}
5095
5096template <class _RandomAccessIterator>
5097inline _LIBCPP_INLINE_VISIBILITY
5098void
5099partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
5100{
5101 _VSTD::partial_sort(__first, __middle, __last,
5102 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5103}
5104
5105// partial_sort_copy
5106
5107template <class _Compare, class _InputIterator, class _RandomAccessIterator>
5108_RandomAccessIterator
5109__partial_sort_copy(_InputIterator __first, _InputIterator __last,
5110 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5111{
5112 _RandomAccessIterator __r = __result_first;
5113 if (__r != __result_last)
5114 {
5115 for (; __first != __last && __r != __result_last; (void) ++__first, ++__r)
5116 *__r = *__first;
5117 __make_heap<_Compare>(__result_first, __r, __comp);
5118 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
5119 for (; __first != __last; ++__first)
5120 if (__comp(*__first, *__result_first))
5121 {
5122 *__result_first = *__first;
5123 __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first);
5124 }
5125 __sort_heap<_Compare>(__result_first, __r, __comp);
5126 }
5127 return __r;
5128}
5129
5130template <class _InputIterator, class _RandomAccessIterator, class _Compare>
5131inline _LIBCPP_INLINE_VISIBILITY
5132_RandomAccessIterator
5133partial_sort_copy(_InputIterator __first, _InputIterator __last,
5134 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5135{
5136#ifdef _LIBCPP_DEBUG
5137 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5138 __debug_less<_Compare> __c(__comp);
5139 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);
5140#else // _LIBCPP_DEBUG
5141 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5142 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
5143#endif // _LIBCPP_DEBUG
5144}
5145
5146template <class _InputIterator, class _RandomAccessIterator>
5147inline _LIBCPP_INLINE_VISIBILITY
5148_RandomAccessIterator
5149partial_sort_copy(_InputIterator __first, _InputIterator __last,
5150 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
5151{
5152 return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
5153 __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5154}
5155
5156// nth_element
5157
5158template <class _Compare, class _RandomAccessIterator>
5159void
5160__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5161{
5162 // _Compare is known to be a reference type
5163 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5164 const difference_type __limit = 7;
5165 while (true)
5166 {
5167 __restart:
5168 if (__nth == __last)
5169 return;
5170 difference_type __len = __last - __first;
5171 switch (__len)
5172 {
5173 case 0:
5174 case 1:
5175 return;
5176 case 2:
5177 if (__comp(*--__last, *__first))
5178 swap(*__first, *__last);
5179 return;
5180 case 3:
5181 {
5182 _RandomAccessIterator __m = __first;
5183 _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
5184 return;
5185 }
5186 }
5187 if (__len <= __limit)
5188 {
5189 __selection_sort<_Compare>(__first, __last, __comp);
5190 return;
5191 }
5192 // __len > __limit >= 3
5193 _RandomAccessIterator __m = __first + __len/2;
5194 _RandomAccessIterator __lm1 = __last;
5195 unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
5196 // *__m is median
5197 // partition [__first, __m) < *__m and *__m <= [__m, __last)
5198 // (this inhibits tossing elements equivalent to __m around unnecessarily)
5199 _RandomAccessIterator __i = __first;
5200 _RandomAccessIterator __j = __lm1;
5201 // j points beyond range to be tested, *__lm1 is known to be <= *__m
5202 // The search going up is known to be guarded but the search coming down isn't.
5203 // Prime the downward search with a guard.
5204 if (!__comp(*__i, *__m)) // if *__first == *__m
5205 {
5206 // *__first == *__m, *__first doesn't go in first part
5207 // manually guard downward moving __j against __i
5208 while (true)
5209 {
5210 if (__i == --__j)
5211 {
5212 // *__first == *__m, *__m <= all other elements
5213 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
5214 ++__i; // __first + 1
5215 __j = __last;
5216 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
5217 {
5218 while (true)
5219 {
5220 if (__i == __j)
5221 return; // [__first, __last) all equivalent elements
5222 if (__comp(*__first, *__i))
5223 {
5224 swap(*__i, *__j);
5225 ++__n_swaps;
5226 ++__i;
5227 break;
5228 }
5229 ++__i;
5230 }
5231 }
5232 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
5233 if (__i == __j)
5234 return;
5235 while (true)
5236 {
5237 while (!__comp(*__first, *__i))
5238 ++__i;
5239 while (__comp(*__first, *--__j))
5240 ;
5241 if (__i >= __j)
5242 break;
5243 swap(*__i, *__j);
5244 ++__n_swaps;
5245 ++__i;
5246 }
5247 // [__first, __i) == *__first and *__first < [__i, __last)
5248 // The first part is sorted,
5249 if (__nth < __i)
5250 return;
5251 // __nth_element the secod part
5252 // __nth_element<_Compare>(__i, __nth, __last, __comp);
5253 __first = __i;
5254 goto __restart;
5255 }
5256 if (__comp(*__j, *__m))
5257 {
5258 swap(*__i, *__j);
5259 ++__n_swaps;
5260 break; // found guard for downward moving __j, now use unguarded partition
5261 }
5262 }
5263 }
5264 ++__i;
5265 // j points beyond range to be tested, *__lm1 is known to be <= *__m
5266 // if not yet partitioned...
5267 if (__i < __j)
5268 {
5269 // known that *(__i - 1) < *__m
5270 while (true)
5271 {
5272 // __m still guards upward moving __i
5273 while (__comp(*__i, *__m))
5274 ++__i;
5275 // It is now known that a guard exists for downward moving __j
5276 while (!__comp(*--__j, *__m))
5277 ;
5278 if (__i >= __j)
5279 break;
5280 swap(*__i, *__j);
5281 ++__n_swaps;
5282 // It is known that __m != __j
5283 // If __m just moved, follow it
5284 if (__m == __i)
5285 __m = __j;
5286 ++__i;
5287 }
5288 }
5289 // [__first, __i) < *__m and *__m <= [__i, __last)
5290 if (__i != __m && __comp(*__m, *__i))
5291 {
5292 swap(*__i, *__m);
5293 ++__n_swaps;
5294 }
5295 // [__first, __i) < *__i and *__i <= [__i+1, __last)
5296 if (__nth == __i)
5297 return;
5298 if (__n_swaps == 0)
5299 {
5300 // We were given a perfectly partitioned sequence. Coincidence?
5301 if (__nth < __i)
5302 {
5303 // Check for [__first, __i) already sorted
5304 __j = __m = __first;
5305 while (++__j != __i)
5306 {
5307 if (__comp(*__j, *__m))
5308 // not yet sorted, so sort
5309 goto not_sorted;
5310 __m = __j;
5311 }
5312 // [__first, __i) sorted
5313 return;
5314 }
5315 else
5316 {
5317 // Check for [__i, __last) already sorted
5318 __j = __m = __i;
5319 while (++__j != __last)
5320 {
5321 if (__comp(*__j, *__m))
5322 // not yet sorted, so sort
5323 goto not_sorted;
5324 __m = __j;
5325 }
5326 // [__i, __last) sorted
5327 return;
5328 }
5329 }
5330not_sorted:
5331 // __nth_element on range containing __nth
5332 if (__nth < __i)
5333 {
5334 // __nth_element<_Compare>(__first, __nth, __i, __comp);
5335 __last = __i;
5336 }
5337 else
5338 {
5339 // __nth_element<_Compare>(__i+1, __nth, __last, __comp);
5340 __first = ++__i;
5341 }
5342 }
5343}
5344
5345template <class _RandomAccessIterator, class _Compare>
5346inline _LIBCPP_INLINE_VISIBILITY
5347void
5348nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5349{
5350#ifdef _LIBCPP_DEBUG
5351 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5352 __debug_less<_Compare> __c(__comp);
5353 __nth_element<_Comp_ref>(__first, __nth, __last, __c);
5354#else // _LIBCPP_DEBUG
5355 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5356 __nth_element<_Comp_ref>(__first, __nth, __last, __comp);
5357#endif // _LIBCPP_DEBUG
5358}
5359
5360template <class _RandomAccessIterator>
5361inline _LIBCPP_INLINE_VISIBILITY
5362void
5363nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
5364{
5365 _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5366}
5367
5368// includes
5369
5370template <class _Compare, class _InputIterator1, class _InputIterator2>
5371_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
5372__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5373 _Compare __comp)
5374{
5375 for (; __first2 != __last2; ++__first1)
5376 {
5377 if (__first1 == __last1 || __comp(*__first2, *__first1))
5378 return false;
5379 if (!__comp(*__first1, *__first2))
5380 ++__first2;
5381 }
5382 return true;
5383}
5384
5385template <class _InputIterator1, class _InputIterator2, class _Compare>
5386_LIBCPP_NODISCARD_EXT inline
5387_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5388bool
5389includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5390 _Compare __comp)
5391{
5392#ifdef _LIBCPP_DEBUG
5393 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5394 __debug_less<_Compare> __c(__comp);
5395 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5396#else // _LIBCPP_DEBUG
5397 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5398 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5399#endif // _LIBCPP_DEBUG
5400}
5401
5402template <class _InputIterator1, class _InputIterator2>
5403_LIBCPP_NODISCARD_EXT inline
5404_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5405bool
5406includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
5407{
5408 return _VSTD::includes(__first1, __last1, __first2, __last2,
5409 __less<typename iterator_traits<_InputIterator1>::value_type,
5410 typename iterator_traits<_InputIterator2>::value_type>());
5411}
5412
5413// set_union
5414
5415template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5416_OutputIterator
5417__set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5418 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5419{
5420 for (; __first1 != __last1; ++__result)
5421 {
5422 if (__first2 == __last2)
5423 return _VSTD::copy(__first1, __last1, __result);
5424 if (__comp(*__first2, *__first1))
5425 {
5426 *__result = *__first2;
5427 ++__first2;
5428 }
5429 else
5430 {
5431 if (!__comp(*__first1, *__first2))
5432 ++__first2;
5433 *__result = *__first1;
5434 ++__first1;
5435 }
5436 }
5437 return _VSTD::copy(__first2, __last2, __result);
5438}
5439
5440template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5441inline _LIBCPP_INLINE_VISIBILITY
5442_OutputIterator
5443set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5444 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5445{
5446#ifdef _LIBCPP_DEBUG
5447 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5448 __debug_less<_Compare> __c(__comp);
5449 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5450#else // _LIBCPP_DEBUG
5451 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5452 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5453#endif // _LIBCPP_DEBUG
5454}
5455
5456template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5457inline _LIBCPP_INLINE_VISIBILITY
5458_OutputIterator
5459set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5460 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5461{
5462 return _VSTD::set_union(__first1, __last1, __first2, __last2, __result,
5463 __less<typename iterator_traits<_InputIterator1>::value_type,
5464 typename iterator_traits<_InputIterator2>::value_type>());
5465}
5466
5467// set_intersection
5468
5469template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5470_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
5471__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5472 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5473{
5474 while (__first1 != __last1 && __first2 != __last2)
5475 {
5476 if (__comp(*__first1, *__first2))
5477 ++__first1;
5478 else
5479 {
5480 if (!__comp(*__first2, *__first1))
5481 {
5482 *__result = *__first1;
5483 ++__result;
5484 ++__first1;
5485 }
5486 ++__first2;
5487 }
5488 }
5489 return __result;
5490}
5491
5492template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5493inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5494_OutputIterator
5495set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5496 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5497{
5498#ifdef _LIBCPP_DEBUG
5499 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5500 __debug_less<_Compare> __c(__comp);
5501 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5502#else // _LIBCPP_DEBUG
5503 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5504 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5505#endif // _LIBCPP_DEBUG
5506}
5507
5508template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5509inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5510_OutputIterator
5511set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5512 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5513{
5514 return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result,
5515 __less<typename iterator_traits<_InputIterator1>::value_type,
5516 typename iterator_traits<_InputIterator2>::value_type>());
5517}
5518
5519// set_difference
5520
5521template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5522_OutputIterator
5523__set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5524 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5525{
5526 while (__first1 != __last1)
5527 {
5528 if (__first2 == __last2)
5529 return _VSTD::copy(__first1, __last1, __result);
5530 if (__comp(*__first1, *__first2))
5531 {
5532 *__result = *__first1;
5533 ++__result;
5534 ++__first1;
5535 }
5536 else
5537 {
5538 if (!__comp(*__first2, *__first1))
5539 ++__first1;
5540 ++__first2;
5541 }
5542 }
5543 return __result;
5544}
5545
5546template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5547inline _LIBCPP_INLINE_VISIBILITY
5548_OutputIterator
5549set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5550 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5551{
5552#ifdef _LIBCPP_DEBUG
5553 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5554 __debug_less<_Compare> __c(__comp);
5555 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5556#else // _LIBCPP_DEBUG
5557 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5558 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5559#endif // _LIBCPP_DEBUG
5560}
5561
5562template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5563inline _LIBCPP_INLINE_VISIBILITY
5564_OutputIterator
5565set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5566 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5567{
5568 return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result,
5569 __less<typename iterator_traits<_InputIterator1>::value_type,
5570 typename iterator_traits<_InputIterator2>::value_type>());
5571}
5572
5573// set_symmetric_difference
5574
5575template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5576_OutputIterator
5577__set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5578 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5579{
5580 while (__first1 != __last1)
5581 {
5582 if (__first2 == __last2)
5583 return _VSTD::copy(__first1, __last1, __result);
5584 if (__comp(*__first1, *__first2))
5585 {
5586 *__result = *__first1;
5587 ++__result;
5588 ++__first1;
5589 }
5590 else
5591 {
5592 if (__comp(*__first2, *__first1))
5593 {
5594 *__result = *__first2;
5595 ++__result;
5596 }
5597 else
5598 ++__first1;
5599 ++__first2;
5600 }
5601 }
5602 return _VSTD::copy(__first2, __last2, __result);
5603}
5604
5605template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5606inline _LIBCPP_INLINE_VISIBILITY
5607_OutputIterator
5608set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5609 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5610{
5611#ifdef _LIBCPP_DEBUG
5612 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5613 __debug_less<_Compare> __c(__comp);
5614 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5615#else // _LIBCPP_DEBUG
5616 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5617 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5618#endif // _LIBCPP_DEBUG
5619}
5620
5621template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5622inline _LIBCPP_INLINE_VISIBILITY
5623_OutputIterator
5624set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5625 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5626{
5627 return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
5628 __less<typename iterator_traits<_InputIterator1>::value_type,
5629 typename iterator_traits<_InputIterator2>::value_type>());
5630}
5631
5632// lexicographical_compare
5633
5634template <class _Compare, class _InputIterator1, class _InputIterator2>
5635_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
5636__lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5637 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5638{
5639 for (; __first2 != __last2; ++__first1, (void) ++__first2)
5640 {
5641 if (__first1 == __last1 || __comp(*__first1, *__first2))
5642 return true;
5643 if (__comp(*__first2, *__first1))
5644 return false;
5645 }
5646 return false;
5647}
5648
5649template <class _InputIterator1, class _InputIterator2, class _Compare>
5650_LIBCPP_NODISCARD_EXT inline
5651_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5652bool
5653lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5654 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5655{
5656#ifdef _LIBCPP_DEBUG
5657 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5658 __debug_less<_Compare> __c(__comp);
5659 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5660#else // _LIBCPP_DEBUG
5661 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5662 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5663#endif // _LIBCPP_DEBUG
5664}
5665
5666template <class _InputIterator1, class _InputIterator2>
5667_LIBCPP_NODISCARD_EXT inline
5668_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
5669bool
5670lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5671 _InputIterator2 __first2, _InputIterator2 __last2)
5672{
5673 return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,
5674 __less<typename iterator_traits<_InputIterator1>::value_type,
5675 typename iterator_traits<_InputIterator2>::value_type>());
5676}
5677
5678// next_permutation
5679
5680template <class _Compare, class _BidirectionalIterator>
5681bool
5682__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5683{
5684 _BidirectionalIterator __i = __last;
5685 if (__first == __last || __first == --__i)
5686 return false;
5687 while (true)
5688 {
5689 _BidirectionalIterator __ip1 = __i;
5690 if (__comp(*--__i, *__ip1))
5691 {
5692 _BidirectionalIterator __j = __last;
5693 while (!__comp(*__i, *--__j))
5694 ;
5695 swap(*__i, *__j);
5696 _VSTD::reverse(__ip1, __last);
5697 return true;
5698 }
5699 if (__i == __first)
5700 {
5701 _VSTD::reverse(__first, __last);
5702 return false;
5703 }
5704 }
5705}
5706
5707template <class _BidirectionalIterator, class _Compare>
5708inline _LIBCPP_INLINE_VISIBILITY
5709bool
5710next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5711{
5712#ifdef _LIBCPP_DEBUG
5713 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5714 __debug_less<_Compare> __c(__comp);
5715 return __next_permutation<_Comp_ref>(__first, __last, __c);
5716#else // _LIBCPP_DEBUG
5717 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5718 return __next_permutation<_Comp_ref>(__first, __last, __comp);
5719#endif // _LIBCPP_DEBUG
5720}
5721
5722template <class _BidirectionalIterator>
5723inline _LIBCPP_INLINE_VISIBILITY
5724bool
5725next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5726{
5727 return _VSTD::next_permutation(__first, __last,
5728 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5729}
5730
5731// prev_permutation
5732
5733template <class _Compare, class _BidirectionalIterator>
5734bool
5735__prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5736{
5737 _BidirectionalIterator __i = __last;
5738 if (__first == __last || __first == --__i)
5739 return false;
5740 while (true)
5741 {
5742 _BidirectionalIterator __ip1 = __i;
5743 if (__comp(*__ip1, *--__i))
5744 {
5745 _BidirectionalIterator __j = __last;
5746 while (!__comp(*--__j, *__i))
5747 ;
5748 swap(*__i, *__j);
5749 _VSTD::reverse(__ip1, __last);
5750 return true;
5751 }
5752 if (__i == __first)
5753 {
5754 _VSTD::reverse(__first, __last);
5755 return false;
5756 }
5757 }
5758}
5759
5760template <class _BidirectionalIterator, class _Compare>
5761inline _LIBCPP_INLINE_VISIBILITY
5762bool
5763prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5764{
5765#ifdef _LIBCPP_DEBUG
5766 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5767 __debug_less<_Compare> __c(__comp);
5768 return __prev_permutation<_Comp_ref>(__first, __last, __c);
5769#else // _LIBCPP_DEBUG
5770 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5771 return __prev_permutation<_Comp_ref>(__first, __last, __comp);
5772#endif // _LIBCPP_DEBUG
5773}
5774
5775template <class _BidirectionalIterator>
5776inline _LIBCPP_INLINE_VISIBILITY
5777bool
5778prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5779{
5780 return _VSTD::prev_permutation(__first, __last,
5781 __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5782}
5783
5784_LIBCPP_END_NAMESPACE_STD
5785
5786_LIBCPP_POP_MACROS
5787
5788#endif // _LIBCPP_ALGORITHM
5789