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