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