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