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