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