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