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 = _VSTD::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 = 3216 _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g); 3217 if (__r < __n) { 3218 *__output_iter++ = *__first; 3219 --__n; 3220 } 3221 } 3222 return __output_iter; 3223} 3224 3225template <class _PopulationIterator, class _SampleIterator, class _Distance, 3226 class _UniformRandomNumberGenerator> 3227_LIBCPP_INLINE_VISIBILITY 3228_SampleIterator __sample(_PopulationIterator __first, 3229 _PopulationIterator __last, _SampleIterator __output_iter, 3230 _Distance __n, _UniformRandomNumberGenerator& __g) { 3231 typedef typename iterator_traits<_PopulationIterator>::iterator_category 3232 _PopCategory; 3233 typedef typename iterator_traits<_PopulationIterator>::difference_type 3234 _Difference; 3235 static_assert(__is_cpp17_forward_iterator<_PopulationIterator>::value || 3236 __is_cpp17_random_access_iterator<_SampleIterator>::value, 3237 "SampleIterator must meet the requirements of RandomAccessIterator"); 3238 typedef typename common_type<_Distance, _Difference>::type _CommonType; 3239 _LIBCPP_ASSERT(__n >= 0, "N must be a positive number."); 3240 return _VSTD::__sample( 3241 __first, __last, __output_iter, _CommonType(__n), 3242 __g, _PopCategory()); 3243} 3244 3245#if _LIBCPP_STD_VER > 14 3246template <class _PopulationIterator, class _SampleIterator, class _Distance, 3247 class _UniformRandomNumberGenerator> 3248inline _LIBCPP_INLINE_VISIBILITY 3249_SampleIterator sample(_PopulationIterator __first, 3250 _PopulationIterator __last, _SampleIterator __output_iter, 3251 _Distance __n, _UniformRandomNumberGenerator&& __g) { 3252 return _VSTD::__sample(__first, __last, __output_iter, __n, __g); 3253} 3254#endif // _LIBCPP_STD_VER > 14 3255 3256template<class _RandomAccessIterator, class _UniformRandomNumberGenerator> 3257 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 3258 _UniformRandomNumberGenerator&& __g) 3259{ 3260 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 3261 typedef uniform_int_distribution<ptrdiff_t> _Dp; 3262 typedef typename _Dp::param_type _Pp; 3263 difference_type __d = __last - __first; 3264 if (__d > 1) 3265 { 3266 _Dp __uid; 3267 for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d) 3268 { 3269 difference_type __i = __uid(__g, _Pp(0, __d)); 3270 if (__i != difference_type(0)) 3271 swap(*__first, *(__first + __i)); 3272 } 3273 } 3274} 3275 3276#if _LIBCPP_STD_VER > 17 3277 3278// shift_left, shift_right 3279 3280template <class _ForwardIterator> 3281inline _LIBCPP_INLINE_VISIBILITY constexpr 3282_ForwardIterator 3283shift_left(_ForwardIterator __first, _ForwardIterator __last, 3284 typename iterator_traits<_ForwardIterator>::difference_type __n) 3285{ 3286 if (__n == 0) { 3287 return __last; 3288 } 3289 3290 _ForwardIterator __m = __first; 3291 if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value) { 3292 if (__n >= __last - __first) { 3293 return __first; 3294 } 3295 __m += __n; 3296 } else { 3297 for (; __n > 0; --__n) { 3298 if (__m == __last) { 3299 return __first; 3300 } 3301 ++__m; 3302 } 3303 } 3304 return _VSTD::move(__m, __last, __first); 3305} 3306 3307template <class _ForwardIterator> 3308inline _LIBCPP_INLINE_VISIBILITY constexpr 3309_ForwardIterator 3310shift_right(_ForwardIterator __first, _ForwardIterator __last, 3311 typename iterator_traits<_ForwardIterator>::difference_type __n) 3312{ 3313 if (__n == 0) { 3314 return __first; 3315 } 3316 3317 if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value) { 3318 decltype(__n) __d = __last - __first; 3319 if (__n >= __d) { 3320 return __last; 3321 } 3322 _ForwardIterator __m = __first + (__d - __n); 3323 return _VSTD::move_backward(__first, __m, __last); 3324 } else if constexpr (__is_cpp17_bidirectional_iterator<_ForwardIterator>::value) { 3325 _ForwardIterator __m = __last; 3326 for (; __n > 0; --__n) { 3327 if (__m == __first) { 3328 return __last; 3329 } 3330 --__m; 3331 } 3332 return _VSTD::move_backward(__first, __m, __last); 3333 } else { 3334 _ForwardIterator __ret = __first; 3335 for (; __n > 0; --__n) { 3336 if (__ret == __last) { 3337 return __last; 3338 } 3339 ++__ret; 3340 } 3341 3342 // We have an __n-element scratch space from __first to __ret. 3343 // Slide an __n-element window [__trail, __lead) from left to right. 3344 // We're essentially doing swap_ranges(__first, __ret, __trail, __lead) 3345 // over and over; but once __lead reaches __last we needn't bother 3346 // to save the values of elements [__trail, __last). 3347 3348 auto __trail = __first; 3349 auto __lead = __ret; 3350 while (__trail != __ret) { 3351 if (__lead == __last) { 3352 _VSTD::move(__first, __trail, __ret); 3353 return __ret; 3354 } 3355 ++__trail; 3356 ++__lead; 3357 } 3358 3359 _ForwardIterator __mid = __first; 3360 while (true) { 3361 if (__lead == __last) { 3362 __trail = _VSTD::move(__mid, __ret, __trail); 3363 _VSTD::move(__first, __mid, __trail); 3364 return __ret; 3365 } 3366 swap(*__mid, *__trail); 3367 ++__mid; 3368 ++__trail; 3369 ++__lead; 3370 if (__mid == __ret) { 3371 __mid = __first; 3372 } 3373 } 3374 } 3375} 3376 3377#endif // _LIBCPP_STD_VER > 17 3378 3379// is_partitioned 3380 3381template <class _InputIterator, class _Predicate> 3382_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool 3383is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred) 3384{ 3385 for (; __first != __last; ++__first) 3386 if (!__pred(*__first)) 3387 break; 3388 if ( __first == __last ) 3389 return true; 3390 ++__first; 3391 for (; __first != __last; ++__first) 3392 if (__pred(*__first)) 3393 return false; 3394 return true; 3395} 3396 3397// partition 3398 3399template <class _Predicate, class _ForwardIterator> 3400_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 3401__partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag) 3402{ 3403 while (true) 3404 { 3405 if (__first == __last) 3406 return __first; 3407 if (!__pred(*__first)) 3408 break; 3409 ++__first; 3410 } 3411 for (_ForwardIterator __p = __first; ++__p != __last;) 3412 { 3413 if (__pred(*__p)) 3414 { 3415 swap(*__first, *__p); 3416 ++__first; 3417 } 3418 } 3419 return __first; 3420} 3421 3422template <class _Predicate, class _BidirectionalIterator> 3423_LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator 3424__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 3425 bidirectional_iterator_tag) 3426{ 3427 while (true) 3428 { 3429 while (true) 3430 { 3431 if (__first == __last) 3432 return __first; 3433 if (!__pred(*__first)) 3434 break; 3435 ++__first; 3436 } 3437 do 3438 { 3439 if (__first == --__last) 3440 return __first; 3441 } while (!__pred(*__last)); 3442 swap(*__first, *__last); 3443 ++__first; 3444 } 3445} 3446 3447template <class _ForwardIterator, class _Predicate> 3448inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 3449_ForwardIterator 3450partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 3451{ 3452 return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type> 3453 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); 3454} 3455 3456// partition_copy 3457 3458template <class _InputIterator, class _OutputIterator1, 3459 class _OutputIterator2, class _Predicate> 3460_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_OutputIterator1, _OutputIterator2> 3461partition_copy(_InputIterator __first, _InputIterator __last, 3462 _OutputIterator1 __out_true, _OutputIterator2 __out_false, 3463 _Predicate __pred) 3464{ 3465 for (; __first != __last; ++__first) 3466 { 3467 if (__pred(*__first)) 3468 { 3469 *__out_true = *__first; 3470 ++__out_true; 3471 } 3472 else 3473 { 3474 *__out_false = *__first; 3475 ++__out_false; 3476 } 3477 } 3478 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false); 3479} 3480 3481// partition_point 3482 3483template<class _ForwardIterator, class _Predicate> 3484_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 3485partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 3486{ 3487 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 3488 difference_type __len = _VSTD::distance(__first, __last); 3489 while (__len != 0) 3490 { 3491 difference_type __l2 = _VSTD::__half_positive(__len); 3492 _ForwardIterator __m = __first; 3493 _VSTD::advance(__m, __l2); 3494 if (__pred(*__m)) 3495 { 3496 __first = ++__m; 3497 __len -= __l2 + 1; 3498 } 3499 else 3500 __len = __l2; 3501 } 3502 return __first; 3503} 3504 3505// stable_partition 3506 3507template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair> 3508_ForwardIterator 3509__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, 3510 _Distance __len, _Pair __p, forward_iterator_tag __fit) 3511{ 3512 // *__first is known to be false 3513 // __len >= 1 3514 if (__len == 1) 3515 return __first; 3516 if (__len == 2) 3517 { 3518 _ForwardIterator __m = __first; 3519 if (__pred(*++__m)) 3520 { 3521 swap(*__first, *__m); 3522 return __m; 3523 } 3524 return __first; 3525 } 3526 if (__len <= __p.second) 3527 { // The buffer is big enough to use 3528 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 3529 __destruct_n __d(0); 3530 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); 3531 // Move the falses into the temporary buffer, and the trues to the front of the line 3532 // Update __first to always point to the end of the trues 3533 value_type* __t = __p.first; 3534 ::new ((void*)__t) value_type(_VSTD::move(*__first)); 3535 __d.template __incr<value_type>(); 3536 ++__t; 3537 _ForwardIterator __i = __first; 3538 while (++__i != __last) 3539 { 3540 if (__pred(*__i)) 3541 { 3542 *__first = _VSTD::move(*__i); 3543 ++__first; 3544 } 3545 else 3546 { 3547 ::new ((void*)__t) value_type(_VSTD::move(*__i)); 3548 __d.template __incr<value_type>(); 3549 ++__t; 3550 } 3551 } 3552 // All trues now at start of range, all falses in buffer 3553 // Move falses back into range, but don't mess up __first which points to first false 3554 __i = __first; 3555 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i) 3556 *__i = _VSTD::move(*__t2); 3557 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer 3558 return __first; 3559 } 3560 // Else not enough buffer, do in place 3561 // __len >= 3 3562 _ForwardIterator __m = __first; 3563 _Distance __len2 = __len / 2; // __len2 >= 2 3564 _VSTD::advance(__m, __len2); 3565 // recurse on [__first, __m), *__first know to be false 3566 // F????????????????? 3567 // f m l 3568 typedef typename add_lvalue_reference<_Predicate>::type _PredRef; 3569 _ForwardIterator __first_false = _VSTD::__stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit); 3570 // TTTFFFFF?????????? 3571 // f ff m l 3572 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true 3573 _ForwardIterator __m1 = __m; 3574 _ForwardIterator __second_false = __last; 3575 _Distance __len_half = __len - __len2; 3576 while (__pred(*__m1)) 3577 { 3578 if (++__m1 == __last) 3579 goto __second_half_done; 3580 --__len_half; 3581 } 3582 // TTTFFFFFTTTF?????? 3583 // f ff m m1 l 3584 __second_false = _VSTD::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit); 3585__second_half_done: 3586 // TTTFFFFFTTTTTFFFFF 3587 // f ff m sf l 3588 return _VSTD::rotate(__first_false, __m, __second_false); 3589 // TTTTTTTTFFFFFFFFFF 3590 // | 3591} 3592 3593struct __return_temporary_buffer 3594{ 3595 template <class _Tp> 3596 _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);} 3597}; 3598 3599template <class _Predicate, class _ForwardIterator> 3600_ForwardIterator 3601__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, 3602 forward_iterator_tag) 3603{ 3604 const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment 3605 // Either prove all true and return __first or point to first false 3606 while (true) 3607 { 3608 if (__first == __last) 3609 return __first; 3610 if (!__pred(*__first)) 3611 break; 3612 ++__first; 3613 } 3614 // We now have a reduced range [__first, __last) 3615 // *__first is known to be false 3616 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 3617 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 3618 difference_type __len = _VSTD::distance(__first, __last); 3619 pair<value_type*, ptrdiff_t> __p(0, 0); 3620 unique_ptr<value_type, __return_temporary_buffer> __h; 3621 if (__len >= __alloc_limit) 3622 { 3623 __p = _VSTD::get_temporary_buffer<value_type>(__len); 3624 __h.reset(__p.first); 3625 } 3626 return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type> 3627 (__first, __last, __pred, __len, __p, forward_iterator_tag()); 3628} 3629 3630template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair> 3631_BidirectionalIterator 3632__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 3633 _Distance __len, _Pair __p, bidirectional_iterator_tag __bit) 3634{ 3635 // *__first is known to be false 3636 // *__last is known to be true 3637 // __len >= 2 3638 if (__len == 2) 3639 { 3640 swap(*__first, *__last); 3641 return __last; 3642 } 3643 if (__len == 3) 3644 { 3645 _BidirectionalIterator __m = __first; 3646 if (__pred(*++__m)) 3647 { 3648 swap(*__first, *__m); 3649 swap(*__m, *__last); 3650 return __last; 3651 } 3652 swap(*__m, *__last); 3653 swap(*__first, *__m); 3654 return __m; 3655 } 3656 if (__len <= __p.second) 3657 { // The buffer is big enough to use 3658 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 3659 __destruct_n __d(0); 3660 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); 3661 // Move the falses into the temporary buffer, and the trues to the front of the line 3662 // Update __first to always point to the end of the trues 3663 value_type* __t = __p.first; 3664 ::new ((void*)__t) value_type(_VSTD::move(*__first)); 3665 __d.template __incr<value_type>(); 3666 ++__t; 3667 _BidirectionalIterator __i = __first; 3668 while (++__i != __last) 3669 { 3670 if (__pred(*__i)) 3671 { 3672 *__first = _VSTD::move(*__i); 3673 ++__first; 3674 } 3675 else 3676 { 3677 ::new ((void*)__t) value_type(_VSTD::move(*__i)); 3678 __d.template __incr<value_type>(); 3679 ++__t; 3680 } 3681 } 3682 // move *__last, known to be true 3683 *__first = _VSTD::move(*__i); 3684 __i = ++__first; 3685 // All trues now at start of range, all falses in buffer 3686 // Move falses back into range, but don't mess up __first which points to first false 3687 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i) 3688 *__i = _VSTD::move(*__t2); 3689 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer 3690 return __first; 3691 } 3692 // Else not enough buffer, do in place 3693 // __len >= 4 3694 _BidirectionalIterator __m = __first; 3695 _Distance __len2 = __len / 2; // __len2 >= 2 3696 _VSTD::advance(__m, __len2); 3697 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false 3698 // F????????????????T 3699 // f m l 3700 _BidirectionalIterator __m1 = __m; 3701 _BidirectionalIterator __first_false = __first; 3702 _Distance __len_half = __len2; 3703 while (!__pred(*--__m1)) 3704 { 3705 if (__m1 == __first) 3706 goto __first_half_done; 3707 --__len_half; 3708 } 3709 // F???TFFF?????????T 3710 // f m1 m l 3711 typedef typename add_lvalue_reference<_Predicate>::type _PredRef; 3712 __first_false = _VSTD::__stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit); 3713__first_half_done: 3714 // TTTFFFFF?????????T 3715 // f ff m l 3716 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true 3717 __m1 = __m; 3718 _BidirectionalIterator __second_false = __last; 3719 ++__second_false; 3720 __len_half = __len - __len2; 3721 while (__pred(*__m1)) 3722 { 3723 if (++__m1 == __last) 3724 goto __second_half_done; 3725 --__len_half; 3726 } 3727 // TTTFFFFFTTTF?????T 3728 // f ff m m1 l 3729 __second_false = _VSTD::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit); 3730__second_half_done: 3731 // TTTFFFFFTTTTTFFFFF 3732 // f ff m sf l 3733 return _VSTD::rotate(__first_false, __m, __second_false); 3734 // TTTTTTTTFFFFFFFFFF 3735 // | 3736} 3737 3738template <class _Predicate, class _BidirectionalIterator> 3739_BidirectionalIterator 3740__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 3741 bidirectional_iterator_tag) 3742{ 3743 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 3744 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 3745 const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment 3746 // Either prove all true and return __first or point to first false 3747 while (true) 3748 { 3749 if (__first == __last) 3750 return __first; 3751 if (!__pred(*__first)) 3752 break; 3753 ++__first; 3754 } 3755 // __first points to first false, everything prior to __first is already set. 3756 // Either prove [__first, __last) is all false and return __first, or point __last to last true 3757 do 3758 { 3759 if (__first == --__last) 3760 return __first; 3761 } while (!__pred(*__last)); 3762 // We now have a reduced range [__first, __last] 3763 // *__first is known to be false 3764 // *__last is known to be true 3765 // __len >= 2 3766 difference_type __len = _VSTD::distance(__first, __last) + 1; 3767 pair<value_type*, ptrdiff_t> __p(0, 0); 3768 unique_ptr<value_type, __return_temporary_buffer> __h; 3769 if (__len >= __alloc_limit) 3770 { 3771 __p = _VSTD::get_temporary_buffer<value_type>(__len); 3772 __h.reset(__p.first); 3773 } 3774 return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type> 3775 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag()); 3776} 3777 3778template <class _ForwardIterator, class _Predicate> 3779inline _LIBCPP_INLINE_VISIBILITY 3780_ForwardIterator 3781stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 3782{ 3783 return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type> 3784 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); 3785} 3786 3787// is_sorted_until 3788 3789template <class _ForwardIterator, class _Compare> 3790_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 3791is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 3792{ 3793 if (__first != __last) 3794 { 3795 _ForwardIterator __i = __first; 3796 while (++__i != __last) 3797 { 3798 if (__comp(*__i, *__first)) 3799 return __i; 3800 __first = __i; 3801 } 3802 } 3803 return __last; 3804} 3805 3806template<class _ForwardIterator> 3807_LIBCPP_NODISCARD_EXT inline 3808_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 3809_ForwardIterator 3810is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) 3811{ 3812 return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); 3813} 3814 3815// is_sorted 3816 3817template <class _ForwardIterator, class _Compare> 3818_LIBCPP_NODISCARD_EXT inline 3819_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 3820bool 3821is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 3822{ 3823 return _VSTD::is_sorted_until(__first, __last, __comp) == __last; 3824} 3825 3826template<class _ForwardIterator> 3827_LIBCPP_NODISCARD_EXT inline 3828_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 3829bool 3830is_sorted(_ForwardIterator __first, _ForwardIterator __last) 3831{ 3832 return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); 3833} 3834 3835// sort 3836 3837// stable, 2-3 compares, 0-2 swaps 3838 3839template <class _Compare, class _ForwardIterator> 3840_LIBCPP_CONSTEXPR_AFTER_CXX11 unsigned 3841__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c) 3842{ 3843 unsigned __r = 0; 3844 if (!__c(*__y, *__x)) // if x <= y 3845 { 3846 if (!__c(*__z, *__y)) // if y <= z 3847 return __r; // x <= y && y <= z 3848 // x <= y && y > z 3849 swap(*__y, *__z); // x <= z && y < z 3850 __r = 1; 3851 if (__c(*__y, *__x)) // if x > y 3852 { 3853 swap(*__x, *__y); // x < y && y <= z 3854 __r = 2; 3855 } 3856 return __r; // x <= y && y < z 3857 } 3858 if (__c(*__z, *__y)) // x > y, if y > z 3859 { 3860 swap(*__x, *__z); // x < y && y < z 3861 __r = 1; 3862 return __r; 3863 } 3864 swap(*__x, *__y); // x > y && y <= z 3865 __r = 1; // x < y && x <= z 3866 if (__c(*__z, *__y)) // if y > z 3867 { 3868 swap(*__y, *__z); // x <= y && y < z 3869 __r = 2; 3870 } 3871 return __r; 3872} // x <= y && y <= z 3873 3874// stable, 3-6 compares, 0-5 swaps 3875 3876template <class _Compare, class _ForwardIterator> 3877unsigned 3878__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 3879 _ForwardIterator __x4, _Compare __c) 3880{ 3881 unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c); 3882 if (__c(*__x4, *__x3)) 3883 { 3884 swap(*__x3, *__x4); 3885 ++__r; 3886 if (__c(*__x3, *__x2)) 3887 { 3888 swap(*__x2, *__x3); 3889 ++__r; 3890 if (__c(*__x2, *__x1)) 3891 { 3892 swap(*__x1, *__x2); 3893 ++__r; 3894 } 3895 } 3896 } 3897 return __r; 3898} 3899 3900// stable, 4-10 compares, 0-9 swaps 3901 3902template <class _Compare, class _ForwardIterator> 3903_LIBCPP_HIDDEN 3904unsigned 3905__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 3906 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) 3907{ 3908 unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c); 3909 if (__c(*__x5, *__x4)) 3910 { 3911 swap(*__x4, *__x5); 3912 ++__r; 3913 if (__c(*__x4, *__x3)) 3914 { 3915 swap(*__x3, *__x4); 3916 ++__r; 3917 if (__c(*__x3, *__x2)) 3918 { 3919 swap(*__x2, *__x3); 3920 ++__r; 3921 if (__c(*__x2, *__x1)) 3922 { 3923 swap(*__x1, *__x2); 3924 ++__r; 3925 } 3926 } 3927 } 3928 } 3929 return __r; 3930} 3931 3932// Assumes size > 0 3933template <class _Compare, class _BidirectionalIterator> 3934_LIBCPP_CONSTEXPR_AFTER_CXX11 void 3935__selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 3936{ 3937 _BidirectionalIterator __lm1 = __last; 3938 for (--__lm1; __first != __lm1; ++__first) 3939 { 3940 _BidirectionalIterator __i = _VSTD::min_element<_BidirectionalIterator, 3941 typename add_lvalue_reference<_Compare>::type> 3942 (__first, __last, __comp); 3943 if (__i != __first) 3944 swap(*__first, *__i); 3945 } 3946} 3947 3948template <class _Compare, class _BidirectionalIterator> 3949void 3950__insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 3951{ 3952 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 3953 if (__first != __last) 3954 { 3955 _BidirectionalIterator __i = __first; 3956 for (++__i; __i != __last; ++__i) 3957 { 3958 _BidirectionalIterator __j = __i; 3959 value_type __t(_VSTD::move(*__j)); 3960 for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j) 3961 *__j = _VSTD::move(*__k); 3962 *__j = _VSTD::move(__t); 3963 } 3964 } 3965} 3966 3967template <class _Compare, class _RandomAccessIterator> 3968void 3969__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 3970{ 3971 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 3972 _RandomAccessIterator __j = __first+2; 3973 _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp); 3974 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) 3975 { 3976 if (__comp(*__i, *__j)) 3977 { 3978 value_type __t(_VSTD::move(*__i)); 3979 _RandomAccessIterator __k = __j; 3980 __j = __i; 3981 do 3982 { 3983 *__j = _VSTD::move(*__k); 3984 __j = __k; 3985 } while (__j != __first && __comp(__t, *--__k)); 3986 *__j = _VSTD::move(__t); 3987 } 3988 __j = __i; 3989 } 3990} 3991 3992template <class _Compare, class _RandomAccessIterator> 3993bool 3994__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 3995{ 3996 switch (__last - __first) 3997 { 3998 case 0: 3999 case 1: 4000 return true; 4001 case 2: 4002 if (__comp(*--__last, *__first)) 4003 swap(*__first, *__last); 4004 return true; 4005 case 3: 4006 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); 4007 return true; 4008 case 4: 4009 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); 4010 return true; 4011 case 5: 4012 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); 4013 return true; 4014 } 4015 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4016 _RandomAccessIterator __j = __first+2; 4017 _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp); 4018 const unsigned __limit = 8; 4019 unsigned __count = 0; 4020 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) 4021 { 4022 if (__comp(*__i, *__j)) 4023 { 4024 value_type __t(_VSTD::move(*__i)); 4025 _RandomAccessIterator __k = __j; 4026 __j = __i; 4027 do 4028 { 4029 *__j = _VSTD::move(*__k); 4030 __j = __k; 4031 } while (__j != __first && __comp(__t, *--__k)); 4032 *__j = _VSTD::move(__t); 4033 if (++__count == __limit) 4034 return ++__i == __last; 4035 } 4036 __j = __i; 4037 } 4038 return true; 4039} 4040 4041template <class _Compare, class _BidirectionalIterator> 4042void 4043__insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1, 4044 typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp) 4045{ 4046 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 4047 if (__first1 != __last1) 4048 { 4049 __destruct_n __d(0); 4050 unique_ptr<value_type, __destruct_n&> __h(__first2, __d); 4051 value_type* __last2 = __first2; 4052 ::new ((void*)__last2) value_type(_VSTD::move(*__first1)); 4053 __d.template __incr<value_type>(); 4054 for (++__last2; ++__first1 != __last1; ++__last2) 4055 { 4056 value_type* __j2 = __last2; 4057 value_type* __i2 = __j2; 4058 if (__comp(*__first1, *--__i2)) 4059 { 4060 ::new ((void*)__j2) value_type(_VSTD::move(*__i2)); 4061 __d.template __incr<value_type>(); 4062 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) 4063 *__j2 = _VSTD::move(*__i2); 4064 *__j2 = _VSTD::move(*__first1); 4065 } 4066 else 4067 { 4068 ::new ((void*)__j2) value_type(_VSTD::move(*__first1)); 4069 __d.template __incr<value_type>(); 4070 } 4071 } 4072 __h.release(); 4073 } 4074} 4075 4076template <class _Compare, class _RandomAccessIterator> 4077void 4078__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4079{ 4080 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4081 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4082 const difference_type __limit = is_trivially_copy_constructible<value_type>::value && 4083 is_trivially_copy_assignable<value_type>::value ? 30 : 6; 4084 while (true) 4085 { 4086 __restart: 4087 difference_type __len = __last - __first; 4088 switch (__len) 4089 { 4090 case 0: 4091 case 1: 4092 return; 4093 case 2: 4094 if (__comp(*--__last, *__first)) 4095 swap(*__first, *__last); 4096 return; 4097 case 3: 4098 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); 4099 return; 4100 case 4: 4101 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); 4102 return; 4103 case 5: 4104 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); 4105 return; 4106 } 4107 if (__len <= __limit) 4108 { 4109 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); 4110 return; 4111 } 4112 // __len > 5 4113 _RandomAccessIterator __m = __first; 4114 _RandomAccessIterator __lm1 = __last; 4115 --__lm1; 4116 unsigned __n_swaps; 4117 { 4118 difference_type __delta; 4119 if (__len >= 1000) 4120 { 4121 __delta = __len/2; 4122 __m += __delta; 4123 __delta /= 2; 4124 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp); 4125 } 4126 else 4127 { 4128 __delta = __len/2; 4129 __m += __delta; 4130 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); 4131 } 4132 } 4133 // *__m is median 4134 // partition [__first, __m) < *__m and *__m <= [__m, __last) 4135 // (this inhibits tossing elements equivalent to __m around unnecessarily) 4136 _RandomAccessIterator __i = __first; 4137 _RandomAccessIterator __j = __lm1; 4138 // j points beyond range to be tested, *__m is known to be <= *__lm1 4139 // The search going up is known to be guarded but the search coming down isn't. 4140 // Prime the downward search with a guard. 4141 if (!__comp(*__i, *__m)) // if *__first == *__m 4142 { 4143 // *__first == *__m, *__first doesn't go in first part 4144 // manually guard downward moving __j against __i 4145 while (true) 4146 { 4147 if (__i == --__j) 4148 { 4149 // *__first == *__m, *__m <= all other elements 4150 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) 4151 ++__i; // __first + 1 4152 __j = __last; 4153 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) 4154 { 4155 while (true) 4156 { 4157 if (__i == __j) 4158 return; // [__first, __last) all equivalent elements 4159 if (__comp(*__first, *__i)) 4160 { 4161 swap(*__i, *__j); 4162 ++__n_swaps; 4163 ++__i; 4164 break; 4165 } 4166 ++__i; 4167 } 4168 } 4169 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 4170 if (__i == __j) 4171 return; 4172 while (true) 4173 { 4174 while (!__comp(*__first, *__i)) 4175 ++__i; 4176 while (__comp(*__first, *--__j)) 4177 ; 4178 if (__i >= __j) 4179 break; 4180 swap(*__i, *__j); 4181 ++__n_swaps; 4182 ++__i; 4183 } 4184 // [__first, __i) == *__first and *__first < [__i, __last) 4185 // The first part is sorted, sort the second part 4186 // _VSTD::__sort<_Compare>(__i, __last, __comp); 4187 __first = __i; 4188 goto __restart; 4189 } 4190 if (__comp(*__j, *__m)) 4191 { 4192 swap(*__i, *__j); 4193 ++__n_swaps; 4194 break; // found guard for downward moving __j, now use unguarded partition 4195 } 4196 } 4197 } 4198 // It is known that *__i < *__m 4199 ++__i; 4200 // j points beyond range to be tested, *__m is known to be <= *__lm1 4201 // if not yet partitioned... 4202 if (__i < __j) 4203 { 4204 // known that *(__i - 1) < *__m 4205 // known that __i <= __m 4206 while (true) 4207 { 4208 // __m still guards upward moving __i 4209 while (__comp(*__i, *__m)) 4210 ++__i; 4211 // It is now known that a guard exists for downward moving __j 4212 while (!__comp(*--__j, *__m)) 4213 ; 4214 if (__i > __j) 4215 break; 4216 swap(*__i, *__j); 4217 ++__n_swaps; 4218 // It is known that __m != __j 4219 // If __m just moved, follow it 4220 if (__m == __i) 4221 __m = __j; 4222 ++__i; 4223 } 4224 } 4225 // [__first, __i) < *__m and *__m <= [__i, __last) 4226 if (__i != __m && __comp(*__m, *__i)) 4227 { 4228 swap(*__i, *__m); 4229 ++__n_swaps; 4230 } 4231 // [__first, __i) < *__i and *__i <= [__i+1, __last) 4232 // If we were given a perfect partition, see if insertion sort is quick... 4233 if (__n_swaps == 0) 4234 { 4235 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); 4236 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp)) 4237 { 4238 if (__fs) 4239 return; 4240 __last = __i; 4241 continue; 4242 } 4243 else 4244 { 4245 if (__fs) 4246 { 4247 __first = ++__i; 4248 continue; 4249 } 4250 } 4251 } 4252 // sort smaller range with recursive call and larger with tail recursion elimination 4253 if (__i - __first < __last - __i) 4254 { 4255 _VSTD::__sort<_Compare>(__first, __i, __comp); 4256 // _VSTD::__sort<_Compare>(__i+1, __last, __comp); 4257 __first = ++__i; 4258 } 4259 else 4260 { 4261 _VSTD::__sort<_Compare>(__i+1, __last, __comp); 4262 // _VSTD::__sort<_Compare>(__first, __i, __comp); 4263 __last = __i; 4264 } 4265 } 4266} 4267 4268template <class _Compare, class _Tp> 4269inline _LIBCPP_INLINE_VISIBILITY 4270void 4271__sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) 4272{ 4273 __less<uintptr_t> __comp; 4274 _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp); 4275} 4276 4277_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&)) 4278_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) 4279_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) 4280_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) 4281_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&)) 4282_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) 4283_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&)) 4284_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) 4285_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&)) 4286_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) 4287_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) 4288_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>&)) 4289_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&)) 4290_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&)) 4291_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) 4292 4293_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&)) 4294_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) 4295_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) 4296_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) 4297_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&)) 4298_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) 4299_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&)) 4300_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) 4301_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&)) 4302_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) 4303_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) 4304_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>&)) 4305_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&)) 4306_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&)) 4307_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) 4308 4309_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>&)) 4310 4311// lower_bound 4312 4313template <class _Compare, class _ForwardIterator, class _Tp> 4314_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 4315__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4316{ 4317 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 4318 difference_type __len = _VSTD::distance(__first, __last); 4319 while (__len != 0) 4320 { 4321 difference_type __l2 = _VSTD::__half_positive(__len); 4322 _ForwardIterator __m = __first; 4323 _VSTD::advance(__m, __l2); 4324 if (__comp(*__m, __value_)) 4325 { 4326 __first = ++__m; 4327 __len -= __l2 + 1; 4328 } 4329 else 4330 __len = __l2; 4331 } 4332 return __first; 4333} 4334 4335template <class _ForwardIterator, class _Tp, class _Compare> 4336_LIBCPP_NODISCARD_EXT inline 4337_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4338_ForwardIterator 4339lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4340{ 4341 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4342 return _VSTD::__lower_bound<_Comp_ref>(__first, __last, __value_, __comp); 4343} 4344 4345template <class _ForwardIterator, class _Tp> 4346_LIBCPP_NODISCARD_EXT inline 4347_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4348_ForwardIterator 4349lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4350{ 4351 return _VSTD::lower_bound(__first, __last, __value_, 4352 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 4353} 4354 4355// upper_bound 4356 4357template <class _Compare, class _ForwardIterator, class _Tp> 4358_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 4359__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4360{ 4361 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 4362 difference_type __len = _VSTD::distance(__first, __last); 4363 while (__len != 0) 4364 { 4365 difference_type __l2 = _VSTD::__half_positive(__len); 4366 _ForwardIterator __m = __first; 4367 _VSTD::advance(__m, __l2); 4368 if (__comp(__value_, *__m)) 4369 __len = __l2; 4370 else 4371 { 4372 __first = ++__m; 4373 __len -= __l2 + 1; 4374 } 4375 } 4376 return __first; 4377} 4378 4379template <class _ForwardIterator, class _Tp, class _Compare> 4380_LIBCPP_NODISCARD_EXT inline 4381_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4382_ForwardIterator 4383upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4384{ 4385 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4386 return _VSTD::__upper_bound<_Comp_ref>(__first, __last, __value_, __comp); 4387} 4388 4389template <class _ForwardIterator, class _Tp> 4390_LIBCPP_NODISCARD_EXT inline 4391_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4392_ForwardIterator 4393upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4394{ 4395 return _VSTD::upper_bound(__first, __last, __value_, 4396 __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>()); 4397} 4398 4399// equal_range 4400 4401template <class _Compare, class _ForwardIterator, class _Tp> 4402_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator> 4403__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4404{ 4405 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 4406 difference_type __len = _VSTD::distance(__first, __last); 4407 while (__len != 0) 4408 { 4409 difference_type __l2 = _VSTD::__half_positive(__len); 4410 _ForwardIterator __m = __first; 4411 _VSTD::advance(__m, __l2); 4412 if (__comp(*__m, __value_)) 4413 { 4414 __first = ++__m; 4415 __len -= __l2 + 1; 4416 } 4417 else if (__comp(__value_, *__m)) 4418 { 4419 __last = __m; 4420 __len = __l2; 4421 } 4422 else 4423 { 4424 _ForwardIterator __mp1 = __m; 4425 return pair<_ForwardIterator, _ForwardIterator> 4426 ( 4427 _VSTD::__lower_bound<_Compare>(__first, __m, __value_, __comp), 4428 _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value_, __comp) 4429 ); 4430 } 4431 } 4432 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 4433} 4434 4435template <class _ForwardIterator, class _Tp, class _Compare> 4436_LIBCPP_NODISCARD_EXT inline 4437_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4438pair<_ForwardIterator, _ForwardIterator> 4439equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4440{ 4441 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4442 return _VSTD::__equal_range<_Comp_ref>(__first, __last, __value_, __comp); 4443} 4444 4445template <class _ForwardIterator, class _Tp> 4446_LIBCPP_NODISCARD_EXT inline 4447_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4448pair<_ForwardIterator, _ForwardIterator> 4449equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4450{ 4451 return _VSTD::equal_range(__first, __last, __value_, 4452 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 4453} 4454 4455// binary_search 4456 4457template <class _Compare, class _ForwardIterator, class _Tp> 4458inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4459bool 4460__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4461{ 4462 __first = _VSTD::__lower_bound<_Compare>(__first, __last, __value_, __comp); 4463 return __first != __last && !__comp(__value_, *__first); 4464} 4465 4466template <class _ForwardIterator, class _Tp, class _Compare> 4467_LIBCPP_NODISCARD_EXT inline 4468_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4469bool 4470binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4471{ 4472 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4473 return _VSTD::__binary_search<_Comp_ref>(__first, __last, __value_, __comp); 4474} 4475 4476template <class _ForwardIterator, class _Tp> 4477_LIBCPP_NODISCARD_EXT inline 4478_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4479bool 4480binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4481{ 4482 return _VSTD::binary_search(__first, __last, __value_, 4483 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 4484} 4485 4486// merge 4487 4488template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 4489_LIBCPP_CONSTEXPR_AFTER_CXX17 4490_OutputIterator 4491__merge(_InputIterator1 __first1, _InputIterator1 __last1, 4492 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 4493{ 4494 for (; __first1 != __last1; ++__result) 4495 { 4496 if (__first2 == __last2) 4497 return _VSTD::copy(__first1, __last1, __result); 4498 if (__comp(*__first2, *__first1)) 4499 { 4500 *__result = *__first2; 4501 ++__first2; 4502 } 4503 else 4504 { 4505 *__result = *__first1; 4506 ++__first1; 4507 } 4508 } 4509 return _VSTD::copy(__first2, __last2, __result); 4510} 4511 4512template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 4513inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4514_OutputIterator 4515merge(_InputIterator1 __first1, _InputIterator1 __last1, 4516 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 4517{ 4518 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4519 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 4520} 4521 4522template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 4523inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4524_OutputIterator 4525merge(_InputIterator1 __first1, _InputIterator1 __last1, 4526 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 4527{ 4528 typedef typename iterator_traits<_InputIterator1>::value_type __v1; 4529 typedef typename iterator_traits<_InputIterator2>::value_type __v2; 4530 return _VSTD::merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>()); 4531} 4532 4533// inplace_merge 4534 4535template <class _Compare, class _InputIterator1, class _InputIterator2, 4536 class _OutputIterator> 4537void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1, 4538 _InputIterator2 __first2, _InputIterator2 __last2, 4539 _OutputIterator __result, _Compare __comp) 4540{ 4541 for (; __first1 != __last1; ++__result) 4542 { 4543 if (__first2 == __last2) 4544 { 4545 _VSTD::move(__first1, __last1, __result); 4546 return; 4547 } 4548 4549 if (__comp(*__first2, *__first1)) 4550 { 4551 *__result = _VSTD::move(*__first2); 4552 ++__first2; 4553 } 4554 else 4555 { 4556 *__result = _VSTD::move(*__first1); 4557 ++__first1; 4558 } 4559 } 4560 // __first2 through __last2 are already in the right spot. 4561} 4562 4563template <class _Compare, class _BidirectionalIterator> 4564void 4565__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4566 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, 4567 typename iterator_traits<_BidirectionalIterator>::difference_type __len2, 4568 typename iterator_traits<_BidirectionalIterator>::value_type* __buff) 4569{ 4570 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 4571 __destruct_n __d(0); 4572 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); 4573 if (__len1 <= __len2) 4574 { 4575 value_type* __p = __buff; 4576 for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p) 4577 ::new ((void*)__p) value_type(_VSTD::move(*__i)); 4578 _VSTD::__half_inplace_merge<_Compare>(__buff, __p, __middle, __last, __first, __comp); 4579 } 4580 else 4581 { 4582 value_type* __p = __buff; 4583 for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p) 4584 ::new ((void*)__p) value_type(_VSTD::move(*__i)); 4585 typedef reverse_iterator<_BidirectionalIterator> _RBi; 4586 typedef reverse_iterator<value_type*> _Rv; 4587 typedef __invert<_Compare> _Inverted; 4588 _VSTD::__half_inplace_merge<_Inverted>(_Rv(__p), _Rv(__buff), 4589 _RBi(__middle), _RBi(__first), 4590 _RBi(__last), _Inverted(__comp)); 4591 } 4592} 4593 4594template <class _Compare, class _BidirectionalIterator> 4595void 4596__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4597 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, 4598 typename iterator_traits<_BidirectionalIterator>::difference_type __len2, 4599 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size) 4600{ 4601 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 4602 while (true) 4603 { 4604 // if __middle == __last, we're done 4605 if (__len2 == 0) 4606 return; 4607 if (__len1 <= __buff_size || __len2 <= __buff_size) 4608 return _VSTD::__buffered_inplace_merge<_Compare> 4609 (__first, __middle, __last, __comp, __len1, __len2, __buff); 4610 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0 4611 for (; true; ++__first, (void) --__len1) 4612 { 4613 if (__len1 == 0) 4614 return; 4615 if (__comp(*__middle, *__first)) 4616 break; 4617 } 4618 // __first < __middle < __last 4619 // *__first > *__middle 4620 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that 4621 // all elements in: 4622 // [__first, __m1) <= [__middle, __m2) 4623 // [__middle, __m2) < [__m1, __middle) 4624 // [__m1, __middle) <= [__m2, __last) 4625 // and __m1 or __m2 is in the middle of its range 4626 _BidirectionalIterator __m1; // "median" of [__first, __middle) 4627 _BidirectionalIterator __m2; // "median" of [__middle, __last) 4628 difference_type __len11; // distance(__first, __m1) 4629 difference_type __len21; // distance(__middle, __m2) 4630 // binary search smaller range 4631 if (__len1 < __len2) 4632 { // __len >= 1, __len2 >= 2 4633 __len21 = __len2 / 2; 4634 __m2 = __middle; 4635 _VSTD::advance(__m2, __len21); 4636 __m1 = _VSTD::__upper_bound<_Compare>(__first, __middle, *__m2, __comp); 4637 __len11 = _VSTD::distance(__first, __m1); 4638 } 4639 else 4640 { 4641 if (__len1 == 1) 4642 { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1 4643 // It is known *__first > *__middle 4644 swap(*__first, *__middle); 4645 return; 4646 } 4647 // __len1 >= 2, __len2 >= 1 4648 __len11 = __len1 / 2; 4649 __m1 = __first; 4650 _VSTD::advance(__m1, __len11); 4651 __m2 = _VSTD::__lower_bound<_Compare>(__middle, __last, *__m1, __comp); 4652 __len21 = _VSTD::distance(__middle, __m2); 4653 } 4654 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle) 4655 difference_type __len22 = __len2 - __len21; // distance(__m2, __last) 4656 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) 4657 // swap middle two partitions 4658 __middle = _VSTD::rotate(__m1, __middle, __m2); 4659 // __len12 and __len21 now have swapped meanings 4660 // merge smaller range with recursive call and larger with tail recursion elimination 4661 if (__len11 + __len21 < __len12 + __len22) 4662 { 4663 _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); 4664// _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); 4665 __first = __middle; 4666 __middle = __m2; 4667 __len1 = __len12; 4668 __len2 = __len22; 4669 } 4670 else 4671 { 4672 _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); 4673// _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); 4674 __last = __middle; 4675 __middle = __m1; 4676 __len1 = __len11; 4677 __len2 = __len21; 4678 } 4679 } 4680} 4681 4682template <class _BidirectionalIterator, class _Compare> 4683inline _LIBCPP_INLINE_VISIBILITY 4684void 4685inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4686 _Compare __comp) 4687{ 4688 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 4689 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 4690 difference_type __len1 = _VSTD::distance(__first, __middle); 4691 difference_type __len2 = _VSTD::distance(__middle, __last); 4692 difference_type __buf_size = _VSTD::min(__len1, __len2); 4693 pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size); 4694 unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first); 4695 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4696 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2, 4697 __buf.first, __buf.second); 4698} 4699 4700template <class _BidirectionalIterator> 4701inline _LIBCPP_INLINE_VISIBILITY 4702void 4703inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) 4704{ 4705 _VSTD::inplace_merge(__first, __middle, __last, 4706 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 4707} 4708 4709// stable_sort 4710 4711template <class _Compare, class _InputIterator1, class _InputIterator2> 4712void 4713__merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1, 4714 _InputIterator2 __first2, _InputIterator2 __last2, 4715 typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp) 4716{ 4717 typedef typename iterator_traits<_InputIterator1>::value_type value_type; 4718 __destruct_n __d(0); 4719 unique_ptr<value_type, __destruct_n&> __h(__result, __d); 4720 for (; true; ++__result) 4721 { 4722 if (__first1 == __last1) 4723 { 4724 for (; __first2 != __last2; ++__first2, ++__result, (void)__d.template __incr<value_type>()) 4725 ::new ((void*)__result) value_type(_VSTD::move(*__first2)); 4726 __h.release(); 4727 return; 4728 } 4729 if (__first2 == __last2) 4730 { 4731 for (; __first1 != __last1; ++__first1, ++__result, (void)__d.template __incr<value_type>()) 4732 ::new ((void*)__result) value_type(_VSTD::move(*__first1)); 4733 __h.release(); 4734 return; 4735 } 4736 if (__comp(*__first2, *__first1)) 4737 { 4738 ::new ((void*)__result) value_type(_VSTD::move(*__first2)); 4739 __d.template __incr<value_type>(); 4740 ++__first2; 4741 } 4742 else 4743 { 4744 ::new ((void*)__result) value_type(_VSTD::move(*__first1)); 4745 __d.template __incr<value_type>(); 4746 ++__first1; 4747 } 4748 } 4749} 4750 4751template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 4752void 4753__merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1, 4754 _InputIterator2 __first2, _InputIterator2 __last2, 4755 _OutputIterator __result, _Compare __comp) 4756{ 4757 for (; __first1 != __last1; ++__result) 4758 { 4759 if (__first2 == __last2) 4760 { 4761 for (; __first1 != __last1; ++__first1, (void) ++__result) 4762 *__result = _VSTD::move(*__first1); 4763 return; 4764 } 4765 if (__comp(*__first2, *__first1)) 4766 { 4767 *__result = _VSTD::move(*__first2); 4768 ++__first2; 4769 } 4770 else 4771 { 4772 *__result = _VSTD::move(*__first1); 4773 ++__first1; 4774 } 4775 } 4776 for (; __first2 != __last2; ++__first2, (void) ++__result) 4777 *__result = _VSTD::move(*__first2); 4778} 4779 4780template <class _Compare, class _RandomAccessIterator> 4781void 4782__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4783 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4784 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size); 4785 4786template <class _Compare, class _RandomAccessIterator> 4787void 4788__stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp, 4789 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4790 typename iterator_traits<_RandomAccessIterator>::value_type* __first2) 4791{ 4792 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4793 switch (__len) 4794 { 4795 case 0: 4796 return; 4797 case 1: 4798 ::new ((void*)__first2) value_type(_VSTD::move(*__first1)); 4799 return; 4800 case 2: 4801 __destruct_n __d(0); 4802 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d); 4803 if (__comp(*--__last1, *__first1)) 4804 { 4805 ::new ((void*)__first2) value_type(_VSTD::move(*__last1)); 4806 __d.template __incr<value_type>(); 4807 ++__first2; 4808 ::new ((void*)__first2) value_type(_VSTD::move(*__first1)); 4809 } 4810 else 4811 { 4812 ::new ((void*)__first2) value_type(_VSTD::move(*__first1)); 4813 __d.template __incr<value_type>(); 4814 ++__first2; 4815 ::new ((void*)__first2) value_type(_VSTD::move(*__last1)); 4816 } 4817 __h2.release(); 4818 return; 4819 } 4820 if (__len <= 8) 4821 { 4822 _VSTD::__insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp); 4823 return; 4824 } 4825 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; 4826 _RandomAccessIterator __m = __first1 + __l2; 4827 _VSTD::__stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2); 4828 _VSTD::__stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2); 4829 _VSTD::__merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp); 4830} 4831 4832template <class _Tp> 4833struct __stable_sort_switch 4834{ 4835 static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value; 4836}; 4837 4838template <class _Compare, class _RandomAccessIterator> 4839void 4840__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4841 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4842 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size) 4843{ 4844 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4845 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4846 switch (__len) 4847 { 4848 case 0: 4849 case 1: 4850 return; 4851 case 2: 4852 if (__comp(*--__last, *__first)) 4853 swap(*__first, *__last); 4854 return; 4855 } 4856 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value)) 4857 { 4858 _VSTD::__insertion_sort<_Compare>(__first, __last, __comp); 4859 return; 4860 } 4861 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; 4862 _RandomAccessIterator __m = __first + __l2; 4863 if (__len <= __buff_size) 4864 { 4865 __destruct_n __d(0); 4866 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); 4867 _VSTD::__stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff); 4868 __d.__set(__l2, (value_type*)nullptr); 4869 _VSTD::__stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2); 4870 __d.__set(__len, (value_type*)nullptr); 4871 _VSTD::__merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp); 4872// _VSTD::__merge<_Compare>(move_iterator<value_type*>(__buff), 4873// move_iterator<value_type*>(__buff + __l2), 4874// move_iterator<_RandomAccessIterator>(__buff + __l2), 4875// move_iterator<_RandomAccessIterator>(__buff + __len), 4876// __first, __comp); 4877 return; 4878 } 4879 _VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size); 4880 _VSTD::__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); 4881 _VSTD::__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); 4882} 4883 4884template <class _RandomAccessIterator, class _Compare> 4885inline _LIBCPP_INLINE_VISIBILITY 4886void 4887stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4888{ 4889 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4890 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4891 difference_type __len = __last - __first; 4892 pair<value_type*, ptrdiff_t> __buf(0, 0); 4893 unique_ptr<value_type, __return_temporary_buffer> __h; 4894 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) 4895 { 4896 __buf = _VSTD::get_temporary_buffer<value_type>(__len); 4897 __h.reset(__buf.first); 4898 } 4899 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4900 _VSTD::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); 4901} 4902 4903template <class _RandomAccessIterator> 4904inline _LIBCPP_INLINE_VISIBILITY 4905void 4906stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 4907{ 4908 _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4909} 4910 4911// is_heap_until 4912 4913template <class _RandomAccessIterator, class _Compare> 4914_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator 4915is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4916{ 4917 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4918 difference_type __len = __last - __first; 4919 difference_type __p = 0; 4920 difference_type __c = 1; 4921 _RandomAccessIterator __pp = __first; 4922 while (__c < __len) 4923 { 4924 _RandomAccessIterator __cp = __first + __c; 4925 if (__comp(*__pp, *__cp)) 4926 return __cp; 4927 ++__c; 4928 ++__cp; 4929 if (__c == __len) 4930 return __last; 4931 if (__comp(*__pp, *__cp)) 4932 return __cp; 4933 ++__p; 4934 ++__pp; 4935 __c = 2 * __p + 1; 4936 } 4937 return __last; 4938} 4939 4940template<class _RandomAccessIterator> 4941_LIBCPP_NODISCARD_EXT inline 4942_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4943_RandomAccessIterator 4944is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) 4945{ 4946 return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4947} 4948 4949// is_heap 4950 4951template <class _RandomAccessIterator, class _Compare> 4952_LIBCPP_NODISCARD_EXT inline 4953_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4954bool 4955is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4956{ 4957 return _VSTD::is_heap_until(__first, __last, __comp) == __last; 4958} 4959 4960template<class _RandomAccessIterator> 4961_LIBCPP_NODISCARD_EXT inline 4962_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4963bool 4964is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 4965{ 4966 return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4967} 4968 4969// push_heap 4970 4971template <class _Compare, class _RandomAccessIterator> 4972_LIBCPP_CONSTEXPR_AFTER_CXX11 void 4973__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4974 typename iterator_traits<_RandomAccessIterator>::difference_type __len) 4975{ 4976 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4977 if (__len > 1) 4978 { 4979 __len = (__len - 2) / 2; 4980 _RandomAccessIterator __ptr = __first + __len; 4981 if (__comp(*__ptr, *--__last)) 4982 { 4983 value_type __t(_VSTD::move(*__last)); 4984 do 4985 { 4986 *__last = _VSTD::move(*__ptr); 4987 __last = __ptr; 4988 if (__len == 0) 4989 break; 4990 __len = (__len - 1) / 2; 4991 __ptr = __first + __len; 4992 } while (__comp(*__ptr, __t)); 4993 *__last = _VSTD::move(__t); 4994 } 4995 } 4996} 4997 4998template <class _RandomAccessIterator, class _Compare> 4999inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5000void 5001push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5002{ 5003 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5004 _VSTD::__sift_up<_Comp_ref>(__first, __last, __comp, __last - __first); 5005} 5006 5007template <class _RandomAccessIterator> 5008inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5009void 5010push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 5011{ 5012 _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5013} 5014 5015// pop_heap 5016 5017template <class _Compare, class _RandomAccessIterator> 5018_LIBCPP_CONSTEXPR_AFTER_CXX11 void 5019__sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/, 5020 _Compare __comp, 5021 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 5022 _RandomAccessIterator __start) 5023{ 5024 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 5025 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 5026 // left-child of __start is at 2 * __start + 1 5027 // right-child of __start is at 2 * __start + 2 5028 difference_type __child = __start - __first; 5029 5030 if (__len < 2 || (__len - 2) / 2 < __child) 5031 return; 5032 5033 __child = 2 * __child + 1; 5034 _RandomAccessIterator __child_i = __first + __child; 5035 5036 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { 5037 // right-child exists and is greater than left-child 5038 ++__child_i; 5039 ++__child; 5040 } 5041 5042 // check if we are in heap-order 5043 if (__comp(*__child_i, *__start)) 5044 // we are, __start is larger than it's largest child 5045 return; 5046 5047 value_type __top(_VSTD::move(*__start)); 5048 do 5049 { 5050 // we are not in heap-order, swap the parent with its largest child 5051 *__start = _VSTD::move(*__child_i); 5052 __start = __child_i; 5053 5054 if ((__len - 2) / 2 < __child) 5055 break; 5056 5057 // recompute the child based off of the updated parent 5058 __child = 2 * __child + 1; 5059 __child_i = __first + __child; 5060 5061 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { 5062 // right-child exists and is greater than left-child 5063 ++__child_i; 5064 ++__child; 5065 } 5066 5067 // check if we are in heap-order 5068 } while (!__comp(*__child_i, __top)); 5069 *__start = _VSTD::move(__top); 5070} 5071 5072template <class _Compare, class _RandomAccessIterator> 5073inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5074void 5075__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 5076 typename iterator_traits<_RandomAccessIterator>::difference_type __len) 5077{ 5078 if (__len > 1) 5079 { 5080 swap(*__first, *--__last); 5081 _VSTD::__sift_down<_Compare>(__first, __last, __comp, __len - 1, __first); 5082 } 5083} 5084 5085template <class _RandomAccessIterator, class _Compare> 5086inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5087void 5088pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5089{ 5090 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5091 _VSTD::__pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first); 5092} 5093 5094template <class _RandomAccessIterator> 5095inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5096void 5097pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 5098{ 5099 _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5100} 5101 5102// make_heap 5103 5104template <class _Compare, class _RandomAccessIterator> 5105_LIBCPP_CONSTEXPR_AFTER_CXX11 void 5106__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5107{ 5108 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 5109 difference_type __n = __last - __first; 5110 if (__n > 1) 5111 { 5112 // start from the first parent, there is no need to consider children 5113 for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) 5114 { 5115 _VSTD::__sift_down<_Compare>(__first, __last, __comp, __n, __first + __start); 5116 } 5117 } 5118} 5119 5120template <class _RandomAccessIterator, class _Compare> 5121inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5122void 5123make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5124{ 5125 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5126 _VSTD::__make_heap<_Comp_ref>(__first, __last, __comp); 5127} 5128 5129template <class _RandomAccessIterator> 5130inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5131void 5132make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 5133{ 5134 _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5135} 5136 5137// sort_heap 5138 5139template <class _Compare, class _RandomAccessIterator> 5140_LIBCPP_CONSTEXPR_AFTER_CXX17 void 5141__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5142{ 5143 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 5144 for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n) 5145 _VSTD::__pop_heap<_Compare>(__first, __last, __comp, __n); 5146} 5147 5148template <class _RandomAccessIterator, class _Compare> 5149inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5150void 5151sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5152{ 5153 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5154 _VSTD::__sort_heap<_Comp_ref>(__first, __last, __comp); 5155} 5156 5157template <class _RandomAccessIterator> 5158inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5159void 5160sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 5161{ 5162 _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5163} 5164 5165// partial_sort 5166 5167template <class _Compare, class _RandomAccessIterator> 5168_LIBCPP_CONSTEXPR_AFTER_CXX17 void 5169__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, 5170 _Compare __comp) 5171{ 5172 _VSTD::__make_heap<_Compare>(__first, __middle, __comp); 5173 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first; 5174 for (_RandomAccessIterator __i = __middle; __i != __last; ++__i) 5175 { 5176 if (__comp(*__i, *__first)) 5177 { 5178 swap(*__i, *__first); 5179 _VSTD::__sift_down<_Compare>(__first, __middle, __comp, __len, __first); 5180 } 5181 } 5182 _VSTD::__sort_heap<_Compare>(__first, __middle, __comp); 5183} 5184 5185template <class _RandomAccessIterator, class _Compare> 5186inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5187void 5188partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, 5189 _Compare __comp) 5190{ 5191 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5192 _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp); 5193} 5194 5195template <class _RandomAccessIterator> 5196inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5197void 5198partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) 5199{ 5200 _VSTD::partial_sort(__first, __middle, __last, 5201 __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5202} 5203 5204// partial_sort_copy 5205 5206template <class _Compare, class _InputIterator, class _RandomAccessIterator> 5207_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator 5208__partial_sort_copy(_InputIterator __first, _InputIterator __last, 5209 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) 5210{ 5211 _RandomAccessIterator __r = __result_first; 5212 if (__r != __result_last) 5213 { 5214 for (; __first != __last && __r != __result_last; ++__first, (void) ++__r) 5215 *__r = *__first; 5216 _VSTD::__make_heap<_Compare>(__result_first, __r, __comp); 5217 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first; 5218 for (; __first != __last; ++__first) 5219 if (__comp(*__first, *__result_first)) 5220 { 5221 *__result_first = *__first; 5222 _VSTD::__sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first); 5223 } 5224 _VSTD::__sort_heap<_Compare>(__result_first, __r, __comp); 5225 } 5226 return __r; 5227} 5228 5229template <class _InputIterator, class _RandomAccessIterator, class _Compare> 5230inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5231_RandomAccessIterator 5232partial_sort_copy(_InputIterator __first, _InputIterator __last, 5233 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) 5234{ 5235 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5236 return _VSTD::__partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp); 5237} 5238 5239template <class _InputIterator, class _RandomAccessIterator> 5240inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5241_RandomAccessIterator 5242partial_sort_copy(_InputIterator __first, _InputIterator __last, 5243 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last) 5244{ 5245 return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last, 5246 __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5247} 5248 5249// nth_element 5250 5251template<class _Compare, class _RandomAccessIterator> 5252_LIBCPP_CONSTEXPR_AFTER_CXX11 bool 5253__nth_element_find_guard(_RandomAccessIterator& __i, _RandomAccessIterator& __j, 5254 _RandomAccessIterator __m, _Compare __comp) 5255{ 5256 // manually guard downward moving __j against __i 5257 while (true) { 5258 if (__i == --__j) { 5259 return false; 5260 } 5261 if (__comp(*__j, *__m)) { 5262 return true; // found guard for downward moving __j, now use unguarded partition 5263 } 5264 } 5265} 5266 5267template <class _Compare, class _RandomAccessIterator> 5268_LIBCPP_CONSTEXPR_AFTER_CXX11 void 5269__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) 5270{ 5271 // _Compare is known to be a reference type 5272 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 5273 const difference_type __limit = 7; 5274 while (true) 5275 { 5276 if (__nth == __last) 5277 return; 5278 difference_type __len = __last - __first; 5279 switch (__len) 5280 { 5281 case 0: 5282 case 1: 5283 return; 5284 case 2: 5285 if (__comp(*--__last, *__first)) 5286 swap(*__first, *__last); 5287 return; 5288 case 3: 5289 { 5290 _RandomAccessIterator __m = __first; 5291 _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp); 5292 return; 5293 } 5294 } 5295 if (__len <= __limit) 5296 { 5297 _VSTD::__selection_sort<_Compare>(__first, __last, __comp); 5298 return; 5299 } 5300 // __len > __limit >= 3 5301 _RandomAccessIterator __m = __first + __len/2; 5302 _RandomAccessIterator __lm1 = __last; 5303 unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp); 5304 // *__m is median 5305 // partition [__first, __m) < *__m and *__m <= [__m, __last) 5306 // (this inhibits tossing elements equivalent to __m around unnecessarily) 5307 _RandomAccessIterator __i = __first; 5308 _RandomAccessIterator __j = __lm1; 5309 // j points beyond range to be tested, *__lm1 is known to be <= *__m 5310 // The search going up is known to be guarded but the search coming down isn't. 5311 // Prime the downward search with a guard. 5312 if (!__comp(*__i, *__m)) // if *__first == *__m 5313 { 5314 // *__first == *__m, *__first doesn't go in first part 5315 if (_VSTD::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) { 5316 swap(*__i, *__j); 5317 ++__n_swaps; 5318 } else { 5319 // *__first == *__m, *__m <= all other elements 5320 // Partition instead into [__first, __i) == *__first and *__first < [__i, __last) 5321 ++__i; // __first + 1 5322 __j = __last; 5323 if (!__comp(*__first, *--__j)) { // we need a guard if *__first == *(__last-1) 5324 while (true) { 5325 if (__i == __j) { 5326 return; // [__first, __last) all equivalent elements 5327 } else if (__comp(*__first, *__i)) { 5328 swap(*__i, *__j); 5329 ++__n_swaps; 5330 ++__i; 5331 break; 5332 } 5333 ++__i; 5334 } 5335 } 5336 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 5337 if (__i == __j) { 5338 return; 5339 } 5340 while (true) { 5341 while (!__comp(*__first, *__i)) 5342 ++__i; 5343 while (__comp(*__first, *--__j)) 5344 ; 5345 if (__i >= __j) 5346 break; 5347 swap(*__i, *__j); 5348 ++__n_swaps; 5349 ++__i; 5350 } 5351 // [__first, __i) == *__first and *__first < [__i, __last) 5352 // The first part is sorted, 5353 if (__nth < __i) { 5354 return; 5355 } 5356 // __nth_element the second part 5357 // _VSTD::__nth_element<_Compare>(__i, __nth, __last, __comp); 5358 __first = __i; 5359 continue; 5360 } 5361 } 5362 ++__i; 5363 // j points beyond range to be tested, *__lm1 is known to be <= *__m 5364 // if not yet partitioned... 5365 if (__i < __j) 5366 { 5367 // known that *(__i - 1) < *__m 5368 while (true) 5369 { 5370 // __m still guards upward moving __i 5371 while (__comp(*__i, *__m)) 5372 ++__i; 5373 // It is now known that a guard exists for downward moving __j 5374 while (!__comp(*--__j, *__m)) 5375 ; 5376 if (__i >= __j) 5377 break; 5378 swap(*__i, *__j); 5379 ++__n_swaps; 5380 // It is known that __m != __j 5381 // If __m just moved, follow it 5382 if (__m == __i) 5383 __m = __j; 5384 ++__i; 5385 } 5386 } 5387 // [__first, __i) < *__m and *__m <= [__i, __last) 5388 if (__i != __m && __comp(*__m, *__i)) 5389 { 5390 swap(*__i, *__m); 5391 ++__n_swaps; 5392 } 5393 // [__first, __i) < *__i and *__i <= [__i+1, __last) 5394 if (__nth == __i) 5395 return; 5396 if (__n_swaps == 0) 5397 { 5398 // We were given a perfectly partitioned sequence. Coincidence? 5399 if (__nth < __i) 5400 { 5401 // Check for [__first, __i) already sorted 5402 __j = __m = __first; 5403 while (true) { 5404 if (++__j == __i) { 5405 // [__first, __i) sorted 5406 return; 5407 } 5408 if (__comp(*__j, *__m)) { 5409 // not yet sorted, so sort 5410 break; 5411 } 5412 __m = __j; 5413 } 5414 } 5415 else 5416 { 5417 // Check for [__i, __last) already sorted 5418 __j = __m = __i; 5419 while (true) { 5420 if (++__j == __last) { 5421 // [__i, __last) sorted 5422 return; 5423 } 5424 if (__comp(*__j, *__m)) { 5425 // not yet sorted, so sort 5426 break; 5427 } 5428 __m = __j; 5429 } 5430 } 5431 } 5432 // __nth_element on range containing __nth 5433 if (__nth < __i) 5434 { 5435 // _VSTD::__nth_element<_Compare>(__first, __nth, __i, __comp); 5436 __last = __i; 5437 } 5438 else 5439 { 5440 // _VSTD::__nth_element<_Compare>(__i+1, __nth, __last, __comp); 5441 __first = ++__i; 5442 } 5443 } 5444} 5445 5446template <class _RandomAccessIterator, class _Compare> 5447inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5448void 5449nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) 5450{ 5451 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5452 _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp); 5453} 5454 5455template <class _RandomAccessIterator> 5456inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5457void 5458nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) 5459{ 5460 _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5461} 5462 5463// sort 5464 5465template <class _RandomAccessIterator, class _Compare> 5466inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5467void 5468sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5469{ 5470 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5471 if (__libcpp_is_constant_evaluated()) { 5472 _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); 5473 } else { 5474 _VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _Comp_ref(__comp)); 5475 } 5476} 5477 5478template <class _RandomAccessIterator> 5479inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5480void 5481sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 5482{ 5483 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5484} 5485 5486// includes 5487 5488template <class _Compare, class _InputIterator1, class _InputIterator2> 5489_LIBCPP_CONSTEXPR_AFTER_CXX17 bool 5490__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, 5491 _Compare __comp) 5492{ 5493 for (; __first2 != __last2; ++__first1) 5494 { 5495 if (__first1 == __last1 || __comp(*__first2, *__first1)) 5496 return false; 5497 if (!__comp(*__first1, *__first2)) 5498 ++__first2; 5499 } 5500 return true; 5501} 5502 5503template <class _InputIterator1, class _InputIterator2, class _Compare> 5504_LIBCPP_NODISCARD_EXT inline 5505_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5506bool 5507includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, 5508 _Compare __comp) 5509{ 5510 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5511 return _VSTD::__includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); 5512} 5513 5514template <class _InputIterator1, class _InputIterator2> 5515_LIBCPP_NODISCARD_EXT inline 5516_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5517bool 5518includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) 5519{ 5520 return _VSTD::includes(__first1, __last1, __first2, __last2, 5521 __less<typename iterator_traits<_InputIterator1>::value_type, 5522 typename iterator_traits<_InputIterator2>::value_type>()); 5523} 5524 5525// set_union 5526 5527template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5528_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 5529__set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5530 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5531{ 5532 for (; __first1 != __last1; ++__result) 5533 { 5534 if (__first2 == __last2) 5535 return _VSTD::copy(__first1, __last1, __result); 5536 if (__comp(*__first2, *__first1)) 5537 { 5538 *__result = *__first2; 5539 ++__first2; 5540 } 5541 else 5542 { 5543 if (!__comp(*__first1, *__first2)) 5544 ++__first2; 5545 *__result = *__first1; 5546 ++__first1; 5547 } 5548 } 5549 return _VSTD::copy(__first2, __last2, __result); 5550} 5551 5552template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5553inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5554_OutputIterator 5555set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5556 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5557{ 5558 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5559 return _VSTD::__set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5560} 5561 5562template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5563inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5564_OutputIterator 5565set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5566 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5567{ 5568 return _VSTD::set_union(__first1, __last1, __first2, __last2, __result, 5569 __less<typename iterator_traits<_InputIterator1>::value_type, 5570 typename iterator_traits<_InputIterator2>::value_type>()); 5571} 5572 5573// set_intersection 5574 5575template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5576_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 5577__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5578 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5579{ 5580 while (__first1 != __last1 && __first2 != __last2) 5581 { 5582 if (__comp(*__first1, *__first2)) 5583 ++__first1; 5584 else 5585 { 5586 if (!__comp(*__first2, *__first1)) 5587 { 5588 *__result = *__first1; 5589 ++__result; 5590 ++__first1; 5591 } 5592 ++__first2; 5593 } 5594 } 5595 return __result; 5596} 5597 5598template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5599inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5600_OutputIterator 5601set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5602 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5603{ 5604 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5605 return _VSTD::__set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5606} 5607 5608template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5609inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5610_OutputIterator 5611set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5612 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5613{ 5614 return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result, 5615 __less<typename iterator_traits<_InputIterator1>::value_type, 5616 typename iterator_traits<_InputIterator2>::value_type>()); 5617} 5618 5619// set_difference 5620 5621template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5622_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 5623__set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5624 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5625{ 5626 while (__first1 != __last1) 5627 { 5628 if (__first2 == __last2) 5629 return _VSTD::copy(__first1, __last1, __result); 5630 if (__comp(*__first1, *__first2)) 5631 { 5632 *__result = *__first1; 5633 ++__result; 5634 ++__first1; 5635 } 5636 else 5637 { 5638 if (!__comp(*__first2, *__first1)) 5639 ++__first1; 5640 ++__first2; 5641 } 5642 } 5643 return __result; 5644} 5645 5646template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5647inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5648_OutputIterator 5649set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5650 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5651{ 5652 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5653 return _VSTD::__set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5654} 5655 5656template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5657inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5658_OutputIterator 5659set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5660 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5661{ 5662 return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result, 5663 __less<typename iterator_traits<_InputIterator1>::value_type, 5664 typename iterator_traits<_InputIterator2>::value_type>()); 5665} 5666 5667// set_symmetric_difference 5668 5669template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5670_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 5671__set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5672 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5673{ 5674 while (__first1 != __last1) 5675 { 5676 if (__first2 == __last2) 5677 return _VSTD::copy(__first1, __last1, __result); 5678 if (__comp(*__first1, *__first2)) 5679 { 5680 *__result = *__first1; 5681 ++__result; 5682 ++__first1; 5683 } 5684 else 5685 { 5686 if (__comp(*__first2, *__first1)) 5687 { 5688 *__result = *__first2; 5689 ++__result; 5690 } 5691 else 5692 ++__first1; 5693 ++__first2; 5694 } 5695 } 5696 return _VSTD::copy(__first2, __last2, __result); 5697} 5698 5699template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5700inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5701_OutputIterator 5702set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5703 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5704{ 5705 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5706 return _VSTD::__set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5707} 5708 5709template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5710inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5711_OutputIterator 5712set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5713 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5714{ 5715 return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, 5716 __less<typename iterator_traits<_InputIterator1>::value_type, 5717 typename iterator_traits<_InputIterator2>::value_type>()); 5718} 5719 5720// lexicographical_compare 5721 5722template <class _Compare, class _InputIterator1, class _InputIterator2> 5723_LIBCPP_CONSTEXPR_AFTER_CXX17 bool 5724__lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5725 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) 5726{ 5727 for (; __first2 != __last2; ++__first1, (void) ++__first2) 5728 { 5729 if (__first1 == __last1 || __comp(*__first1, *__first2)) 5730 return true; 5731 if (__comp(*__first2, *__first1)) 5732 return false; 5733 } 5734 return false; 5735} 5736 5737template <class _InputIterator1, class _InputIterator2, class _Compare> 5738_LIBCPP_NODISCARD_EXT inline 5739_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5740bool 5741lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5742 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) 5743{ 5744 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5745 return _VSTD::__lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); 5746} 5747 5748template <class _InputIterator1, class _InputIterator2> 5749_LIBCPP_NODISCARD_EXT inline 5750_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5751bool 5752lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5753 _InputIterator2 __first2, _InputIterator2 __last2) 5754{ 5755 return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2, 5756 __less<typename iterator_traits<_InputIterator1>::value_type, 5757 typename iterator_traits<_InputIterator2>::value_type>()); 5758} 5759 5760// next_permutation 5761 5762template <class _Compare, class _BidirectionalIterator> 5763_LIBCPP_CONSTEXPR_AFTER_CXX17 bool 5764__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5765{ 5766 _BidirectionalIterator __i = __last; 5767 if (__first == __last || __first == --__i) 5768 return false; 5769 while (true) 5770 { 5771 _BidirectionalIterator __ip1 = __i; 5772 if (__comp(*--__i, *__ip1)) 5773 { 5774 _BidirectionalIterator __j = __last; 5775 while (!__comp(*__i, *--__j)) 5776 ; 5777 swap(*__i, *__j); 5778 _VSTD::reverse(__ip1, __last); 5779 return true; 5780 } 5781 if (__i == __first) 5782 { 5783 _VSTD::reverse(__first, __last); 5784 return false; 5785 } 5786 } 5787} 5788 5789template <class _BidirectionalIterator, class _Compare> 5790inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5791bool 5792next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5793{ 5794 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5795 return _VSTD::__next_permutation<_Comp_ref>(__first, __last, __comp); 5796} 5797 5798template <class _BidirectionalIterator> 5799inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5800bool 5801next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) 5802{ 5803 return _VSTD::next_permutation(__first, __last, 5804 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 5805} 5806 5807// prev_permutation 5808 5809template <class _Compare, class _BidirectionalIterator> 5810_LIBCPP_CONSTEXPR_AFTER_CXX17 bool 5811__prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5812{ 5813 _BidirectionalIterator __i = __last; 5814 if (__first == __last || __first == --__i) 5815 return false; 5816 while (true) 5817 { 5818 _BidirectionalIterator __ip1 = __i; 5819 if (__comp(*__ip1, *--__i)) 5820 { 5821 _BidirectionalIterator __j = __last; 5822 while (!__comp(*--__j, *__i)) 5823 ; 5824 swap(*__i, *__j); 5825 _VSTD::reverse(__ip1, __last); 5826 return true; 5827 } 5828 if (__i == __first) 5829 { 5830 _VSTD::reverse(__first, __last); 5831 return false; 5832 } 5833 } 5834} 5835 5836template <class _BidirectionalIterator, class _Compare> 5837inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5838bool 5839prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5840{ 5841 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5842 return _VSTD::__prev_permutation<_Comp_ref>(__first, __last, __comp); 5843} 5844 5845template <class _BidirectionalIterator> 5846inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5847bool 5848prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) 5849{ 5850 return _VSTD::prev_permutation(__first, __last, 5851 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 5852} 5853 5854_LIBCPP_END_NAMESPACE_STD 5855 5856_LIBCPP_POP_MACROS 5857 5858#if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17 5859# include <__pstl_algorithm> 5860#endif 5861 5862#endif // _LIBCPP_ALGORITHM 5863