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