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