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