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