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