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