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