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