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