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