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