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