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