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