## Coverage Report

#### Created: 2020-02-25 14:32

/Users/buildslave/jenkins/workspace/coverage/llvm-project/libcxx/include/algorithm
Line
Count
1
// -*- C++ -*-
2
//===-------------------------- algorithm ---------------------------------===//
3
//
4
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5
6
7
//
8
//===----------------------------------------------------------------------===//
9
10
#ifndef _LIBCPP_ALGORITHM
11
#define _LIBCPP_ALGORITHM
12
13
/*
14
algorithm synopsis
15
16
#include <initializer_list>
17
18
namespace std
19
{
20
21
template <class InputIterator, class Predicate>
22
constexpr bool     // constexpr in C++20
23
all_of(InputIterator first, InputIterator last, Predicate pred);
24
25
template <class InputIterator, class Predicate>
26
constexpr bool     // constexpr in C++20
27
any_of(InputIterator first, InputIterator last, Predicate pred);
28
29
template <class InputIterator, class Predicate>
30
constexpr bool     // constexpr in C++20
31
none_of(InputIterator first, InputIterator last, Predicate pred);
32
33
template <class InputIterator, class Function>
34
constexpr Function          // constexpr in C++20
35
for_each(InputIterator first, InputIterator last, Function f);
36
37
template<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
41
template <class InputIterator, class T>
42
constexpr InputIterator     // constexpr in C++20
43
find(InputIterator first, InputIterator last, const T& value);
44
45
template <class InputIterator, class Predicate>
46
constexpr InputIterator     // constexpr in C++20
47
find_if(InputIterator first, InputIterator last, Predicate pred);
48
49
template<class InputIterator, class Predicate>
50
InputIterator               // constexpr in C++20
51
find_if_not(InputIterator first, InputIterator last, Predicate pred);
52
53
template <class ForwardIterator1, class ForwardIterator2>
54
ForwardIterator1            // constexpr in C++20
55
find_end(ForwardIterator1 first1, ForwardIterator1 last1,
56
ForwardIterator2 first2, ForwardIterator2 last2);
57
58
template <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
63
template <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
68
template <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
73
template <class ForwardIterator>
74
constexpr ForwardIterator   // constexpr in C++20
75
76
77
template <class ForwardIterator, class BinaryPredicate>
78
constexpr ForwardIterator   // constexpr in C++20
79
adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
80
81
template <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
85
template <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
89
template <class InputIterator1, class InputIterator2>
90
constexpr pair<InputIterator1, InputIterator2>   // constexpr in C++20
91
mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
92
93
template <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
98
template <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
103
template <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
109
template <class InputIterator1, class InputIterator2>
110
constexpr bool      // constexpr in C++20
111
equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
112
113
template <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
118
template <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
123
template <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
129
template<class ForwardIterator1, class ForwardIterator2>
130
constexpr bool      // constexpr in C++20
131
is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
132
ForwardIterator2 first2);
133
134
template<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
139
template<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
144
template<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
150
template <class ForwardIterator1, class ForwardIterator2>
151
constexpr ForwardIterator1      // constexpr in C++20
152
search(ForwardIterator1 first1, ForwardIterator1 last1,
153
ForwardIterator2 first2, ForwardIterator2 last2);
154
155
template <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
160
template <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
164
template <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
169
template <class InputIterator, class OutputIterator>
170
constexpr OutputIterator      // constexpr in C++20
171
copy(InputIterator first, InputIterator last, OutputIterator result);
172
173
template<class InputIterator, class OutputIterator, class Predicate>
174
constexpr OutputIterator      // constexpr in C++20
175
copy_if(InputIterator first, InputIterator last,
176
OutputIterator result, Predicate pred);
177
178
template<class InputIterator, class Size, class OutputIterator>
179
constexpr OutputIterator      // constexpr in C++20
180
copy_n(InputIterator first, Size n, OutputIterator result);
181
182
template <class BidirectionalIterator1, class BidirectionalIterator2>
183
constexpr BidirectionalIterator2      // constexpr in C++20
184
copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
185
BidirectionalIterator2 result);
186
187
template <class ForwardIterator1, class ForwardIterator2>
188
ForwardIterator2
189
swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
190
191
template <class ForwardIterator1, class ForwardIterator2>
192
void
193
iter_swap(ForwardIterator1 a, ForwardIterator2 b);
194
195
template <class InputIterator, class OutputIterator, class UnaryOperation>
196
constexpr OutputIterator      // constexpr in C++20
197
transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
198
199
template <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
204
template <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
208
template <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
212
template <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
217
template <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
221
template <class ForwardIterator, class T>
222
constexpr void      // constexpr in C++20
223
fill(ForwardIterator first, ForwardIterator last, const T& value);
224
225
template <class OutputIterator, class Size, class T>
226
constexpr OutputIterator      // constexpr in C++20
227
fill_n(OutputIterator first, Size n, const T& value);
228
229
template <class ForwardIterator, class Generator>
230
constexpr void      // constexpr in C++20
231
generate(ForwardIterator first, ForwardIterator last, Generator gen);
232
233
template <class OutputIterator, class Size, class Generator>
234
constexpr OutputIterator      // constexpr in C++20
235
generate_n(OutputIterator first, Size n, Generator gen);
236
237
template <class ForwardIterator, class T>
238
constexpr ForwardIterator     // constexpr in C++20
239
remove(ForwardIterator first, ForwardIterator last, const T& value);
240
241
template <class ForwardIterator, class Predicate>
242
constexpr ForwardIterator     // constexpr in C++20
243
remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
244
245
template <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
249
template <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
253
template <class ForwardIterator>
254
ForwardIterator
255
unique(ForwardIterator first, ForwardIterator last);
256
257
template <class ForwardIterator, class BinaryPredicate>
258
ForwardIterator
259
unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
260
261
template <class InputIterator, class OutputIterator>
262
OutputIterator
263
unique_copy(InputIterator first, InputIterator last, OutputIterator result);
264
265
template <class InputIterator, class OutputIterator, class BinaryPredicate>
266
OutputIterator
267
unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
268
269
template <class BidirectionalIterator>
270
void
271
reverse(BidirectionalIterator first, BidirectionalIterator last);
272
273
template <class BidirectionalIterator, class OutputIterator>
274
constexpr OutputIterator       // constexpr in C++20
275
reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
276
277
template <class ForwardIterator>
278
ForwardIterator
279
rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
280
281
template <class ForwardIterator, class OutputIterator>
282
OutputIterator
283
rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
284
285
template <class RandomAccessIterator>
286
void
287
random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17
288
289
template <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
294
template<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
300
template<class RandomAccessIterator, class UniformRandomNumberGenerator>
301
void shuffle(RandomAccessIterator first, RandomAccessIterator last,
302
UniformRandomNumberGenerator&& g);
303
304
template <class InputIterator, class Predicate>
305
constexpr bool  // constexpr in C++20
306
is_partitioned(InputIterator first, InputIterator last, Predicate pred);
307
308
template <class ForwardIterator, class Predicate>
309
ForwardIterator
310
partition(ForwardIterator first, ForwardIterator last, Predicate pred);
311
312
template <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
319
template <class ForwardIterator, class Predicate>
320
ForwardIterator
321
stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
322
323
template<class ForwardIterator, class Predicate>
324
constexpr ForwardIterator  // constexpr in C++20
325
partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
326
327
template <class ForwardIterator>
328
constexpr bool  // constexpr in C++20
329
is_sorted(ForwardIterator first, ForwardIterator last);
330
331
template <class ForwardIterator, class Compare>
332
bool
333
is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
334
335
template<class ForwardIterator>
336
constexpr ForwardIterator    // constexpr in C++20
337
is_sorted_until(ForwardIterator first, ForwardIterator last);
338
339
template <class ForwardIterator, class Compare>
340
constexpr ForwardIterator    // constexpr in C++20
341
is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
342
343
template <class RandomAccessIterator>
344
void
345
sort(RandomAccessIterator first, RandomAccessIterator last);
346
347
template <class RandomAccessIterator, class Compare>
348
void
349
sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
350
351
template <class RandomAccessIterator>
352
void
353
stable_sort(RandomAccessIterator first, RandomAccessIterator last);
354
355
template <class RandomAccessIterator, class Compare>
356
void
357
stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
358
359
template <class RandomAccessIterator>
360
void
361
partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
362
363
template <class RandomAccessIterator, class Compare>
364
void
365
partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
366
367
template <class InputIterator, class RandomAccessIterator>
368
RandomAccessIterator
369
partial_sort_copy(InputIterator first, InputIterator last,
370
RandomAccessIterator result_first, RandomAccessIterator result_last);
371
372
template <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
377
template <class RandomAccessIterator>
378
void
379
nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
380
381
template <class RandomAccessIterator, class Compare>
382
void
383
nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
384
385
template <class ForwardIterator, class T>
386
constexpr ForwardIterator                         // constexpr in C++20
387
lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
388
389
template <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
393
template <class ForwardIterator, class T>
394
constexpr ForwardIterator                         // constexpr in C++20
395
upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
396
397
template <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
401
template <class ForwardIterator, class T>
402
constexpr pair<ForwardIterator, ForwardIterator>  // constexpr in C++20
403
equal_range(ForwardIterator first, ForwardIterator last, const T& value);
404
405
template <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
409
template <class ForwardIterator, class T>
410
constexpr bool                                    // constexpr in C++20
411
binary_search(ForwardIterator first, ForwardIterator last, const T& value);
412
413
template <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
417
template <class InputIterator1, class InputIterator2, class OutputIterator>
418
OutputIterator
419
merge(InputIterator1 first1, InputIterator1 last1,
420
InputIterator2 first2, InputIterator2 last2, OutputIterator result);
421
422
template <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
427
template <class BidirectionalIterator>
428
void
429
inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
430
431
template <class BidirectionalIterator, class Compare>
432
void
433
inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
434
435
template <class InputIterator1, class InputIterator2>
436
constexpr bool                                    // constexpr in C++20
437
includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
438
439
template <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
443
template <class InputIterator1, class InputIterator2, class OutputIterator>
444
OutputIterator
445
set_union(InputIterator1 first1, InputIterator1 last1,
446
InputIterator2 first2, InputIterator2 last2, OutputIterator result);
447
448
template <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
453
template <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
458
template <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
463
template <class InputIterator1, class InputIterator2, class OutputIterator>
464
OutputIterator
465
set_difference(InputIterator1 first1, InputIterator1 last1,
466
InputIterator2 first2, InputIterator2 last2, OutputIterator result);
467
468
template <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
473
template <class InputIterator1, class InputIterator2, class OutputIterator>
474
OutputIterator
475
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
476
InputIterator2 first2, InputIterator2 last2, OutputIterator result);
477
478
template <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
483
template <class RandomAccessIterator>
484
void
485
push_heap(RandomAccessIterator first, RandomAccessIterator last);
486
487
template <class RandomAccessIterator, class Compare>
488
void
489
push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
490
491
template <class RandomAccessIterator>
492
void
493
pop_heap(RandomAccessIterator first, RandomAccessIterator last);
494
495
template <class RandomAccessIterator, class Compare>
496
void
497
pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
498
499
template <class RandomAccessIterator>
500
void
501
make_heap(RandomAccessIterator first, RandomAccessIterator last);
502
503
template <class RandomAccessIterator, class Compare>
504
void
505
make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
506
507
template <class RandomAccessIterator>
508
void
509
sort_heap(RandomAccessIterator first, RandomAccessIterator last);
510
511
template <class RandomAccessIterator, class Compare>
512
void
513
sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
514
515
template <class RandomAccessIterator>
516
constexpr bool   // constexpr in C++20
517
is_heap(RandomAccessIterator first, RandomAccessiterator last);
518
519
template <class RandomAccessIterator, class Compare>
520
constexpr bool   // constexpr in C++20
521
is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
522
523
template <class RandomAccessIterator>
524
constexpr RandomAccessIterator   // constexpr in C++20
525
is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
526
527
template <class RandomAccessIterator, class Compare>
528
constexpr RandomAccessIterator   // constexpr in C++20
529
is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
530
531
template <class ForwardIterator>
532
ForwardIterator
533
min_element(ForwardIterator first, ForwardIterator last);  // constexpr in C++14
534
535
template <class ForwardIterator, class Compare>
536
ForwardIterator
537
min_element(ForwardIterator first, ForwardIterator last, Compare comp);  // constexpr in C++14
538
539
template <class T>
540
const T&
541
min(const T& a, const T& b);  // constexpr in C++14
542
543
template <class T, class Compare>
544
const T&
545
min(const T& a, const T& b, Compare comp);  // constexpr in C++14
546
547
template<class T>
548
T
549
min(initializer_list<T> t);  // constexpr in C++14
550
551
template<class T, class Compare>
552
T
553
min(initializer_list<T> t, Compare comp);  // constexpr in C++14
554
555
template<class T>
556
constexpr const T& clamp( const T& v, const T& lo, const T& hi );               // C++17
557
558
template<class T, class Compare>
559
constexpr const T& clamp( const T& v, const T& lo, const T& hi, Compare comp ); // C++17
560
561
template <class ForwardIterator>
562
ForwardIterator
563
max_element(ForwardIterator first, ForwardIterator last);  // constexpr in C++14
564
565
template <class ForwardIterator, class Compare>
566
ForwardIterator
567
max_element(ForwardIterator first, ForwardIterator last, Compare comp);  // constexpr in C++14
568
569
template <class T>
570
const T&
571
max(const T& a, const T& b); // constexpr in C++14
572
573
template <class T, class Compare>
574
const T&
575
max(const T& a, const T& b, Compare comp);  // constexpr in C++14
576
577
template<class T>
578
T
579
max(initializer_list<T> t);  // constexpr in C++14
580
581
template<class T, class Compare>
582
T
583
max(initializer_list<T> t, Compare comp);  // constexpr in C++14
584
585
template<class ForwardIterator>
586
pair<ForwardIterator, ForwardIterator>
587
minmax_element(ForwardIterator first, ForwardIterator last);   // constexpr in C++14
588
589
template<class ForwardIterator, class Compare>
590
pair<ForwardIterator, ForwardIterator>
591
minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);   // constexpr in C++14
592
593
template<class T>
594
pair<const T&, const T&>
595
minmax(const T& a, const T& b);  // constexpr in C++14
596
597
template<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
601
template<class T>
602
pair<T, T>
603
minmax(initializer_list<T> t);  // constexpr in C++14
604
605
template<class T, class Compare>
606
pair<T, T>
607
minmax(initializer_list<T> t, Compare comp);  // constexpr in C++14
608
609
template <class InputIterator1, class InputIterator2>
610
constexpr bool     // constexpr in C++20
611
lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
612
613
template <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
618
template <class BidirectionalIterator>
619
bool
620
next_permutation(BidirectionalIterator first, BidirectionalIterator last);
621
622
template <class BidirectionalIterator, class Compare>
623
bool
624
next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
625
626
template <class BidirectionalIterator>
627
bool
628
prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
629
630
template <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
653
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.
665
template <class _T1, class _T2 = _T1>
666
struct __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
674
template <class _T1>
675
struct __equal_to<_T1, _T1>
676
{
677
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
678
1.10G
bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
std::__1::__equal_to<char, char>::operator()(char const&, char const&) const
 Line Count Source 678 1.10G bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}
Unexecuted instantiation: std::__1::__equal_to<wchar_t, wchar_t>::operator()(wchar_t const&, wchar_t const&) const
679
};
680
681
template <class _T1>
682
struct __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
688
template <class _T1>
689
struct __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
695
template <class _T1, class _T2 = _T1>
696
struct __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
1.38M
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
711
template <class _T1>
712
struct __less<_T1, _T1>
713
{
714
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
715
6.22G
bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
std::__1::__less<char, char>::operator()(char const&, char const&) const
 Line Count Source 715 873 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
Unexecuted instantiation: std::__1::__less<wchar_t, wchar_t>::operator()(wchar_t const&, wchar_t const&) const
Unexecuted instantiation: std::__1::__less<signed char, signed char>::operator()(signed char const&, signed char const&) const
std::__1::__less<unsigned char, unsigned char>::operator()(unsigned char const&, unsigned char const&) const
 Line Count Source 715 69.5k bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
std::__1::__less<short, short>::operator()(short const&, short const&) const
 Line Count Source 715 886 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
std::__1::__less<unsigned short, unsigned short>::operator()(unsigned short const&, unsigned short const&) const
 Line Count Source 715 713k bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
std::__1::__less<int, int>::operator()(int const&, int const&) const
 Line Count Source 715 72.5M bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
std::__1::__less<unsigned int, unsigned int>::operator()(unsigned int const&, unsigned int const&) const
 Line Count Source 715 1.91G bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
std::__1::__less<long, long>::operator()(long const&, long const&) const
 Line Count Source 715 254M bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
std::__1::__less<unsigned long, unsigned long>::operator()(unsigned long const&, unsigned long const&) const
 Line Count Source 715 3.80G bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
std::__1::__less<long long, long long>::operator()(long long const&, long long const&) const
 Line Count Source 715 1.94M bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
std::__1::__less<unsigned long long, unsigned long long>::operator()(unsigned long long const&, unsigned long long const&) const
 Line Count Source 715 143M bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
std::__1::__less<float, float>::operator()(float const&, float const&) const
 Line Count Source 715 2.90M bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
std::__1::__less<double, double>::operator()(double const&, double const&) const
 Line Count Source 715 282k bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
Unexecuted instantiation: std::__1::__less<long double, long double>::operator()(long double const&, long double const&) const
std::__1::__less<char*, char*>::operator()(char* const&, char* const&) const
 Line Count Source 715 32.7M bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
716
};
717
718
template <class _T1>
719
struct __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
725
template <class _T1>
726
struct __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
732
template <class _Predicate>
733
class __invert // invert the sense of a comparison
734
{
735
private:
736
_Predicate __p_;
737
public:
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
754
template <typename _Integral>
755
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
756
typename enable_if
757
<
758
is_integral<_Integral>::value,
759
_Integral
760
>::type
761
__half_positive(_Integral __value)
762
3.85G
{
763
3.85G
return static_cast<_Integral>(static_cast<typename make_unsigned<_Integral>::type>(__value) / 2);
764
3.85G
}
765
766
template <typename _Tp>
767
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
768
typename 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
780
template <class _Compare>
781
struct __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
825
template <class _Comp>
826
struct __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
831
#else
832
typedef __debug_less<_Comp> type;
833
#endif
834
};
835
836
// all_of
837
838
template <class _InputIterator, class _Predicate>
839
840
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
841
bool
842
all_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
852
template <class _InputIterator, class _Predicate>
853
854
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
855
bool
856
any_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
866
template <class _InputIterator, class _Predicate>
867
868
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
869
bool
870
none_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
880
template <class _InputIterator, class _Function>
881
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
882
_Function
883
for_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
893
template <class _InputIterator, class _Size, class _Function>
894
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
895
_InputIterator
896
for_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
912
template <class _InputIterator, class _Tp>
913
914
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
915
_InputIterator
916
find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
917
0
{
918
0
for (; __first != __last; ++__first)
919
0
if (*__first == __value_)
920
0
break;
921
0
return __first;
922
0
}
Unexecuted instantiation: std::__1::__i_node** std::__1::find<std::__1::__i_node**, std::__1::__i_node*>(std::__1::__i_node**, std::__1::__i_node**, std::__1::__i_node* const&)
Unexecuted instantiation: char* std::__1::find<char*, char>(char*, char*, char const&)
Unexecuted instantiation: wchar_t* std::__1::find<wchar_t*, wchar_t>(wchar_t*, wchar_t*, wchar_t const&)
923
924
// find_if
925
926
template <class _InputIterator, class _Predicate>
927
928
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
929
_InputIterator
930
find_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
940
template<class _InputIterator, class _Predicate>
941
942
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
943
_InputIterator
944
find_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
954
template <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
988
{
989
++__first1;
990
break;
991
}  // else there is a match, check next elements
992
}
993
}
994
}
995
996
template <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
1035
template <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
413
{
1041
413
// Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
1042
413
typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;
1043
413
if (__len2 == 0)
1044
0
return __last1;
1045
413
typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;
1046
413
if (__len1 < __len2)
1047
0
return __last1;
1048
413
const _RandomAccessIterator1 __s = __first1 + (__len2 - 1);  // End of pattern match can't go before here
1049
413
_RandomAccessIterator1 __l1 = __last1;
1050
413
_RandomAccessIterator2 __l2 = __last2;
1051
413
--__l2;
1052
497
while (true)
1053
497
{
1054
1.86k
while (true)
1055
1.86k
{
1056
1.86k
if (__s == __l1)
1057
28
return __last1;
1058
1.84k
if (__pred(*--__l1, *__l2))
1059
469
break;
1060
1.84k
}
1061
497
_RandomAccessIterator1 __m1 = __l1;
1062
469
_RandomAccessIterator2 __m2 = __l2;
1063
5.04k
while (true)
1064
5.04k
{
1065
5.04k
if (__m2 == __first2)
1066
385
return __m1;
1067
4.66k
// no need to check range on __m1 because __s guarantees we have enough source
1068
4.66k
if (!__pred(*--__m1, *--__m2))
1069
84
{
1070
84
break;
1071
84
}
1072
4.66k
}
1073
469
}
1074
413
}
char const* std::__1::__find_end<bool (*)(char, char), char const*, char const*>(char const*, char const*, char const*, char const*, bool (*)(char, char), std::__1::random_access_iterator_tag, std::__1::random_access_iterator_tag)
 Line Count Source 1040 413 { 1041 413 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern 1042 413 typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2; 1043 413 if (__len2 == 0) 1044 0 return __last1; 1045 413 typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1; 1046 413 if (__len1 < __len2) 1047 0 return __last1; 1048 413 const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here 1049 413 _RandomAccessIterator1 __l1 = __last1; 1050 413 _RandomAccessIterator2 __l2 = __last2; 1051 413 --__l2; 1052 497 while (true) 1053 497 { 1054 1.86k while (true) 1055 1.86k { 1056 1.86k if (__s == __l1) 1057 28 return __last1; 1058 1.84k if (__pred(*--__l1, *__l2)) 1059 469 break; 1060 1.84k } 1061 497 _RandomAccessIterator1 __m1 = __l1; 1062 469 _RandomAccessIterator2 __m2 = __l2; 1063 5.04k while (true) 1064 5.04k { 1065 5.04k if (__m2 == __first2) 1066 385 return __m1; 1067 4.66k // no need to check range on __m1 because __s guarantees we have enough source 1068 4.66k if (!__pred(*--__m1, *--__m2)) 1069 84 { 1070 84 break; 1071 84 } 1072 4.66k } 1073 469 } 1074 413 }
Unexecuted instantiation: wchar_t const* std::__1::__find_end<bool (*)(wchar_t, wchar_t), wchar_t const*, wchar_t const*>(wchar_t const*, wchar_t const*, wchar_t const*, wchar_t const*, bool (*)(wchar_t, wchar_t), std::__1::random_access_iterator_tag, std::__1::random_access_iterator_tag)
1075
1076
template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1077
1078
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1079
_ForwardIterator1
1080
find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1081
_ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1082
{
1083
1084
(__first1, __last1, __first2, __last2, __pred,
1085
typename iterator_traits<_ForwardIterator1>::iterator_category(),
1086
typename iterator_traits<_ForwardIterator2>::iterator_category());
1087
}
1088
1089
template <class _ForwardIterator1, class _ForwardIterator2>
1090
1091
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1092
_ForwardIterator1
1093
find_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
1103
template <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
700k
{
1108
17.6M
for (; __first1 != __last1; )
1109
53.3M
__j != __last2; )
1110
36.3M
if (__pred(*__first1, *__j))
1111
137k
return __first1;
1112
700k
;
1113
700k
}
char const* std::__1::__find_first_of_ce<char const*, char const*, bool (*)(char, char)>(char const*, char const*, char const*, char const*, bool (*)(char, char))
 Line Count Source 1107 700k { 1108 17.6M for (; __first1 != __last1; ++__first116.9M) 1109 53.3M for (_ForwardIterator2 __j = __first2; 17.1M__j != __last2; ++__j36.2M) 1110 36.3M if (__pred(*__first1, *__j)) 1111 137k return __first1; 1112 700k return __last1562k; 1113 700k }
Unexecuted instantiation: wchar_t const* std::__1::__find_first_of_ce<wchar_t const*, wchar_t const*, bool (*)(wchar_t, wchar_t)>(wchar_t const*, wchar_t const*, wchar_t const*, wchar_t const*, bool (*)(wchar_t, wchar_t))
1114
1115
1116
template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1117
1118
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1119
_ForwardIterator1
1120
find_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
1126
template <class _ForwardIterator1, class _ForwardIterator2>
1127
1128
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1129
_ForwardIterator1
1130
find_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
1139
1140
template <class _ForwardIterator, class _BinaryPredicate>
1141
1142
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1143
_ForwardIterator
1144
adjacent_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
1159
template <class _ForwardIterator>
1160
1161
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1162
_ForwardIterator
1163
1164
{
1165
typedef typename iterator_traits<_ForwardIterator>::value_type __v;
1166
1167
}
1168
1169
// count
1170
1171
template <class _InputIterator, class _Tp>
1172
1173
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1174
typename iterator_traits<_InputIterator>::difference_type
1175
count(_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
1186
template <class _InputIterator, class _Predicate>
1187
1188
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1189
typename iterator_traits<_InputIterator>::difference_type
1190
count_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
1201
template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1202
1203
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1204
pair<_InputIterator1, _InputIterator2>
1205
mismatch(_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
1214
template <class _InputIterator1, class _InputIterator2>
1215
1216
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1217
pair<_InputIterator1, _InputIterator2>
1218
mismatch(_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
1226
template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1227
1228
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1229
pair<_InputIterator1, _InputIterator2>
1230
mismatch(_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
1240
template <class _InputIterator1, class _InputIterator2>
1241
1242
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1243
pair<_InputIterator1, _InputIterator2>
1244
mismatch(_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
1255
template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1256
1257
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1258
bool
1259
equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred)
1260
0
{
1261
0
for (; __first1 != __last1; ++__first1, (void) ++__first2)
1262
0
if (!__pred(*__first1, *__first2))
1263
0
return false;
1264
0
return true;
1265
0
}
Unexecuted instantiation: bool std::__1::equal<std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>, std::__1::__equal_to<char, char> >(std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>, std::__1::__equal_to<char, char>)
Unexecuted instantiation: bool std::__1::equal<std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>, std::__1::__equal_to<wchar_t, wchar_t> >(std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>, std::__1::__equal_to<wchar_t, wchar_t>)
1266
1267
template <class _InputIterator1, class _InputIterator2>
1268
1269
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1270
bool
1271
equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2)
1272
0
{
1273
0
typedef typename iterator_traits<_InputIterator1>::value_type __v1;
1274
0
typedef typename iterator_traits<_InputIterator2>::value_type __v2;
1275
0
return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>());
1276
0
}
Unexecuted instantiation: bool std::__1::equal<std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*> >(std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>)
Unexecuted instantiation: bool std::__1::equal<std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*> >(std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>)
1277
1278
#if _LIBCPP_STD_VER > 11
1279
template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2>
1280
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1281
bool
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
1292
template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
1293
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1294
bool
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
1303
(__first1, __last1, __first2, __pred );
1304
}
1305
1306
template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
1307
1308
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1309
bool
1310
equal(_InputIterator1 __first1, _InputIterator1 __last1,
1311
_InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred )
1312
{
1313
1314
(__first1, __last1, __first2, __last2, __pred,
1315
typename iterator_traits<_InputIterator1>::iterator_category(),
1316
typename iterator_traits<_InputIterator2>::iterator_category());
1317
}
1318
1319
template <class _InputIterator1, class _InputIterator2>
1320
1321
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1322
bool
1323
equal(_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
1336
template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1337
1338
is_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
1383
template<class _ForwardIterator1, class _ForwardIterator2>
1384
1385
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1386
bool
1387
is_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
1396
template<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
1449
template<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
1460
(__first1, __last1, __first2, __pred );
1461
}
1462
1463
template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1464
1465
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1466
bool
1467
is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1468
_ForwardIterator2 __first2, _ForwardIterator2 __last2,
1469
_BinaryPredicate __pred )
1470
{
1471
1472
(__first1, __last1, __first2, __last2, __pred,
1473
typename iterator_traits<_ForwardIterator1>::iterator_category(),
1474
typename iterator_traits<_ForwardIterator2>::iterator_category());
1475
}
1476
1477
template<class _ForwardIterator1, class _ForwardIterator2>
1478
1479
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1480
bool
1481
is_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
1496
template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
1497
1498
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1499
_ForwardIterator1
1500
search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1501
_ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
1502
{
1503
1504
(__first1, __last1, __first2, __last2, __pred,
1505
typename iterator_traits<_ForwardIterator1>::iterator_category(),
1506
typename iterator_traits<_ForwardIterator2>::iterator_category())
1507
.first;
1508
}
1509
1510
template <class _ForwardIterator1, class _ForwardIterator2>
1511
1512
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1513
_ForwardIterator1
1514
search(_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
1524
template <class _ForwardIterator, class _Searcher>
1525
1526
_ForwardIterator search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher &__s)
1527
{ return __s(__f, __l).first; }
1528
#endif
1529
1530
// search_n
1531
1532
template <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
1569
template <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
1609
template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
1610
1611
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1612
_ForwardIterator
1613
search_n(_ForwardIterator __first, _ForwardIterator __last,
1614
_Size __count, const _Tp& __value_, _BinaryPredicate __pred)
1615
{
1616
1617
(__first, __last, __convert_to_integral(__count), __value_, __pred,
1618
typename iterator_traits<_ForwardIterator>::iterator_category());
1619
}
1620
1621
template <class _ForwardIterator, class _Size, class _Tp>
1622
1623
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1624
_ForwardIterator
1625
search_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
1633
template <class _Iter>
1634
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1635
_Iter
1636
__unwrap_iter(_Iter __i)
1637
955k
{
1638
955k
return __i;
1639
955k
}
char* std::__1::__unwrap_iter<char*>(char*)
 Line Count Source 1637 955k { 1638 955k return __i; 1639 955k }
Unexecuted instantiation: wchar_t const* std::__1::__unwrap_iter<wchar_t const*>(wchar_t const*)
Unexecuted instantiation: wchar_t* std::__1::__unwrap_iter<wchar_t*>(wchar_t*)
Unexecuted instantiation: std::__1::locale::facet** std::__1::__unwrap_iter<std::__1::locale::facet**>(std::__1::locale::facet**)
std::__1::ostreambuf_iterator<char, std::__1::char_traits<char> > std::__1::__unwrap_iter<std::__1::ostreambuf_iterator<char, std::__1::char_traits<char> > >(std::__1::ostreambuf_iterator<char, std::__1::char_traits<char> >)
 Line Count Source 1637 9 { 1638 9 return __i; 1639 9 }
Unexecuted instantiation: std::__1::ostreambuf_iterator<wchar_t, std::__1::char_traits<wchar_t> > std::__1::__unwrap_iter<std::__1::ostreambuf_iterator<wchar_t, std::__1::char_traits<wchar_t> > >(std::__1::ostreambuf_iterator<wchar_t, std::__1::char_traits<wchar_t> >)
Unexecuted instantiation: std::__1::__fs::filesystem::__dir_stream** std::__1::__unwrap_iter<std::__1::__fs::filesystem::__dir_stream**>(std::__1::__fs::filesystem::__dir_stream**)
1640
1641
template <class _Tp>
1642
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1643
typename 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
1655
template <class _Tp>
1656
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
1657
typename enable_if
1658
<
1659
is_trivially_copy_assignable<_Tp>::value,
1660
_Tp*
1661
>::type
1662
__unwrap_iter(__wrap_iter<_Tp*> __i)
1663
3.53k
{
1664
3.53k
return __i.base();
1665
3.53k
}
std::__1::enable_if<is_trivially_copy_assignable<char>::value, char*>::type std::__1::__unwrap_iter<char>(std::__1::__wrap_iter<char*>)
 Line Count Source 1663 3.53k { 1664 3.53k return __i.base(); 1665 3.53k }
Unexecuted instantiation: std::__1::enable_if<is_trivially_copy_assignable<wchar_t>::value, wchar_t*>::type std::__1::__unwrap_iter<wchar_t>(std::__1::__wrap_iter<wchar_t*>)
1666
1667
template <class _Tp>
1668
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
1669
typename enable_if
1670
<
1671
is_trivially_copy_assignable<_Tp>::value,
1672
const _Tp*
1673
>::type
1674
__unwrap_iter(__wrap_iter<const _Tp*> __i)
1675
5.64k
{
1676
5.64k
return __i.base();
1677
5.64k
}
std::__1::enable_if<is_trivially_copy_assignable<char>::value, char const*>::type std::__1::__unwrap_iter<char>(std::__1::__wrap_iter<char const*>)
 Line Count Source 1675 5.64k { 1676 5.64k return __i.base(); 1677 5.64k }
Unexecuted instantiation: std::__1::enable_if<is_trivially_copy_assignable<wchar_t>::value, wchar_t const*>::type std::__1::__unwrap_iter<wchar_t>(std::__1::__wrap_iter<wchar_t const*>)
1678
1679
#else
1680
1681
template <class _Tp>
1682
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
1683
typename 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
1695
template <class _InputIterator, class _OutputIterator>
1696
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1697
_OutputIterator
1698
__copy_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1699
0
{
1700
0
for (; __first != __last; ++__first, (void) ++__result)
1701
0
*__result = *__first;
1702
0
return __result;
1703
0
}
Unexecuted instantiation: char* std::__1::__copy_constexpr<char const*, char*>(char const*, char const*, char*)
Unexecuted instantiation: wchar_t* std::__1::__copy_constexpr<wchar_t const*, wchar_t*>(wchar_t const*, wchar_t const*, wchar_t*)
Unexecuted instantiation: std::__1::ostreambuf_iterator<char, std::__1::char_traits<char> > std::__1::__copy_constexpr<char*, std::__1::ostreambuf_iterator<char, std::__1::char_traits<char> > >(char*, char*, std::__1::ostreambuf_iterator<char, std::__1::char_traits<char> >)
Unexecuted instantiation: std::__1::ostreambuf_iterator<wchar_t, std::__1::char_traits<wchar_t> > std::__1::__copy_constexpr<wchar_t*, std::__1::ostreambuf_iterator<wchar_t, std::__1::char_traits<wchar_t> > >(wchar_t*, wchar_t*, std::__1::ostreambuf_iterator<wchar_t, std::__1::char_traits<wchar_t> >)
Unexecuted instantiation: std::__1::locale::facet** std::__1::__copy_constexpr<std::__1::locale::facet**, std::__1::locale::facet**>(std::__1::locale::facet**, std::__1::locale::facet**, std::__1::locale::facet**)
1704
1705
template <class _InputIterator, class _OutputIterator>
1706
inline _LIBCPP_INLINE_VISIBILITY
1707
_OutputIterator
1708
__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1709
0
{
1710
0
return __copy_constexpr(__first, __last, __result);
1711
0
}
Unexecuted instantiation: std::__1::ostreambuf_iterator<char, std::__1::char_traits<char> > std::__1::__copy<char*, std::__1::ostreambuf_iterator<char, std::__1::char_traits<char> > >(char*, char*, std::__1::ostreambuf_iterator<char, std::__1::char_traits<char> >)
Unexecuted instantiation: std::__1::ostreambuf_iterator<wchar_t, std::__1::char_traits<wchar_t> > std::__1::__copy<wchar_t*, std::__1::ostreambuf_iterator<wchar_t, std::__1::char_traits<wchar_t> > >(wchar_t*, wchar_t*, std::__1::ostreambuf_iterator<wchar_t, std::__1::char_traits<wchar_t> >)
1712
1713
template <class _Tp, class _Up>
1714
inline _LIBCPP_INLINE_VISIBILITY
1715
typename enable_if
1716
<
1717
is_same<typename remove_const<_Tp>::type, _Up>::value &&
1718
is_trivially_copy_assignable<_Up>::value,
1719
_Up*
1720
>::type
1721
__copy(_Tp* __first, _Tp* __last, _Up* __result)
1722
442k
{
1723
442k
const size_t __n = static_cast<size_t>(__last - __first);
1724
442k
if (__n > 0)
1725
442k
;
1726
442k
return __result + __n;
1727
442k
}
std::__1::enable_if<(is_same<std::__1::remove_const<char const>::type, char>::value) && (is_trivially_copy_assignable<char>::value), char*>::type std::__1::__copy<char const, char>(char const*, char const*, char*)
 Line Count Source 1722 442k { 1723 442k const size_t __n = static_cast(__last - __first); 1724 442k if (__n > 0) 1725 442k _VSTD442k::memmove(__result, __first, __n * sizeof(_Up))442k; 1726 442k return __result + __n; 1727 442k }
Unexecuted instantiation: std::__1::enable_if<(is_same<std::__1::remove_const<wchar_t const>::type, wchar_t>::value) && (is_trivially_copy_assignable<wchar_t>::value), wchar_t*>::type std::__1::__copy<wchar_t const, wchar_t>(wchar_t const*, wchar_t const*, wchar_t*)
Unexecuted instantiation: std::__1::enable_if<(is_same<std::__1::remove_const<std::__1::locale::facet*>::type, std::__1::locale::facet*>::value) && (is_trivially_copy_assignable<std::__1::locale::facet*>::value), std::__1::locale::facet**>::type std::__1::__copy<std::__1::locale::facet*, std::__1::locale::facet*>(std::__1::locale::facet**, std::__1::locale::facet**, std::__1::locale::facet**)
1728
1729
template <class _InputIterator, class _OutputIterator>
1730
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
1731
_OutputIterator
1732
copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1733
38
{
1734
38
if (__libcpp_is_constant_evaluated()) {
1735
0
return _VSTD::__copy_constexpr(
1736
0
__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1737
38
} else {
1738
38
return _VSTD::__copy(
1739
38
__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1740
38
}
1741
38
}
Unexecuted instantiation: wchar_t* std::__1::copy<wchar_t const*, wchar_t*>(wchar_t const*, wchar_t const*, wchar_t*)
Unexecuted instantiation: std::__1::locale::facet** std::__1::copy<std::__1::locale::facet**, std::__1::locale::facet**>(std::__1::locale::facet**, std::__1::locale::facet**, std::__1::locale::facet**)
Unexecuted instantiation: std::__1::ostreambuf_iterator<char, std::__1::char_traits<char> > std::__1::copy<char*, std::__1::ostreambuf_iterator<char, std::__1::char_traits<char> > >(char*, char*, std::__1::ostreambuf_iterator<char, std::__1::char_traits<char> >)
Unexecuted instantiation: std::__1::ostreambuf_iterator<wchar_t, std::__1::char_traits<wchar_t> > std::__1::copy<wchar_t*, std::__1::ostreambuf_iterator<wchar_t, std::__1::char_traits<wchar_t> > >(wchar_t*, wchar_t*, std::__1::ostreambuf_iterator<wchar_t, std::__1::char_traits<wchar_t> >)
char* std::__1::copy<std::__1::__wrap_iter<char const*>, char*>(std::__1::__wrap_iter<char const*>, std::__1::__wrap_iter<char const*>, char*)
 Line Count Source 1733 38 { 1734 38 if (__libcpp_is_constant_evaluated()) { 1735 0 return _VSTD::__copy_constexpr( 1736 0 __unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result)); 1737 38 } else { 1738 38 return _VSTD::__copy( 1739 38 __unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result)); 1740 38 } 1741 38 }
Unexecuted instantiation: wchar_t* std::__1::copy<std::__1::__wrap_iter<wchar_t const*>, wchar_t*>(std::__1::__wrap_iter<wchar_t const*>, std::__1::__wrap_iter<wchar_t const*>, wchar_t*)
1742
1743
// copy_backward
1744
1745
template <class _BidirectionalIterator, class _OutputIterator>
1746
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1747
_OutputIterator
1748
__copy_backward_constexpr(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
1749
0
{
1750
0
while (__first != __last)
1751
0
*--__result = *--__last;
1752
0
return __result;
1753
0
}
Unexecuted instantiation: char* std::__1::__copy_backward_constexpr<char const*, char*>(char const*, char const*, char*)
Unexecuted instantiation: wchar_t* std::__1::__copy_backward_constexpr<wchar_t const*, wchar_t*>(wchar_t const*, wchar_t const*, wchar_t*)
1754
1755
template <class _BidirectionalIterator, class _OutputIterator>
1756
inline _LIBCPP_INLINE_VISIBILITY
1757
_OutputIterator
1758
__copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
1759
{
1760
return __copy_backward_constexpr(__first, __last, __result);
1761
}
1762
1763
template <class _Tp, class _Up>
1764
inline _LIBCPP_INLINE_VISIBILITY
1765
typename enable_if
1766
<
1767
is_same<typename remove_const<_Tp>::type, _Up>::value &&
1768
is_trivially_copy_assignable<_Up>::value,
1769
_Up*
1770
>::type
1771
__copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
1772
0
{
1773
0
const size_t __n = static_cast<size_t>(__last - __first);
1774
0
if (__n > 0)
1775
0
{
1776
0
__result -= __n;
1777
0
_VSTD::memmove(__result, __first, __n * sizeof(_Up));
1778
0
}
1779
0
return __result;
1780
0
}
Unexecuted instantiation: std::__1::enable_if<(is_same<std::__1::remove_const<char const>::type, char>::value) && (is_trivially_copy_assignable<char>::value), char*>::type std::__1::__copy_backward<char const, char>(char const*, char const*, char*)
Unexecuted instantiation: std::__1::enable_if<(is_same<std::__1::remove_const<wchar_t const>::type, wchar_t>::value) && (is_trivially_copy_assignable<wchar_t>::value), wchar_t*>::type std::__1::__copy_backward<wchar_t const, wchar_t>(wchar_t const*, wchar_t const*, wchar_t*)
1781
1782
template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1783
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
1784
_BidirectionalIterator2
1785
copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1786
_BidirectionalIterator2 __result)
1787
0
{
1788
0
if (__libcpp_is_constant_evaluated()) {
1789
0
return _VSTD::__copy_backward_constexpr(__unwrap_iter(__first),
1790
0
__unwrap_iter(__last),
1791
0
__unwrap_iter(__result));
1792
0
} else {
1793
0
return _VSTD::__copy_backward(__unwrap_iter(__first),
1794
0
__unwrap_iter(__last),
1795
0
__unwrap_iter(__result));
1796
0
}
1797
0
}
Unexecuted instantiation: char* std::__1::copy_backward<char const*, char*>(char const*, char const*, char*)
Unexecuted instantiation: wchar_t* std::__1::copy_backward<wchar_t const*, wchar_t*>(wchar_t const*, wchar_t const*, wchar_t*)
1798
1799
// copy_if
1800
1801
template<class _InputIterator, class _OutputIterator, class _Predicate>
1802
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1803
_OutputIterator
1804
copy_if(_InputIterator __first, _InputIterator __last,
1805
_OutputIterator __result, _Predicate __pred)
1806
{
1807
for (; __first != __last; ++__first)
1808
{
1809
if (__pred(*__first))
1810
{
1811
*__result = *__first;
1812
++__result;
1813
}
1814
}
1815
return __result;
1816
}
1817
1818
// copy_n
1819
1820
template<class _InputIterator, class _Size, class _OutputIterator>
1821
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
1822
typename enable_if
1823
<
1824
__is_cpp17_input_iterator<_InputIterator>::value &&
1825
!__is_cpp17_random_access_iterator<_InputIterator>::value,
1826
_OutputIterator
1827
>::type
1828
copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1829
{
1830
typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
1831
_IntegralSize __n = __orig_n;
1832
if (__n > 0)
1833
{
1834
*__result = *__first;
1835
++__result;
1836
for (--__n; __n > 0; --__n)
1837
{
1838
++__first;
1839
*__result = *__first;
1840
++__result;
1841
}
1842
}
1843
return __result;
1844
}
1845
1846
template<class _InputIterator, class _Size, class _OutputIterator>
1847
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED
1848
typename enable_if
1849
<
1850
__is_cpp17_random_access_iterator<_InputIterator>::value,
1851
_OutputIterator
1852
>::type
1853
copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1854
0
{
1855
0
typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
1856
0
_IntegralSize __n = __orig_n;
1857
0
return _VSTD::copy(__first, __first + __n, __result);
1858
0
}
Unexecuted instantiation: std::__1::enable_if<__is_cpp17_random_access_iterator<char const*>::value, char*>::type std::__1::copy_n<char const*, unsigned long, char*>(char const*, unsigned long, char*)
Unexecuted instantiation: std::__1::enable_if<__is_cpp17_random_access_iterator<wchar_t const*>::value, wchar_t*>::type std::__1::copy_n<wchar_t const*, unsigned long, wchar_t*>(wchar_t const*, unsigned long, wchar_t*)
1859
1860
// move
1861
1862
template <class _InputIterator, class _OutputIterator>
1863
inline _LIBCPP_INLINE_VISIBILITY
1864
_OutputIterator
1865
__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1866
{
1867
for (; __first != __last; ++__first, (void) ++__result)
1868
*__result = _VSTD::move(*__first);
1869
return __result;
1870
}
1871
1872
template <class _Tp, class _Up>
1873
inline _LIBCPP_INLINE_VISIBILITY
1874
typename enable_if
1875
<
1876
is_same<typename remove_const<_Tp>::type, _Up>::value &&
1877
is_trivially_copy_assignable<_Up>::value,
1878
_Up*
1879
>::type
1880
__move(_Tp* __first, _Tp* __last, _Up* __result)
1881
87.8k
{
1882
87.8k
const size_t __n = static_cast<size_t>(__last - __first);
1883
87.8k
if (__n > 0)
1884
87.8k
_VSTD::memmove(__result, __first, __n * sizeof(_Up));
1885
87.8k
return __result + __n;
1886
87.8k
}
std::__1::enable_if<(is_same<std::__1::remove_const<char>::type, char>::value) && (is_trivially_copy_assignable<char>::value), char*>::type std::__1::__move<char, char>(char*, char*, char*)
 Line Count Source 1881 87.8k { 1882 87.8k const size_t __n = static_cast(__last - __first); 1883 87.8k if (__n > 0) 1884 87.8k _VSTD::memmove(__result, __first, __n * sizeof(_Up)); 1885 87.8k return __result + __n; 1886 87.8k }
Unexecuted instantiation: std::__1::enable_if<(is_same<std::__1::remove_const<wchar_t>::type, wchar_t>::value) && (is_trivially_copy_assignable<wchar_t>::value), wchar_t*>::type std::__1::__move<wchar_t, wchar_t>(wchar_t*, wchar_t*, wchar_t*)
Unexecuted instantiation: std::__1::enable_if<(is_same<std::__1::remove_const<std::__1::__fs::filesystem::__dir_stream*>::type, std::__1::__fs::filesystem::__dir_stream*>::value) && (is_trivially_copy_assignable<std::__1::__fs::filesystem::__dir_stream*>::value), std::__1::__fs::filesystem::__dir_stream**>::type std::__1::__move<std::__1::__fs::filesystem::__dir_stream*, std::__1::__fs::filesystem::__dir_stream*>(std::__1::__fs::filesystem::__dir_stream**, std::__1::__fs::filesystem::__dir_stream**, std::__1::__fs::filesystem::__dir_stream**)
1887
1888
template <class _InputIterator, class _OutputIterator>
1889
inline _LIBCPP_INLINE_VISIBILITY
1890
_OutputIterator
1891
move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1892
0
{
1893
0
return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1894
0
}
Unexecuted instantiation: std::__1::__wrap_iter<char*> std::__1::move<std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*> >(std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>)
Unexecuted instantiation: std::__1::__wrap_iter<wchar_t*> std::__1::move<std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*> >(std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>)
Unexecuted instantiation: std::__1::__fs::filesystem::__dir_stream** std::__1::move<std::__1::__fs::filesystem::__dir_stream**, std::__1::__fs::filesystem::__dir_stream**>(std::__1::__fs::filesystem::__dir_stream**, std::__1::__fs::filesystem::__dir_stream**, std::__1::__fs::filesystem::__dir_stream**)
1895
1896
// move_backward
1897
1898
template <class _InputIterator, class _OutputIterator>
1899
inline _LIBCPP_INLINE_VISIBILITY
1900
_OutputIterator
1901
__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1902
{
1903
while (__first != __last)
1904
*--__result = _VSTD::move(*--__last);
1905
return __result;
1906
}
1907
1908
template <class _Tp, class _Up>
1909
inline _LIBCPP_INLINE_VISIBILITY
1910
typename enable_if
1911
<
1912
is_same<typename remove_const<_Tp>::type, _Up>::value &&
1913
is_trivially_copy_assignable<_Up>::value,
1914
_Up*
1915
>::type
1916
__move_backward(_Tp* __first, _Tp* __last, _Up* __result)
1917
66.9k
{
1918
66.9k
const size_t __n = static_cast<size_t>(__last - __first);
1919
66.9k
if (__n > 0)
1920
43.5k
{
1921
43.5k
__result -= __n;
1922
43.5k
_VSTD::memmove(__result, __first, __n * sizeof(_Up));
1923
43.5k
}
1924
66.9k
return __result;
1925
66.9k
}
std::__1::enable_if<(is_same<std::__1::remove_const<char>::type, char>::value) && (is_trivially_copy_assignable<char>::value), char*>::type std::__1::__move_backward<char, char>(char*, char*, char*)
 Line Count Source 1917 66.9k { 1918 66.9k const size_t __n = static_cast(__last - __first); 1919 66.9k if (__n > 0) 1920 43.5k { 1921 43.5k __result -= __n; 1922 43.5k _VSTD::memmove(__result, __first, __n * sizeof(_Up)); 1923 43.5k } 1924 66.9k return __result; 1925 66.9k }
Unexecuted instantiation: std::__1::enable_if<(is_same<std::__1::remove_const<wchar_t>::type, wchar_t>::value) && (is_trivially_copy_assignable<wchar_t>::value), wchar_t*>::type std::__1::__move_backward<wchar_t, wchar_t>(wchar_t*, wchar_t*, wchar_t*)
Unexecuted instantiation: std::__1::enable_if<(is_same<std::__1::remove_const<std::__1::__fs::filesystem::__dir_stream*>::type, std::__1::__fs::filesystem::__dir_stream*>::value) && (is_trivially_copy_assignable<std::__1::__fs::filesystem::__dir_stream*>::value), std::__1::__fs::filesystem::__dir_stream**>::type std::__1::__move_backward<std::__1::__fs::filesystem::__dir_stream*, std::__1::__fs::filesystem::__dir_stream*>(std::__1::__fs::filesystem::__dir_stream**, std::__1::__fs::filesystem::__dir_stream**, std::__1::__fs::filesystem::__dir_stream**)
1926
1927
template <class _BidirectionalIterator1, class _BidirectionalIterator2>
1928
inline _LIBCPP_INLINE_VISIBILITY
1929
_BidirectionalIterator2
1930
move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1931
_BidirectionalIterator2 __result)
1932
0
{
1933
0
return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1934
0
}
Unexecuted instantiation: std::__1::__wrap_iter<char*> std::__1::move_backward<std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*> >(std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>)
Unexecuted instantiation: std::__1::__wrap_iter<wchar_t*> std::__1::move_backward<std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*> >(std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>)
Unexecuted instantiation: std::__1::__fs::filesystem::__dir_stream** std::__1::move_backward<std::__1::__fs::filesystem::__dir_stream**, std::__1::__fs::filesystem::__dir_stream**>(std::__1::__fs::filesystem::__dir_stream**, std::__1::__fs::filesystem::__dir_stream**, std::__1::__fs::filesystem::__dir_stream**)
1935
1936
// iter_swap
1937
1938
// moved to <type_traits> for better swap / noexcept support
1939
1940
// transform
1941
1942
template <class _InputIterator, class _OutputIterator, class _UnaryOperation>
1943
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1944
_OutputIterator
1945
transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op)
1946
{
1947
for (; __first != __last; ++__first, (void) ++__result)
1948
*__result = __op(*__first);
1949
return __result;
1950
}
1951
1952
template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation>
1953
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1954
_OutputIterator
1955
transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
1956
_OutputIterator __result, _BinaryOperation __binary_op)
1957
{
1958
for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result)
1959
*__result = __binary_op(*__first1, *__first2);
1960
return __result;
1961
}
1962
1963
// replace
1964
1965
template <class _ForwardIterator, class _Tp>
1966
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1967
void
1968
replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value)
1969
{
1970
for (; __first != __last; ++__first)
1971
if (*__first == __old_value)
1972
*__first = __new_value;
1973
}
1974
1975
// replace_if
1976
1977
template <class _ForwardIterator, class _Predicate, class _Tp>
1978
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1979
void
1980
replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value)
1981
{
1982
for (; __first != __last; ++__first)
1983
if (__pred(*__first))
1984
*__first = __new_value;
1985
}
1986
1987
// replace_copy
1988
1989
template <class _InputIterator, class _OutputIterator, class _Tp>
1990
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1991
_OutputIterator
1992
replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1993
const _Tp& __old_value, const _Tp& __new_value)
1994
{
1995
for (; __first != __last; ++__first, (void) ++__result)
1996
if (*__first == __old_value)
1997
*__result = __new_value;
1998
else
1999
*__result = *__first;
2000
return __result;
2001
}
2002
2003
// replace_copy_if
2004
2005
template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp>
2006
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2007
_OutputIterator
2008
replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
2009
_Predicate __pred, const _Tp& __new_value)
2010
{
2011
for (; __first != __last; ++__first, (void) ++__result)
2012
if (__pred(*__first))
2013
*__result = __new_value;
2014
else
2015
*__result = *__first;
2016
return __result;
2017
}
2018
2019
// fill_n
2020
2021
template <class _OutputIterator, class _Size, class _Tp>
2022
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2023
_OutputIterator
2024
__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2025
0
{
2026
0
for (; __n > 0; ++__first, (void) --__n)
2027
0
*__first = __value_;
2028
0
return __first;
2029
0
}
2030
2031
template <class _OutputIterator, class _Size, class _Tp>
2032
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2033
_OutputIterator
2034
fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2035
0
{
2036
0
return _VSTD::__fill_n(__first, __convert_to_integral(__n), __value_);
2037
0
}
2038
2039
// fill
2040
2041
template <class _ForwardIterator, class _Tp>
2042
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2043
void
2044
__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
2045
{
2046
for (; __first != __last; ++__first)
2047
*__first = __value_;
2048
}
2049
2050
template <class _RandomAccessIterator, class _Tp>
2051
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2052
void
2053
__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag)
2054
{
2055
_VSTD::fill_n(__first, __last - __first, __value_);
2056
}
2057
2058
template <class _ForwardIterator, class _Tp>
2059
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2060
void
2061
fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2062
{
2063
_VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category());
2064
}
2065
2066
// generate
2067
2068
template <class _ForwardIterator, class _Generator>
2069
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2070
void
2071
generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
2072
{
2073
for (; __first != __last; ++__first)
2074
*__first = __gen();
2075
}
2076
2077
// generate_n
2078
2079
template <class _OutputIterator, class _Size, class _Generator>
2080
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2081
_OutputIterator
2082
generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen)
2083
{
2084
typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
2085
_IntegralSize __n = __orig_n;
2086
for (; __n > 0; ++__first, (void) --__n)
2087
*__first = __gen();
2088
return __first;
2089
}
2090
2091
// remove
2092
2093
template <class _ForwardIterator, class _Tp>
2094
2095
remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2096
{
2097
__first = _VSTD::find(__first, __last, __value_);
2098
if (__first != __last)
2099
{
2100
_ForwardIterator __i = __first;
2101
while (++__i != __last)
2102
{
2103
if (!(*__i == __value_))
2104
{
2105
*__first = _VSTD::move(*__i);
2106
++__first;
2107
}
2108
}
2109
}
2110
return __first;
2111
}
2112
2113
// remove_if
2114
2115
template <class _ForwardIterator, class _Predicate>
2116
2117
remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2118
{
2119
2120
(__first, __last, __pred);
2121
if (__first != __last)
2122
{
2123
_ForwardIterator __i = __first;
2124
while (++__i != __last)
2125
{
2126
if (!__pred(*__i))
2127
{
2128
*__first = _VSTD::move(*__i);
2129
++__first;
2130
}
2131
}
2132
}
2133
return __first;
2134
}
2135
2136
// remove_copy
2137
2138
template <class _InputIterator, class _OutputIterator, class _Tp>
2139
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2140
_OutputIterator
2141
remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_)
2142
{
2143
for (; __first != __last; ++__first)
2144
{
2145
if (!(*__first == __value_))
2146
{
2147
*__result = *__first;
2148
++__result;
2149
}
2150
}
2151
return __result;
2152
}
2153
2154
// remove_copy_if
2155
2156
template <class _InputIterator, class _OutputIterator, class _Predicate>
2157
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2158
_OutputIterator
2159
remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
2160
{
2161
for (; __first != __last; ++__first)
2162
{
2163
if (!__pred(*__first))
2164
{
2165
*__result = *__first;
2166
++__result;
2167
}
2168
}
2169
return __result;
2170
}
2171
2172
// unique
2173
2174
template <class _ForwardIterator, class _BinaryPredicate>
2175
2176
unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
2177
{
2178
2179
(__first, __last, __pred);
2180
if (__first != __last)
2181
{
2182
// ...  a  a  ?  ...
2183
//      f     i
2184
_ForwardIterator __i = __first;
2185
for (++__i; ++__i != __last;)
2186
if (!__pred(*__first, *__i))
2187
*++__first = _VSTD::move(*__i);
2188
++__first;
2189
}
2190
return __first;
2191
}
2192
2193
template <class _ForwardIterator>
2194
2195
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2196
_ForwardIterator
2197
unique(_ForwardIterator __first, _ForwardIterator __last)
2198
{
2199
typedef typename iterator_traits<_ForwardIterator>::value_type __v;
2200
return _VSTD::unique(__first, __last, __equal_to<__v>());
2201
}
2202
2203
// unique_copy
2204
2205
template <class _BinaryPredicate, class _InputIterator, class _OutputIterator>
2206
_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
2207
__unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2208
input_iterator_tag, output_iterator_tag)
2209
{
2210
if (__first != __last)
2211
{
2212
typename iterator_traits<_InputIterator>::value_type __t(*__first);
2213
*__result = __t;
2214
++__result;
2215
while (++__first != __last)
2216
{
2217
if (!__pred(__t, *__first))
2218
{
2219
__t = *__first;
2220
*__result = __t;
2221
++__result;
2222
}
2223
}
2224
}
2225
return __result;
2226
}
2227
2228
template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator>
2229
_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
2230
__unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred,
2231
forward_iterator_tag, output_iterator_tag)
2232
{
2233
if (__first != __last)
2234
{
2235
_ForwardIterator __i = __first;
2236
*__result = *__i;
2237
++__result;
2238
while (++__first != __last)
2239
{
2240
if (!__pred(*__i, *__first))
2241
{
2242
*__result = *__first;
2243
++__result;
2244
__i = __first;
2245
}
2246
}
2247
}
2248
return __result;
2249
}
2250
2251
template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator>
2252
_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
2253
__unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred,
2254
input_iterator_tag, forward_iterator_tag)
2255
{
2256
if (__first != __last)
2257
{
2258
*__result = *__first;
2259
while (++__first != __last)
2260
if (!__pred(*__result, *__first))
2261
*++__result = *__first;
2262
++__result;
2263
}
2264
return __result;
2265
}
2266
2267
template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
2268
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2269
_OutputIterator
2270
unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred)
2271
{
2272
2273
(__first, __last, __result, __pred,
2274
typename iterator_traits<_InputIterator>::iterator_category(),
2275
typename iterator_traits<_OutputIterator>::iterator_category());
2276
}
2277
2278
template <class _InputIterator, class _OutputIterator>
2279
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2280
_OutputIterator
2281
unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
2282
{
2283
typedef typename iterator_traits<_InputIterator>::value_type __v;
2284
return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());
2285
}
2286
2287
// reverse
2288
2289
template <class _BidirectionalIterator>
2290
inline _LIBCPP_INLINE_VISIBILITY
2291
void
2292
__reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
2293
{
2294
while (__first != __last)
2295
{
2296
if (__first == --__last)
2297
break;
2298
_VSTD::iter_swap(__first, __last);
2299
++__first;
2300
}
2301
}
2302
2303
template <class _RandomAccessIterator>
2304
inline _LIBCPP_INLINE_VISIBILITY
2305
void
2306
__reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
2307
81.1k
{
2308
81.1k
if (__first != __last)
2309
158k
__first < --__last; )
2310
144k
_VSTD::iter_swap(__first, __last);
2311
81.1k
}
void std::__1::__reverse<unsigned int*>(unsigned int*, unsigned int*, std::__1::random_access_iterator_tag)
 Line Count Source 2307 67.6k { 2308 67.6k if (__first != __last) 2309 3.72k for (; 1.05k__first < --__last; ++__first2.67k) 2310 2.67k _VSTD::iter_swap(__first, __last); 2311 67.6k }
void std::__1::__reverse<char*>(char*, char*, std::__1::random_access_iterator_tag)
 Line Count Source 2307 13.4k { 2308 13.4k if (__first != __last) 2309 155k for (; 13.4k__first < --__last; ++__first141k) 2310 141k _VSTD::iter_swap(__first, __last); 2311 13.4k }
Unexecuted instantiation: void std::__1::__reverse<wchar_t*>(wchar_t*, wchar_t*, std::__1::random_access_iterator_tag)
2312
2313
template <class _BidirectionalIterator>
2314
inline _LIBCPP_INLINE_VISIBILITY
2315
void
2316
reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
2317
81.1k
{
2318
81.1k
_VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());
2319
81.1k
}
void std::__1::reverse<unsigned int*>(unsigned int*, unsigned int*)
 Line Count Source 2317 67.6k { 2318 67.6k _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category()); 2319 67.6k }
void std::__1::reverse<char*>(char*, char*)
 Line Count Source 2317 13.4k { 2318 13.4k _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category()); 2319 13.4k }
Unexecuted instantiation: void std::__1::reverse<wchar_t*>(wchar_t*, wchar_t*)
2320
2321
// reverse_copy
2322
2323
template <class _BidirectionalIterator, class _OutputIterator>
2324
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
2325
_OutputIterator
2326
reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
2327
{
2328
for (; __first != __last; ++__result)
2329
*__result = *--__last;
2330
return __result;
2331
}
2332
2333
// rotate
2334
2335
template <class _ForwardIterator>
2336
_ForwardIterator
2337
__rotate_left(_ForwardIterator __first, _ForwardIterator __last)
2338
0
{
2339
0
typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2340
0
value_type __tmp = _VSTD::move(*__first);
2341
0
_ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
2342
0
*__lm1 = _VSTD::move(__tmp);
2343
0
return __lm1;
2344
0
}
Unexecuted instantiation: std::__1::__wrap_iter<char*> std::__1::__rotate_left<std::__1::__wrap_iter<char*> >(std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>)
Unexecuted instantiation: std::__1::__wrap_iter<wchar_t*> std::__1::__rotate_left<std::__1::__wrap_iter<wchar_t*> >(std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>)
2345
2346
template <class _BidirectionalIterator>
2347
_BidirectionalIterator
2348
__rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
2349
0
{
2350
0
typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
2351
0
_BidirectionalIterator __lm1 = _VSTD::prev(__last);
2352
0
value_type __tmp = _VSTD::move(*__lm1);
2353
0
_BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
2354
0
*__first = _VSTD::move(__tmp);
2355
0
return __fp1;
2356
0
}
Unexecuted instantiation: std::__1::__wrap_iter<char*> std::__1::__rotate_right<std::__1::__wrap_iter<char*> >(std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>)
Unexecuted instantiation: std::__1::__wrap_iter<wchar_t*> std::__1::__rotate_right<std::__1::__wrap_iter<wchar_t*> >(std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>)
2357
2358
template <class _ForwardIterator>
2359
_ForwardIterator
2360
__rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2361
0
{
2362
0
_ForwardIterator __i = __middle;
2363
0
while (true)
2364
0
{
2365
0
swap(*__first, *__i);
2366
0
++__first;
2367
0
if (++__i == __last)
2368
0
break;
2369
0
if (__first == __middle)
2370
0
__middle = __i;
2371
0
}
2372
0
_ForwardIterator __r = __first;
2373
0
if (__first != __middle)
2374
0
{
2375
0
__i = __middle;
2376
0
while (true)
2377
0
{
2378
0
swap(*__first, *__i);
2379
0
++__first;
2380
0
if (++__i == __last)
2381
0
{
2382
0
if (__first == __middle)
2383
0
break;
2384
0
__i = __middle;
2385
0
}
2386
0
else if (__first == __middle)
2387
0
__middle = __i;
2388
0
}
2389
0
}
2390
0
return __r;
2391
0
}
Unexecuted instantiation: std::__1::__wrap_iter<char*> std::__1::__rotate_forward<std::__1::__wrap_iter<char*> >(std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>)
Unexecuted instantiation: std::__1::__wrap_iter<wchar_t*> std::__1::__rotate_forward<std::__1::__wrap_iter<wchar_t*> >(std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>)
2392
2393
template<typename _Integral>
2394
inline _LIBCPP_INLINE_VISIBILITY
2395
_Integral
2396
__algo_gcd(_Integral __x, _Integral __y)
2397
40.5k
{
2398
40.5k
do
2399
167k
{
2400
167k
_Integral __t = __x % __y;
2401
167k
__x = __y;
2402
167k
__y = __t;
2403
167k
} while (__y);
2404
40.5k
return __x;
2405
40.5k
}
2406
2407
template<typename _RandomAccessIterator>
2408
_RandomAccessIterator
2409
__rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
2410
0
{
2411
0
typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
2412
0
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
2413
0
2414
0
const difference_type __m1 = __middle - __first;
2415
0
const difference_type __m2 = __last - __middle;
2416
0
if (__m1 == __m2)
2417
0
{
2418
0
_VSTD::swap_ranges(__first, __middle, __middle);
2419
0
return __middle;
2420
0
}
2421
0
const difference_type __g = _VSTD::__algo_gcd(__m1, __m2);
2422
0
for (_RandomAccessIterator __p = __first + __g; __p != __first;)
2423
0
{
2424
0
value_type __t(_VSTD::move(*--__p));
2425
0
_RandomAccessIterator __p1 = __p;
2426
0
_RandomAccessIterator __p2 = __p1 + __m1;
2427
0
do
2428
0
{
2429
0
*__p1 = _VSTD::move(*__p2);
2430
0
__p1 = __p2;
2431
0
const difference_type __d = __last - __p2;
2432
0
if (__m1 < __d)
2433
0
__p2 += __m1;
2434
0
else
2435
0
__p2 = __first + (__m1 - __d);
2436
0
} while (__p2 != __p);
2437
0
*__p1 = _VSTD::move(__t);
2438
0
}
2439
0
return __first + __m2;
2440
0
}
Unexecuted instantiation: std::__1::__wrap_iter<char*> std::__1::__rotate_gcd<std::__1::__wrap_iter<char*> >(std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>)
Unexecuted instantiation: std::__1::__wrap_iter<wchar_t*> std::__1::__rotate_gcd<std::__1::__wrap_iter<wchar_t*> >(std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>)
2441
2442
template <class _ForwardIterator>
2443
inline _LIBCPP_INLINE_VISIBILITY
2444
_ForwardIterator
2445
__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
2446
_VSTD::forward_iterator_tag)
2447
{
2448
typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type;
2449
if (_VSTD::is_trivially_move_assignable<value_type>::value)
2450
{
2451
if (_VSTD::next(__first) == __middle)
2452
return _VSTD::__rotate_left(__first, __last);
2453
}
2454
return _VSTD::__rotate_forward(__first, __middle, __last);
2455
}
2456
2457
template <class _BidirectionalIterator>
2458
inline _LIBCPP_INLINE_VISIBILITY
2459
_BidirectionalIterator
2460
__rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
2461
_VSTD::bidirectional_iterator_tag)
2462
{
2463
typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type;
2464
if (_VSTD::is_trivially_move_assignable<value_type>::value)
2465
{
2466
if (_VSTD::next(__first) == __middle)
2467
return _VSTD::__rotate_left(__first, __last);
2468
if (_VSTD::next(__middle) == __last)
2469
return _VSTD::__rotate_right(__first, __last);
2470
}
2471
return _VSTD::__rotate_forward(__first, __middle, __last);
2472
}
2473
2474
template <class _RandomAccessIterator>
2475
inline _LIBCPP_INLINE_VISIBILITY
2476
_RandomAccessIterator
2477
__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
2478
_VSTD::random_access_iterator_tag)
2479
0
{
2480
0
typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
2481
0
if (_VSTD::is_trivially_move_assignable<value_type>::value)
2482
0
{
2483
0
if (_VSTD::next(__first) == __middle)
2484
0
return _VSTD::__rotate_left(__first, __last);
2485
0
if (_VSTD::next(__middle) == __last)
2486
0
return _VSTD::__rotate_right(__first, __last);
2487
0
return _VSTD::__rotate_gcd(__first, __middle, __last);
2488
0
}
2489
0
return _VSTD::__rotate_forward(__first, __middle, __last);
2490
0
}
Unexecuted instantiation: std::__1::__wrap_iter<char*> std::__1::__rotate<std::__1::__wrap_iter<char*> >(std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>, std::__1::random_access_iterator_tag)
Unexecuted instantiation: std::__1::__wrap_iter<wchar_t*> std::__1::__rotate<std::__1::__wrap_iter<wchar_t*> >(std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>, std::__1::random_access_iterator_tag)
2491
2492
template <class _ForwardIterator>
2493
inline _LIBCPP_INLINE_VISIBILITY
2494
_ForwardIterator
2495
rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2496
0
{
2497
0
if (__first == __middle)
2498
0
return __last;
2499
0
if (__middle == __last)
2500
0
return __first;
2501
0
return _VSTD::__rotate(__first, __middle, __last,
2502
0
typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());
2503
0
}
Unexecuted instantiation: std::__1::__wrap_iter<char*> std::__1::rotate<std::__1::__wrap_iter<char*> >(std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>, std::__1::__wrap_iter<char*>)
Unexecuted instantiation: std::__1::__wrap_iter<wchar_t*> std::__1::rotate<std::__1::__wrap_iter<wchar_t*> >(std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>, std::__1::__wrap_iter<wchar_t*>)
2504
2505
// rotate_copy
2506
2507
template <class _ForwardIterator, class _OutputIterator>
2508
inline _LIBCPP_INLINE_VISIBILITY
2509
_OutputIterator
2510
rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
2511
{
2512
return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));
2513
}
2514
2515
// min_element
2516
2517
template <class _ForwardIterator, class _Compare>
2518
2519
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2520
_ForwardIterator
2521
min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2522
{
2523
static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value,
2524
"std::min_element requires a ForwardIterator");
2525
if (__first != __last)
2526
{
2527
_ForwardIterator __i = __first;
2528
while (++__i != __last)
2529
if (__comp(*__i, *__first))
2530
__first = __i;
2531
}
2532
return __first;
2533
}
2534
2535
template <class _ForwardIterator>
2536
2537
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2538
_ForwardIterator
2539
min_element(_ForwardIterator __first, _ForwardIterator __last)
2540
{
2541
return _VSTD::min_element(__first, __last,
2542
__less<typename iterator_traits<_ForwardIterator>::value_type>());
2543
}
2544
2545
// min
2546
2547
template <class _Tp, class _Compare>
2548
2549
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2550
const _Tp&
2551
min(const _Tp& __a, const _Tp& __b, _Compare __comp)
2552
3.54G
{
2553
3.54G
return __comp(__b, __a) ?  : ;
2554
3.54G
}
unsigned long const& std::__1::min<unsigned long, std::__1::__less<unsigned long, unsigned long> >(unsigned long const&, unsigned long const&, std::__1::__less<unsigned long, unsigned long>)
 Line Count Source 2552 3.28G { 2553 3.28G return __comp(__b, __a) ? __b957M : __a2.33G; 2554 3.28G }
long const& std::__1::min<long, std::__1::__less<long, long> >(long const&, long const&, std::__1::__less<long, long>)
 Line Count Source 2552 254M { 2553 254M return __comp(__b, __a) ? __b241M : __a12.4M; 2554 254M }
Unexecuted instantiation: char* const& std::__1::min<char*, std::__1::__less<char*, char*> >(char* const&, char* const&, std::__1::__less<char*, char*>)
2555
2556
template <class _Tp>
2557
2558
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2559
const _Tp&
2560
min(const _Tp& __a, const _Tp& __b)
2561
3.54G
{
2562
3.54G
return _VSTD::min(__a, __b, __less<_Tp>());
2563
3.54G
}
unsigned long const& std::__1::min<unsigned long>(unsigned long const&, unsigned long const&)
 Line Count Source 2561 3.28G { 2562 3.28G return _VSTD::min(__a, __b, __less<_Tp>()); 2563 3.28G }
long const& std::__1::min<long>(long const&, long const&)
 Line Count Source 2561 254M { 2562 254M return _VSTD::min(__a, __b, __less<_Tp>()); 2563 254M }
Unexecuted instantiation: char* const& std::__1::min<char*>(char* const&, char* const&)
2564
2565
#ifndef _LIBCPP_CXX03_LANG
2566
2567
template<class _Tp, class _Compare>
2568
2569
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2570
_Tp
2571
min(initializer_list<_Tp> __t, _Compare __comp)
2572
{
2573
return *_VSTD::min_element(__t.begin(), __t.end(), __comp);
2574
}
2575
2576
template<class _Tp>
2577
2578
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2579
_Tp
2580
min(initializer_list<_Tp> __t)
2581
{
2582
return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>());
2583
}
2584
2585
#endif  // _LIBCPP_CXX03_LANG
2586
2587
// max_element
2588
2589
template <class _ForwardIterator, class _Compare>
2590
2591
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2592
_ForwardIterator
2593
max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2594
{
2595
static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value,
2596
"std::max_element requires a ForwardIterator");
2597
if (__first != __last)
2598
{
2599
_ForwardIterator __i = __first;
2600
while (++__i != __last)
2601
if (__comp(*__first, *__i))
2602
__first = __i;
2603
}
2604
return __first;
2605
}
2606
2607
2608
template <class _ForwardIterator>
2609
2610
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2611
_ForwardIterator
2612
max_element(_ForwardIterator __first, _ForwardIterator __last)
2613
{
2614
return _VSTD::max_element(__first, __last,
2615
__less<typename iterator_traits<_ForwardIterator>::value_type>());
2616
}
2617
2618
// max
2619
2620
template <class _Tp, class _Compare>
2621
2622
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2623
const _Tp&
2624
max(const _Tp& __a, const _Tp& __b, _Compare __comp)
2625
617M
{
2626
617M
return __comp(__a, __b) ?  : ;
2627
617M
}
Unexecuted instantiation: long const& std::__1::max<long, std::__1::__less<long, long> >(long const&, long const&, std::__1::__less<long, long>)
unsigned long const& std::__1::max<unsigned long, std::__1::__less<unsigned long, unsigned long> >(unsigned long const&, unsigned long const&, std::__1::__less<unsigned long, unsigned long>)
 Line Count Source 2625 517M { 2626 517M return __comp(__a, __b) ? __b329M : __a187M; 2627 517M }
int const& std::__1::max<int, std::__1::__less<int, int> >(int const&, int const&, std::__1::__less<int, int>)
 Line Count Source 2625 66.9M { 2626 66.9M return __comp(__a, __b) ? __b8.90M : __a58.0M; 2627 66.9M }
char* const& std::__1::max<char*, std::__1::__less<char*, char*> >(char* const&, char* const&, std::__1::__less<char*, char*>)
 Line Count Source 2625 32.7M { 2626 32.7M return __comp(__a, __b) ? __b150 : __a32.7M; 2627 32.7M }
2628
2629
template <class _Tp>
2630
2631
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2632
const _Tp&
2633
max(const _Tp& __a, const _Tp& __b)
2634
617M
{
2635
617M
return _VSTD::max(__a, __b, __less<_Tp>());
2636
617M
}
Unexecuted instantiation: long const& std::__1::max<long>(long const&, long const&)
unsigned long const& std::__1::max<unsigned long>(unsigned long const&, unsigned long const&)
 Line Count Source 2634 517M { 2635 517M return _VSTD::max(__a, __b, __less<_Tp>()); 2636 517M }
int const& std::__1::max<int>(int const&, int const&)
 Line Count Source 2634 66.9M { 2635 66.9M return _VSTD::max(__a, __b, __less<_Tp>()); 2636 66.9M }
char* const& std::__1::max<char*>(char* const&, char* const&)
 Line Count Source 2634 32.7M { 2635 32.7M return _VSTD::max(__a, __b, __less<_Tp>()); 2636 32.7M }
2637
2638
#ifndef _LIBCPP_CXX03_LANG
2639
2640
template<class _Tp, class _Compare>
2641
2642
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2643
_Tp
2644
max(initializer_list<_Tp> __t, _Compare __comp)
2645
{
2646
return *_VSTD::max_element(__t.begin(), __t.end(), __comp);
2647
}
2648
2649
template<class _Tp>
2650
2651
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2652
_Tp
2653
max(initializer_list<_Tp> __t)
2654
{
2655
return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>());
2656
}
2657
2658
#endif  // _LIBCPP_CXX03_LANG
2659
2660
#if _LIBCPP_STD_VER > 14
2661
// clamp
2662
template<class _Tp, class _Compare>
2663
2664
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
2665
const _Tp&
2666
clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
2667
{
2668
_LIBCPP_ASSERT(!__comp(__hi, __lo), "Bad bounds passed to std::clamp");
2669
return __comp(__v, __lo) ? __lo : __comp(__hi, __v) ? __hi : __v;
2670
2671
}
2672
2673
template<class _Tp>
2674
2675
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
2676
const _Tp&
2677
clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi)
2678
{
2679
return _VSTD::clamp(__v, __lo, __hi, __less<_Tp>());
2680
}
2681
#endif
2682
2683
// minmax_element
2684
2685
template <class _ForwardIterator, class _Compare>
2686
2687
std::pair<_ForwardIterator, _ForwardIterator>
2688
minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2689
{
2690
static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value,
2691
"std::minmax_element requires a ForwardIterator");
2692
std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);
2693
if (__first != __last)
2694
{
2695
if (++__first != __last)
2696
{
2697
if (__comp(*__first, *__result.first))
2698
__result.first = __first;
2699
else
2700
__result.second = __first;
2701
while (++__first != __last)
2702
{
2703
_ForwardIterator __i = __first;
2704
if (++__first == __last)
2705
{
2706
if (__comp(*__i, *__result.first))
2707
__result.first = __i;
2708
else if (!__comp(*__i, *__result.second))
2709
__result.second = __i;
2710
break;
2711
}
2712
else
2713
{
2714
if (__comp(*__first, *__i))
2715
{
2716
if (__comp(*__first, *__result.first))
2717
__result.first = __first;
2718
if (!__comp(*__i, *__result.second))
2719
__result.second = __i;
2720
}
2721
else
2722
{
2723
if (__comp(*__i, *__result.first))
2724
__result.first = __i;
2725
if (!__comp(*__first, *__result.second))
2726
__result.second = __first;
2727
}
2728
}
2729
}
2730
}
2731
}
2732
return __result;
2733
}
2734
2735
template <class _ForwardIterator>
2736
2737
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2738
std::pair<_ForwardIterator, _ForwardIterator>
2739
minmax_element(_ForwardIterator __first, _ForwardIterator __last)
2740
{
2741
return _VSTD::minmax_element(__first, __last,
2742
__less<typename iterator_traits<_ForwardIterator>::value_type>());
2743
}
2744
2745
// minmax
2746
2747
template<class _Tp, class _Compare>
2748
2749
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2750
pair<const _Tp&, const _Tp&>
2751
minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
2752
{
2753
return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) :
2754
pair<const _Tp&, const _Tp&>(__a, __b);
2755
}
2756
2757
template<class _Tp>
2758
2759
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2760
pair<const _Tp&, const _Tp&>
2761
minmax(const _Tp& __a, const _Tp& __b)
2762
{
2763
return _VSTD::minmax(__a, __b, __less<_Tp>());
2764
}
2765
2766
#ifndef _LIBCPP_CXX03_LANG
2767
2768
template<class _Tp, class _Compare>
2769
2770
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2771
pair<_Tp, _Tp>
2772
minmax(initializer_list<_Tp> __t, _Compare __comp)
2773
{
2774
typedef typename initializer_list<_Tp>::const_iterator _Iter;
2775
_Iter __first = __t.begin();
2776
_Iter __last  = __t.end();
2777
std::pair<_Tp, _Tp> __result(*__first, *__first);
2778
2779
++__first;
2780
if (__t.size() % 2 == 0)
2781
{
2782
if (__comp(*__first,  __result.first))
2783
__result.first  = *__first;
2784
else
2785
__result.second = *__first;
2786
++__first;
2787
}
2788
2789
while (__first != __last)
2790
{
2791
_Tp __prev = *__first++;
2792
if (__comp(*__first, __prev)) {
2793
if ( __comp(*__first, __result.first)) __result.first  = *__first;
2794
if (!__comp(__prev, __result.second))  __result.second = __prev;
2795
}
2796
else {
2797
if ( __comp(__prev, __result.first))    __result.first  = __prev;
2798
if (!__comp(*__first, __result.second)) __result.second = *__first;
2799
}
2800
2801
__first++;
2802
}
2803
return __result;
2804
}
2805
2806
template<class _Tp>
2807
2808
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
2809
pair<_Tp, _Tp>
2810
minmax(initializer_list<_Tp> __t)
2811
{
2812
return _VSTD::minmax(__t, __less<_Tp>());
2813
}
2814
2815
#endif  // _LIBCPP_CXX03_LANG
2816
2817
// random_shuffle
2818
2819
// __independent_bits_engine
2820
2821
template <unsigned long long _Xp, size_t _Rp>
2822
struct __log2_imp
2823
{
2824
static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp
2825
: __log2_imp<_Xp, _Rp - 1>::value;
2826
};
2827
2828
template <unsigned long long _Xp>
2829
struct __log2_imp<_Xp, 0>
2830
{
2831
static const size_t value = 0;
2832
};
2833
2834
template <size_t _Rp>
2835
struct __log2_imp<0, _Rp>
2836
{
2837
static const size_t value = _Rp + 1;
2838
};
2839
2840
template <class _UIntType, _UIntType _Xp>
2841
struct __log2
2842
{
2843
static const size_t value = __log2_imp<_Xp,
2844
sizeof(_UIntType) * __CHAR_BIT__ - 1>::value;
2845
};
2846
2847
template<class _Engine, class _UIntType>
2848
class __independent_bits_engine
2849
{
2850
public:
2851
// types
2852
typedef _UIntType result_type;
2853
2854
private:
2855
typedef typename _Engine::result_type _Engine_result_type;
2856
typedef typename conditional
2857
<
2858
sizeof(_Engine_result_type) <= sizeof(result_type),
2859
result_type,
2860
_Engine_result_type
2861
>::type _Working_result_type;
2862
2863
_Engine& __e_;
2864
size_t __w_;
2865
size_t __w0_;
2866
size_t __n_;
2867
size_t __n0_;
2868
_Working_result_type __y0_;
2869
_Working_result_type __y1_;
2870
2871
2872
2873
#ifdef _LIBCPP_CXX03_LANG
2874
static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
2875
+ _Working_result_type(1);
2876
#else
2877
static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()
2878
+ _Working_result_type(1);
2879
#endif
2880
static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value;
2881
static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits;
2882
static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
2883
2884
public:
2885
// constructors and seeding functions
2886
__independent_bits_engine(_Engine& __e, size_t __w);
2887
2888
// generating functions
2889
result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
2890
2891
private:
2892
result_type __eval(false_type);
2893
result_type __eval(true_type);
2894
};
2895
2896
template<class _Engine, class _UIntType>
2897
__independent_bits_engine<_Engine, _UIntType>
2898
::__independent_bits_engine(_Engine& __e, size_t __w)
2899
: __e_(__e),
2900
__w_(__w)
2901
{
2902
__n_ = __w_ / __m + (__w_ % __m != 0);
2903
__w0_ = __w_ / __n_;
2904
if (_Rp == 0)
2905
__y0_ = _Rp;
2906
else if (__w0_ < _WDt)
2907
__y0_ = (_Rp >> __w0_) << __w0_;
2908
else
2909
__y0_ = 0;
2910
if (_Rp - __y0_ > __y0_ / __n_)
2911
{
2912
++__n_;
2913
__w0_ = __w_ / __n_;
2914
if (__w0_ < _WDt)
2915
__y0_ = (_Rp >> __w0_) << __w0_;
2916
else
2917
__y0_ = 0;
2918
}
2919
__n0_ = __n_ - __w_ % __n_;
2920
if (__w0_ < _WDt - 1)
2921
__y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1);
2922
else
2923
__y1_ = 0;
2924
__mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :
2925
_Engine_result_type(0);
2926
__mask1_ = __w0_ < _EDt - 1 ?
2927
_Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :
2928
_Engine_result_type(~0);
2929
}
2930
2931
template<class _Engine, class _UIntType>
2932
inline
2933
_UIntType
2934
__independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
2935
{
2936
2937
}
2938
2939
template<class _Engine, class _UIntType>
2940
_UIntType
2941
__independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
2942
{
2943
const size_t _WRt = numeric_limits<result_type>::digits;
2944
result_type _Sp = 0;
2945
for (size_t __k = 0; __k < __n0_; ++__k)
2946
{
2947
_Engine_result_type __u;
2948
do
2949
{
2950
__u = __e_() - _Engine::min();
2951
} while (__u >= __y0_);
2952
if (__w0_ < _WRt)
2953
_Sp <<= __w0_;
2954
else
2955
_Sp = 0;
2956
2957
}
2958
for (size_t __k = __n0_; __k < __n_; ++__k)
2959
{
2960
_Engine_result_type __u;
2961
do
2962
{
2963
__u = __e_() - _Engine::min();
2964
} while (__u >= __y1_);
2965
if (__w0_ < _WRt - 1)
2966
_Sp <<= __w0_ + 1;
2967
else
2968
_Sp = 0;
2969
2970
}
2971
return _Sp;
2972
}
2973
2974
// uniform_int_distribution
2975
2976
template<class _IntType = int>
2977
class uniform_int_distribution
2978
{
2979
public:
2980
// types
2981
typedef _IntType result_type;
2982
2983
class param_type
2984
{
2985
result_type __a_;
2986
result_type __b_;
2987
public:
2988
typedef uniform_int_distribution distribution_type;
2989
2990
explicit param_type(result_type __a = 0,
2991
result_type __b = numeric_limits<result_type>::max())
2992
: __a_(__a), __b_(__b) {}
2993
2994
result_type a() const {return __a_;}
2995
result_type b() const {return __b_;}
2996
2997
friend bool operator==(const param_type& __x, const param_type& __y)
2998
{return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
2999
friend bool operator!=(const param_type& __x, const param_type& __y)
3000
{return !(__x == __y);}
3001
};
3002
3003
private:
3004
param_type __p_;
3005
3006
public:
3007
// constructors and reset functions
3008
explicit uniform_int_distribution(result_type __a = 0,
3009
result_type __b = numeric_limits<result_type>::max())
3010
: __p_(param_type(__a, __b)) {}
3011
explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
3012
void reset() {}
3013
3014
// generating functions
3015
template<class _URNG> result_type operator()(_URNG& __g)
3016
{return (*this)(__g, __p_);}
3017
template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3018
3019
// property functions
3020
result_type a() const {return __p_.a();}
3021
result_type b() const {return __p_.b();}
3022
3023
param_type param() const {return __p_;}
3024
void param(const param_type& __p) {__p_ = __p;}
3025
3026
result_type min() const {return a();}
3027
result_type max() const {return b();}
3028
3029
friend bool operator==(const uniform_int_distribution& __x,
3030
const uniform_int_distribution& __y)
3031
{return __x.__p_ == __y.__p_;}
3032
friend bool operator!=(const uniform_int_distribution& __x,
3033
const uniform_int_distribution& __y)
3034
{return !(__x == __y);}
3035
};
3036
3037
template<class _IntType>
3038
template<class _URNG>
3039
typename uniform_int_distribution<_IntType>::result_type
3040
uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
3041
_LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
3042
{
3043
typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
3044
uint32_t, uint64_t>::type _UIntType;
3045
const _UIntType _Rp = _UIntType(__p.b()) - _UIntType(__p.a()) + _UIntType(1);
3046
if (_Rp == 1)
3047
return __p.a();
3048
const size_t _Dt = numeric_limits<_UIntType>::digits;
3049
typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
3050
if (_Rp == 0)
3051
return static_cast<result_type>(_Eng(__g, _Dt)());
3052
size_t __w = _Dt - __libcpp_clz(_Rp) - 1;
3053
if ((_Rp & (std::numeric_limits<_UIntType>::max() >> (_Dt - __w))) != 0)
3054
++__w;
3055
_Eng __e(__g, __w);
3056
_UIntType __u;
3057
do
3058
{
3059
__u = __e();
3060
} while (__u >= _Rp);
3061
return static_cast<result_type>(__u + __p.a());
3062
}
3063
3064
#if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \
3065
|| defined(_LIBCPP_BUILDING_LIBRARY)
3066
class _LIBCPP_TYPE_VIS __rs_default;
3067
3068
_LIBCPP_FUNC_VIS __rs_default __rs_get();
3069
3070
class _LIBCPP_TYPE_VIS __rs_default
3071
{
3072
static unsigned __c_;
3073
3074
__rs_default();
3075
public:
3076
typedef uint_fast32_t result_type;
3077
3078
static const result_type _Min = 0;
3079
static const result_type _Max = 0xFFFFFFFF;
3080
3081
__rs_default(const __rs_default&);
3082
~__rs_default();
3083
3084
result_type operator()();
3085
3086
0
static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
3087
0
static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
3088
3089
friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
3090
};
3091
3092
_LIBCPP_FUNC_VIS __rs_default __rs_get();
3093
3094
template <class _RandomAccessIterator>
3095
_LIBCPP_DEPRECATED_IN_CXX14 void
3096
random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
3097
{
3098
typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3099
typedef uniform_int_distribution<ptrdiff_t> _Dp;
3100
typedef typename _Dp::param_type _Pp;
3101
difference_type __d = __last - __first;
3102
if (__d > 1)
3103
{
3104
_Dp __uid;
3105
__rs_default __g = __rs_get();
3106
for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
3107
{
3108
difference_type __i = __uid(__g, _Pp(0, __d));
3109
if (__i != difference_type(0))
3110
swap(*__first, *(__first + __i));
3111
}
3112
}
3113
}
3114
3115
template <class _RandomAccessIterator, class _RandomNumberGenerator>
3116
_LIBCPP_DEPRECATED_IN_CXX14 void
3117
random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3118
#ifndef _LIBCPP_CXX03_LANG
3119
_RandomNumberGenerator&& __rand)
3120
#else
3121
_RandomNumberGenerator& __rand)
3122
#endif
3123
{
3124
typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3125
difference_type __d = __last - __first;
3126
if (__d > 1)
3127
{
3128
for (--__last; __first < __last; ++__first, (void) --__d)
3129
{
3130
difference_type __i = __rand(__d);
3131
if (__i != difference_type(0))
3132
swap(*__first, *(__first + __i));
3133
}
3134
}
3135
}
3136
#endif
3137
3138
template <class _PopulationIterator, class _SampleIterator, class _Distance,
3139
class _UniformRandomNumberGenerator>
3140
_LIBCPP_INLINE_VISIBILITY
3141
_SampleIterator __sample(_PopulationIterator __first,
3142
_PopulationIterator __last, _SampleIterator __output_iter,
3143
_Distance __n,
3144
_UniformRandomNumberGenerator & __g,
3145
input_iterator_tag) {
3146
3147
_Distance __k = 0;
3148
for (; __first != __last && __k < __n; ++__first, (void) ++__k)
3149
__output_iter[__k] = *__first;
3150
_Distance __sz = __k;
3151
for (; __first != __last; ++__first, (void) ++__k) {
3152
_Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g);
3153
if (__r < __sz)
3154
__output_iter[__r] = *__first;
3155
}
3156
return __output_iter + _VSTD::min(__n, __k);
3157
}
3158
3159
template <class _PopulationIterator, class _SampleIterator, class _Distance,
3160
class _UniformRandomNumberGenerator>
3161
_LIBCPP_INLINE_VISIBILITY
3162
_SampleIterator __sample(_PopulationIterator __first,
3163
_PopulationIterator __last, _SampleIterator __output_iter,
3164
_Distance __n,
3165
_UniformRandomNumberGenerator& __g,
3166
forward_iterator_tag) {
3167
_Distance __unsampled_sz = _VSTD::distance(__first, __last);
3168
for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
3169
_Distance __r =
3170
_VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g);
3171
if (__r < __n) {
3172
*__output_iter++ = *__first;
3173
--__n;
3174
}
3175
}
3176
return __output_iter;
3177
}
3178
3179
template <class _PopulationIterator, class _SampleIterator, class _Distance,
3180
class _UniformRandomNumberGenerator>
3181
_LIBCPP_INLINE_VISIBILITY
3182
_SampleIterator __sample(_PopulationIterator __first,
3183
_PopulationIterator __last, _SampleIterator __output_iter,
3184
_Distance __n, _UniformRandomNumberGenerator& __g) {
3185
typedef typename iterator_traits<_PopulationIterator>::iterator_category
3186
_PopCategory;
3187
typedef typename iterator_traits<_PopulationIterator>::difference_type
3188
_Difference;
3189
static_assert(__is_cpp17_forward_iterator<_PopulationIterator>::value ||
3190
__is_cpp17_random_access_iterator<_SampleIterator>::value,
3191
"SampleIterator must meet the requirements of RandomAccessIterator");
3192
typedef typename common_type<_Distance, _Difference>::type _CommonType;
3193
_LIBCPP_ASSERT(__n >= 0, "N must be a positive number.");
3194
return _VSTD::__sample(
3195
__first, __last, __output_iter, _CommonType(__n),
3196
__g, _PopCategory());
3197
}
3198
3199
#if _LIBCPP_STD_VER > 14
3200
template <class _PopulationIterator, class _SampleIterator, class _Distance,
3201
class _UniformRandomNumberGenerator>
3202
inline _LIBCPP_INLINE_VISIBILITY
3203
_SampleIterator sample(_PopulationIterator __first,
3204
_PopulationIterator __last, _SampleIterator __output_iter,
3205
_Distance __n, _UniformRandomNumberGenerator&& __g) {
3206
return _VSTD::__sample(__first, __last, __output_iter, __n, __g);
3207
}
3208
#endif // _LIBCPP_STD_VER > 14
3209
3210
template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
3211
void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3212
_UniformRandomNumberGenerator&& __g)
3213
{
3214
typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3215
typedef uniform_int_distribution<ptrdiff_t> _Dp;
3216
typedef typename _Dp::param_type _Pp;
3217
difference_type __d = __last - __first;
3218
if (__d > 1)
3219
{
3220
_Dp __uid;
3221
for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
3222
{
3223
difference_type __i = __uid(__g, _Pp(0, __d));
3224
if (__i != difference_type(0))
3225
swap(*__first, *(__first + __i));
3226
}
3227
}
3228
}
3229
3230
template <class _InputIterator, class _Predicate>
3231
3232
is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3233
{
3234
for (; __first != __last; ++__first)
3235
if (!__pred(*__first))
3236
break;
3237
if ( __first == __last )
3238
return true;
3239
++__first;
3240
for (; __first != __last; ++__first)
3241
if (__pred(*__first))
3242
return false;
3243
return true;
3244
}
3245
3246
// partition
3247
3248
template <class _Predicate, class _ForwardIterator>
3249
_ForwardIterator
3250
__partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
3251
{
3252
while (true)
3253
{
3254
if (__first == __last)
3255
return __first;
3256
if (!__pred(*__first))
3257
break;
3258
++__first;
3259
}
3260
for (_ForwardIterator __p = __first; ++__p != __last;)
3261
{
3262
if (__pred(*__p))
3263
{
3264
swap(*__first, *__p);
3265
++__first;
3266
}
3267
}
3268
return __first;
3269
}
3270
3271
template <class _Predicate, class _BidirectionalIterator>
3272
_BidirectionalIterator
3273
__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3274
bidirectional_iterator_tag)
3275
{
3276
while (true)
3277
{
3278
while (true)
3279
{
3280
if (__first == __last)
3281
return __first;
3282
if (!__pred(*__first))
3283
break;
3284
++__first;
3285
}
3286
do
3287
{
3288
if (__first == --__last)
3289
return __first;
3290
} while (!__pred(*__last));
3291
swap(*__first, *__last);
3292
++__first;
3293
}
3294
}
3295
3296
template <class _ForwardIterator, class _Predicate>
3297
inline _LIBCPP_INLINE_VISIBILITY
3298
_ForwardIterator
3299
partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3300
{
3301
3302
(__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3303
}
3304
3305
// partition_copy
3306
3307
template <class _InputIterator, class _OutputIterator1,
3308
class _OutputIterator2, class _Predicate>
3309
_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_OutputIterator1, _OutputIterator2>
3310
partition_copy(_InputIterator __first, _InputIterator __last,
3311
_OutputIterator1 __out_true, _OutputIterator2 __out_false,
3312
_Predicate __pred)
3313
{
3314
for (; __first != __last; ++__first)
3315
{
3316
if (__pred(*__first))
3317
{
3318
*__out_true = *__first;
3319
++__out_true;
3320
}
3321
else
3322
{
3323
*__out_false = *__first;
3324
++__out_false;
3325
}
3326
}
3327
return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
3328
}
3329
3330
// partition_point
3331
3332
template<class _ForwardIterator, class _Predicate>
3333
_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
3334
partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3335
{
3336
typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3337
difference_type __len = _VSTD::distance(__first, __last);
3338
while (__len != 0)
3339
{
3340
difference_type __l2 = _VSTD::__half_positive(__len);
3341
_ForwardIterator __m = __first;
3342
3343
if (__pred(*__m))
3344
{
3345
__first = ++__m;
3346
__len -= __l2 + 1;
3347
}
3348
else
3349
__len = __l2;
3350
}
3351
return __first;
3352
}
3353
3354
// stable_partition
3355
3356
template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
3357
_ForwardIterator
3358
__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3359
_Distance __len, _Pair __p, forward_iterator_tag __fit)
3360
{
3361
// *__first is known to be false
3362
// __len >= 1
3363
if (__len == 1)
3364
return __first;
3365
if (__len == 2)
3366
{
3367
_ForwardIterator __m = __first;
3368
if (__pred(*++__m))
3369
{
3370
swap(*__first, *__m);
3371
return __m;
3372
}
3373
return __first;
3374
}
3375
if (__len <= __p.second)
3376
{   // The buffer is big enough to use
3377
typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3378
__destruct_n __d(0);
3379
unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3380
// Move the falses into the temporary buffer, and the trues to the front of the line
3381
// Update __first to always point to the end of the trues
3382
value_type* __t = __p.first;
3383
::new(__t) value_type(_VSTD::move(*__first));
3384
__d.__incr((value_type*)0);
3385
++__t;
3386
_ForwardIterator __i = __first;
3387
while (++__i != __last)
3388
{
3389
if (__pred(*__i))
3390
{
3391
*__first = _VSTD::move(*__i);
3392
++__first;
3393
}
3394
else
3395
{
3396
::new(__t) value_type(_VSTD::move(*__i));
3397
__d.__incr((value_type*)0);
3398
++__t;
3399
}
3400
}
3401
// All trues now at start of range, all falses in buffer
3402
// Move falses back into range, but don't mess up __first which points to first false
3403
__i = __first;
3404
for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i)
3405
*__i = _VSTD::move(*__t2);
3406
// __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3407
return __first;
3408
}
3409
// Else not enough buffer, do in place
3410
// __len >= 3
3411
_ForwardIterator __m = __first;
3412
_Distance __len2 = __len / 2;  // __len2 >= 2
3413
3414
// recurse on [__first, __m), *__first know to be false
3415
// F?????????????????
3416
// f       m         l
3417
3418
_ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
3419
// TTTFFFFF??????????
3420
// f  ff   m         l
3421
// recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3422
_ForwardIterator __m1 = __m;
3423
_ForwardIterator __second_false = __last;
3424
_Distance __len_half = __len - __len2;
3425
while (__pred(*__m1))
3426
{
3427
if (++__m1 == __last)
3428
goto __second_half_done;
3429
--__len_half;
3430
}
3431
// TTTFFFFFTTTF??????
3432
// f  ff   m  m1     l
3433
__second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
3434
__second_half_done:
3435
// TTTFFFFFTTTTTFFFFF
3436
// f  ff   m    sf   l
3437
return _VSTD::rotate(__first_false, __m, __second_false);
3438
// TTTTTTTTFFFFFFFFFF
3439
//         |
3440
}
3441
3442
struct __return_temporary_buffer
3443
{
3444
template <class _Tp>
3445
_LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}
3446
};
3447
3448
template <class _Predicate, class _ForwardIterator>
3449
_ForwardIterator
3450
__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3451
forward_iterator_tag)
3452
{
3453
const unsigned __alloc_limit = 3;  // might want to make this a function of trivial assignment
3454
// Either prove all true and return __first or point to first false
3455
while (true)
3456
{
3457
if (__first == __last)
3458
return __first;
3459
if (!__pred(*__first))
3460
break;
3461
++__first;
3462
}
3463
// We now have a reduced range [__first, __last)
3464
// *__first is known to be false
3465
typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3466
typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3467
difference_type __len = _VSTD::distance(__first, __last);
3468
pair<value_type*, ptrdiff_t> __p(0, 0);
3469
unique_ptr<value_type, __return_temporary_buffer> __h;
3470
if (__len >= __alloc_limit)
3471
{
3472
__p = _VSTD::get_temporary_buffer<value_type>(__len);
3473
__h.reset(__p.first);
3474
}
3475
3476
(__first, __last, __pred, __len, __p, forward_iterator_tag());
3477
}
3478
3479
template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
3480
_BidirectionalIterator
3481
__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3482
_Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
3483
{
3484
// *__first is known to be false
3485
// *__last is known to be true
3486
// __len >= 2
3487
if (__len == 2)
3488
{
3489
swap(*__first, *__last);
3490
return __last;
3491
}
3492
if (__len == 3)
3493
{
3494
_BidirectionalIterator __m = __first;
3495
if (__pred(*++__m))
3496
{
3497
swap(*__first, *__m);
3498
swap(*__m, *__last);
3499
return __last;
3500
}
3501
swap(*__m, *__last);
3502
swap(*__first, *__m);
3503
return __m;
3504
}
3505
if (__len <= __p.second)
3506
{   // The buffer is big enough to use
3507
typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3508
__destruct_n __d(0);
3509
unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3510
// Move the falses into the temporary buffer, and the trues to the front of the line
3511
// Update __first to always point to the end of the trues
3512
value_type* __t = __p.first;
3513
::new(__t) value_type(_VSTD::move(*__first));
3514
__d.__incr((value_type*)0);
3515
++__t;
3516
_BidirectionalIterator __i = __first;
3517
while (++__i != __last)
3518
{
3519
if (__pred(*__i))
3520
{
3521
*__first = _VSTD::move(*__i);
3522
++__first;
3523
}
3524
else
3525
{
3526
::new(__t) value_type(_VSTD::move(*__i));
3527
__d.__incr((value_type*)0);
3528
++__t;
3529
}
3530
}
3531
// move *__last, known to be true
3532
*__first = _VSTD::move(*__i);
3533
__i = ++__first;
3534
// All trues now at start of range, all falses in buffer
3535
// Move falses back into range, but don't mess up __first which points to first false
3536
for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i)
3537
*__i = _VSTD::move(*__t2);
3538
// __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3539
return __first;
3540
}
3541
// Else not enough buffer, do in place
3542
// __len >= 4
3543
_BidirectionalIterator __m = __first;
3544
_Distance __len2 = __len / 2;  // __len2 >= 2
3545
3546
// recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
3547
// F????????????????T
3548
// f       m        l
3549
_BidirectionalIterator __m1 = __m;
3550
_BidirectionalIterator __first_false = __first;
3551
_Distance __len_half = __len2;
3552
while (!__pred(*--__m1))
3553
{
3554
if (__m1 == __first)
3555
goto __first_half_done;
3556
--__len_half;
3557
}
3558
// F???TFFF?????????T
3559
// f   m1  m        l
3560
3561
__first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3562
__first_half_done:
3563
// TTTFFFFF?????????T
3564
// f  ff   m        l
3565
// recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3566
__m1 = __m;
3567
_BidirectionalIterator __second_false = __last;
3568
++__second_false;
3569
__len_half = __len - __len2;
3570
while (__pred(*__m1))
3571
{
3572
if (++__m1 == __last)
3573
goto __second_half_done;
3574
--__len_half;
3575
}
3576
// TTTFFFFFTTTF?????T
3577
// f  ff   m  m1    l
3578
__second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
3579
__second_half_done:
3580
// TTTFFFFFTTTTTFFFFF
3581
// f  ff   m    sf  l
3582
return _VSTD::rotate(__first_false, __m, __second_false);
3583
// TTTTTTTTFFFFFFFFFF
3584
//         |
3585
}
3586
3587
template <class _Predicate, class _BidirectionalIterator>
3588
_BidirectionalIterator
3589
__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3590
bidirectional_iterator_tag)
3591
{
3592
typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3593
typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3594
const difference_type __alloc_limit = 4;  // might want to make this a function of trivial assignment
3595
// Either prove all true and return __first or point to first false
3596
while (true)
3597
{
3598
if (__first == __last)
3599
return __first;
3600
if (!__pred(*__first))
3601
break;
3602
++__first;
3603
}
3604
// __first points to first false, everything prior to __first is already set.
3605
// Either prove [__first, __last) is all false and return __first, or point __last to last true
3606
do
3607
{
3608
if (__first == --__last)
3609
return __first;
3610
} while (!__pred(*__last));
3611
// We now have a reduced range [__first, __last]
3612
// *__first is known to be false
3613
// *__last is known to be true
3614
// __len >= 2
3615
difference_type __len = _VSTD::distance(__first, __last) + 1;
3616
pair<value_type*, ptrdiff_t> __p(0, 0);
3617
unique_ptr<value_type, __return_temporary_buffer> __h;
3618
if (__len >= __alloc_limit)
3619
{
3620
__p = _VSTD::get_temporary_buffer<value_type>(__len);
3621
__h.reset(__p.first);
3622
}
3623
3624
(__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3625
}
3626
3627
template <class _ForwardIterator, class _Predicate>
3628
inline _LIBCPP_INLINE_VISIBILITY
3629
_ForwardIterator
3630
stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3631
{
3632
3633
(__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3634
}
3635
3636
// is_sorted_until
3637
3638
template <class _ForwardIterator, class _Compare>
3639
3640
is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3641
{
3642
if (__first != __last)
3643
{
3644
_ForwardIterator __i = __first;
3645
while (++__i != __last)
3646
{
3647
if (__comp(*__i, *__first))
3648
return __i;
3649
__first = __i;
3650
}
3651
}
3652
return __last;
3653
}
3654
3655
template<class _ForwardIterator>
3656
3657
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3658
_ForwardIterator
3659
is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3660
{
3661
return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3662
}
3663
3664
// is_sorted
3665
3666
template <class _ForwardIterator, class _Compare>
3667
3668
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3669
bool
3670
is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3671
{
3672
return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
3673
}
3674
3675
template<class _ForwardIterator>
3676
3677
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3678
bool
3679
is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3680
{
3681
return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3682
}
3683
3684
// sort
3685
3686
// stable, 2-3 compares, 0-2 swaps
3687
3688
template <class _Compare, class _ForwardIterator>
3689
unsigned
3690
__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
3691
0
{
3692
0
unsigned __r = 0;
3693
0
if (!__c(*__y, *__x))          // if x <= y
3694
0
{
3695
0
if (!__c(*__z, *__y))      // if y <= z
3696
0
return __r;            // x <= y && y <= z
3697
0
// x <= y && y > z
3698
0
swap(*__y, *__z);          // x <= z && y < z
3699
0
__r = 1;
3700
0
if (__c(*__y, *__x))       // if x > y
3701
0
{
3702
0
swap(*__x, *__y);      // x < y && y <= z
3703
0
__r = 2;
3704
0
}
3705
0
return __r;                // x <= y && y < z
3706
0
}
3707
0
if (__c(*__z, *__y))           // x > y, if y > z
3708
0
{
3709
0
swap(*__x, *__z);          // x < y && y < z
3710
0
__r = 1;
3711
0
return __r;
3712
0
}
3713
0
swap(*__x, *__y);              // x > y && y <= z
3714
0
__r = 1;                       // x < y && x <= z
3715
0
if (__c(*__z, *__y))           // if y > z
3716
0
{
3717
0
swap(*__y, *__z);          // x <= y && y < z
3718
0
__r = 2;
3719
0
}
3720
0
return __r;
3721
0
}                                  // x <= y && y <= z
Unexecuted instantiation: unsigned int std::__1::__sort3<std::__1::__less<char, char>&, char*>(char*, char*, char*, std::__1::__less<char, char>&)
Unexecuted instantiation: unsigned int std::__1::__sort3<std::__1::__less<wchar_t, wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, wchar_t*, std::__1::__less<wchar_t, wchar_t>&)
Unexecuted instantiation: unsigned int std::__1::__sort3<std::__1::__less<signed char, signed char>&, signed char*>(signed char*, signed char*, signed char*, std::__1::__less<signed char, signed char>&)
Unexecuted instantiation: unsigned int std::__1::__sort3<std::__1::__less<unsigned char, unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, unsigned char*, std::__1::__less<unsigned char, unsigned char>&)
Unexecuted instantiation: unsigned int std::__1::__sort3<std::__1::__less<short, short>&, short*>(short*, short*, short*, std::__1::__less<short, short>&)
Unexecuted instantiation: unsigned int std::__1::__sort3<std::__1::__less<unsigned short, unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, unsigned short*, std::__1::__less<unsigned short, unsigned short>&)
Unexecuted instantiation: unsigned int std::__1::__sort3<std::__1::__less<int, int>&, int*>(int*, int*, int*, std::__1::__less<int, int>&)
Unexecuted instantiation: unsigned int std::__1::__sort3<std::__1::__less<unsigned int, unsigned int>&, unsigned int*>(unsigned int*, unsigned int*, unsigned int*, std::__1::__less<unsigned int, unsigned int>&)
Unexecuted instantiation: unsigned int std::__1::__sort3<std::__1::__less<long, long>&, long*>(long*, long*, long*, std::__1::__less<long, long>&)
Unexecuted instantiation: unsigned int std::__1::__sort3<std::__1::__less<unsigned long, unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, unsigned long*, std::__1::__less<unsigned long, unsigned long>&)
Unexecuted instantiation: unsigned int std::__1::__sort3<std::__1::__less<long long, long long>&, long long*>(long long*, long long*, long long*, std::__1::__less<long long, long long>&)
Unexecuted instantiation: unsigned int std::__1::__sort3<std::__1::__less<unsigned long long, unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, unsigned long long*, std::__1::__less<unsigned long long, unsigned long long>&)
Unexecuted instantiation: unsigned int std::__1::__sort3<std::__1::__less<float, float>&, float*>(float*, float*, float*, std::__1::__less<float, float>&)
Unexecuted instantiation: unsigned int std::__1::__sort3<std::__1::__less<double, double>&, double*>(double*, double*, double*, std::__1::__less<double, double>&)
Unexecuted instantiation: unsigned int std::__1::__sort3<std::__1::__less<long double, long double>&, long double*>(long double*, long double*, long double*, std::__1::__less<long double, long double>&)
3722
3723
// stable, 3-6 compares, 0-5 swaps
3724
3725
template <class _Compare, class _ForwardIterator>
3726
unsigned
3727
__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3728
_ForwardIterator __x4, _Compare __c)
3729
0
{
3730
0
unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
3731
0
if (__c(*__x4, *__x3))
3732
0
{
3733
0
swap(*__x3, *__x4);
3734
0
++__r;
3735
0
if (__c(*__x3, *__x2))
3736
0
{
3737
0
swap(*__x2, *__x3);
3738
0
++__r;
3739
0
if (__c(*__x2, *__x1))
3740
0
{
3741
0
swap(*__x1, *__x2);
3742
0
++__r;
3743
0
}
3744
0
}
3745
0
}
3746
0
return __r;
3747
0
}
Unexecuted instantiation: unsigned int std::__1::__sort4<std::__1::__less<char, char>&, char*>(char*, char*, char*, char*, std::__1::__less<char, char>&)
Unexecuted instantiation: unsigned int std::__1::__sort4<std::__1::__less<wchar_t, wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, wchar_t*, wchar_t*, std::__1::__less<wchar_t, wchar_t>&)
Unexecuted instantiation: unsigned int std::__1::__sort4<std::__1::__less<signed char, signed char>&, signed char*>(signed char*, signed char*, signed char*, signed char*, std::__1::__less<signed char, signed char>&)
Unexecuted instantiation: unsigned int std::__1::__sort4<std::__1::__less<unsigned char, unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, unsigned char*, unsigned char*, std::__1::__less<unsigned char, unsigned char>&)
Unexecuted instantiation: unsigned int std::__1::__sort4<std::__1::__less<short, short>&, short*>(short*, short*, short*, short*, std::__1::__less<short, short>&)
Unexecuted instantiation: unsigned int std::__1::__sort4<std::__1::__less<unsigned short, unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, unsigned short*, unsigned short*, std::__1::__less<unsigned short, unsigned short>&)
Unexecuted instantiation: unsigned int std::__1::__sort4<std::__1::__less<int, int>&, int*>(int*, int*, int*, int*, std::__1::__less<int, int>&)
Unexecuted instantiation: unsigned int std::__1::__sort4<std::__1::__less<unsigned int, unsigned int>&, unsigned int*>(unsigned int*, unsigned int*, unsigned int*, unsigned int*, std::__1::__less<unsigned int, unsigned int>&)
Unexecuted instantiation: unsigned int std::__1::__sort4<std::__1::__less<long, long>&, long*>(long*, long*, long*, long*, std::__1::__less<long, long>&)
Unexecuted instantiation: unsigned int std::__1::__sort4<std::__1::__less<unsigned long, unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, unsigned long*, unsigned long*, std::__1::__less<unsigned long, unsigned long>&)
Unexecuted instantiation: unsigned int std::__1::__sort4<std::__1::__less<long long, long long>&, long long*>(long long*, long long*, long long*, long long*, std::__1::__less<long long, long long>&)
Unexecuted instantiation: unsigned int std::__1::__sort4<std::__1::__less<unsigned long long, unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, unsigned long long*, unsigned long long*, std::__1::__less<unsigned long long, unsigned long long>&)
Unexecuted instantiation: unsigned int std::__1::__sort4<std::__1::__less<float, float>&, float*>(float*, float*, float*, float*, std::__1::__less<float, float>&)
Unexecuted instantiation: unsigned int std::__1::__sort4<std::__1::__less<double, double>&, double*>(double*, double*, double*, double*, std::__1::__less<double, double>&)
Unexecuted instantiation: unsigned int std::__1::__sort4<std::__1::__less<long double, long double>&, long double*>(long double*, long double*, long double*, long double*, std::__1::__less<long double, long double>&)
3748
3749
// stable, 4-10 compares, 0-9 swaps
3750
3751
template <class _Compare, class _ForwardIterator>
3752
_LIBCPP_HIDDEN
3753
unsigned
3754
__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3755
_ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
3756
0
{
3757
0
unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
3758
0
if (__c(*__x5, *__x4))
3759
0
{
3760
0
swap(*__x4, *__x5);
3761
0
++__r;
3762
0
if (__c(*__x4, *__x3))
3763
0
{
3764
0
swap(*__x3, *__x4);
3765
0
++__r;
3766
0
if (__c(*__x3, *__x2))
3767
0
{
3768
0
swap(*__x2, *__x3);
3769
0
++__r;
3770
0
if (__c(*__x2, *__x1))
3771
0
{
3772
0
swap(*__x1, *__x2);
3773
0
++__r;
3774
0
}
3775
0
}
3776
0
}
3777
0
}
3778
0
return __r;
3779
0
}
Unexecuted instantiation: unsigned int std::__1::__sort5<std::__1::__less<long double, long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, std::__1::__less<long double, long double>&)
Unexecuted instantiation: unsigned int std::__1::__sort5<std::__1::__less<char, char>&, char*>(char*, char*, char*, char*, char*, std::__1::__less<char, char>&)
Unexecuted instantiation: unsigned int std::__1::__sort5<std::__1::__less<wchar_t, wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, wchar_t*, wchar_t*, wchar_t*, std::__1::__less<wchar_t, wchar_t>&)
Unexecuted instantiation: unsigned int std::__1::__sort5<std::__1::__less<signed char, signed char>&, signed char*>(signed char*, signed char*, signed char*, signed char*, signed char*, std::__1::__less<signed char, signed char>&)
Unexecuted instantiation: unsigned int std::__1::__sort5<std::__1::__less<unsigned char, unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, unsigned char*, unsigned char*, unsigned char*, std::__1::__less<unsigned char, unsigned char>&)
Unexecuted instantiation: unsigned int std::__1::__sort5<std::__1::__less<short, short>&, short*>(short*, short*, short*, short*, short*, std::__1::__less<short, short>&)
Unexecuted instantiation: unsigned int std::__1::__sort5<std::__1::__less<unsigned short, unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, unsigned short*, unsigned short*, unsigned short*, std::__1::__less<unsigned short, unsigned short>&)
Unexecuted instantiation: unsigned int std::__1::__sort5<std::__1::__less<int, int>&, int*>(int*, int*, int*, int*, int*, std::__1::__less<int, int>&)
Unexecuted instantiation: unsigned int std::__1::__sort5<std::__1::__less<unsigned int, unsigned int>&, unsigned int*>(unsigned int*, unsigned int*, unsigned int*, unsigned int*, unsigned int*, std::__1::__less<unsigned int, unsigned int>&)
Unexecuted instantiation: unsigned int std::__1::__sort5<std::__1::__less<long, long>&, long*>(long*, long*, long*, long*, long*, std::__1::__less<long, long>&)
Unexecuted instantiation: unsigned int std::__1::__sort5<std::__1::__less<unsigned long, unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, unsigned long*, unsigned long*, unsigned long*, std::__1::__less<unsigned long, unsigned long>&)
Unexecuted instantiation: unsigned int std::__1::__sort5<std::__1::__less<long long, long long>&, long long*>(long long*, long long*, long long*, long long*, long long*, std::__1::__less<long long, long long>&)
Unexecuted instantiation: unsigned int std::__1::__sort5<std::__1::__less<unsigned long long, unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, unsigned long long*, unsigned long long*, unsigned long long*, std::__1::__less<unsigned long long, unsigned long long>&)
Unexecuted instantiation: unsigned int std::__1::__sort5<std::__1::__less<float, float>&, float*>(float*, float*, float*, float*, float*, std::__1::__less<float, float>&)
Unexecuted instantiation: unsigned int std::__1::__sort5<std::__1::__less<double, double>&, double*>(double*, double*, double*, double*, double*, std::__1::__less<double, double>&)
3780
3781
// Assumes size > 0
3782
template <class _Compare, class _BirdirectionalIterator>
3783
void
3784
__selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3785
{
3786
_BirdirectionalIterator __lm1 = __last;
3787
for (--__lm1; __first != __lm1; ++__first)
3788
{
3789
_BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator,
3790
3791
(__first, __last, __comp);
3792
if (__i != __first)
3793
swap(*__first, *__i);
3794
}
3795
}
3796
3797
template <class _Compare, class _BirdirectionalIterator>
3798
void
3799
__insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3800
{
3801
typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3802
if (__first != __last)
3803
{
3804
_BirdirectionalIterator __i = __first;
3805
for (++__i; __i != __last; ++__i)
3806
{
3807
_BirdirectionalIterator __j = __i;
3808
value_type __t(_VSTD::move(*__j));
3809
for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t,  *--__k); --__j)
3810
*__j = _VSTD::move(*__k);
3811
*__j = _VSTD::move(__t);
3812
}
3813
}
3814
}
3815
3816
template <class _Compare, class _RandomAccessIterator>
3817
void
3818
__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3819
0
{
3820
0
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3821
0
_RandomAccessIterator __j = __first+2;
3822
0
__sort3<_Compare>(__first, __first+1, __j, __comp);
3823
0
for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3824
0
{
3825
0
if (__comp(*__i, *__j))
3826
0
{
3827
0
value_type __t(_VSTD::move(*__i));
3828
0
_RandomAccessIterator __k = __j;
3829
0
__j = __i;
3830
0
do
3831
0
{
3832
0
*__j = _VSTD::move(*__k);
3833
0
__j = __k;
3834
0
} while (__j != __first && __comp(__t, *--__k));
3835
0
*__j = _VSTD::move(__t);
3836
0
}
3837
0
__j = __i;
3838
0
}
3839
0
}
Unexecuted instantiation: void std::__1::__insertion_sort_3<std::__1::__less<char, char>&, char*>(char*, char*, std::__1::__less<char, char>&)
Unexecuted instantiation: void std::__1::__insertion_sort_3<std::__1::__less<wchar_t, wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, std::__1::__less<wchar_t, wchar_t>&)
Unexecuted instantiation: void std::__1::__insertion_sort_3<std::__1::__less<signed char, signed char>&, signed char*>(signed char*, signed char*, std::__1::__less<signed char, signed char>&)
Unexecuted instantiation: void std::__1::__insertion_sort_3<std::__1::__less<unsigned char, unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, std::__1::__less<unsigned char, unsigned char>&)
Unexecuted instantiation: void std::__1::__insertion_sort_3<std::__1::__less<short, short>&, short*>(short*, short*, std::__1::__less<short, short>&)
Unexecuted instantiation: void std::__1::__insertion_sort_3<std::__1::__less<unsigned short, unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, std::__1::__less<unsigned short, unsigned short>&)
Unexecuted instantiation: void std::__1::__insertion_sort_3<std::__1::__less<int, int>&, int*>(int*, int*, std::__1::__less<int, int>&)
Unexecuted instantiation: void std::__1::__insertion_sort_3<std::__1::__less<unsigned int, unsigned int>&, unsigned int*>(unsigned int*, unsigned int*, std::__1::__less<unsigned int, unsigned int>&)
Unexecuted instantiation: void std::__1::__insertion_sort_3<std::__1::__less<long, long>&, long*>(long*, long*, std::__1::__less<long, long>&)
Unexecuted instantiation: void std::__1::__insertion_sort_3<std::__1::__less<unsigned long, unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, std::__1::__less<unsigned long, unsigned long>&)
Unexecuted instantiation: void std::__1::__insertion_sort_3<std::__1::__less<long long, long long>&, long long*>(long long*, long long*, std::__1::__less<long long, long long>&)
Unexecuted instantiation: void std::__1::__insertion_sort_3<std::__1::__less<unsigned long long, unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, std::__1::__less<unsigned long long, unsigned long long>&)
Unexecuted instantiation: void std::__1::__insertion_sort_3<std::__1::__less<float, float>&, float*>(float*, float*, std::__1::__less<float, float>&)
Unexecuted instantiation: void std::__1::__insertion_sort_3<std::__1::__less<double, double>&, double*>(double*, double*, std::__1::__less<double, double>&)
Unexecuted instantiation: void std::__1::__insertion_sort_3<std::__1::__less<long double, long double>&, long double*>(long double*, long double*, std::__1::__less<long double, long double>&)
3840
3841
template <class _Compare, class _RandomAccessIterator>
3842
bool
3843
__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3844
0
{
3845
0
switch (__last - __first)
3846
0
{
3847
0
case 0:
3848
0
case 1:
3849
0
return true;
3850
0
case 2:
3851
0
if (__comp(*--__last, *__first))
3852
0
swap(*__first, *__last);
3853
0
return true;
3854
0
case 3:
3855
0
_VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3856
0
return true;
3857
0
case 4:
3858
0
_VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3859
0
return true;
3860
0
case 5:
3861
0
_VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3862
0
return true;
3863
0
}
3864
0
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3865
0
_RandomAccessIterator __j = __first+2;
3866
0
__sort3<_Compare>(__first, __first+1, __j, __comp);
3867
0
const unsigned __limit = 8;
3868
0
unsigned __count = 0;
3869
0
for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3870
0
{
3871
0
if (__comp(*__i, *__j))
3872
0
{
3873
0
value_type __t(_VSTD::move(*__i));
3874
0
_RandomAccessIterator __k = __j;
3875
0
__j = __i;
3876
0
do
3877
0
{
3878
0
*__j = _VSTD::move(*__k);
3879
0
__j = __k;
3880
0
} while (__j != __first && __comp(__t, *--__k));
3881
0
*__j = _VSTD::move(__t);
3882
0
if (++__count == __limit)
3883
0
return ++__i == __last;
3884
0
}
3885
0
__j = __i;
3886
0
}
3887
0
return true;
3888
0
}
Unexecuted instantiation: bool std::__1::__insertion_sort_incomplete<std::__1::__less<char, char>&, char*>(char*, char*, std::__1::__less<char, char>&)
Unexecuted instantiation: bool std::__1::__insertion_sort_incomplete<std::__1::__less<wchar_t, wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, std::__1::__less<wchar_t, wchar_t>&)
Unexecuted instantiation: bool std::__1::__insertion_sort_incomplete<std::__1::__less<signed char, signed char>&, signed char*>(signed char*, signed char*, std::__1::__less<signed char, signed char>&)
Unexecuted instantiation: bool std::__1::__insertion_sort_incomplete<std::__1::__less<unsigned char, unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, std::__1::__less<unsigned char, unsigned char>&)
Unexecuted instantiation: bool std::__1::__insertion_sort_incomplete<std::__1::__less<short, short>&, short*>(short*, short*, std::__1::__less<short, short>&)
Unexecuted instantiation: bool std::__1::__insertion_sort_incomplete<std::__1::__less<unsigned short, unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, std::__1::__less<unsigned short, unsigned short>&)
Unexecuted instantiation: bool std::__1::__insertion_sort_incomplete<std::__1::__less<int, int>&, int*>(int*, int*, std::__1::__less<int, int>&)
Unexecuted instantiation: bool std::__1::__insertion_sort_incomplete<std::__1::__less<unsigned int, unsigned int>&, unsigned int*>(unsigned int*, unsigned int*, std::__1::__less<unsigned int, unsigned int>&)
Unexecuted instantiation: bool std::__1::__insertion_sort_incomplete<std::__1::__less<long, long>&, long*>(long*, long*, std::__1::__less<long, long>&)
Unexecuted instantiation: bool std::__1::__insertion_sort_incomplete<std::__1::__less<unsigned long, unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, std::__1::__less<unsigned long, unsigned long>&)
Unexecuted instantiation: bool std::__1::__insertion_sort_incomplete<std::__1::__less<long long, long long>&, long long*>(long long*, long long*, std::__1::__less<long long, long long>&)
Unexecuted instantiation: bool std::__1::__insertion_sort_incomplete<std::__1::__less<unsigned long long, unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, std::__1::__less<unsigned long long, unsigned long long>&)
Unexecuted instantiation: bool std::__1::__insertion_sort_incomplete<std::__1::__less<float, float>&, float*>(float*, float*, std::__1::__less<float, float>&)
Unexecuted instantiation: bool std::__1::__insertion_sort_incomplete<std::__1::__less<double, double>&, double*>(double*, double*, std::__1::__less<double, double>&)
Unexecuted instantiation: bool std::__1::__insertion_sort_incomplete<std::__1::__less<long double, long double>&, long double*>(long double*, long double*, std::__1::__less<long double, long double>&)
3889
3890
template <class _Compare, class _BirdirectionalIterator>
3891
void
3892
__insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
3893
typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
3894
{
3895
typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3896
if (__first1 != __last1)
3897
{
3898
__destruct_n __d(0);
3899
unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
3900
value_type* __last2 = __first2;
3901
::new(__last2) value_type(_VSTD::move(*__first1));
3902
__d.__incr((value_type*)0);
3903
for (++__last2; ++__first1 != __last1; ++__last2)
3904
{
3905
value_type* __j2 = __last2;
3906
value_type* __i2 = __j2;
3907
if (__comp(*__first1, *--__i2))
3908
{
3909
::new(__j2) value_type(_VSTD::move(*__i2));
3910
__d.__incr((value_type*)0);
3911
for (--__j2; __i2 != __first2 && __comp(*__first1,  *--__i2); --__j2)
3912
*__j2 = _VSTD::move(*__i2);
3913
*__j2 = _VSTD::move(*__first1);
3914
}
3915
else
3916
{
3917
::new(__j2) value_type(_VSTD::move(*__first1));
3918
__d.__incr((value_type*)0);
3919
}
3920
}
3921
__h.release();
3922
}
3923
}
3924
3925
template <class _Compare, class _RandomAccessIterator>
3926
void
3927
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3928
0
{
3929
0
// _Compare is known to be a reference type
3930
0
typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3931
0
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3932
0
const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
3933
0
is_trivially_copy_assignable<value_type>::value ? 30 : 6;
3934
0
while (true)
3935
0
{
3936
0
__restart:
3937
0
difference_type __len = __last - __first;
3938
0
switch (__len)
3939
0
{
3940
0
case 0:
3941
0
case 1:
3942
0
return;
3943
0
case 2:
3944
0
if (__comp(*--__last, *__first))
3945
0
swap(*__first, *__last);
3946
0
return;
3947
0
case 3:
3948
0
_VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3949
0
return;
3950
0
case 4:
3951
0
_VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3952
0
return;
3953
0
case 5:
3954
0
_VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3955
0
return;
3956
0
}
3957
0
if (__len <= __limit)
3958
0
{
3959
0
_VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
3960
0
return;
3961
0
}
3962
0
// __len > 5
3963
0
_RandomAccessIterator __m = __first;
3964
0
_RandomAccessIterator __lm1 = __last;
3965
0
--__lm1;
3966
0
unsigned __n_swaps;
3967
0
{
3968
0
difference_type __delta;
3969
0
if (__len >= 1000)
3970
0
{
3971
0
__delta = __len/2;
3972
0
__m += __delta;
3973
0
__delta /= 2;
3974
0
__n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
3975
0
}
3976
0
else
3977
0
{
3978
0
__delta = __len/2;
3979
0
__m += __delta;
3980
0
__n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
3981
0
}
3982
0
}
3983
0
// *__m is median
3984
0
// partition [__first, __m) < *__m and *__m <= [__m, __last)
3985
0
// (this inhibits tossing elements equivalent to __m around unnecessarily)
3986
0
_RandomAccessIterator __i = __first;
3987
0
_RandomAccessIterator __j = __lm1;
3988
0
// j points beyond range to be tested, *__m is known to be <= *__lm1
3989
0
// The search going up is known to be guarded but the search coming down isn't.
3990
0
// Prime the downward search with a guard.
3991
0
if (!__comp(*__i, *__m))  // if *__first == *__m
3992
0
{
3993
0
// *__first == *__m, *__first doesn't go in first part
3994
0
// manually guard downward moving __j against __i
3995
0
while (true)
3996
0
{
3997
0
if (__i == --__j)
3998
0
{
3999
0
// *__first == *__m, *__m <= all other elements
4000
0
// Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
4001
0
++__i;  // __first + 1
4002
0
__j = __last;
4003
0
if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
4004
0
{
4005
0
while (true)
4006
0
{
4007
0
if (__i == __j)
4008
0
return;  // [__first, __last) all equivalent elements
4009
0
if (__comp(*__first, *__i))
4010
0
{
4011
0
swap(*__i, *__j);
4012
0
++__n_swaps;
4013
0
++__i;
4014
0
break;
4015
0
}
4016
0
++__i;
4017
0
}
4018
0
}
4019
0
// [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
4020
0
if (__i == __j)
4021
0
return;
4022
0
while (true)
4023
0
{
4024
0
while (!__comp(*__first, *__i))
4025
0
++__i;
4026
0
while (__comp(*__first, *--__j))
4027
0
;
4028
0
if (__i >= __j)
4029
0
break;
4030
0
swap(*__i, *__j);
4031
0
++__n_swaps;
4032
0
++__i;
4033
0
}
4034
0
// [__first, __i) == *__first and *__first < [__i, __last)
4035
0
// The first part is sorted, sort the secod part
4036
0
// _VSTD::__sort<_Compare>(__i, __last, __comp);
4037
0
__first = __i;
4038
0
goto __restart;
4039
0
}
4040
0
if (__comp(*__j, *__m))
4041
0
{
4042
0
swap(*__i, *__j);
4043
0
++__n_swaps;
4044
0
break;  // found guard for downward moving __j, now use unguarded partition
4045
0
}
4046
0
}
4047
0
}
4048
0
// It is known that *__i < *__m
4049
0
++__i;
4050
0
// j points beyond range to be tested, *__m is known to be <= *__lm1
4051
0
// if not yet partitioned...
4052
0
if (__i < __j)
4053
0
{
4054
0
// known that *(__i - 1) < *__m
4055
0
// known that __i <= __m
4056
0
while (true)
4057
0
{
4058
0
// __m still guards upward moving __i
4059
0
while (__comp(*__i, *__m))
4060
0
++__i;
4061
0
// It is now known that a guard exists for downward moving __j
4062
0
while (!__comp(*--__j, *__m))
4063
0
;
4064
0
if (__i > __j)
4065
0
break;
4066
0
swap(*__i, *__j);
4067
0
++__n_swaps;
4068
0
// It is known that __m != __j
4069
0
// If __m just moved, follow it
4070
0
if (__m == __i)
4071
0
__m = __j;
4072
0
++__i;
4073
0
}
4074
0
}
4075
0
// [__first, __i) < *__m and *__m <= [__i, __last)
4076
0
if (__i != __m && __comp(*__m, *__i))
4077
0
{
4078
0
swap(*__i, *__m);
4079
0
++__n_swaps;
4080
0
}
4081
0
// [__first, __i) < *__i and *__i <= [__i+1, __last)
4082
0
// If we were given a perfect partition, see if insertion sort is quick...
4083
0
if (__n_swaps == 0)
4084
0
{
4085
0
bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
4086
0
if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
4087
0
{
4088
0
if (__fs)
4089
0
return;
4090
0
__last = __i;
4091
0
continue;
4092
0
}
4093
0
else
4094
0
{
4095
0
if (__fs)
4096
0
{
4097
0
__first = ++__i;
4098
0
continue;
4099
0
}
4100
0
}
4101
0
}
4102
0
// sort smaller range with recursive call and larger with tail recursion elimination
4103
0
if (__i - __first < __last - __i)
4104
0
{
4105
0
_VSTD::__sort<_Compare>(__first, __i, __comp);
4106
0
// _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4107
0
__first = ++__i;
4108
0
}
4109
0
else
4110
0
{
4111
0
_VSTD::__sort<_Compare>(__i+1, __last, __comp);
4112
0
// _VSTD::__sort<_Compare>(__first, __i, __comp);
4113
0
__last = __i;
4114
0
}
4115
0
}
4116
0
}
Unexecuted instantiation: void std::__1::__sort<std::__1::__less<char, char>&, char*>(char*, char*, std::__1::__less<char, char>&)
Unexecuted instantiation: void std::__1::__sort<std::__1::__less<wchar_t, wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, std::__1::__less<wchar_t, wchar_t>&)
Unexecuted instantiation: void std::__1::__sort<std::__1::__less<signed char, signed char>&, signed char*>(signed char*, signed char*, std::__1::__less<signed char, signed char>&)
Unexecuted instantiation: void std::__1::__sort<std::__1::__less<unsigned char, unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, std::__1::__less<unsigned char, unsigned char>&)
Unexecuted instantiation: void std::__1::__sort<std::__1::__less<short, short>&, short*>(short*, short*, std::__1::__less<short, short>&)
Unexecuted instantiation: void std::__1::__sort<std::__1::__less<unsigned short, unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, std::__1::__less<unsigned short, unsigned short>&)
Unexecuted instantiation: void std::__1::__sort<std::__1::__less<int, int>&, int*>(int*, int*, std::__1::__less<int, int>&)
Unexecuted instantiation: void std::__1::__sort<std::__1::__less<unsigned int, unsigned int>&, unsigned int*>(unsigned int*, unsigned int*, std::__1::__less<unsigned int, unsigned int>&)
Unexecuted instantiation: void std::__1::__sort<std::__1::__less<long, long>&, long*>(long*, long*, std::__1::__less<long, long>&)
Unexecuted instantiation: void std::__1::__sort<std::__1::__less<unsigned long, unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, std::__1::__less<unsigned long, unsigned long>&)
Unexecuted instantiation: void std::__1::__sort<std::__1::__less<long long, long long>&, long long*>(long long*, long long*, std::__1::__less<long long, long long>&)
Unexecuted instantiation: void std::__1::__sort<std::__1::__less<unsigned long long, unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, std::__1::__less<unsigned long long, unsigned long long>&)
Unexecuted instantiation: void std::__1::__sort<std::__1::__less<float, float>&, float*>(float*, float*, std::__1::__less<float, float>&)
Unexecuted instantiation: void std::__1::__sort<std::__1::__less<double, double>&, double*>(double*, double*, std::__1::__less<double, double>&)
Unexecuted instantiation: void std::__1::__sort<std::__1::__less<long double, long double>&, long double*>(long double*, long double*, std::__1::__less<long double, long double>&)
4117
4118
// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
4119
template <class _RandomAccessIterator, class _Compare>
4120
inline _LIBCPP_INLINE_VISIBILITY
4121
void
4122
sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4123
{
4124
typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4125
_VSTD::__sort<_Comp_ref>(__first, __last, _Comp_ref(__comp));
4126
}
4127
4128
template <class _RandomAccessIterator>
4129
inline _LIBCPP_INLINE_VISIBILITY
4130
void
4131
sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4132
{
4133
_VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4134
}
4135
4136
template <class _Tp>
4137
inline _LIBCPP_INLINE_VISIBILITY
4138
void
4139
sort(_Tp** __first, _Tp** __last)
4140
{
4141
_VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
4142
}
4143
4144
template <class _Tp>
4145
inline _LIBCPP_INLINE_VISIBILITY
4146
void
4147
sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
4148
{
4149
_VSTD::sort(__first.base(), __last.base());
4150
}
4151
4152
template <class _Tp, class _Compare>
4153
inline _LIBCPP_INLINE_VISIBILITY
4154
void
4155
sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
4156
{
4157
4158
_VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
4159
}
4160
4161
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
4162
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4163
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4164
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4165
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))
4166
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4167
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&))
4168
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4169
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&))
4170
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4171
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4172
_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>&))
4173
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&))
4174
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&))
4175
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4176
4177
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))
4178
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4179
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4180
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4181
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))
4182
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4183
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&))
4184
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4185
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&))
4186
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4187
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4188
_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>&))
4189
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&))
4190
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&))
4191
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4192
4193
_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>&))
4194
4195
// lower_bound
4196
4197
template <class _Compare, class _ForwardIterator, class _Tp>
4198
_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
4199
__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4200
246k
{
4201
246k
typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4202
246k
difference_type __len = _VSTD::distance(__first, __last);
4203
1.63M
while (__len != 0)
4204
1.38M
{
4205
1.38M
difference_type __l2 = _VSTD::__half_positive(__len);
4206
1.38M
_ForwardIterator __m = __first;
4207
1.38M
4208
1.38M
if (__comp(*__m, __value_))
4209
461k
{
4210
461k
__first = ++__m;
4211
461k
__len -= __l2 + 1;
4212
461k
}
4213
923k
else
4214
923k
__len = __l2;
4215
1.38M
}
4216
246k
return __first;
4217
246k
}
unsigned int const* std::__1::__lower_bound<std::__1::__less<unsigned int, unsigned long>&, unsigned int const*, unsigned long>(unsigned int const*, unsigned int const*, unsigned long const&, std::__1::__less<unsigned int, unsigned long>&)
 Line Count Source 4200 246k { 4201 246k typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 4202 246k difference_type __len = _VSTD::distance(__first, __last); 4203 1.63M while (__len != 0) 4204 1.38M { 4205 1.38M difference_type __l2 = _VSTD::__half_positive(__len); 4206 1.38M _ForwardIterator __m = __first; 4207 1.38M _VSTD::advance(__m, __l2); 4208 1.38M if (__comp(*__m, __value_)) 4209 461k { 4210 461k __first = ++__m; 4211 461k __len -= __l2 + 1; 4212 461k } 4213 923k else 4214 923k __len = __l2; 4215 1.38M } 4216 246k return __first; 4217 246k }
Unexecuted instantiation: regex.cpp:std::__1::(anonymous namespace)::collationnames const* std::__1::__lower_bound<std::__1::(anonymous namespace)::use_strcmp&, std::__1::(anonymous namespace)::collationnames const*, char const*>(std::__1::(anonymous namespace)::collationnames const*, std::__1::(anonymous namespace)::collationnames const*, char const* const&, std::__1::(anonymous namespace)::use_strcmp&)
Unexecuted instantiation: regex.cpp:std::__1::(anonymous namespace)::classnames const* std::__1::__lower_bound<std::__1::(anonymous namespace)::use_strcmp&, std::__1::(anonymous namespace)::classnames const*, char const*>(std::__1::(anonymous namespace)::classnames const*, std::__1::(anonymous namespace)::classnames const*, char const* const&, std::__1::(anonymous namespace)::use_strcmp&)
4218
4219
template <class _ForwardIterator, class _Tp, class _Compare>
4220
4221
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4222
_ForwardIterator
4223
lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4224
246k
{
4225
246k
4226
246k
return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp);
4227
246k
}
unsigned int const* std::__1::lower_bound<unsigned int const*, unsigned long, std::__1::__less<unsigned int, unsigned long> >(unsigned int const*, unsigned int const*, unsigned long const&, std::__1::__less<unsigned int, unsigned long>)
 Line Count Source 4224 246k { 4225 246k typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4226 246k return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp); 4227 246k }
Unexecuted instantiation: regex.cpp:std::__1::(anonymous namespace)::collationnames const* std::__1::lower_bound<std::__1::(anonymous namespace)::collationnames const*, char const*, std::__1::(anonymous namespace)::use_strcmp>(std::__1::(anonymous namespace)::collationnames const*, std::__1::(anonymous namespace)::collationnames const*, char const* const&, std::__1::(anonymous namespace)::use_strcmp)
Unexecuted instantiation: regex.cpp:std::__1::(anonymous namespace)::classnames const* std::__1::lower_bound<std::__1::(anonymous namespace)::classnames const*, char const*, std::__1::(anonymous namespace)::use_strcmp>(std::__1::(anonymous namespace)::classnames const*, std::__1::(anonymous namespace)::classnames const*, char const* const&, std::__1::(anonymous namespace)::use_strcmp)
4228
4229
template <class _ForwardIterator, class _Tp>
4230
4231
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4232
_ForwardIterator
4233
lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4234
246k
{
4235
246k
return _VSTD::lower_bound(__first, __last, __value_,
4236
246k
__less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4237
246k
}
4238
4239
// upper_bound
4240
4241
template <class _Compare, class _ForwardIterator, class _Tp>
4242
_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
4243
__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4244
{
4245
typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4246
difference_type __len = _VSTD::distance(__first, __last);
4247
while (__len != 0)
4248
{
4249
difference_type __l2 = _VSTD::__half_positive(__len);
4250
_ForwardIterator __m = __first;
4251
4252
if (__comp(__value_, *__m))
4253
__len = __l2;
4254
else
4255
{
4256
__first = ++__m;
4257
__len -= __l2 + 1;
4258
}
4259
}
4260
return __first;
4261
}
4262
4263
template <class _ForwardIterator, class _Tp, class _Compare>
4264
4265
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4266
_ForwardIterator
4267
upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4268
{
4269
4270
return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp);
4271
}
4272
4273
template <class _ForwardIterator, class _Tp>
4274
4275
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4276
_ForwardIterator
4277
upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4278
{
4279
return _VSTD::upper_bound(__first, __last, __value_,
4280
__less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
4281
}
4282
4283
// equal_range
4284
4285
template <class _Compare, class _ForwardIterator, class _Tp>
4286
_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator>
4287
__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4288
{
4289
typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4290
difference_type __len = _VSTD::distance(__first, __last);
4291
while (__len != 0)
4292
{
4293
difference_type __l2 = _VSTD::__half_positive(__len);
4294
_ForwardIterator __m = __first;
4295
4296
if (__comp(*__m, __value_))
4297
{
4298
__first = ++__m;
4299
__len -= __l2 + 1;
4300
}
4301
else if (__comp(__value_, *__m))
4302
{
4303
__last = __m;
4304
__len = __l2;
4305
}
4306
else
4307
{
4308
_ForwardIterator __mp1 = __m;
4309
return pair<_ForwardIterator, _ForwardIterator>
4310
(
4311
__lower_bound<_Compare>(__first, __m, __value_, __comp),
4312
__upper_bound<_Compare>(++__mp1, __last, __value_, __comp)
4313
);
4314
}
4315
}
4316
return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4317
}
4318
4319
template <class _ForwardIterator, class _Tp, class _Compare>
4320
4321
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4322
pair<_ForwardIterator, _ForwardIterator>
4323
equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4324
{
4325
typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4326
return __equal_range<_Comp_ref>(__first, __last, __value_, __comp);
4327
}
4328
4329
template <class _ForwardIterator, class _Tp>
4330
4331
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4332
pair<_ForwardIterator, _ForwardIterator>
4333
equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4334
{
4335
return _VSTD::equal_range(__first, __last, __value_,
4336
__less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4337
}
4338
4339
// binary_search
4340
4341
template <class _Compare, class _ForwardIterator, class _Tp>
4342
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4343
bool
4344
__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4345
{
4346
__first = __lower_bound<_Compare>(__first, __last, __value_, __comp);
4347
return __first != __last && !__comp(__value_, *__first);
4348
}
4349
4350
template <class _ForwardIterator, class _Tp, class _Compare>
4351
4352
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4353
bool
4354
binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4355
{
4356
typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4357
return __binary_search<_Comp_ref>(__first, __last, __value_, __comp);
4358
}
4359
4360
template <class _ForwardIterator, class _Tp>
4361
4362
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4363
bool
4364
binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4365
{
4366
return _VSTD::binary_search(__first, __last, __value_,
4367
__less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4368
}
4369
4370
// merge
4371
4372
template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4373
_OutputIterator
4374
__merge(_InputIterator1 __first1, _InputIterator1 __last1,
4375
_InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4376
{
4377
for (; __first1 != __last1; ++__result)
4378
{
4379
if (__first2 == __last2)
4380
return _VSTD::copy(__first1, __last1, __result);
4381
if (__comp(*__first2, *__first1))
4382
{
4383
*__result = *__first2;
4384
++__first2;
4385
}
4386
else
4387
{
4388
*__result = *__first1;
4389
++__first1;
4390
}
4391
}
4392
return _VSTD::copy(__first2, __last2, __result);
4393
}
4394
4395
template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4396
inline _LIBCPP_INLINE_VISIBILITY
4397
_OutputIterator
4398
merge(_InputIterator1 __first1, _InputIterator1 __last1,
4399
_InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4400
{
4401
typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4402
return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4403
}
4404
4405
template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4406
inline _LIBCPP_INLINE_VISIBILITY
4407
_OutputIterator
4408
merge(_InputIterator1 __first1, _InputIterator1 __last1,
4409
_InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4410
{
4411
typedef typename iterator_traits<_InputIterator1>::value_type __v1;
4412
typedef typename iterator_traits<_InputIterator2>::value_type __v2;
4413
return _VSTD::merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
4414
}
4415
4416
// inplace_merge
4417
4418
template <class _Compare, class _InputIterator1, class _InputIterator2,
4419
class _OutputIterator>
4420
void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
4421
_InputIterator2 __first2, _InputIterator2 __last2,
4422
_OutputIterator __result, _Compare __comp)
4423
{
4424
for (; __first1 != __last1; ++__result)
4425
{
4426
if (__first2 == __last2)
4427
{
4428
_VSTD::move(__first1, __last1, __result);
4429
return;
4430
}
4431
4432
if (__comp(*__first2, *__first1))
4433
{
4434
*__result = _VSTD::move(*__first2);
4435
++__first2;
4436
}
4437
else
4438
{
4439
*__result = _VSTD::move(*__first1);
4440
++__first1;
4441
}
4442
}
4443
// __first2 through __last2 are already in the right spot.
4444
}
4445
4446
template <class _Compare, class _BidirectionalIterator>
4447
void
4448
__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4449
_Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4450
typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4451
typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
4452
{
4453
typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4454
__destruct_n __d(0);
4455
unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4456
if (__len1 <= __len2)
4457
{
4458
value_type* __p = __buff;
4459
for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, (void) ++__p)
4460
::new(__p) value_type(_VSTD::move(*__i));
4461
__half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);
4462
}
4463
else
4464
{
4465
value_type* __p = __buff;
4466
for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, (void) ++__p)
4467
::new(__p) value_type(_VSTD::move(*__i));
4468
typedef reverse_iterator<_BidirectionalIterator> _RBi;
4469
typedef reverse_iterator<value_type*> _Rv;
4470
__half_inplace_merge(_Rv(__p), _Rv(__buff),
4471
_RBi(__middle), _RBi(__first),
4472
_RBi(__last), __invert<_Compare>(__comp));
4473
}
4474
}
4475
4476
template <class _Compare, class _BidirectionalIterator>
4477
void
4478
__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4479
_Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4480
typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4481
typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
4482
{
4483
typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4484
while (true)
4485
{
4486
// if __middle == __last, we're done
4487
if (__len2 == 0)
4488
return;
4489
if (__len1 <= __buff_size || __len2 <= __buff_size)
4490
return __buffered_inplace_merge<_Compare>
4491
(__first, __middle, __last, __comp, __len1, __len2, __buff);
4492
// shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
4493
for (; true; ++__first, (void) --__len1)
4494
{
4495
if (__len1 == 0)
4496
return;
4497
if (__comp(*__middle, *__first))
4498
break;
4499
}
4500
// __first < __middle < __last
4501
// *__first > *__middle
4502
// partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4503
//     all elements in:
4504
//         [__first, __m1)  <= [__middle, __m2)
4505
//         [__middle, __m2) <  [__m1, __middle)
4506
//         [__m1, __middle) <= [__m2, __last)
4507
//     and __m1 or __m2 is in the middle of its range
4508
_BidirectionalIterator __m1;  // "median" of [__first, __middle)
4509
_BidirectionalIterator __m2;  // "median" of [__middle, __last)
4510
difference_type __len11;      // distance(__first, __m1)
4511
difference_type __len21;      // distance(__middle, __m2)
4512
// binary search smaller range
4513
if (__len1 < __len2)
4514
{   // __len >= 1, __len2 >= 2
4515
__len21 = __len2 / 2;
4516
__m2 = __middle;
4517
4518
__m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4519
__len11 = _VSTD::distance(__first, __m1);
4520
}
4521
else
4522
{
4523
if (__len1 == 1)
4524
{   // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
4525
// It is known *__first > *__middle
4526
swap(*__first, *__middle);
4527
return;
4528
}
4529
// __len1 >= 2, __len2 >= 1
4530
__len11 = __len1 / 2;
4531
__m1 = __first;
4532
4533
__m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp);
4534
__len21 = _VSTD::distance(__middle, __m2);
4535
}
4536
difference_type __len12 = __len1 - __len11;  // distance(__m1, __middle)
4537
difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)
4538
// [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4539
// swap middle two partitions
4540
__middle = _VSTD::rotate(__m1, __middle, __m2);
4541
// __len12 and __len21 now have swapped meanings
4542
// merge smaller range with recurisve call and larger with tail recursion elimination
4543
if (__len11 + __len21 < __len12 + __len22)
4544
{
4545
__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4546
//          __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4547
__first = __middle;
4548
__middle = __m2;
4549
__len1 = __len12;
4550
__len2 = __len22;
4551
}
4552
else
4553
{
4554
__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4555
//          __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4556
__last = __middle;
4557
__middle = __m1;
4558
__len1 = __len11;
4559
__len2 = __len21;
4560
}
4561
}
4562
}
4563
4564
template <class _BidirectionalIterator, class _Compare>
4565
inline _LIBCPP_INLINE_VISIBILITY
4566
void
4567
inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4568
_Compare __comp)
4569
{
4570
typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4571
typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4572
difference_type __len1 = _VSTD::distance(__first, __middle);
4573
difference_type __len2 = _VSTD::distance(__middle, __last);
4574
difference_type __buf_size = _VSTD::min(__len1, __len2);
4575
pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
4576
unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
4577
typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4578
return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4579
__buf.first, __buf.second);
4580
}
4581
4582
template <class _BidirectionalIterator>
4583
inline _LIBCPP_INLINE_VISIBILITY
4584
void
4585
inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
4586
{
4587
_VSTD::inplace_merge(__first, __middle, __last,
4588
__less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4589
}
4590
4591
// stable_sort
4592
4593
template <class _Compare, class _InputIterator1, class _InputIterator2>
4594
void
4595
__merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
4596
_InputIterator2 __first2, _InputIterator2 __last2,
4597
typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
4598
{
4599
typedef typename iterator_traits<_InputIterator1>::value_type value_type;
4600
__destruct_n __d(0);
4601
unique_ptr<value_type, __destruct_n&> __h(__result, __d);
4602
for (; true; ++__result)
4603
{
4604
if (__first1 == __last1)
4605
{
4606
for (; __first2 != __last2; ++__first2, ++__result, (void) __d.__incr((value_type*)0))
4607
::new (__result) value_type(_VSTD::move(*__first2));
4608
__h.release();
4609
return;
4610
}
4611
if (__first2 == __last2)
4612
{
4613
for (; __first1 != __last1; ++__first1, ++__result, (void) __d.__incr((value_type*)0))
4614
::new (__result) value_type(_VSTD::move(*__first1));
4615
__h.release();
4616
return;
4617
}
4618
if (__comp(*__first2, *__first1))
4619
{
4620
::new (__result) value_type(_VSTD::move(*__first2));
4621
__d.__incr((value_type*)0);
4622
++__first2;
4623
}
4624
else
4625
{
4626
::new (__result) value_type(_VSTD::move(*__first1));
4627
__d.__incr((value_type*)0);
4628
++__first1;
4629
}
4630
}
4631
}
4632
4633
template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4634
void
4635
__merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
4636
_InputIterator2 __first2, _InputIterator2 __last2,
4637
_OutputIterator __result, _Compare __comp)
4638
{
4639
for (; __first1 != __last1; ++__result)
4640
{
4641
if (__first2 == __last2)
4642
{
4643
for (; __first1 != __last1; ++__first1, (void) ++__result)
4644
*__result = _VSTD::move(*__first1);
4645
return;
4646
}
4647
if (__comp(*__first2, *__first1))
4648
{
4649
*__result = _VSTD::move(*__first2);
4650
++__first2;
4651
}
4652
else
4653
{
4654
*__result = _VSTD::move(*__first1);
4655
++__first1;
4656
}
4657
}
4658
for (; __first2 != __last2; ++__first2, (void) ++__result)
4659
*__result = _VSTD::move(*__first2);
4660
}
4661
4662
template <class _Compare, class _RandomAccessIterator>
4663
void
4664
__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4665
typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4666
typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
4667
4668
template <class _Compare, class _RandomAccessIterator>
4669
void
4670
__stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
4671
typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4672
typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
4673
{
4674
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4675
switch (__len)
4676
{
4677
case 0:
4678
return;
4679
case 1:
4680
::new(__first2) value_type(_VSTD::move(*__first1));
4681
return;
4682
case 2:
4683
__destruct_n __d(0);
4684
unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
4685
if (__comp(*--__last1, *__first1))
4686
{
4687
::new(__first2) value_type(_VSTD::move(*__last1));
4688
__d.__incr((value_type*)0);
4689
++__first2;
4690
::new(__first2) value_type(_VSTD::move(*__first1));
4691
}
4692
else
4693
{
4694
::new(__first2) value_type(_VSTD::move(*__first1));
4695
__d.__incr((value_type*)0);
4696
++__first2;
4697
::new(__first2) value_type(_VSTD::move(*__last1));
4698
}
4699
__h2.release();
4700
return;
4701
}
4702
if (__len <= 8)
4703
{
4704
__insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
4705
return;
4706
}
4707
typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4708
_RandomAccessIterator __m = __first1 + __l2;
4709
__stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
4710
__stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
4711
__merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
4712
}
4713
4714
template <class _Tp>
4715
struct __stable_sort_switch
4716
{
4717
static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
4718
};
4719
4720
template <class _Compare, class _RandomAccessIterator>
4721
void
4722
__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4723
typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4724
typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
4725
{
4726
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4727
typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4728
switch (__len)
4729
{
4730
case 0:
4731
case 1:
4732
return;
4733
case 2:
4734
if (__comp(*--__last, *__first))
4735
swap(*__first, *__last);
4736
return;
4737
}
4738
if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4739
{
4740
__insertion_sort<_Compare>(__first, __last, __comp);
4741
return;
4742
}
4743
typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4744
_RandomAccessIterator __m = __first + __l2;
4745
if (__len <= __buff_size)
4746
{
4747
__destruct_n __d(0);
4748
unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4749
__stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4750
__d.__set(__l2, (value_type*)0);
4751
__stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
4752
__d.__set(__len, (value_type*)0);
4753
__merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4754
//         __merge<_Compare>(move_iterator<value_type*>(__buff),
4755
//                           move_iterator<value_type*>(__buff + __l2),
4756
//                           move_iterator<_RandomAccessIterator>(__buff + __l2),
4757
//                           move_iterator<_RandomAccessIterator>(__buff + __len),
4758
//                           __first, __comp);
4759
return;
4760
}
4761
__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4762
__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
4763
__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4764
}
4765
4766
template <class _RandomAccessIterator, class _Compare>
4767
inline _LIBCPP_INLINE_VISIBILITY
4768
void
4769
stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4770
{
4771
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4772
typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4773
difference_type __len = __last - __first;
4774
pair<value_type*, ptrdiff_t> __buf(0, 0);
4775
unique_ptr<value_type, __return_temporary_buffer> __h;
4776
if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4777
{
4778
__buf = _VSTD::get_temporary_buffer<value_type>(__len);
4779
__h.reset(__buf.first);
4780
}
4781
typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4782
__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4783
}
4784
4785
template <class _RandomAccessIterator>
4786
inline _LIBCPP_INLINE_VISIBILITY
4787
void
4788
stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4789
{
4790
_VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4791
}
4792
4793
// is_heap_until
4794
4795
template <class _RandomAccessIterator, class _Compare>
4796
4797
is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4798
{
4799
typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4800
difference_type __len = __last - __first;
4801
difference_type __p = 0;
4802
difference_type __c = 1;
4803
_RandomAccessIterator __pp = __first;
4804
while (__c < __len)
4805
{
4806
_RandomAccessIterator __cp = __first + __c;
4807
if (__comp(*__pp, *__cp))
4808
return __cp;
4809
++__c;
4810
++__cp;
4811
if (__c == __len)
4812
return __last;
4813
if (__comp(*__pp, *__cp))
4814
return __cp;
4815
++__p;
4816
++__pp;
4817
__c = 2 * __p + 1;
4818
}
4819
return __last;
4820
}
4821
4822
template<class _RandomAccessIterator>
4823
4824
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4825
_RandomAccessIterator
4826
is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4827
{
4828
return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4829
}
4830
4831
// is_heap
4832
4833
template <class _RandomAccessIterator, class _Compare>
4834
4835
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4836
bool
4837
is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4838
{
4839
return _VSTD::is_heap_until(__first, __last, __comp) == __last;
4840
}
4841
4842
template<class _RandomAccessIterator>
4843
4844
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
4845
bool
4846
is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4847
{
4848
return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4849
}
4850
4851
// push_heap
4852
4853
template <class _Compare, class _RandomAccessIterator>
4854
void
4855
__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4856
typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4857
{
4858
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4859
if (__len > 1)
4860
{
4861
__len = (__len - 2) / 2;
4862
_RandomAccessIterator __ptr = __first + __len;
4863
if (__comp(*__ptr, *--__last))
4864
{
4865
value_type __t(_VSTD::move(*__last));
4866
do
4867
{
4868
*__last = _VSTD::move(*__ptr);
4869
__last = __ptr;
4870
if (__len == 0)
4871
break;
4872
__len = (__len - 1) / 2;
4873
__ptr = __first + __len;
4874
} while (__comp(*__ptr, __t));
4875
*__last = _VSTD::move(__t);
4876
}
4877
}
4878
}
4879
4880
template <class _RandomAccessIterator, class _Compare>
4881
inline _LIBCPP_INLINE_VISIBILITY
4882
void
4883
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4884
{
4885
typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
4886
__sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
4887
}
4888
4889
template <class _RandomAccessIterator>
4890
inline _LIBCPP_INLINE_VISIBILITY
4891
void
4892
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4893
{
4894
_VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4895
}
4896
4897
// pop_heap
4898
4899
template <class _Compare, class _RandomAccessIterator>
4900
void
4901
__sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/,
4902
_Compare __comp,
4903
typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4904