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