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