algorithm revision 246487
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 <cstddef> 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 _BidirectionalIterator, class _OutputIterator> 1532inline _LIBCPP_INLINE_VISIBILITY 1533_OutputIterator 1534__copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __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_left(_ForwardIterator __first, _ForwardIterator __last) 2107{ 2108 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 2109 value_type __tmp = _VSTD::move(*__first); 2110 _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first); 2111 *__lm1 = _VSTD::move(__tmp); 2112 return __lm1; 2113} 2114 2115template <class _BidirectionalIterator> 2116_BidirectionalIterator 2117__rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last) 2118{ 2119 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 2120 _BidirectionalIterator __lm1 = _VSTD::prev(__last); 2121 value_type __tmp = _VSTD::move(*__lm1); 2122 _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last); 2123 *__first = _VSTD::move(__tmp); 2124 return __fp1; 2125} 2126 2127template <class _ForwardIterator> 2128_ForwardIterator 2129__rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) 2130{ 2131 _ForwardIterator __i = __middle; 2132 while (true) 2133 { 2134 swap(*__first, *__i); 2135 ++__first; 2136 if (++__i == __last) 2137 break; 2138 if (__first == __middle) 2139 __middle = __i; 2140 } 2141 _ForwardIterator __r = __first; 2142 if (__first != __middle) 2143 { 2144 __i = __middle; 2145 while (true) 2146 { 2147 swap(*__first, *__i); 2148 ++__first; 2149 if (++__i == __last) 2150 { 2151 if (__first == __middle) 2152 break; 2153 __i = __middle; 2154 } 2155 else if (__first == __middle) 2156 __middle = __i; 2157 } 2158 } 2159 return __r; 2160} 2161 2162template<typename _Integral> 2163inline _LIBCPP_INLINE_VISIBILITY 2164_Integral 2165__gcd(_Integral __x, _Integral __y) 2166{ 2167 do 2168 { 2169 _Integral __t = __x % __y; 2170 __x = __y; 2171 __y = __t; 2172 } while (__y); 2173 return __x; 2174} 2175 2176template<typename _RandomAccessIterator> 2177_RandomAccessIterator 2178__rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) 2179{ 2180 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 2181 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 2182 2183 const difference_type __m1 = __middle - __first; 2184 const difference_type __m2 = __last - __middle; 2185 if (__m1 == __m2) 2186 { 2187 _VSTD::swap_ranges(__first, __middle, __middle); 2188 return __middle; 2189 } 2190 const difference_type __g = _VSTD::__gcd(__m1, __m2); 2191 for (_RandomAccessIterator __p = __first + __g; __p != __first;) 2192 { 2193 value_type __t(_VSTD::move(*--__p)); 2194 _RandomAccessIterator __p1 = __p; 2195 _RandomAccessIterator __p2 = __p1 + __m1; 2196 do 2197 { 2198 *__p1 = _VSTD::move(*__p2); 2199 __p1 = __p2; 2200 const difference_type __d = __last - __p2; 2201 if (__m1 < __d) 2202 __p2 += __m1; 2203 else 2204 __p2 = __first + (__m1 - __d); 2205 } while (__p2 != __p); 2206 *__p1 = _VSTD::move(__t); 2207 } 2208 return __first + __m2; 2209} 2210 2211template <class _ForwardIterator> 2212inline _LIBCPP_INLINE_VISIBILITY 2213_ForwardIterator 2214__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, 2215 _VSTD::forward_iterator_tag) 2216{ 2217 typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type; 2218 if (_VSTD::is_trivially_move_assignable<value_type>::value) 2219 { 2220 if (_VSTD::next(__first) == __middle) 2221 return _VSTD::__rotate_left(__first, __last); 2222 } 2223 return _VSTD::__rotate_forward(__first, __middle, __last); 2224} 2225 2226template <class _BidirectionalIterator> 2227inline _LIBCPP_INLINE_VISIBILITY 2228_BidirectionalIterator 2229__rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 2230 _VSTD::bidirectional_iterator_tag) 2231{ 2232 typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type; 2233 if (_VSTD::is_trivially_move_assignable<value_type>::value) 2234 { 2235 if (_VSTD::next(__first) == __middle) 2236 return _VSTD::__rotate_left(__first, __last); 2237 if (_VSTD::next(__middle) == __last) 2238 return _VSTD::__rotate_right(__first, __last); 2239 } 2240 return _VSTD::__rotate_forward(__first, __middle, __last); 2241} 2242 2243template <class _RandomAccessIterator> 2244inline _LIBCPP_INLINE_VISIBILITY 2245_RandomAccessIterator 2246__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, 2247 _VSTD::random_access_iterator_tag) 2248{ 2249 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type; 2250 if (_VSTD::is_trivially_move_assignable<value_type>::value) 2251 { 2252 if (_VSTD::next(__first) == __middle) 2253 return _VSTD::__rotate_left(__first, __last); 2254 if (_VSTD::next(__middle) == __last) 2255 return _VSTD::__rotate_right(__first, __last); 2256 return _VSTD::__rotate_gcd(__first, __middle, __last); 2257 } 2258 return _VSTD::__rotate_forward(__first, __middle, __last); 2259} 2260 2261template <class _ForwardIterator> 2262inline _LIBCPP_INLINE_VISIBILITY 2263_ForwardIterator 2264rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) 2265{ 2266 if (__first == __middle) 2267 return __last; 2268 if (__middle == __last) 2269 return __first; 2270 return _VSTD::__rotate(__first, __middle, __last, 2271 typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category()); 2272} 2273 2274// rotate_copy 2275 2276template <class _ForwardIterator, class _OutputIterator> 2277inline _LIBCPP_INLINE_VISIBILITY 2278_OutputIterator 2279rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result) 2280{ 2281 return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result)); 2282} 2283 2284// min_element 2285 2286template <class _ForwardIterator, class _Compare> 2287inline _LIBCPP_INLINE_VISIBILITY 2288_ForwardIterator 2289min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 2290{ 2291 if (__first != __last) 2292 { 2293 _ForwardIterator __i = __first; 2294 while (++__i != __last) 2295 if (__comp(*__i, *__first)) 2296 __first = __i; 2297 } 2298 return __first; 2299} 2300 2301template <class _ForwardIterator> 2302inline _LIBCPP_INLINE_VISIBILITY 2303_ForwardIterator 2304min_element(_ForwardIterator __first, _ForwardIterator __last) 2305{ 2306 return _VSTD::min_element(__first, __last, 2307 __less<typename iterator_traits<_ForwardIterator>::value_type>()); 2308} 2309 2310// min 2311 2312template <class _Tp, class _Compare> 2313inline _LIBCPP_INLINE_VISIBILITY 2314const _Tp& 2315min(const _Tp& __a, const _Tp& __b, _Compare __comp) 2316{ 2317 return __comp(__b, __a) ? __b : __a; 2318} 2319 2320template <class _Tp> 2321inline _LIBCPP_INLINE_VISIBILITY 2322const _Tp& 2323min(const _Tp& __a, const _Tp& __b) 2324{ 2325 return _VSTD::min(__a, __b, __less<_Tp>()); 2326} 2327 2328#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2329 2330template<class _Tp, class _Compare> 2331inline _LIBCPP_INLINE_VISIBILITY 2332_Tp 2333min(initializer_list<_Tp> __t, _Compare __comp) 2334{ 2335 return *_VSTD::min_element(__t.begin(), __t.end(), __comp); 2336} 2337 2338template<class _Tp> 2339inline _LIBCPP_INLINE_VISIBILITY 2340_Tp 2341min(initializer_list<_Tp> __t) 2342{ 2343 return *_VSTD::min_element(__t.begin(), __t.end()); 2344} 2345 2346#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2347 2348// max_element 2349 2350template <class _ForwardIterator, class _Compare> 2351inline _LIBCPP_INLINE_VISIBILITY 2352_ForwardIterator 2353max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 2354{ 2355 if (__first != __last) 2356 { 2357 _ForwardIterator __i = __first; 2358 while (++__i != __last) 2359 if (__comp(*__first, *__i)) 2360 __first = __i; 2361 } 2362 return __first; 2363} 2364 2365template <class _ForwardIterator> 2366inline _LIBCPP_INLINE_VISIBILITY 2367_ForwardIterator 2368max_element(_ForwardIterator __first, _ForwardIterator __last) 2369{ 2370 return _VSTD::max_element(__first, __last, 2371 __less<typename iterator_traits<_ForwardIterator>::value_type>()); 2372} 2373 2374// max 2375 2376template <class _Tp, class _Compare> 2377inline _LIBCPP_INLINE_VISIBILITY 2378const _Tp& 2379max(const _Tp& __a, const _Tp& __b, _Compare __comp) 2380{ 2381 return __comp(__a, __b) ? __b : __a; 2382} 2383 2384template <class _Tp> 2385inline _LIBCPP_INLINE_VISIBILITY 2386const _Tp& 2387max(const _Tp& __a, const _Tp& __b) 2388{ 2389 return _VSTD::max(__a, __b, __less<_Tp>()); 2390} 2391 2392#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2393 2394template<class _Tp, class _Compare> 2395inline _LIBCPP_INLINE_VISIBILITY 2396_Tp 2397max(initializer_list<_Tp> __t, _Compare __comp) 2398{ 2399 return *_VSTD::max_element(__t.begin(), __t.end(), __comp); 2400} 2401 2402template<class _Tp> 2403inline _LIBCPP_INLINE_VISIBILITY 2404_Tp 2405max(initializer_list<_Tp> __t) 2406{ 2407 return *_VSTD::max_element(__t.begin(), __t.end()); 2408} 2409 2410#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2411 2412// minmax_element 2413 2414template <class _ForwardIterator, class _Compare> 2415std::pair<_ForwardIterator, _ForwardIterator> 2416minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 2417{ 2418 std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first); 2419 if (__first != __last) 2420 { 2421 if (++__first != __last) 2422 { 2423 if (__comp(*__first, *__result.first)) 2424 __result.first = __first; 2425 else 2426 __result.second = __first; 2427 while (++__first != __last) 2428 { 2429 _ForwardIterator __i = __first; 2430 if (++__first == __last) 2431 { 2432 if (__comp(*__i, *__result.first)) 2433 __result.first = __i; 2434 else if (!__comp(*__i, *__result.second)) 2435 __result.second = __i; 2436 break; 2437 } 2438 else 2439 { 2440 if (__comp(*__first, *__i)) 2441 { 2442 if (__comp(*__first, *__result.first)) 2443 __result.first = __first; 2444 if (!__comp(*__i, *__result.second)) 2445 __result.second = __i; 2446 } 2447 else 2448 { 2449 if (__comp(*__i, *__result.first)) 2450 __result.first = __i; 2451 if (!__comp(*__first, *__result.second)) 2452 __result.second = __first; 2453 } 2454 } 2455 } 2456 } 2457 } 2458 return __result; 2459} 2460 2461template <class _ForwardIterator> 2462inline _LIBCPP_INLINE_VISIBILITY 2463std::pair<_ForwardIterator, _ForwardIterator> 2464minmax_element(_ForwardIterator __first, _ForwardIterator __last) 2465{ 2466 return _VSTD::minmax_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); 2467} 2468 2469// minmax 2470 2471template<class _Tp, class _Compare> 2472inline _LIBCPP_INLINE_VISIBILITY 2473pair<const _Tp&, const _Tp&> 2474minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) 2475{ 2476 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) : 2477 pair<const _Tp&, const _Tp&>(__a, __b); 2478} 2479 2480template<class _Tp> 2481inline _LIBCPP_INLINE_VISIBILITY 2482pair<const _Tp&, const _Tp&> 2483minmax(const _Tp& __a, const _Tp& __b) 2484{ 2485 return _VSTD::minmax(__a, __b, __less<_Tp>()); 2486} 2487 2488#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2489 2490template<class _Tp> 2491inline _LIBCPP_INLINE_VISIBILITY 2492pair<_Tp, _Tp> 2493minmax(initializer_list<_Tp> __t) 2494{ 2495 pair<const _Tp*, const _Tp*> __p = 2496 _VSTD::minmax_element(__t.begin(), __t.end()); 2497 return pair<_Tp, _Tp>(*__p.first, *__p.second); 2498} 2499 2500template<class _Tp, class _Compare> 2501inline _LIBCPP_INLINE_VISIBILITY 2502pair<_Tp, _Tp> 2503minmax(initializer_list<_Tp> __t, _Compare __comp) 2504{ 2505 pair<const _Tp*, const _Tp*> __p = 2506 _VSTD::minmax_element(__t.begin(), __t.end(), __comp); 2507 return pair<_Tp, _Tp>(*__p.first, *__p.second); 2508} 2509 2510#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2511 2512// random_shuffle 2513 2514// __independent_bits_engine 2515 2516template <unsigned long long _Xp, size_t _Rp> 2517struct __log2_imp 2518{ 2519 static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp 2520 : __log2_imp<_Xp, _Rp - 1>::value; 2521}; 2522 2523template <unsigned long long _Xp> 2524struct __log2_imp<_Xp, 0> 2525{ 2526 static const size_t value = 0; 2527}; 2528 2529template <size_t _Rp> 2530struct __log2_imp<0, _Rp> 2531{ 2532 static const size_t value = _Rp + 1; 2533}; 2534 2535template <class _UI, _UI _Xp> 2536struct __log2 2537{ 2538 static const size_t value = __log2_imp<_Xp, 2539 sizeof(_UI) * __CHAR_BIT__ - 1>::value; 2540}; 2541 2542template<class _Engine, class _UIntType> 2543class __independent_bits_engine 2544{ 2545public: 2546 // types 2547 typedef _UIntType result_type; 2548 2549private: 2550 typedef typename _Engine::result_type _Engine_result_type; 2551 typedef typename conditional 2552 < 2553 sizeof(_Engine_result_type) <= sizeof(result_type), 2554 result_type, 2555 _Engine_result_type 2556 >::type _Working_result_type; 2557 2558 _Engine& __e_; 2559 size_t __w_; 2560 size_t __w0_; 2561 size_t __n_; 2562 size_t __n0_; 2563 _Working_result_type __y0_; 2564 _Working_result_type __y1_; 2565 _Engine_result_type __mask0_; 2566 _Engine_result_type __mask1_; 2567 2568#ifdef _LIBCPP_HAS_NO_CONSTEXPR 2569 static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min 2570 + _Working_result_type(1); 2571#else 2572 static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min() 2573 + _Working_result_type(1); 2574#endif 2575 static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value; 2576 static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits; 2577 static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits; 2578 2579public: 2580 // constructors and seeding functions 2581 __independent_bits_engine(_Engine& __e, size_t __w); 2582 2583 // generating functions 2584 result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());} 2585 2586private: 2587 result_type __eval(false_type); 2588 result_type __eval(true_type); 2589}; 2590 2591template<class _Engine, class _UIntType> 2592__independent_bits_engine<_Engine, _UIntType> 2593 ::__independent_bits_engine(_Engine& __e, size_t __w) 2594 : __e_(__e), 2595 __w_(__w) 2596{ 2597 __n_ = __w_ / __m + (__w_ % __m != 0); 2598 __w0_ = __w_ / __n_; 2599 if (_Rp == 0) 2600 __y0_ = _Rp; 2601 else if (__w0_ < _WDt) 2602 __y0_ = (_Rp >> __w0_) << __w0_; 2603 else 2604 __y0_ = 0; 2605 if (_Rp - __y0_ > __y0_ / __n_) 2606 { 2607 ++__n_; 2608 __w0_ = __w_ / __n_; 2609 if (__w0_ < _WDt) 2610 __y0_ = (_Rp >> __w0_) << __w0_; 2611 else 2612 __y0_ = 0; 2613 } 2614 __n0_ = __n_ - __w_ % __n_; 2615 if (__w0_ < _WDt - 1) 2616 __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1); 2617 else 2618 __y1_ = 0; 2619 __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) : 2620 _Engine_result_type(0); 2621 __mask1_ = __w0_ < _EDt - 1 ? 2622 _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) : 2623 _Engine_result_type(~0); 2624} 2625 2626template<class _Engine, class _UIntType> 2627inline 2628_UIntType 2629__independent_bits_engine<_Engine, _UIntType>::__eval(false_type) 2630{ 2631 return static_cast<result_type>(__e_() & __mask0_); 2632} 2633 2634template<class _Engine, class _UIntType> 2635_UIntType 2636__independent_bits_engine<_Engine, _UIntType>::__eval(true_type) 2637{ 2638 result_type _Sp = 0; 2639 for (size_t __k = 0; __k < __n0_; ++__k) 2640 { 2641 _Engine_result_type __u; 2642 do 2643 { 2644 __u = __e_() - _Engine::min(); 2645 } while (__u >= __y0_); 2646 if (__w0_ < _WDt) 2647 _Sp <<= __w0_; 2648 else 2649 _Sp = 0; 2650 _Sp += __u & __mask0_; 2651 } 2652 for (size_t __k = __n0_; __k < __n_; ++__k) 2653 { 2654 _Engine_result_type __u; 2655 do 2656 { 2657 __u = __e_() - _Engine::min(); 2658 } while (__u >= __y1_); 2659 if (__w0_ < _WDt - 1) 2660 _Sp <<= __w0_ + 1; 2661 else 2662 _Sp = 0; 2663 _Sp += __u & __mask1_; 2664 } 2665 return _Sp; 2666} 2667 2668// uniform_int_distribution 2669 2670template<class _IntType = int> 2671class uniform_int_distribution 2672{ 2673public: 2674 // types 2675 typedef _IntType result_type; 2676 2677 class param_type 2678 { 2679 result_type __a_; 2680 result_type __b_; 2681 public: 2682 typedef uniform_int_distribution distribution_type; 2683 2684 explicit param_type(result_type __a = 0, 2685 result_type __b = numeric_limits<result_type>::max()) 2686 : __a_(__a), __b_(__b) {} 2687 2688 result_type a() const {return __a_;} 2689 result_type b() const {return __b_;} 2690 2691 friend bool operator==(const param_type& __x, const param_type& __y) 2692 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;} 2693 friend bool operator!=(const param_type& __x, const param_type& __y) 2694 {return !(__x == __y);} 2695 }; 2696 2697private: 2698 param_type __p_; 2699 2700public: 2701 // constructors and reset functions 2702 explicit uniform_int_distribution(result_type __a = 0, 2703 result_type __b = numeric_limits<result_type>::max()) 2704 : __p_(param_type(__a, __b)) {} 2705 explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {} 2706 void reset() {} 2707 2708 // generating functions 2709 template<class _URNG> result_type operator()(_URNG& __g) 2710 {return (*this)(__g, __p_);} 2711 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p); 2712 2713 // property functions 2714 result_type a() const {return __p_.a();} 2715 result_type b() const {return __p_.b();} 2716 2717 param_type param() const {return __p_;} 2718 void param(const param_type& __p) {__p_ = __p;} 2719 2720 result_type min() const {return a();} 2721 result_type max() const {return b();} 2722 2723 friend bool operator==(const uniform_int_distribution& __x, 2724 const uniform_int_distribution& __y) 2725 {return __x.__p_ == __y.__p_;} 2726 friend bool operator!=(const uniform_int_distribution& __x, 2727 const uniform_int_distribution& __y) 2728 {return !(__x == __y);} 2729}; 2730 2731template<class _IntType> 2732template<class _URNG> 2733typename uniform_int_distribution<_IntType>::result_type 2734uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p) 2735{ 2736 typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t), 2737 uint32_t, uint64_t>::type _UIntType; 2738 const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1); 2739 if (_Rp == 1) 2740 return __p.a(); 2741 const size_t _Dt = numeric_limits<_UIntType>::digits; 2742 typedef __independent_bits_engine<_URNG, _UIntType> _Eng; 2743 if (_Rp == 0) 2744 return static_cast<result_type>(_Eng(__g, _Dt)()); 2745 size_t __w = _Dt - __clz(_Rp) - 1; 2746 if ((_Rp & (_UIntType(~0) >> (_Dt - __w))) != 0) 2747 ++__w; 2748 _Eng __e(__g, __w); 2749 _UIntType __u; 2750 do 2751 { 2752 __u = __e(); 2753 } while (__u >= _Rp); 2754 return static_cast<result_type>(__u + __p.a()); 2755} 2756 2757class __rs_default; 2758 2759__rs_default __rs_get(); 2760 2761class __rs_default 2762{ 2763 static unsigned __c_; 2764 2765 __rs_default(); 2766public: 2767 typedef unsigned result_type; 2768 2769 static const result_type _Min = 0; 2770 static const result_type _Max = 0xFFFFFFFF; 2771 2772 __rs_default(const __rs_default&); 2773 ~__rs_default(); 2774 2775 result_type operator()(); 2776 2777 static _LIBCPP_CONSTEXPR result_type min() {return _Min;} 2778 static _LIBCPP_CONSTEXPR result_type max() {return _Max;} 2779 2780 friend __rs_default __rs_get(); 2781}; 2782 2783__rs_default __rs_get(); 2784 2785template <class _RandomAccessIterator> 2786void 2787random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 2788{ 2789 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 2790 typedef uniform_int_distribution<ptrdiff_t> _Dp; 2791 typedef typename _Dp::param_type _Pp; 2792 difference_type __d = __last - __first; 2793 if (__d > 1) 2794 { 2795 _Dp __uid; 2796 __rs_default __g = __rs_get(); 2797 for (--__last, --__d; __first < __last; ++__first, --__d) 2798 { 2799 difference_type __i = __uid(__g, _Pp(0, __d)); 2800 if (__i != difference_type(0)) 2801 swap(*__first, *(__first + __i)); 2802 } 2803 } 2804} 2805 2806template <class _RandomAccessIterator, class _RandomNumberGenerator> 2807void 2808random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 2809#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2810 _RandomNumberGenerator&& __rand) 2811#else 2812 _RandomNumberGenerator& __rand) 2813#endif 2814{ 2815 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 2816 difference_type __d = __last - __first; 2817 if (__d > 1) 2818 { 2819 for (--__last; __first < __last; ++__first, --__d) 2820 { 2821 difference_type __i = __rand(__d); 2822 swap(*__first, *(__first + __i)); 2823 } 2824 } 2825} 2826 2827template<class _RandomAccessIterator, class _UniformRandomNumberGenerator> 2828 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 2829#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2830 _UniformRandomNumberGenerator&& __g) 2831#else 2832 _UniformRandomNumberGenerator& __g) 2833#endif 2834{ 2835 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 2836 typedef uniform_int_distribution<ptrdiff_t> _Dp; 2837 typedef typename _Dp::param_type _Pp; 2838 difference_type __d = __last - __first; 2839 if (__d > 1) 2840 { 2841 _Dp __uid; 2842 for (--__last, --__d; __first < __last; ++__first, --__d) 2843 { 2844 difference_type __i = __uid(__g, _Pp(0, __d)); 2845 if (__i != difference_type(0)) 2846 swap(*__first, *(__first + __i)); 2847 } 2848 } 2849} 2850 2851template <class _InputIterator, class _Predicate> 2852bool 2853is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred) 2854{ 2855 for (; __first != __last; ++__first) 2856 if (!__pred(*__first)) 2857 break; 2858 for (; __first != __last; ++__first) 2859 if (__pred(*__first)) 2860 return false; 2861 return true; 2862} 2863 2864// partition 2865 2866template <class _Predicate, class _ForwardIterator> 2867_ForwardIterator 2868__partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag) 2869{ 2870 while (true) 2871 { 2872 if (__first == __last) 2873 return __first; 2874 if (!__pred(*__first)) 2875 break; 2876 ++__first; 2877 } 2878 for (_ForwardIterator __p = __first; ++__p != __last;) 2879 { 2880 if (__pred(*__p)) 2881 { 2882 swap(*__first, *__p); 2883 ++__first; 2884 } 2885 } 2886 return __first; 2887} 2888 2889template <class _Predicate, class _BidirectionalIterator> 2890_BidirectionalIterator 2891__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 2892 bidirectional_iterator_tag) 2893{ 2894 while (true) 2895 { 2896 while (true) 2897 { 2898 if (__first == __last) 2899 return __first; 2900 if (!__pred(*__first)) 2901 break; 2902 ++__first; 2903 } 2904 do 2905 { 2906 if (__first == --__last) 2907 return __first; 2908 } while (!__pred(*__last)); 2909 swap(*__first, *__last); 2910 ++__first; 2911 } 2912} 2913 2914template <class _ForwardIterator, class _Predicate> 2915inline _LIBCPP_INLINE_VISIBILITY 2916_ForwardIterator 2917partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 2918{ 2919 return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type> 2920 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); 2921} 2922 2923// partition_copy 2924 2925template <class _InputIterator, class _OutputIterator1, 2926 class _OutputIterator2, class _Predicate> 2927pair<_OutputIterator1, _OutputIterator2> 2928partition_copy(_InputIterator __first, _InputIterator __last, 2929 _OutputIterator1 __out_true, _OutputIterator2 __out_false, 2930 _Predicate __pred) 2931{ 2932 for (; __first != __last; ++__first) 2933 { 2934 if (__pred(*__first)) 2935 { 2936 *__out_true = *__first; 2937 ++__out_true; 2938 } 2939 else 2940 { 2941 *__out_false = *__first; 2942 ++__out_false; 2943 } 2944 } 2945 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false); 2946} 2947 2948// partition_point 2949 2950template<class _ForwardIterator, class _Predicate> 2951_ForwardIterator 2952partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 2953{ 2954 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 2955 difference_type __len = _VSTD::distance(__first, __last); 2956 while (__len != 0) 2957 { 2958 difference_type __l2 = __len / 2; 2959 _ForwardIterator __m = __first; 2960 _VSTD::advance(__m, __l2); 2961 if (__pred(*__m)) 2962 { 2963 __first = ++__m; 2964 __len -= __l2 + 1; 2965 } 2966 else 2967 __len = __l2; 2968 } 2969 return __first; 2970} 2971 2972// stable_partition 2973 2974template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair> 2975_ForwardIterator 2976__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, 2977 _Distance __len, _Pair __p, forward_iterator_tag __fit) 2978{ 2979 // *__first is known to be false 2980 // __len >= 1 2981 if (__len == 1) 2982 return __first; 2983 if (__len == 2) 2984 { 2985 _ForwardIterator __m = __first; 2986 if (__pred(*++__m)) 2987 { 2988 swap(*__first, *__m); 2989 return __m; 2990 } 2991 return __first; 2992 } 2993 if (__len <= __p.second) 2994 { // The buffer is big enough to use 2995 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 2996 __destruct_n __d(0); 2997 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); 2998 // Move the falses into the temporary buffer, and the trues to the front of the line 2999 // Update __first to always point to the end of the trues 3000 value_type* __t = __p.first; 3001 ::new(__t) value_type(_VSTD::move(*__first)); 3002 __d.__incr((value_type*)0); 3003 ++__t; 3004 _ForwardIterator __i = __first; 3005 while (++__i != __last) 3006 { 3007 if (__pred(*__i)) 3008 { 3009 *__first = _VSTD::move(*__i); 3010 ++__first; 3011 } 3012 else 3013 { 3014 ::new(__t) value_type(_VSTD::move(*__i)); 3015 __d.__incr((value_type*)0); 3016 ++__t; 3017 } 3018 } 3019 // All trues now at start of range, all falses in buffer 3020 // Move falses back into range, but don't mess up __first which points to first false 3021 __i = __first; 3022 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i) 3023 *__i = _VSTD::move(*__t2); 3024 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer 3025 return __first; 3026 } 3027 // Else not enough buffer, do in place 3028 // __len >= 3 3029 _ForwardIterator __m = __first; 3030 _Distance __len2 = __len / 2; // __len2 >= 2 3031 _VSTD::advance(__m, __len2); 3032 // recurse on [__first, __m), *__first know to be false 3033 // F????????????????? 3034 // f m l 3035 typedef typename add_lvalue_reference<_Predicate>::type _PredRef; 3036 _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit); 3037 // TTTFFFFF?????????? 3038 // f ff m l 3039 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true 3040 _ForwardIterator __m1 = __m; 3041 _ForwardIterator __second_false = __last; 3042 _Distance __len_half = __len - __len2; 3043 while (__pred(*__m1)) 3044 { 3045 if (++__m1 == __last) 3046 goto __second_half_done; 3047 --__len_half; 3048 } 3049 // TTTFFFFFTTTF?????? 3050 // f ff m m1 l 3051 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit); 3052__second_half_done: 3053 // TTTFFFFFTTTTTFFFFF 3054 // f ff m sf l 3055 return _VSTD::rotate(__first_false, __m, __second_false); 3056 // TTTTTTTTFFFFFFFFFF 3057 // | 3058} 3059 3060struct __return_temporary_buffer 3061{ 3062 template <class _Tp> 3063 _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);} 3064}; 3065 3066template <class _Predicate, class _ForwardIterator> 3067_ForwardIterator 3068__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, 3069 forward_iterator_tag) 3070{ 3071 const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment 3072 // Either prove all true and return __first or point to first false 3073 while (true) 3074 { 3075 if (__first == __last) 3076 return __first; 3077 if (!__pred(*__first)) 3078 break; 3079 ++__first; 3080 } 3081 // We now have a reduced range [__first, __last) 3082 // *__first is known to be false 3083 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 3084 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 3085 difference_type __len = _VSTD::distance(__first, __last); 3086 pair<value_type*, ptrdiff_t> __p(0, 0); 3087 unique_ptr<value_type, __return_temporary_buffer> __h; 3088 if (__len >= __alloc_limit) 3089 { 3090 __p = _VSTD::get_temporary_buffer<value_type>(__len); 3091 __h.reset(__p.first); 3092 } 3093 return __stable_partition<typename add_lvalue_reference<_Predicate>::type> 3094 (__first, __last, __pred, __len, __p, forward_iterator_tag()); 3095} 3096 3097template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair> 3098_BidirectionalIterator 3099__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 3100 _Distance __len, _Pair __p, bidirectional_iterator_tag __bit) 3101{ 3102 // *__first is known to be false 3103 // *__last is known to be true 3104 // __len >= 2 3105 if (__len == 2) 3106 { 3107 swap(*__first, *__last); 3108 return __last; 3109 } 3110 if (__len == 3) 3111 { 3112 _BidirectionalIterator __m = __first; 3113 if (__pred(*++__m)) 3114 { 3115 swap(*__first, *__m); 3116 swap(*__m, *__last); 3117 return __last; 3118 } 3119 swap(*__m, *__last); 3120 swap(*__first, *__m); 3121 return __m; 3122 } 3123 if (__len <= __p.second) 3124 { // The buffer is big enough to use 3125 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 3126 __destruct_n __d(0); 3127 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); 3128 // Move the falses into the temporary buffer, and the trues to the front of the line 3129 // Update __first to always point to the end of the trues 3130 value_type* __t = __p.first; 3131 ::new(__t) value_type(_VSTD::move(*__first)); 3132 __d.__incr((value_type*)0); 3133 ++__t; 3134 _BidirectionalIterator __i = __first; 3135 while (++__i != __last) 3136 { 3137 if (__pred(*__i)) 3138 { 3139 *__first = _VSTD::move(*__i); 3140 ++__first; 3141 } 3142 else 3143 { 3144 ::new(__t) value_type(_VSTD::move(*__i)); 3145 __d.__incr((value_type*)0); 3146 ++__t; 3147 } 3148 } 3149 // move *__last, known to be true 3150 *__first = _VSTD::move(*__i); 3151 __i = ++__first; 3152 // All trues now at start of range, all falses in buffer 3153 // Move falses back into range, but don't mess up __first which points to first false 3154 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i) 3155 *__i = _VSTD::move(*__t2); 3156 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer 3157 return __first; 3158 } 3159 // Else not enough buffer, do in place 3160 // __len >= 4 3161 _BidirectionalIterator __m = __first; 3162 _Distance __len2 = __len / 2; // __len2 >= 2 3163 _VSTD::advance(__m, __len2); 3164 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false 3165 // F????????????????T 3166 // f m l 3167 _BidirectionalIterator __m1 = __m; 3168 _BidirectionalIterator __first_false = __first; 3169 _Distance __len_half = __len2; 3170 while (!__pred(*--__m1)) 3171 { 3172 if (__m1 == __first) 3173 goto __first_half_done; 3174 --__len_half; 3175 } 3176 // F???TFFF?????????T 3177 // f m1 m l 3178 typedef typename add_lvalue_reference<_Predicate>::type _PredRef; 3179 __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit); 3180__first_half_done: 3181 // TTTFFFFF?????????T 3182 // f ff m l 3183 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true 3184 __m1 = __m; 3185 _BidirectionalIterator __second_false = __last; 3186 ++__second_false; 3187 __len_half = __len - __len2; 3188 while (__pred(*__m1)) 3189 { 3190 if (++__m1 == __last) 3191 goto __second_half_done; 3192 --__len_half; 3193 } 3194 // TTTFFFFFTTTF?????T 3195 // f ff m m1 l 3196 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit); 3197__second_half_done: 3198 // TTTFFFFFTTTTTFFFFF 3199 // f ff m sf l 3200 return _VSTD::rotate(__first_false, __m, __second_false); 3201 // TTTTTTTTFFFFFFFFFF 3202 // | 3203} 3204 3205template <class _Predicate, class _BidirectionalIterator> 3206_BidirectionalIterator 3207__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 3208 bidirectional_iterator_tag) 3209{ 3210 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 3211 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 3212 const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment 3213 // Either prove all true and return __first or point to first false 3214 while (true) 3215 { 3216 if (__first == __last) 3217 return __first; 3218 if (!__pred(*__first)) 3219 break; 3220 ++__first; 3221 } 3222 // __first points to first false, everything prior to __first is already set. 3223 // Either prove [__first, __last) is all false and return __first, or point __last to last true 3224 do 3225 { 3226 if (__first == --__last) 3227 return __first; 3228 } while (!__pred(*__last)); 3229 // We now have a reduced range [__first, __last] 3230 // *__first is known to be false 3231 // *__last is known to be true 3232 // __len >= 2 3233 difference_type __len = _VSTD::distance(__first, __last) + 1; 3234 pair<value_type*, ptrdiff_t> __p(0, 0); 3235 unique_ptr<value_type, __return_temporary_buffer> __h; 3236 if (__len >= __alloc_limit) 3237 { 3238 __p = _VSTD::get_temporary_buffer<value_type>(__len); 3239 __h.reset(__p.first); 3240 } 3241 return __stable_partition<typename add_lvalue_reference<_Predicate>::type> 3242 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag()); 3243} 3244 3245template <class _ForwardIterator, class _Predicate> 3246inline _LIBCPP_INLINE_VISIBILITY 3247_ForwardIterator 3248stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 3249{ 3250 return __stable_partition<typename add_lvalue_reference<_Predicate>::type> 3251 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); 3252} 3253 3254// is_sorted_until 3255 3256template <class _ForwardIterator, class _Compare> 3257_ForwardIterator 3258is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 3259{ 3260 if (__first != __last) 3261 { 3262 _ForwardIterator __i = __first; 3263 while (++__i != __last) 3264 { 3265 if (__comp(*__i, *__first)) 3266 return __i; 3267 __first = __i; 3268 } 3269 } 3270 return __last; 3271} 3272 3273template<class _ForwardIterator> 3274inline _LIBCPP_INLINE_VISIBILITY 3275_ForwardIterator 3276is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) 3277{ 3278 return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); 3279} 3280 3281// is_sorted 3282 3283template <class _ForwardIterator, class _Compare> 3284inline _LIBCPP_INLINE_VISIBILITY 3285bool 3286is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 3287{ 3288 return _VSTD::is_sorted_until(__first, __last, __comp) == __last; 3289} 3290 3291template<class _ForwardIterator> 3292inline _LIBCPP_INLINE_VISIBILITY 3293bool 3294is_sorted(_ForwardIterator __first, _ForwardIterator __last) 3295{ 3296 return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); 3297} 3298 3299// sort 3300 3301// stable, 2-3 compares, 0-2 swaps 3302 3303template <class _Compare, class _ForwardIterator> 3304unsigned 3305__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c) 3306{ 3307 unsigned __r = 0; 3308 if (!__c(*__y, *__x)) // if x <= y 3309 { 3310 if (!__c(*__z, *__y)) // if y <= z 3311 return __r; // x <= y && y <= z 3312 // x <= y && y > z 3313 swap(*__y, *__z); // x <= z && y < z 3314 __r = 1; 3315 if (__c(*__y, *__x)) // if x > y 3316 { 3317 swap(*__x, *__y); // x < y && y <= z 3318 __r = 2; 3319 } 3320 return __r; // x <= y && y < z 3321 } 3322 if (__c(*__z, *__y)) // x > y, if y > z 3323 { 3324 swap(*__x, *__z); // x < y && y < z 3325 __r = 1; 3326 return __r; 3327 } 3328 swap(*__x, *__y); // x > y && y <= z 3329 __r = 1; // x < y && x <= z 3330 if (__c(*__z, *__y)) // if y > z 3331 { 3332 swap(*__y, *__z); // x <= y && y < z 3333 __r = 2; 3334 } 3335 return __r; 3336} // x <= y && y <= z 3337 3338// stable, 3-6 compares, 0-5 swaps 3339 3340template <class _Compare, class _ForwardIterator> 3341unsigned 3342__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 3343 _ForwardIterator __x4, _Compare __c) 3344{ 3345 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c); 3346 if (__c(*__x4, *__x3)) 3347 { 3348 swap(*__x3, *__x4); 3349 ++__r; 3350 if (__c(*__x3, *__x2)) 3351 { 3352 swap(*__x2, *__x3); 3353 ++__r; 3354 if (__c(*__x2, *__x1)) 3355 { 3356 swap(*__x1, *__x2); 3357 ++__r; 3358 } 3359 } 3360 } 3361 return __r; 3362} 3363 3364// stable, 4-10 compares, 0-9 swaps 3365 3366template <class _Compare, class _ForwardIterator> 3367unsigned 3368__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 3369 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) 3370{ 3371 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c); 3372 if (__c(*__x5, *__x4)) 3373 { 3374 swap(*__x4, *__x5); 3375 ++__r; 3376 if (__c(*__x4, *__x3)) 3377 { 3378 swap(*__x3, *__x4); 3379 ++__r; 3380 if (__c(*__x3, *__x2)) 3381 { 3382 swap(*__x2, *__x3); 3383 ++__r; 3384 if (__c(*__x2, *__x1)) 3385 { 3386 swap(*__x1, *__x2); 3387 ++__r; 3388 } 3389 } 3390 } 3391 } 3392 return __r; 3393} 3394 3395// Assumes size > 0 3396template <class _Compare, class _BirdirectionalIterator> 3397void 3398__selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp) 3399{ 3400 _BirdirectionalIterator __lm1 = __last; 3401 for (--__lm1; __first != __lm1; ++__first) 3402 { 3403 _BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator, 3404 typename add_lvalue_reference<_Compare>::type> 3405 (__first, __last, __comp); 3406 if (__i != __first) 3407 swap(*__first, *__i); 3408 } 3409} 3410 3411template <class _Compare, class _BirdirectionalIterator> 3412void 3413__insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp) 3414{ 3415 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type; 3416 if (__first != __last) 3417 { 3418 _BirdirectionalIterator __i = __first; 3419 for (++__i; __i != __last; ++__i) 3420 { 3421 _BirdirectionalIterator __j = __i; 3422 value_type __t(_VSTD::move(*__j)); 3423 for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j) 3424 *__j = _VSTD::move(*__k); 3425 *__j = _VSTD::move(__t); 3426 } 3427 } 3428} 3429 3430template <class _Compare, class _RandomAccessIterator> 3431void 3432__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 3433{ 3434 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 3435 _RandomAccessIterator __j = __first+2; 3436 __sort3<_Compare>(__first, __first+1, __j, __comp); 3437 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) 3438 { 3439 if (__comp(*__i, *__j)) 3440 { 3441 value_type __t(_VSTD::move(*__i)); 3442 _RandomAccessIterator __k = __j; 3443 __j = __i; 3444 do 3445 { 3446 *__j = _VSTD::move(*__k); 3447 __j = __k; 3448 } while (__j != __first && __comp(__t, *--__k)); 3449 *__j = _VSTD::move(__t); 3450 } 3451 __j = __i; 3452 } 3453} 3454 3455template <class _Compare, class _RandomAccessIterator> 3456bool 3457__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 3458{ 3459 switch (__last - __first) 3460 { 3461 case 0: 3462 case 1: 3463 return true; 3464 case 2: 3465 if (__comp(*--__last, *__first)) 3466 swap(*__first, *__last); 3467 return true; 3468 case 3: 3469 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); 3470 return true; 3471 case 4: 3472 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); 3473 return true; 3474 case 5: 3475 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); 3476 return true; 3477 } 3478 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 3479 _RandomAccessIterator __j = __first+2; 3480 __sort3<_Compare>(__first, __first+1, __j, __comp); 3481 const unsigned __limit = 8; 3482 unsigned __count = 0; 3483 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) 3484 { 3485 if (__comp(*__i, *__j)) 3486 { 3487 value_type __t(_VSTD::move(*__i)); 3488 _RandomAccessIterator __k = __j; 3489 __j = __i; 3490 do 3491 { 3492 *__j = _VSTD::move(*__k); 3493 __j = __k; 3494 } while (__j != __first && __comp(__t, *--__k)); 3495 *__j = _VSTD::move(__t); 3496 if (++__count == __limit) 3497 return ++__i == __last; 3498 } 3499 __j = __i; 3500 } 3501 return true; 3502} 3503 3504template <class _Compare, class _BirdirectionalIterator> 3505void 3506__insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1, 3507 typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp) 3508{ 3509 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type; 3510 if (__first1 != __last1) 3511 { 3512 __destruct_n __d(0); 3513 unique_ptr<value_type, __destruct_n&> __h(__first2, __d); 3514 value_type* __last2 = __first2; 3515 ::new(__last2) value_type(_VSTD::move(*__first1)); 3516 __d.__incr((value_type*)0); 3517 for (++__last2; ++__first1 != __last1; ++__last2) 3518 { 3519 value_type* __j2 = __last2; 3520 value_type* __i2 = __j2; 3521 if (__comp(*__first1, *--__i2)) 3522 { 3523 ::new(__j2) value_type(_VSTD::move(*__i2)); 3524 __d.__incr((value_type*)0); 3525 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) 3526 *__j2 = _VSTD::move(*__i2); 3527 *__j2 = _VSTD::move(*__first1); 3528 } 3529 else 3530 { 3531 ::new(__j2) value_type(_VSTD::move(*__first1)); 3532 __d.__incr((value_type*)0); 3533 } 3534 } 3535 __h.release(); 3536 } 3537} 3538 3539template <class _Compare, class _RandomAccessIterator> 3540void 3541__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 3542{ 3543 // _Compare is known to be a reference type 3544 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 3545 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 3546 const difference_type __limit = is_trivially_copy_constructible<value_type>::value && 3547 is_trivially_copy_assignable<value_type>::value ? 30 : 6; 3548 while (true) 3549 { 3550 __restart: 3551 difference_type __len = __last - __first; 3552 switch (__len) 3553 { 3554 case 0: 3555 case 1: 3556 return; 3557 case 2: 3558 if (__comp(*--__last, *__first)) 3559 swap(*__first, *__last); 3560 return; 3561 case 3: 3562 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); 3563 return; 3564 case 4: 3565 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); 3566 return; 3567 case 5: 3568 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); 3569 return; 3570 } 3571 if (__len <= __limit) 3572 { 3573 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); 3574 return; 3575 } 3576 // __len > 5 3577 _RandomAccessIterator __m = __first; 3578 _RandomAccessIterator __lm1 = __last; 3579 --__lm1; 3580 unsigned __n_swaps; 3581 { 3582 difference_type __delta; 3583 if (__len >= 1000) 3584 { 3585 __delta = __len/2; 3586 __m += __delta; 3587 __delta /= 2; 3588 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp); 3589 } 3590 else 3591 { 3592 __delta = __len/2; 3593 __m += __delta; 3594 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); 3595 } 3596 } 3597 // *__m is median 3598 // partition [__first, __m) < *__m and *__m <= [__m, __last) 3599 // (this inhibits tossing elements equivalent to __m around unnecessarily) 3600 _RandomAccessIterator __i = __first; 3601 _RandomAccessIterator __j = __lm1; 3602 // j points beyond range to be tested, *__m is known to be <= *__lm1 3603 // The search going up is known to be guarded but the search coming down isn't. 3604 // Prime the downward search with a guard. 3605 if (!__comp(*__i, *__m)) // if *__first == *__m 3606 { 3607 // *__first == *__m, *__first doesn't go in first part 3608 // manually guard downward moving __j against __i 3609 while (true) 3610 { 3611 if (__i == --__j) 3612 { 3613 // *__first == *__m, *__m <= all other elements 3614 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) 3615 ++__i; // __first + 1 3616 __j = __last; 3617 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) 3618 { 3619 while (true) 3620 { 3621 if (__i == __j) 3622 return; // [__first, __last) all equivalent elements 3623 if (__comp(*__first, *__i)) 3624 { 3625 swap(*__i, *__j); 3626 ++__n_swaps; 3627 ++__i; 3628 break; 3629 } 3630 ++__i; 3631 } 3632 } 3633 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 3634 if (__i == __j) 3635 return; 3636 while (true) 3637 { 3638 while (!__comp(*__first, *__i)) 3639 ++__i; 3640 while (__comp(*__first, *--__j)) 3641 ; 3642 if (__i >= __j) 3643 break; 3644 swap(*__i, *__j); 3645 ++__n_swaps; 3646 ++__i; 3647 } 3648 // [__first, __i) == *__first and *__first < [__i, __last) 3649 // The first part is sorted, sort the secod part 3650 // _VSTD::__sort<_Compare>(__i, __last, __comp); 3651 __first = __i; 3652 goto __restart; 3653 } 3654 if (__comp(*__j, *__m)) 3655 { 3656 swap(*__i, *__j); 3657 ++__n_swaps; 3658 break; // found guard for downward moving __j, now use unguarded partition 3659 } 3660 } 3661 } 3662 // It is known that *__i < *__m 3663 ++__i; 3664 // j points beyond range to be tested, *__m is known to be <= *__lm1 3665 // if not yet partitioned... 3666 if (__i < __j) 3667 { 3668 // known that *(__i - 1) < *__m 3669 // known that __i <= __m 3670 while (true) 3671 { 3672 // __m still guards upward moving __i 3673 while (__comp(*__i, *__m)) 3674 ++__i; 3675 // It is now known that a guard exists for downward moving __j 3676 while (!__comp(*--__j, *__m)) 3677 ; 3678 if (__i > __j) 3679 break; 3680 swap(*__i, *__j); 3681 ++__n_swaps; 3682 // It is known that __m != __j 3683 // If __m just moved, follow it 3684 if (__m == __i) 3685 __m = __j; 3686 ++__i; 3687 } 3688 } 3689 // [__first, __i) < *__m and *__m <= [__i, __last) 3690 if (__i != __m && __comp(*__m, *__i)) 3691 { 3692 swap(*__i, *__m); 3693 ++__n_swaps; 3694 } 3695 // [__first, __i) < *__i and *__i <= [__i+1, __last) 3696 // If we were given a perfect partition, see if insertion sort is quick... 3697 if (__n_swaps == 0) 3698 { 3699 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); 3700 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp)) 3701 { 3702 if (__fs) 3703 return; 3704 __last = __i; 3705 continue; 3706 } 3707 else 3708 { 3709 if (__fs) 3710 { 3711 __first = ++__i; 3712 continue; 3713 } 3714 } 3715 } 3716 // sort smaller range with recursive call and larger with tail recursion elimination 3717 if (__i - __first < __last - __i) 3718 { 3719 _VSTD::__sort<_Compare>(__first, __i, __comp); 3720 // _VSTD::__sort<_Compare>(__i+1, __last, __comp); 3721 __first = ++__i; 3722 } 3723 else 3724 { 3725 _VSTD::__sort<_Compare>(__i+1, __last, __comp); 3726 // _VSTD::__sort<_Compare>(__first, __i, __comp); 3727 __last = __i; 3728 } 3729 } 3730} 3731 3732// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare 3733template <class _RandomAccessIterator, class _Compare> 3734inline _LIBCPP_INLINE_VISIBILITY 3735void 3736sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 3737{ 3738#ifdef _LIBCPP_DEBUG2 3739 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 3740 __debug_less<_Compare> __c(__comp); 3741 __sort<_Comp_ref>(__first, __last, __c); 3742#else // _LIBCPP_DEBUG2 3743 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 3744 __sort<_Comp_ref>(__first, __last, __comp); 3745#endif // _LIBCPP_DEBUG2 3746} 3747 3748template <class _RandomAccessIterator> 3749inline _LIBCPP_INLINE_VISIBILITY 3750void 3751sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 3752{ 3753 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 3754} 3755 3756template <class _Tp> 3757inline _LIBCPP_INLINE_VISIBILITY 3758void 3759sort(_Tp** __first, _Tp** __last) 3760{ 3761 _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>()); 3762} 3763 3764template <class _Tp> 3765inline _LIBCPP_INLINE_VISIBILITY 3766void 3767sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last) 3768{ 3769 _VSTD::sort(__first.base(), __last.base()); 3770} 3771 3772template <class _Tp, class _Compare> 3773inline _LIBCPP_INLINE_VISIBILITY 3774void 3775sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp) 3776{ 3777 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 3778 _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp); 3779} 3780 3781#ifdef _MSC_VER 3782#pragma warning( push ) 3783#pragma warning( disable: 4231) 3784#endif // _MSC_VER 3785_LIBCPP_EXTERN_TEMPLATE(void __sort<__less<char>&, char*>(char*, char*, __less<char>&)) 3786_LIBCPP_EXTERN_TEMPLATE(void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) 3787_LIBCPP_EXTERN_TEMPLATE(void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) 3788_LIBCPP_EXTERN_TEMPLATE(void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) 3789_LIBCPP_EXTERN_TEMPLATE(void __sort<__less<short>&, short*>(short*, short*, __less<short>&)) 3790_LIBCPP_EXTERN_TEMPLATE(void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) 3791_LIBCPP_EXTERN_TEMPLATE(void __sort<__less<int>&, int*>(int*, int*, __less<int>&)) 3792_LIBCPP_EXTERN_TEMPLATE(void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) 3793_LIBCPP_EXTERN_TEMPLATE(void __sort<__less<long>&, long*>(long*, long*, __less<long>&)) 3794_LIBCPP_EXTERN_TEMPLATE(void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) 3795_LIBCPP_EXTERN_TEMPLATE(void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) 3796_LIBCPP_EXTERN_TEMPLATE(void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&)) 3797_LIBCPP_EXTERN_TEMPLATE(void __sort<__less<float>&, float*>(float*, float*, __less<float>&)) 3798_LIBCPP_EXTERN_TEMPLATE(void __sort<__less<double>&, double*>(double*, double*, __less<double>&)) 3799_LIBCPP_EXTERN_TEMPLATE(void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) 3800 3801_LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&)) 3802_LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) 3803_LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) 3804_LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) 3805_LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&)) 3806_LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) 3807_LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&)) 3808_LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) 3809_LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&)) 3810_LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) 3811_LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) 3812_LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&)) 3813_LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&)) 3814_LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&)) 3815_LIBCPP_EXTERN_TEMPLATE(bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) 3816 3817_LIBCPP_EXTERN_TEMPLATE(unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&)) 3818#ifdef _MSC_VER 3819#pragma warning( pop ) 3820#endif // _MSC_VER 3821 3822// lower_bound 3823 3824template <class _Compare, class _ForwardIterator, class _Tp> 3825_ForwardIterator 3826__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 3827{ 3828 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 3829 difference_type __len = _VSTD::distance(__first, __last); 3830 while (__len != 0) 3831 { 3832 difference_type __l2 = __len / 2; 3833 _ForwardIterator __m = __first; 3834 _VSTD::advance(__m, __l2); 3835 if (__comp(*__m, __value_)) 3836 { 3837 __first = ++__m; 3838 __len -= __l2 + 1; 3839 } 3840 else 3841 __len = __l2; 3842 } 3843 return __first; 3844} 3845 3846template <class _ForwardIterator, class _Tp, class _Compare> 3847inline _LIBCPP_INLINE_VISIBILITY 3848_ForwardIterator 3849lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 3850{ 3851#ifdef _LIBCPP_DEBUG2 3852 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 3853 __debug_less<_Compare> __c(__comp); 3854 return __lower_bound<_Comp_ref>(__first, __last, __value_, __c); 3855#else // _LIBCPP_DEBUG2 3856 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 3857 return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp); 3858#endif // _LIBCPP_DEBUG2 3859} 3860 3861template <class _ForwardIterator, class _Tp> 3862inline _LIBCPP_INLINE_VISIBILITY 3863_ForwardIterator 3864lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 3865{ 3866 return _VSTD::lower_bound(__first, __last, __value_, 3867 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 3868} 3869 3870// upper_bound 3871 3872template <class _Compare, class _ForwardIterator, class _Tp> 3873_ForwardIterator 3874__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 3875{ 3876 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 3877 difference_type __len = _VSTD::distance(__first, __last); 3878 while (__len != 0) 3879 { 3880 difference_type __l2 = __len / 2; 3881 _ForwardIterator __m = __first; 3882 _VSTD::advance(__m, __l2); 3883 if (__comp(__value_, *__m)) 3884 __len = __l2; 3885 else 3886 { 3887 __first = ++__m; 3888 __len -= __l2 + 1; 3889 } 3890 } 3891 return __first; 3892} 3893 3894template <class _ForwardIterator, class _Tp, class _Compare> 3895inline _LIBCPP_INLINE_VISIBILITY 3896_ForwardIterator 3897upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 3898{ 3899#ifdef _LIBCPP_DEBUG2 3900 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 3901 __debug_less<_Compare> __c(__comp); 3902 return __upper_bound<_Comp_ref>(__first, __last, __value_, __c); 3903#else // _LIBCPP_DEBUG2 3904 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 3905 return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp); 3906#endif // _LIBCPP_DEBUG2 3907} 3908 3909template <class _ForwardIterator, class _Tp> 3910inline _LIBCPP_INLINE_VISIBILITY 3911_ForwardIterator 3912upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 3913{ 3914 return _VSTD::upper_bound(__first, __last, __value_, 3915 __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>()); 3916} 3917 3918// equal_range 3919 3920template <class _Compare, class _ForwardIterator, class _Tp> 3921pair<_ForwardIterator, _ForwardIterator> 3922__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 3923{ 3924 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 3925 difference_type __len = _VSTD::distance(__first, __last); 3926 while (__len != 0) 3927 { 3928 difference_type __l2 = __len / 2; 3929 _ForwardIterator __m = __first; 3930 _VSTD::advance(__m, __l2); 3931 if (__comp(*__m, __value_)) 3932 { 3933 __first = ++__m; 3934 __len -= __l2 + 1; 3935 } 3936 else if (__comp(__value_, *__m)) 3937 { 3938 __last = __m; 3939 __len = __l2; 3940 } 3941 else 3942 { 3943 _ForwardIterator __mp1 = __m; 3944 return pair<_ForwardIterator, _ForwardIterator> 3945 ( 3946 __lower_bound<_Compare>(__first, __m, __value_, __comp), 3947 __upper_bound<_Compare>(++__mp1, __last, __value_, __comp) 3948 ); 3949 } 3950 } 3951 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 3952} 3953 3954template <class _ForwardIterator, class _Tp, class _Compare> 3955inline _LIBCPP_INLINE_VISIBILITY 3956pair<_ForwardIterator, _ForwardIterator> 3957equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 3958{ 3959#ifdef _LIBCPP_DEBUG2 3960 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 3961 __debug_less<_Compare> __c(__comp); 3962 return __equal_range<_Comp_ref>(__first, __last, __value_, __c); 3963#else // _LIBCPP_DEBUG2 3964 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 3965 return __equal_range<_Comp_ref>(__first, __last, __value_, __comp); 3966#endif // _LIBCPP_DEBUG2 3967} 3968 3969template <class _ForwardIterator, class _Tp> 3970inline _LIBCPP_INLINE_VISIBILITY 3971pair<_ForwardIterator, _ForwardIterator> 3972equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 3973{ 3974 return _VSTD::equal_range(__first, __last, __value_, 3975 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 3976} 3977 3978// binary_search 3979 3980template <class _Compare, class _ForwardIterator, class _Tp> 3981inline _LIBCPP_INLINE_VISIBILITY 3982bool 3983__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 3984{ 3985 __first = __lower_bound<_Compare>(__first, __last, __value_, __comp); 3986 return __first != __last && !__comp(__value_, *__first); 3987} 3988 3989template <class _ForwardIterator, class _Tp, class _Compare> 3990inline _LIBCPP_INLINE_VISIBILITY 3991bool 3992binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 3993{ 3994#ifdef _LIBCPP_DEBUG2 3995 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 3996 __debug_less<_Compare> __c(__comp); 3997 return __binary_search<_Comp_ref>(__first, __last, __value_, __c); 3998#else // _LIBCPP_DEBUG2 3999 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4000 return __binary_search<_Comp_ref>(__first, __last, __value_, __comp); 4001#endif // _LIBCPP_DEBUG2 4002} 4003 4004template <class _ForwardIterator, class _Tp> 4005inline _LIBCPP_INLINE_VISIBILITY 4006bool 4007binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4008{ 4009 return _VSTD::binary_search(__first, __last, __value_, 4010 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 4011} 4012 4013// merge 4014 4015template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 4016_OutputIterator 4017__merge(_InputIterator1 __first1, _InputIterator1 __last1, 4018 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 4019{ 4020 for (; __first1 != __last1; ++__result) 4021 { 4022 if (__first2 == __last2) 4023 return _VSTD::copy(__first1, __last1, __result); 4024 if (__comp(*__first2, *__first1)) 4025 { 4026 *__result = *__first2; 4027 ++__first2; 4028 } 4029 else 4030 { 4031 *__result = *__first1; 4032 ++__first1; 4033 } 4034 } 4035 return _VSTD::copy(__first2, __last2, __result); 4036} 4037 4038template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 4039inline _LIBCPP_INLINE_VISIBILITY 4040_OutputIterator 4041merge(_InputIterator1 __first1, _InputIterator1 __last1, 4042 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 4043{ 4044#ifdef _LIBCPP_DEBUG2 4045 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4046 __debug_less<_Compare> __c(__comp); 4047 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c); 4048#else // _LIBCPP_DEBUG2 4049 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4050 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 4051#endif // _LIBCPP_DEBUG2 4052} 4053 4054template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 4055inline _LIBCPP_INLINE_VISIBILITY 4056_OutputIterator 4057merge(_InputIterator1 __first1, _InputIterator1 __last1, 4058 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 4059{ 4060 typedef typename iterator_traits<_InputIterator1>::value_type __v1; 4061 typedef typename iterator_traits<_InputIterator2>::value_type __v2; 4062 return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>()); 4063} 4064 4065// inplace_merge 4066 4067template <class _Compare, class _BidirectionalIterator> 4068void 4069__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4070 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, 4071 typename iterator_traits<_BidirectionalIterator>::difference_type __len2, 4072 typename iterator_traits<_BidirectionalIterator>::value_type* __buff) 4073{ 4074 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 4075 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 4076 typedef typename iterator_traits<_BidirectionalIterator>::pointer pointer; 4077 __destruct_n __d(0); 4078 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); 4079 if (__len1 <= __len2) 4080 { 4081 value_type* __p = __buff; 4082 for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), ++__i, ++__p) 4083 ::new(__p) value_type(_VSTD::move(*__i)); 4084 __merge<_Compare>(move_iterator<value_type*>(__buff), 4085 move_iterator<value_type*>(__p), 4086 move_iterator<_BidirectionalIterator>(__middle), 4087 move_iterator<_BidirectionalIterator>(__last), 4088 __first, __comp); 4089 } 4090 else 4091 { 4092 value_type* __p = __buff; 4093 for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), ++__i, ++__p) 4094 ::new(__p) value_type(_VSTD::move(*__i)); 4095 typedef reverse_iterator<_BidirectionalIterator> _RBi; 4096 typedef reverse_iterator<value_type*> _Rv; 4097 __merge(move_iterator<_RBi>(_RBi(__middle)), move_iterator<_RBi>(_RBi(__first)), 4098 move_iterator<_Rv>(_Rv(__p)), move_iterator<_Rv>(_Rv(__buff)), 4099 _RBi(__last), __negate<_Compare>(__comp)); 4100 } 4101} 4102 4103template <class _Compare, class _BidirectionalIterator> 4104void 4105__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4106 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, 4107 typename iterator_traits<_BidirectionalIterator>::difference_type __len2, 4108 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size) 4109{ 4110 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 4111 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 4112 while (true) 4113 { 4114 // if __middle == __last, we're done 4115 if (__len2 == 0) 4116 return; 4117 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0 4118 for (; true; ++__first, --__len1) 4119 { 4120 if (__len1 == 0) 4121 return; 4122 if (__comp(*__middle, *__first)) 4123 break; 4124 } 4125 if (__len1 <= __buff_size || __len2 <= __buff_size) 4126 { 4127 __buffered_inplace_merge<_Compare>(__first, __middle, __last, __comp, __len1, __len2, __buff); 4128 return; 4129 } 4130 // __first < __middle < __last 4131 // *__first > *__middle 4132 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that 4133 // all elements in: 4134 // [__first, __m1) <= [__middle, __m2) 4135 // [__middle, __m2) < [__m1, __middle) 4136 // [__m1, __middle) <= [__m2, __last) 4137 // and __m1 or __m2 is in the middle of its range 4138 _BidirectionalIterator __m1; // "median" of [__first, __middle) 4139 _BidirectionalIterator __m2; // "median" of [__middle, __last) 4140 difference_type __len11; // distance(__first, __m1) 4141 difference_type __len21; // distance(__middle, __m2) 4142 // binary search smaller range 4143 if (__len1 < __len2) 4144 { // __len >= 1, __len2 >= 2 4145 __len21 = __len2 / 2; 4146 __m2 = __middle; 4147 _VSTD::advance(__m2, __len21); 4148 __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp); 4149 __len11 = _VSTD::distance(__first, __m1); 4150 } 4151 else 4152 { 4153 if (__len1 == 1) 4154 { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1 4155 // It is known *__first > *__middle 4156 swap(*__first, *__middle); 4157 return; 4158 } 4159 // __len1 >= 2, __len2 >= 1 4160 __len11 = __len1 / 2; 4161 __m1 = __first; 4162 _VSTD::advance(__m1, __len11); 4163 __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp); 4164 __len21 = _VSTD::distance(__middle, __m2); 4165 } 4166 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle) 4167 difference_type __len22 = __len2 - __len21; // distance(__m2, __last) 4168 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) 4169 // swap middle two partitions 4170 __middle = _VSTD::rotate(__m1, __middle, __m2); 4171 // __len12 and __len21 now have swapped meanings 4172 // merge smaller range with recurisve call and larger with tail recursion elimination 4173 if (__len11 + __len21 < __len12 + __len22) 4174 { 4175 __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); 4176// __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); 4177 __first = __middle; 4178 __middle = __m2; 4179 __len1 = __len12; 4180 __len2 = __len22; 4181 } 4182 else 4183 { 4184 __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); 4185// __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); 4186 __last = __middle; 4187 __middle = __m1; 4188 __len1 = __len11; 4189 __len2 = __len21; 4190 } 4191 } 4192} 4193 4194template <class _Tp> 4195struct __inplace_merge_switch 4196{ 4197 static const unsigned value = is_trivially_copy_assignable<_Tp>::value; 4198}; 4199 4200template <class _BidirectionalIterator, class _Compare> 4201inline _LIBCPP_INLINE_VISIBILITY 4202void 4203inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4204 _Compare __comp) 4205{ 4206 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 4207 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 4208 difference_type __len1 = _VSTD::distance(__first, __middle); 4209 difference_type __len2 = _VSTD::distance(__middle, __last); 4210 difference_type __buf_size = _VSTD::min(__len1, __len2); 4211 pair<value_type*, ptrdiff_t> __buf(0, 0); 4212 unique_ptr<value_type, __return_temporary_buffer> __h; 4213 if (__inplace_merge_switch<value_type>::value && __buf_size > 8) 4214 { 4215 __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size); 4216 __h.reset(__buf.first); 4217 } 4218#ifdef _LIBCPP_DEBUG2 4219 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4220 __debug_less<_Compare> __c(__comp); 4221 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2, 4222 __buf.first, __buf.second); 4223#else // _LIBCPP_DEBUG2 4224 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4225 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2, 4226 __buf.first, __buf.second); 4227#endif // _LIBCPP_DEBUG2 4228} 4229 4230template <class _BidirectionalIterator> 4231inline _LIBCPP_INLINE_VISIBILITY 4232void 4233inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) 4234{ 4235 _VSTD::inplace_merge(__first, __middle, __last, 4236 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 4237} 4238 4239// stable_sort 4240 4241template <class _Compare, class _InputIterator1, class _InputIterator2> 4242void 4243__merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1, 4244 _InputIterator2 __first2, _InputIterator2 __last2, 4245 typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp) 4246{ 4247 typedef typename iterator_traits<_InputIterator1>::value_type value_type; 4248 __destruct_n __d(0); 4249 unique_ptr<value_type, __destruct_n&> __h(__result, __d); 4250 for (; true; ++__result) 4251 { 4252 if (__first1 == __last1) 4253 { 4254 for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0)) 4255 ::new (__result) value_type(_VSTD::move(*__first2)); 4256 __h.release(); 4257 return; 4258 } 4259 if (__first2 == __last2) 4260 { 4261 for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0)) 4262 ::new (__result) value_type(_VSTD::move(*__first1)); 4263 __h.release(); 4264 return; 4265 } 4266 if (__comp(*__first2, *__first1)) 4267 { 4268 ::new (__result) value_type(_VSTD::move(*__first2)); 4269 __d.__incr((value_type*)0); 4270 ++__first2; 4271 } 4272 else 4273 { 4274 ::new (__result) value_type(_VSTD::move(*__first1)); 4275 __d.__incr((value_type*)0); 4276 ++__first1; 4277 } 4278 } 4279} 4280 4281template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 4282void 4283__merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1, 4284 _InputIterator2 __first2, _InputIterator2 __last2, 4285 _OutputIterator __result, _Compare __comp) 4286{ 4287 for (; __first1 != __last1; ++__result) 4288 { 4289 if (__first2 == __last2) 4290 { 4291 for (; __first1 != __last1; ++__first1, ++__result) 4292 *__result = _VSTD::move(*__first1); 4293 return; 4294 } 4295 if (__comp(*__first2, *__first1)) 4296 { 4297 *__result = _VSTD::move(*__first2); 4298 ++__first2; 4299 } 4300 else 4301 { 4302 *__result = _VSTD::move(*__first1); 4303 ++__first1; 4304 } 4305 } 4306 for (; __first2 != __last2; ++__first2, ++__result) 4307 *__result = _VSTD::move(*__first2); 4308} 4309 4310template <class _Compare, class _RandomAccessIterator> 4311void 4312__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4313 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4314 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size); 4315 4316template <class _Compare, class _RandomAccessIterator> 4317void 4318__stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp, 4319 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4320 typename iterator_traits<_RandomAccessIterator>::value_type* __first2) 4321{ 4322 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4323 switch (__len) 4324 { 4325 case 0: 4326 return; 4327 case 1: 4328 ::new(__first2) value_type(_VSTD::move(*__first1)); 4329 return; 4330 case 2: 4331 __destruct_n __d(0); 4332 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d); 4333 if (__comp(*--__last1, *__first1)) 4334 { 4335 ::new(__first2) value_type(_VSTD::move(*__last1)); 4336 __d.__incr((value_type*)0); 4337 ++__first2; 4338 ::new(__first2) value_type(_VSTD::move(*__first1)); 4339 } 4340 else 4341 { 4342 ::new(__first2) value_type(_VSTD::move(*__first1)); 4343 __d.__incr((value_type*)0); 4344 ++__first2; 4345 ::new(__first2) value_type(_VSTD::move(*__last1)); 4346 } 4347 __h2.release(); 4348 return; 4349 } 4350 if (__len <= 8) 4351 { 4352 __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp); 4353 return; 4354 } 4355 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; 4356 _RandomAccessIterator __m = __first1 + __l2; 4357 __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2); 4358 __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2); 4359 __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp); 4360} 4361 4362template <class _Tp> 4363struct __stable_sort_switch 4364{ 4365 static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value; 4366}; 4367 4368template <class _Compare, class _RandomAccessIterator> 4369void 4370__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4371 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4372 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size) 4373{ 4374 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4375 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4376 switch (__len) 4377 { 4378 case 0: 4379 case 1: 4380 return; 4381 case 2: 4382 if (__comp(*--__last, *__first)) 4383 swap(*__first, *__last); 4384 return; 4385 } 4386 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value)) 4387 { 4388 __insertion_sort<_Compare>(__first, __last, __comp); 4389 return; 4390 } 4391 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; 4392 _RandomAccessIterator __m = __first + __l2; 4393 if (__len <= __buff_size) 4394 { 4395 __destruct_n __d(0); 4396 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); 4397 __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff); 4398 __d.__set(__l2, (value_type*)0); 4399 __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2); 4400 __d.__set(__len, (value_type*)0); 4401 __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp); 4402// __merge<_Compare>(move_iterator<value_type*>(__buff), 4403// move_iterator<value_type*>(__buff + __l2), 4404// move_iterator<_RandomAccessIterator>(__buff + __l2), 4405// move_iterator<_RandomAccessIterator>(__buff + __len), 4406// __first, __comp); 4407 return; 4408 } 4409 __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size); 4410 __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); 4411 __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); 4412} 4413 4414template <class _RandomAccessIterator, class _Compare> 4415inline _LIBCPP_INLINE_VISIBILITY 4416void 4417stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4418{ 4419 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4420 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4421 difference_type __len = __last - __first; 4422 pair<value_type*, ptrdiff_t> __buf(0, 0); 4423 unique_ptr<value_type, __return_temporary_buffer> __h; 4424 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) 4425 { 4426 __buf = _VSTD::get_temporary_buffer<value_type>(__len); 4427 __h.reset(__buf.first); 4428 } 4429#ifdef _LIBCPP_DEBUG2 4430 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4431 __debug_less<_Compare> __c(__comp); 4432 __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second); 4433#else // _LIBCPP_DEBUG2 4434 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4435 __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); 4436#endif // _LIBCPP_DEBUG2 4437} 4438 4439template <class _RandomAccessIterator> 4440inline _LIBCPP_INLINE_VISIBILITY 4441void 4442stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 4443{ 4444 _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4445} 4446 4447// is_heap_until 4448 4449template <class _RandomAccessIterator, class _Compare> 4450_RandomAccessIterator 4451is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4452{ 4453 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4454 difference_type __len = __last - __first; 4455 difference_type __p = 0; 4456 difference_type __c = 1; 4457 _RandomAccessIterator __pp = __first; 4458 while (__c < __len) 4459 { 4460 _RandomAccessIterator __cp = __first + __c; 4461 if (__comp(*__pp, *__cp)) 4462 return __cp; 4463 ++__c; 4464 ++__cp; 4465 if (__c == __len) 4466 return __last; 4467 if (__comp(*__pp, *__cp)) 4468 return __cp; 4469 ++__p; 4470 ++__pp; 4471 __c = 2 * __p + 1; 4472 } 4473 return __last; 4474} 4475 4476template<class _RandomAccessIterator> 4477inline _LIBCPP_INLINE_VISIBILITY 4478_RandomAccessIterator 4479is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) 4480{ 4481 return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4482} 4483 4484// is_heap 4485 4486template <class _RandomAccessIterator, class _Compare> 4487inline _LIBCPP_INLINE_VISIBILITY 4488bool 4489is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4490{ 4491 return _VSTD::is_heap_until(__first, __last, __comp) == __last; 4492} 4493 4494template<class _RandomAccessIterator> 4495inline _LIBCPP_INLINE_VISIBILITY 4496bool 4497is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 4498{ 4499 return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4500} 4501 4502// push_heap 4503 4504template <class _Compare, class _RandomAccessIterator> 4505void 4506__push_heap_front(_RandomAccessIterator __first, _RandomAccessIterator, _Compare __comp, 4507 typename iterator_traits<_RandomAccessIterator>::difference_type __len) 4508{ 4509 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4510 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4511 if (__len > 1) 4512 { 4513 difference_type __p = 0; 4514 _RandomAccessIterator __pp = __first; 4515 difference_type __c = 2; 4516 _RandomAccessIterator __cp = __first + __c; 4517 if (__c == __len || __comp(*__cp, *(__cp - 1))) 4518 { 4519 --__c; 4520 --__cp; 4521 } 4522 if (__comp(*__pp, *__cp)) 4523 { 4524 value_type __t(_VSTD::move(*__pp)); 4525 do 4526 { 4527 *__pp = _VSTD::move(*__cp); 4528 __pp = __cp; 4529 __p = __c; 4530 __c = (__p + 1) * 2; 4531 if (__c > __len) 4532 break; 4533 __cp = __first + __c; 4534 if (__c == __len || __comp(*__cp, *(__cp - 1))) 4535 { 4536 --__c; 4537 --__cp; 4538 } 4539 } while (__comp(__t, *__cp)); 4540 *__pp = _VSTD::move(__t); 4541 } 4542 } 4543} 4544 4545template <class _Compare, class _RandomAccessIterator> 4546void 4547__push_heap_back(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4548 typename iterator_traits<_RandomAccessIterator>::difference_type __len) 4549{ 4550 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4551 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4552 if (__len > 1) 4553 { 4554 __len = (__len - 2) / 2; 4555 _RandomAccessIterator __ptr = __first + __len; 4556 if (__comp(*__ptr, *--__last)) 4557 { 4558 value_type __t(_VSTD::move(*__last)); 4559 do 4560 { 4561 *__last = _VSTD::move(*__ptr); 4562 __last = __ptr; 4563 if (__len == 0) 4564 break; 4565 __len = (__len - 1) / 2; 4566 __ptr = __first + __len; 4567 } while (__comp(*__ptr, __t)); 4568 *__last = _VSTD::move(__t); 4569 } 4570 } 4571} 4572 4573template <class _RandomAccessIterator, class _Compare> 4574inline _LIBCPP_INLINE_VISIBILITY 4575void 4576push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4577{ 4578#ifdef _LIBCPP_DEBUG2 4579 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4580 __debug_less<_Compare> __c(__comp); 4581 __push_heap_back<_Comp_ref>(__first, __last, __c, __last - __first); 4582#else // _LIBCPP_DEBUG2 4583 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4584 __push_heap_back<_Comp_ref>(__first, __last, __comp, __last - __first); 4585#endif // _LIBCPP_DEBUG2 4586} 4587 4588template <class _RandomAccessIterator> 4589inline _LIBCPP_INLINE_VISIBILITY 4590void 4591push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 4592{ 4593 _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4594} 4595 4596// pop_heap 4597 4598template <class _Compare, class _RandomAccessIterator> 4599inline _LIBCPP_INLINE_VISIBILITY 4600void 4601__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4602 typename iterator_traits<_RandomAccessIterator>::difference_type __len) 4603{ 4604 if (__len > 1) 4605 { 4606 swap(*__first, *--__last); 4607 __push_heap_front<_Compare>(__first, __last, __comp, __len-1); 4608 } 4609} 4610 4611template <class _RandomAccessIterator, class _Compare> 4612inline _LIBCPP_INLINE_VISIBILITY 4613void 4614pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4615{ 4616#ifdef _LIBCPP_DEBUG2 4617 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4618 __debug_less<_Compare> __c(__comp); 4619 __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first); 4620#else // _LIBCPP_DEBUG2 4621 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4622 __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first); 4623#endif // _LIBCPP_DEBUG2 4624} 4625 4626template <class _RandomAccessIterator> 4627inline _LIBCPP_INLINE_VISIBILITY 4628void 4629pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 4630{ 4631 _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4632} 4633 4634// make_heap 4635 4636template <class _Compare, class _RandomAccessIterator> 4637void 4638__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4639{ 4640 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4641 difference_type __n = __last - __first; 4642 if (__n > 1) 4643 { 4644 __last = __first; 4645 ++__last; 4646 for (difference_type __i = 1; __i < __n;) 4647 __push_heap_back<_Compare>(__first, ++__last, __comp, ++__i); 4648 } 4649} 4650 4651template <class _RandomAccessIterator, class _Compare> 4652inline _LIBCPP_INLINE_VISIBILITY 4653void 4654make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4655{ 4656#ifdef _LIBCPP_DEBUG2 4657 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4658 __debug_less<_Compare> __c(__comp); 4659 __make_heap<_Comp_ref>(__first, __last, __c); 4660#else // _LIBCPP_DEBUG2 4661 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4662 __make_heap<_Comp_ref>(__first, __last, __comp); 4663#endif // _LIBCPP_DEBUG2 4664} 4665 4666template <class _RandomAccessIterator> 4667inline _LIBCPP_INLINE_VISIBILITY 4668void 4669make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 4670{ 4671 _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4672} 4673 4674// sort_heap 4675 4676template <class _Compare, class _RandomAccessIterator> 4677void 4678__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4679{ 4680 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4681 for (difference_type __n = __last - __first; __n > 1; --__last, --__n) 4682 __pop_heap<_Compare>(__first, __last, __comp, __n); 4683} 4684 4685template <class _RandomAccessIterator, class _Compare> 4686inline _LIBCPP_INLINE_VISIBILITY 4687void 4688sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4689{ 4690#ifdef _LIBCPP_DEBUG2 4691 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4692 __debug_less<_Compare> __c(__comp); 4693 __sort_heap<_Comp_ref>(__first, __last, __c); 4694#else // _LIBCPP_DEBUG2 4695 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4696 __sort_heap<_Comp_ref>(__first, __last, __comp); 4697#endif // _LIBCPP_DEBUG2 4698} 4699 4700template <class _RandomAccessIterator> 4701inline _LIBCPP_INLINE_VISIBILITY 4702void 4703sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 4704{ 4705 _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4706} 4707 4708// partial_sort 4709 4710template <class _Compare, class _RandomAccessIterator> 4711void 4712__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, 4713 _Compare __comp) 4714{ 4715 __make_heap<_Compare>(__first, __middle, __comp); 4716 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first; 4717 for (_RandomAccessIterator __i = __middle; __i != __last; ++__i) 4718 { 4719 if (__comp(*__i, *__first)) 4720 { 4721 swap(*__i, *__first); 4722 __push_heap_front<_Compare>(__first, __middle, __comp, __len); 4723 } 4724 } 4725 __sort_heap<_Compare>(__first, __middle, __comp); 4726} 4727 4728template <class _RandomAccessIterator, class _Compare> 4729inline _LIBCPP_INLINE_VISIBILITY 4730void 4731partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, 4732 _Compare __comp) 4733{ 4734#ifdef _LIBCPP_DEBUG2 4735 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4736 __debug_less<_Compare> __c(__comp); 4737 __partial_sort<_Comp_ref>(__first, __middle, __last, __c); 4738#else // _LIBCPP_DEBUG2 4739 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4740 __partial_sort<_Comp_ref>(__first, __middle, __last, __comp); 4741#endif // _LIBCPP_DEBUG2 4742} 4743 4744template <class _RandomAccessIterator> 4745inline _LIBCPP_INLINE_VISIBILITY 4746void 4747partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) 4748{ 4749 _VSTD::partial_sort(__first, __middle, __last, 4750 __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4751} 4752 4753// partial_sort_copy 4754 4755template <class _Compare, class _InputIterator, class _RandomAccessIterator> 4756_RandomAccessIterator 4757__partial_sort_copy(_InputIterator __first, _InputIterator __last, 4758 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) 4759{ 4760 _RandomAccessIterator __r = __result_first; 4761 if (__r != __result_last) 4762 { 4763 typename iterator_traits<_RandomAccessIterator>::difference_type __len = 0; 4764 for (; __first != __last && __r != __result_last; ++__first, ++__r, ++__len) 4765 *__r = *__first; 4766 __make_heap<_Compare>(__result_first, __r, __comp); 4767 for (; __first != __last; ++__first) 4768 if (__comp(*__first, *__result_first)) 4769 { 4770 *__result_first = *__first; 4771 __push_heap_front<_Compare>(__result_first, __r, __comp, __len); 4772 } 4773 __sort_heap<_Compare>(__result_first, __r, __comp); 4774 } 4775 return __r; 4776} 4777 4778template <class _InputIterator, class _RandomAccessIterator, class _Compare> 4779inline _LIBCPP_INLINE_VISIBILITY 4780_RandomAccessIterator 4781partial_sort_copy(_InputIterator __first, _InputIterator __last, 4782 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) 4783{ 4784#ifdef _LIBCPP_DEBUG2 4785 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4786 __debug_less<_Compare> __c(__comp); 4787 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c); 4788#else // _LIBCPP_DEBUG2 4789 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4790 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp); 4791#endif // _LIBCPP_DEBUG2 4792} 4793 4794template <class _InputIterator, class _RandomAccessIterator> 4795inline _LIBCPP_INLINE_VISIBILITY 4796_RandomAccessIterator 4797partial_sort_copy(_InputIterator __first, _InputIterator __last, 4798 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last) 4799{ 4800 return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last, 4801 __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4802} 4803 4804// nth_element 4805 4806template <class _Compare, class _RandomAccessIterator> 4807void 4808__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) 4809{ 4810 // _Compare is known to be a reference type 4811 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4812 const difference_type __limit = 7; 4813 while (true) 4814 { 4815 __restart: 4816 if (__nth == __last) 4817 return; 4818 difference_type __len = __last - __first; 4819 switch (__len) 4820 { 4821 case 0: 4822 case 1: 4823 return; 4824 case 2: 4825 if (__comp(*--__last, *__first)) 4826 swap(*__first, *__last); 4827 return; 4828 case 3: 4829 { 4830 _RandomAccessIterator __m = __first; 4831 _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp); 4832 return; 4833 } 4834 } 4835 if (__len <= __limit) 4836 { 4837 __selection_sort<_Compare>(__first, __last, __comp); 4838 return; 4839 } 4840 // __len > __limit >= 3 4841 _RandomAccessIterator __m = __first + __len/2; 4842 _RandomAccessIterator __lm1 = __last; 4843 unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp); 4844 // *__m is median 4845 // partition [__first, __m) < *__m and *__m <= [__m, __last) 4846 // (this inhibits tossing elements equivalent to __m around unnecessarily) 4847 _RandomAccessIterator __i = __first; 4848 _RandomAccessIterator __j = __lm1; 4849 // j points beyond range to be tested, *__lm1 is known to be <= *__m 4850 // The search going up is known to be guarded but the search coming down isn't. 4851 // Prime the downward search with a guard. 4852 if (!__comp(*__i, *__m)) // if *__first == *__m 4853 { 4854 // *__first == *__m, *__first doesn't go in first part 4855 // manually guard downward moving __j against __i 4856 while (true) 4857 { 4858 if (__i == --__j) 4859 { 4860 // *__first == *__m, *__m <= all other elements 4861 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) 4862 ++__i; // __first + 1 4863 __j = __last; 4864 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) 4865 { 4866 while (true) 4867 { 4868 if (__i == __j) 4869 return; // [__first, __last) all equivalent elements 4870 if (__comp(*__first, *__i)) 4871 { 4872 swap(*__i, *__j); 4873 ++__n_swaps; 4874 ++__i; 4875 break; 4876 } 4877 ++__i; 4878 } 4879 } 4880 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 4881 if (__i == __j) 4882 return; 4883 while (true) 4884 { 4885 while (!__comp(*__first, *__i)) 4886 ++__i; 4887 while (__comp(*__first, *--__j)) 4888 ; 4889 if (__i >= __j) 4890 break; 4891 swap(*__i, *__j); 4892 ++__n_swaps; 4893 ++__i; 4894 } 4895 // [__first, __i) == *__first and *__first < [__i, __last) 4896 // The first part is sorted, 4897 if (__nth < __i) 4898 return; 4899 // __nth_element the secod part 4900 // __nth_element<_Compare>(__i, __nth, __last, __comp); 4901 __first = __i; 4902 goto __restart; 4903 } 4904 if (__comp(*__j, *__m)) 4905 { 4906 swap(*__i, *__j); 4907 ++__n_swaps; 4908 break; // found guard for downward moving __j, now use unguarded partition 4909 } 4910 } 4911 } 4912 ++__i; 4913 // j points beyond range to be tested, *__lm1 is known to be <= *__m 4914 // if not yet partitioned... 4915 if (__i < __j) 4916 { 4917 // known that *(__i - 1) < *__m 4918 while (true) 4919 { 4920 // __m still guards upward moving __i 4921 while (__comp(*__i, *__m)) 4922 ++__i; 4923 // It is now known that a guard exists for downward moving __j 4924 while (!__comp(*--__j, *__m)) 4925 ; 4926 if (__i >= __j) 4927 break; 4928 swap(*__i, *__j); 4929 ++__n_swaps; 4930 // It is known that __m != __j 4931 // If __m just moved, follow it 4932 if (__m == __i) 4933 __m = __j; 4934 ++__i; 4935 } 4936 } 4937 // [__first, __i) < *__m and *__m <= [__i, __last) 4938 if (__i != __m && __comp(*__m, *__i)) 4939 { 4940 swap(*__i, *__m); 4941 ++__n_swaps; 4942 } 4943 // [__first, __i) < *__i and *__i <= [__i+1, __last) 4944 if (__nth == __i) 4945 return; 4946 if (__n_swaps == 0) 4947 { 4948 // We were given a perfectly partitioned sequence. Coincidence? 4949 if (__nth < __i) 4950 { 4951 // Check for [__first, __i) already sorted 4952 __j = __m = __first; 4953 while (++__j != __i) 4954 { 4955 if (__comp(*__j, *__m)) 4956 // not yet sorted, so sort 4957 goto not_sorted; 4958 __m = __j; 4959 } 4960 // [__first, __i) sorted 4961 return; 4962 } 4963 else 4964 { 4965 // Check for [__i, __last) already sorted 4966 __j = __m = __i; 4967 while (++__j != __last) 4968 { 4969 if (__comp(*__j, *__m)) 4970 // not yet sorted, so sort 4971 goto not_sorted; 4972 __m = __j; 4973 } 4974 // [__i, __last) sorted 4975 return; 4976 } 4977 } 4978not_sorted: 4979 // __nth_element on range containing __nth 4980 if (__nth < __i) 4981 { 4982 // __nth_element<_Compare>(__first, __nth, __i, __comp); 4983 __last = __i; 4984 } 4985 else 4986 { 4987 // __nth_element<_Compare>(__i+1, __nth, __last, __comp); 4988 __first = ++__i; 4989 } 4990 } 4991} 4992 4993template <class _RandomAccessIterator, class _Compare> 4994inline _LIBCPP_INLINE_VISIBILITY 4995void 4996nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) 4997{ 4998#ifdef _LIBCPP_DEBUG2 4999 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5000 __debug_less<_Compare> __c(__comp); 5001 __nth_element<_Comp_ref>(__first, __nth, __last, __c); 5002#else // _LIBCPP_DEBUG2 5003 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5004 __nth_element<_Comp_ref>(__first, __nth, __last, __comp); 5005#endif // _LIBCPP_DEBUG2 5006} 5007 5008template <class _RandomAccessIterator> 5009inline _LIBCPP_INLINE_VISIBILITY 5010void 5011nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) 5012{ 5013 _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5014} 5015 5016// includes 5017 5018template <class _Compare, class _InputIterator1, class _InputIterator2> 5019bool 5020__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, 5021 _Compare __comp) 5022{ 5023 for (; __first2 != __last2; ++__first1) 5024 { 5025 if (__first1 == __last1 || __comp(*__first2, *__first1)) 5026 return false; 5027 if (!__comp(*__first1, *__first2)) 5028 ++__first2; 5029 } 5030 return true; 5031} 5032 5033template <class _InputIterator1, class _InputIterator2, class _Compare> 5034inline _LIBCPP_INLINE_VISIBILITY 5035bool 5036includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, 5037 _Compare __comp) 5038{ 5039#ifdef _LIBCPP_DEBUG2 5040 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5041 __debug_less<_Compare> __c(__comp); 5042 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c); 5043#else // _LIBCPP_DEBUG2 5044 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5045 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); 5046#endif // _LIBCPP_DEBUG2 5047} 5048 5049template <class _InputIterator1, class _InputIterator2> 5050inline _LIBCPP_INLINE_VISIBILITY 5051bool 5052includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) 5053{ 5054 return _VSTD::includes(__first1, __last1, __first2, __last2, 5055 __less<typename iterator_traits<_InputIterator1>::value_type, 5056 typename iterator_traits<_InputIterator2>::value_type>()); 5057} 5058 5059// set_union 5060 5061template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5062_OutputIterator 5063__set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5064 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5065{ 5066 for (; __first1 != __last1; ++__result) 5067 { 5068 if (__first2 == __last2) 5069 return _VSTD::copy(__first1, __last1, __result); 5070 if (__comp(*__first2, *__first1)) 5071 { 5072 *__result = *__first2; 5073 ++__first2; 5074 } 5075 else 5076 { 5077 *__result = *__first1; 5078 if (!__comp(*__first1, *__first2)) 5079 ++__first2; 5080 ++__first1; 5081 } 5082 } 5083 return _VSTD::copy(__first2, __last2, __result); 5084} 5085 5086template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5087inline _LIBCPP_INLINE_VISIBILITY 5088_OutputIterator 5089set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5090 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5091{ 5092#ifdef _LIBCPP_DEBUG2 5093 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5094 __debug_less<_Compare> __c(__comp); 5095 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c); 5096#else // _LIBCPP_DEBUG2 5097 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5098 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5099#endif // _LIBCPP_DEBUG2 5100} 5101 5102template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5103inline _LIBCPP_INLINE_VISIBILITY 5104_OutputIterator 5105set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5106 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5107{ 5108 return _VSTD::set_union(__first1, __last1, __first2, __last2, __result, 5109 __less<typename iterator_traits<_InputIterator1>::value_type, 5110 typename iterator_traits<_InputIterator2>::value_type>()); 5111} 5112 5113// set_intersection 5114 5115template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5116_OutputIterator 5117__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5118 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5119{ 5120 while (__first1 != __last1 && __first2 != __last2) 5121 { 5122 if (__comp(*__first1, *__first2)) 5123 ++__first1; 5124 else 5125 { 5126 if (!__comp(*__first2, *__first1)) 5127 { 5128 *__result = *__first1; 5129 ++__result; 5130 ++__first1; 5131 } 5132 ++__first2; 5133 } 5134 } 5135 return __result; 5136} 5137 5138template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5139inline _LIBCPP_INLINE_VISIBILITY 5140_OutputIterator 5141set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5142 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5143{ 5144#ifdef _LIBCPP_DEBUG2 5145 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5146 __debug_less<_Compare> __c(__comp); 5147 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c); 5148#else // _LIBCPP_DEBUG2 5149 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5150 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5151#endif // _LIBCPP_DEBUG2 5152} 5153 5154template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5155inline _LIBCPP_INLINE_VISIBILITY 5156_OutputIterator 5157set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5158 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5159{ 5160 return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result, 5161 __less<typename iterator_traits<_InputIterator1>::value_type, 5162 typename iterator_traits<_InputIterator2>::value_type>()); 5163} 5164 5165// set_difference 5166 5167template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5168_OutputIterator 5169__set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5170 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5171{ 5172 while (__first1 != __last1) 5173 { 5174 if (__first2 == __last2) 5175 return _VSTD::copy(__first1, __last1, __result); 5176 if (__comp(*__first1, *__first2)) 5177 { 5178 *__result = *__first1; 5179 ++__result; 5180 ++__first1; 5181 } 5182 else 5183 { 5184 if (!__comp(*__first2, *__first1)) 5185 ++__first1; 5186 ++__first2; 5187 } 5188 } 5189 return __result; 5190} 5191 5192template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5193inline _LIBCPP_INLINE_VISIBILITY 5194_OutputIterator 5195set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5196 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5197{ 5198#ifdef _LIBCPP_DEBUG2 5199 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5200 __debug_less<_Compare> __c(__comp); 5201 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c); 5202#else // _LIBCPP_DEBUG2 5203 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5204 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5205#endif // _LIBCPP_DEBUG2 5206} 5207 5208template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5209inline _LIBCPP_INLINE_VISIBILITY 5210_OutputIterator 5211set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5212 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5213{ 5214 return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result, 5215 __less<typename iterator_traits<_InputIterator1>::value_type, 5216 typename iterator_traits<_InputIterator2>::value_type>()); 5217} 5218 5219// set_symmetric_difference 5220 5221template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5222_OutputIterator 5223__set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5224 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5225{ 5226 while (__first1 != __last1) 5227 { 5228 if (__first2 == __last2) 5229 return _VSTD::copy(__first1, __last1, __result); 5230 if (__comp(*__first1, *__first2)) 5231 { 5232 *__result = *__first1; 5233 ++__result; 5234 ++__first1; 5235 } 5236 else 5237 { 5238 if (__comp(*__first2, *__first1)) 5239 { 5240 *__result = *__first2; 5241 ++__result; 5242 } 5243 else 5244 ++__first1; 5245 ++__first2; 5246 } 5247 } 5248 return _VSTD::copy(__first2, __last2, __result); 5249} 5250 5251template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5252inline _LIBCPP_INLINE_VISIBILITY 5253_OutputIterator 5254set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5255 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5256{ 5257#ifdef _LIBCPP_DEBUG2 5258 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5259 __debug_less<_Compare> __c(__comp); 5260 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c); 5261#else // _LIBCPP_DEBUG2 5262 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5263 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5264#endif // _LIBCPP_DEBUG2 5265} 5266 5267template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5268inline _LIBCPP_INLINE_VISIBILITY 5269_OutputIterator 5270set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5271 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5272{ 5273 return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, 5274 __less<typename iterator_traits<_InputIterator1>::value_type, 5275 typename iterator_traits<_InputIterator2>::value_type>()); 5276} 5277 5278// lexicographical_compare 5279 5280template <class _Compare, class _InputIterator1, class _InputIterator2> 5281bool 5282__lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5283 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) 5284{ 5285 for (; __first2 != __last2; ++__first1, ++__first2) 5286 { 5287 if (__first1 == __last1 || __comp(*__first1, *__first2)) 5288 return true; 5289 if (__comp(*__first2, *__first1)) 5290 return false; 5291 } 5292 return false; 5293} 5294 5295template <class _InputIterator1, class _InputIterator2, class _Compare> 5296inline _LIBCPP_INLINE_VISIBILITY 5297bool 5298lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5299 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) 5300{ 5301#ifdef _LIBCPP_DEBUG2 5302 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5303 __debug_less<_Compare> __c(__comp); 5304 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c); 5305#else // _LIBCPP_DEBUG2 5306 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5307 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); 5308#endif // _LIBCPP_DEBUG2 5309} 5310 5311template <class _InputIterator1, class _InputIterator2> 5312inline _LIBCPP_INLINE_VISIBILITY 5313bool 5314lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5315 _InputIterator2 __first2, _InputIterator2 __last2) 5316{ 5317 return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2, 5318 __less<typename iterator_traits<_InputIterator1>::value_type, 5319 typename iterator_traits<_InputIterator2>::value_type>()); 5320} 5321 5322// next_permutation 5323 5324template <class _Compare, class _BidirectionalIterator> 5325bool 5326__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5327{ 5328 _BidirectionalIterator __i = __last; 5329 if (__first == __last || __first == --__i) 5330 return false; 5331 while (true) 5332 { 5333 _BidirectionalIterator __ip1 = __i; 5334 if (__comp(*--__i, *__ip1)) 5335 { 5336 _BidirectionalIterator __j = __last; 5337 while (!__comp(*__i, *--__j)) 5338 ; 5339 swap(*__i, *__j); 5340 _VSTD::reverse(__ip1, __last); 5341 return true; 5342 } 5343 if (__i == __first) 5344 { 5345 _VSTD::reverse(__first, __last); 5346 return false; 5347 } 5348 } 5349} 5350 5351template <class _BidirectionalIterator, class _Compare> 5352inline _LIBCPP_INLINE_VISIBILITY 5353bool 5354next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5355{ 5356#ifdef _LIBCPP_DEBUG2 5357 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5358 __debug_less<_Compare> __c(__comp); 5359 return __next_permutation<_Comp_ref>(__first, __last, __c); 5360#else // _LIBCPP_DEBUG2 5361 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5362 return __next_permutation<_Comp_ref>(__first, __last, __comp); 5363#endif // _LIBCPP_DEBUG2 5364} 5365 5366template <class _BidirectionalIterator> 5367inline _LIBCPP_INLINE_VISIBILITY 5368bool 5369next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) 5370{ 5371 return _VSTD::next_permutation(__first, __last, 5372 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 5373} 5374 5375// prev_permutation 5376 5377template <class _Compare, class _BidirectionalIterator> 5378bool 5379__prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5380{ 5381 _BidirectionalIterator __i = __last; 5382 if (__first == __last || __first == --__i) 5383 return false; 5384 while (true) 5385 { 5386 _BidirectionalIterator __ip1 = __i; 5387 if (__comp(*__ip1, *--__i)) 5388 { 5389 _BidirectionalIterator __j = __last; 5390 while (!__comp(*--__j, *__i)) 5391 ; 5392 swap(*__i, *__j); 5393 _VSTD::reverse(__ip1, __last); 5394 return true; 5395 } 5396 if (__i == __first) 5397 { 5398 _VSTD::reverse(__first, __last); 5399 return false; 5400 } 5401 } 5402} 5403 5404template <class _BidirectionalIterator, class _Compare> 5405inline _LIBCPP_INLINE_VISIBILITY 5406bool 5407prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5408{ 5409#ifdef _LIBCPP_DEBUG2 5410 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5411 __debug_less<_Compare> __c(__comp); 5412 return __prev_permutation<_Comp_ref>(__first, __last, __c); 5413#else // _LIBCPP_DEBUG2 5414 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5415 return __prev_permutation<_Comp_ref>(__first, __last, __comp); 5416#endif // _LIBCPP_DEBUG2 5417} 5418 5419template <class _BidirectionalIterator> 5420inline _LIBCPP_INLINE_VISIBILITY 5421bool 5422prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) 5423{ 5424 return _VSTD::prev_permutation(__first, __last, 5425 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 5426} 5427 5428template <class _Tp> 5429inline _LIBCPP_INLINE_VISIBILITY 5430typename enable_if 5431< 5432 is_integral<_Tp>::value, 5433 _Tp 5434>::type 5435__rotate_left(_Tp __t, _Tp __n = 1) 5436{ 5437 const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1); 5438 __n &= __bits; 5439 return static_cast<_Tp>((__t << __n) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> (__bits - __n))); 5440} 5441 5442template <class _Tp> 5443inline _LIBCPP_INLINE_VISIBILITY 5444typename enable_if 5445< 5446 is_integral<_Tp>::value, 5447 _Tp 5448>::type 5449__rotate_right(_Tp __t, _Tp __n = 1) 5450{ 5451 const unsigned __bits = static_cast<unsigned>(sizeof(_Tp) * __CHAR_BIT__ - 1); 5452 __n &= __bits; 5453 return static_cast<_Tp>((__t << (__bits - __n)) | (static_cast<typename make_unsigned<_Tp>::type>(__t) >> __n)); 5454} 5455 5456_LIBCPP_END_NAMESPACE_STD 5457 5458#endif // _LIBCPP_ALGORITHM 5459