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