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