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