1// -*- C++ -*- 2//===-------------------------- algorithm ---------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP_ALGORITHM 11#define _LIBCPP_ALGORITHM 12 13/* 14 algorithm synopsis 15 16#include <initializer_list> 17 18namespace std 19{ 20 21template <class InputIterator, class Predicate> 22 constexpr bool // constexpr in C++20 23 all_of(InputIterator first, InputIterator last, Predicate pred); 24 25template <class InputIterator, class Predicate> 26 constexpr bool // constexpr in C++20 27 any_of(InputIterator first, InputIterator last, Predicate pred); 28 29template <class InputIterator, class Predicate> 30 constexpr bool // constexpr in C++20 31 none_of(InputIterator first, InputIterator last, Predicate pred); 32 33template <class InputIterator, class Function> 34 constexpr Function // constexpr in C++20 35 for_each(InputIterator first, InputIterator last, Function f); 36 37template<class InputIterator, class Size, class Function> 38 constexpr InputIterator // constexpr in C++20 39 for_each_n(InputIterator first, Size n, Function f); // C++17 40 41template <class InputIterator, class T> 42 constexpr InputIterator // constexpr in C++20 43 find(InputIterator first, InputIterator last, const T& value); 44 45template <class InputIterator, class Predicate> 46 constexpr InputIterator // constexpr in C++20 47 find_if(InputIterator first, InputIterator last, Predicate pred); 48 49template<class InputIterator, class Predicate> 50 constexpr InputIterator // constexpr in C++20 51 find_if_not(InputIterator first, InputIterator last, Predicate pred); 52 53template <class ForwardIterator1, class ForwardIterator2> 54 constexpr ForwardIterator1 // constexpr in C++20 55 find_end(ForwardIterator1 first1, ForwardIterator1 last1, 56 ForwardIterator2 first2, ForwardIterator2 last2); 57 58template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 59 constexpr ForwardIterator1 // constexpr in C++20 60 find_end(ForwardIterator1 first1, ForwardIterator1 last1, 61 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); 62 63template <class ForwardIterator1, class ForwardIterator2> 64 constexpr ForwardIterator1 // constexpr in C++20 65 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, 66 ForwardIterator2 first2, ForwardIterator2 last2); 67 68template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 69 constexpr ForwardIterator1 // constexpr in C++20 70 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, 71 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); 72 73template <class ForwardIterator> 74 constexpr ForwardIterator // constexpr in C++20 75 adjacent_find(ForwardIterator first, ForwardIterator last); 76 77template <class ForwardIterator, class BinaryPredicate> 78 constexpr ForwardIterator // constexpr in C++20 79 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); 80 81template <class InputIterator, class T> 82 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20 83 count(InputIterator first, InputIterator last, const T& value); 84 85template <class InputIterator, class Predicate> 86 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20 87 count_if(InputIterator first, InputIterator last, Predicate pred); 88 89template <class InputIterator1, class InputIterator2> 90 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 91 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); 92 93template <class InputIterator1, class InputIterator2> 94 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 95 mismatch(InputIterator1 first1, InputIterator1 last1, 96 InputIterator2 first2, InputIterator2 last2); // **C++14** 97 98template <class InputIterator1, class InputIterator2, class BinaryPredicate> 99 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 100 mismatch(InputIterator1 first1, InputIterator1 last1, 101 InputIterator2 first2, BinaryPredicate pred); 102 103template <class InputIterator1, class InputIterator2, class BinaryPredicate> 104 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 105 mismatch(InputIterator1 first1, InputIterator1 last1, 106 InputIterator2 first2, InputIterator2 last2, 107 BinaryPredicate pred); // **C++14** 108 109template <class InputIterator1, class InputIterator2> 110 constexpr bool // constexpr in C++20 111 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); 112 113template <class InputIterator1, class InputIterator2> 114 constexpr bool // constexpr in C++20 115 equal(InputIterator1 first1, InputIterator1 last1, 116 InputIterator2 first2, InputIterator2 last2); // **C++14** 117 118template <class InputIterator1, class InputIterator2, class BinaryPredicate> 119 constexpr bool // constexpr in C++20 120 equal(InputIterator1 first1, InputIterator1 last1, 121 InputIterator2 first2, BinaryPredicate pred); 122 123template <class InputIterator1, class InputIterator2, class BinaryPredicate> 124 constexpr bool // constexpr in C++20 125 equal(InputIterator1 first1, InputIterator1 last1, 126 InputIterator2 first2, InputIterator2 last2, 127 BinaryPredicate pred); // **C++14** 128 129template<class ForwardIterator1, class ForwardIterator2> 130 constexpr bool // constexpr in C++20 131 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 132 ForwardIterator2 first2); 133 134template<class ForwardIterator1, class ForwardIterator2> 135 constexpr bool // constexpr in C++20 136 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 137 ForwardIterator2 first2, ForwardIterator2 last2); // **C++14** 138 139template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 140 constexpr bool // constexpr in C++20 141 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 142 ForwardIterator2 first2, BinaryPredicate pred); 143 144template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 145 constexpr bool // constexpr in C++20 146 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 147 ForwardIterator2 first2, ForwardIterator2 last2, 148 BinaryPredicate pred); // **C++14** 149 150template <class ForwardIterator1, class ForwardIterator2> 151 constexpr ForwardIterator1 // constexpr in C++20 152 search(ForwardIterator1 first1, ForwardIterator1 last1, 153 ForwardIterator2 first2, ForwardIterator2 last2); 154 155template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 156 constexpr ForwardIterator1 // constexpr in C++20 157 search(ForwardIterator1 first1, ForwardIterator1 last1, 158 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); 159 160template <class ForwardIterator, class Size, class T> 161 constexpr ForwardIterator // constexpr in C++20 162 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value); 163 164template <class ForwardIterator, class Size, class T, class BinaryPredicate> 165 constexpr ForwardIterator // constexpr in C++20 166 search_n(ForwardIterator first, ForwardIterator last, 167 Size count, const T& value, BinaryPredicate pred); 168 169template <class InputIterator, class OutputIterator> 170 constexpr OutputIterator // constexpr in C++20 171 copy(InputIterator first, InputIterator last, OutputIterator result); 172 173template<class InputIterator, class OutputIterator, class Predicate> 174 constexpr OutputIterator // constexpr in C++20 175 copy_if(InputIterator first, InputIterator last, 176 OutputIterator result, Predicate pred); 177 178template<class InputIterator, class Size, class OutputIterator> 179 constexpr OutputIterator // constexpr in C++20 180 copy_n(InputIterator first, Size n, OutputIterator result); 181 182template <class BidirectionalIterator1, class BidirectionalIterator2> 183 constexpr BidirectionalIterator2 // constexpr in C++20 184 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, 185 BidirectionalIterator2 result); 186 187template <class ForwardIterator1, class ForwardIterator2> 188 constexpr ForwardIterator2 // constexpr in C++20 189 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); 190 191template <class ForwardIterator1, class ForwardIterator2> 192 constexpr void // constexpr in C++20 193 iter_swap(ForwardIterator1 a, ForwardIterator2 b); 194 195template <class InputIterator, class OutputIterator, class UnaryOperation> 196 constexpr OutputIterator // constexpr in C++20 197 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op); 198 199template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> 200 constexpr OutputIterator // constexpr in C++20 201 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, 202 OutputIterator result, BinaryOperation binary_op); 203 204template <class ForwardIterator, class T> 205 constexpr void // constexpr in C++20 206 replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value); 207 208template <class ForwardIterator, class Predicate, class T> 209 constexpr void // constexpr in C++20 210 replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value); 211 212template <class InputIterator, class OutputIterator, class T> 213 constexpr OutputIterator // constexpr in C++20 214 replace_copy(InputIterator first, InputIterator last, OutputIterator result, 215 const T& old_value, const T& new_value); 216 217template <class InputIterator, class OutputIterator, class Predicate, class T> 218 constexpr OutputIterator // constexpr in C++20 219 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value); 220 221template <class ForwardIterator, class T> 222 constexpr void // constexpr in C++20 223 fill(ForwardIterator first, ForwardIterator last, const T& value); 224 225template <class OutputIterator, class Size, class T> 226 constexpr OutputIterator // constexpr in C++20 227 fill_n(OutputIterator first, Size n, const T& value); 228 229template <class ForwardIterator, class Generator> 230 constexpr void // constexpr in C++20 231 generate(ForwardIterator first, ForwardIterator last, Generator gen); 232 233template <class OutputIterator, class Size, class Generator> 234 constexpr OutputIterator // constexpr in C++20 235 generate_n(OutputIterator first, Size n, Generator gen); 236 237template <class ForwardIterator, class T> 238 constexpr ForwardIterator // constexpr in C++20 239 remove(ForwardIterator first, ForwardIterator last, const T& value); 240 241template <class ForwardIterator, class Predicate> 242 constexpr ForwardIterator // constexpr in C++20 243 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred); 244 245template <class InputIterator, class OutputIterator, class T> 246 constexpr OutputIterator // constexpr in C++20 247 remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value); 248 249template <class InputIterator, class OutputIterator, class Predicate> 250 constexpr OutputIterator // constexpr in C++20 251 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred); 252 253template <class ForwardIterator> 254 constexpr ForwardIterator // constexpr in C++20 255 unique(ForwardIterator first, ForwardIterator last); 256 257template <class ForwardIterator, class BinaryPredicate> 258 constexpr ForwardIterator // constexpr in C++20 259 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); 260 261template <class InputIterator, class OutputIterator> 262 constexpr OutputIterator // constexpr in C++20 263 unique_copy(InputIterator first, InputIterator last, OutputIterator result); 264 265template <class InputIterator, class OutputIterator, class BinaryPredicate> 266 constexpr OutputIterator // constexpr in C++20 267 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred); 268 269template <class BidirectionalIterator> 270 constexpr void // constexpr in C++20 271 reverse(BidirectionalIterator first, BidirectionalIterator last); 272 273template <class BidirectionalIterator, class OutputIterator> 274 constexpr OutputIterator // constexpr in C++20 275 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result); 276 277template <class ForwardIterator> 278 constexpr ForwardIterator // constexpr in C++20 279 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); 280 281template <class ForwardIterator, class OutputIterator> 282 constexpr OutputIterator // constexpr in C++20 283 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result); 284 285template <class RandomAccessIterator> 286 void 287 random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17 288 289template <class RandomAccessIterator, class RandomNumberGenerator> 290 void 291 random_shuffle(RandomAccessIterator first, RandomAccessIterator last, 292 RandomNumberGenerator& rand); // deprecated in C++14, removed in C++17 293 294template<class PopulationIterator, class SampleIterator, 295 class Distance, class UniformRandomBitGenerator> 296 SampleIterator sample(PopulationIterator first, PopulationIterator last, 297 SampleIterator out, Distance n, 298 UniformRandomBitGenerator&& g); // C++17 299 300template<class RandomAccessIterator, class UniformRandomNumberGenerator> 301 void shuffle(RandomAccessIterator first, RandomAccessIterator last, 302 UniformRandomNumberGenerator&& g); 303 304template<class ForwardIterator> 305 constexpr ForwardIterator 306 shift_left(ForwardIterator first, ForwardIterator last, 307 typename iterator_traits<ForwardIterator>::difference_type n); // C++20 308 309template<class ForwardIterator> 310 constexpr ForwardIterator 311 shift_right(ForwardIterator first, ForwardIterator last, 312 typename iterator_traits<ForwardIterator>::difference_type n); // C++20 313 314template <class InputIterator, class Predicate> 315 constexpr bool // constexpr in C++20 316 is_partitioned(InputIterator first, InputIterator last, Predicate pred); 317 318template <class ForwardIterator, class Predicate> 319 constexpr ForwardIterator // constexpr in C++20 320 partition(ForwardIterator first, ForwardIterator last, Predicate pred); 321 322template <class InputIterator, class OutputIterator1, 323 class OutputIterator2, class Predicate> 324 constexpr pair<OutputIterator1, OutputIterator2> // constexpr in C++20 325 partition_copy(InputIterator first, InputIterator last, 326 OutputIterator1 out_true, OutputIterator2 out_false, 327 Predicate pred); 328 329template <class ForwardIterator, class Predicate> 330 ForwardIterator 331 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred); 332 333template<class ForwardIterator, class Predicate> 334 constexpr ForwardIterator // constexpr in C++20 335 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred); 336 337template <class ForwardIterator> 338 constexpr bool // constexpr in C++20 339 is_sorted(ForwardIterator first, ForwardIterator last); 340 341template <class ForwardIterator, class Compare> 342 constexpr bool // constexpr in C++20 343 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp); 344 345template<class ForwardIterator> 346 constexpr ForwardIterator // constexpr in C++20 347 is_sorted_until(ForwardIterator first, ForwardIterator last); 348 349template <class ForwardIterator, class Compare> 350 constexpr ForwardIterator // constexpr in C++20 351 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp); 352 353template <class RandomAccessIterator> 354 void 355 sort(RandomAccessIterator first, RandomAccessIterator last); 356 357template <class RandomAccessIterator, class Compare> 358 void 359 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 360 361template <class RandomAccessIterator> 362 void 363 stable_sort(RandomAccessIterator first, RandomAccessIterator last); 364 365template <class RandomAccessIterator, class Compare> 366 void 367 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 368 369template <class RandomAccessIterator> 370 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 // _Compare is known to be a reference type 4051 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4052 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4053 const difference_type __limit = is_trivially_copy_constructible<value_type>::value && 4054 is_trivially_copy_assignable<value_type>::value ? 30 : 6; 4055 while (true) 4056 { 4057 __restart: 4058 difference_type __len = __last - __first; 4059 switch (__len) 4060 { 4061 case 0: 4062 case 1: 4063 return; 4064 case 2: 4065 if (__comp(*--__last, *__first)) 4066 swap(*__first, *__last); 4067 return; 4068 case 3: 4069 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); 4070 return; 4071 case 4: 4072 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); 4073 return; 4074 case 5: 4075 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); 4076 return; 4077 } 4078 if (__len <= __limit) 4079 { 4080 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); 4081 return; 4082 } 4083 // __len > 5 4084 _RandomAccessIterator __m = __first; 4085 _RandomAccessIterator __lm1 = __last; 4086 --__lm1; 4087 unsigned __n_swaps; 4088 { 4089 difference_type __delta; 4090 if (__len >= 1000) 4091 { 4092 __delta = __len/2; 4093 __m += __delta; 4094 __delta /= 2; 4095 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp); 4096 } 4097 else 4098 { 4099 __delta = __len/2; 4100 __m += __delta; 4101 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); 4102 } 4103 } 4104 // *__m is median 4105 // partition [__first, __m) < *__m and *__m <= [__m, __last) 4106 // (this inhibits tossing elements equivalent to __m around unnecessarily) 4107 _RandomAccessIterator __i = __first; 4108 _RandomAccessIterator __j = __lm1; 4109 // j points beyond range to be tested, *__m is known to be <= *__lm1 4110 // The search going up is known to be guarded but the search coming down isn't. 4111 // Prime the downward search with a guard. 4112 if (!__comp(*__i, *__m)) // if *__first == *__m 4113 { 4114 // *__first == *__m, *__first doesn't go in first part 4115 // manually guard downward moving __j against __i 4116 while (true) 4117 { 4118 if (__i == --__j) 4119 { 4120 // *__first == *__m, *__m <= all other elements 4121 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) 4122 ++__i; // __first + 1 4123 __j = __last; 4124 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) 4125 { 4126 while (true) 4127 { 4128 if (__i == __j) 4129 return; // [__first, __last) all equivalent elements 4130 if (__comp(*__first, *__i)) 4131 { 4132 swap(*__i, *__j); 4133 ++__n_swaps; 4134 ++__i; 4135 break; 4136 } 4137 ++__i; 4138 } 4139 } 4140 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 4141 if (__i == __j) 4142 return; 4143 while (true) 4144 { 4145 while (!__comp(*__first, *__i)) 4146 ++__i; 4147 while (__comp(*__first, *--__j)) 4148 ; 4149 if (__i >= __j) 4150 break; 4151 swap(*__i, *__j); 4152 ++__n_swaps; 4153 ++__i; 4154 } 4155 // [__first, __i) == *__first and *__first < [__i, __last) 4156 // The first part is sorted, sort the second part 4157 // _VSTD::__sort<_Compare>(__i, __last, __comp); 4158 __first = __i; 4159 goto __restart; 4160 } 4161 if (__comp(*__j, *__m)) 4162 { 4163 swap(*__i, *__j); 4164 ++__n_swaps; 4165 break; // found guard for downward moving __j, now use unguarded partition 4166 } 4167 } 4168 } 4169 // It is known that *__i < *__m 4170 ++__i; 4171 // j points beyond range to be tested, *__m is known to be <= *__lm1 4172 // if not yet partitioned... 4173 if (__i < __j) 4174 { 4175 // known that *(__i - 1) < *__m 4176 // known that __i <= __m 4177 while (true) 4178 { 4179 // __m still guards upward moving __i 4180 while (__comp(*__i, *__m)) 4181 ++__i; 4182 // It is now known that a guard exists for downward moving __j 4183 while (!__comp(*--__j, *__m)) 4184 ; 4185 if (__i > __j) 4186 break; 4187 swap(*__i, *__j); 4188 ++__n_swaps; 4189 // It is known that __m != __j 4190 // If __m just moved, follow it 4191 if (__m == __i) 4192 __m = __j; 4193 ++__i; 4194 } 4195 } 4196 // [__first, __i) < *__m and *__m <= [__i, __last) 4197 if (__i != __m && __comp(*__m, *__i)) 4198 { 4199 swap(*__i, *__m); 4200 ++__n_swaps; 4201 } 4202 // [__first, __i) < *__i and *__i <= [__i+1, __last) 4203 // If we were given a perfect partition, see if insertion sort is quick... 4204 if (__n_swaps == 0) 4205 { 4206 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); 4207 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp)) 4208 { 4209 if (__fs) 4210 return; 4211 __last = __i; 4212 continue; 4213 } 4214 else 4215 { 4216 if (__fs) 4217 { 4218 __first = ++__i; 4219 continue; 4220 } 4221 } 4222 } 4223 // sort smaller range with recursive call and larger with tail recursion elimination 4224 if (__i - __first < __last - __i) 4225 { 4226 _VSTD::__sort<_Compare>(__first, __i, __comp); 4227 // _VSTD::__sort<_Compare>(__i+1, __last, __comp); 4228 __first = ++__i; 4229 } 4230 else 4231 { 4232 _VSTD::__sort<_Compare>(__i+1, __last, __comp); 4233 // _VSTD::__sort<_Compare>(__first, __i, __comp); 4234 __last = __i; 4235 } 4236 } 4237} 4238 4239// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare 4240template <class _RandomAccessIterator, class _Compare> 4241inline _LIBCPP_INLINE_VISIBILITY 4242void 4243sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4244{ 4245 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4246 _VSTD::__sort<_Comp_ref>(__first, __last, _Comp_ref(__comp)); 4247} 4248 4249template <class _RandomAccessIterator> 4250inline _LIBCPP_INLINE_VISIBILITY 4251void 4252sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 4253{ 4254 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4255} 4256 4257template <class _Tp> 4258inline _LIBCPP_INLINE_VISIBILITY 4259void 4260sort(_Tp** __first, _Tp** __last) 4261{ 4262 _VSTD::sort((uintptr_t*)__first, (uintptr_t*)__last, __less<uintptr_t>()); 4263} 4264 4265template <class _Tp> 4266inline _LIBCPP_INLINE_VISIBILITY 4267void 4268sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last) 4269{ 4270 _VSTD::sort(__first.base(), __last.base()); 4271} 4272 4273template <class _Tp, class _Compare> 4274inline _LIBCPP_INLINE_VISIBILITY 4275void 4276sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp) 4277{ 4278 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4279 _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp); 4280} 4281 4282_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&)) 4283_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) 4284_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) 4285_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) 4286_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&)) 4287_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) 4288_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&)) 4289_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) 4290_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&)) 4291_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) 4292_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) 4293_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>&)) 4294_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&)) 4295_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&)) 4296_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) 4297 4298_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&)) 4299_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) 4300_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) 4301_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) 4302_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&)) 4303_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) 4304_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&)) 4305_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) 4306_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&)) 4307_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) 4308_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) 4309_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>&)) 4310_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&)) 4311_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&)) 4312_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) 4313 4314_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>&)) 4315 4316// lower_bound 4317 4318template <class _Compare, class _ForwardIterator, class _Tp> 4319_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 4320__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4321{ 4322 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 4323 difference_type __len = _VSTD::distance(__first, __last); 4324 while (__len != 0) 4325 { 4326 difference_type __l2 = _VSTD::__half_positive(__len); 4327 _ForwardIterator __m = __first; 4328 _VSTD::advance(__m, __l2); 4329 if (__comp(*__m, __value_)) 4330 { 4331 __first = ++__m; 4332 __len -= __l2 + 1; 4333 } 4334 else 4335 __len = __l2; 4336 } 4337 return __first; 4338} 4339 4340template <class _ForwardIterator, class _Tp, class _Compare> 4341_LIBCPP_NODISCARD_EXT inline 4342_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4343_ForwardIterator 4344lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4345{ 4346 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4347 return _VSTD::__lower_bound<_Comp_ref>(__first, __last, __value_, __comp); 4348} 4349 4350template <class _ForwardIterator, class _Tp> 4351_LIBCPP_NODISCARD_EXT inline 4352_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4353_ForwardIterator 4354lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4355{ 4356 return _VSTD::lower_bound(__first, __last, __value_, 4357 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 4358} 4359 4360// upper_bound 4361 4362template <class _Compare, class _ForwardIterator, class _Tp> 4363_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 4364__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4365{ 4366 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 4367 difference_type __len = _VSTD::distance(__first, __last); 4368 while (__len != 0) 4369 { 4370 difference_type __l2 = _VSTD::__half_positive(__len); 4371 _ForwardIterator __m = __first; 4372 _VSTD::advance(__m, __l2); 4373 if (__comp(__value_, *__m)) 4374 __len = __l2; 4375 else 4376 { 4377 __first = ++__m; 4378 __len -= __l2 + 1; 4379 } 4380 } 4381 return __first; 4382} 4383 4384template <class _ForwardIterator, class _Tp, class _Compare> 4385_LIBCPP_NODISCARD_EXT inline 4386_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4387_ForwardIterator 4388upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4389{ 4390 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4391 return _VSTD::__upper_bound<_Comp_ref>(__first, __last, __value_, __comp); 4392} 4393 4394template <class _ForwardIterator, class _Tp> 4395_LIBCPP_NODISCARD_EXT inline 4396_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4397_ForwardIterator 4398upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4399{ 4400 return _VSTD::upper_bound(__first, __last, __value_, 4401 __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>()); 4402} 4403 4404// equal_range 4405 4406template <class _Compare, class _ForwardIterator, class _Tp> 4407_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator> 4408__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4409{ 4410 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 4411 difference_type __len = _VSTD::distance(__first, __last); 4412 while (__len != 0) 4413 { 4414 difference_type __l2 = _VSTD::__half_positive(__len); 4415 _ForwardIterator __m = __first; 4416 _VSTD::advance(__m, __l2); 4417 if (__comp(*__m, __value_)) 4418 { 4419 __first = ++__m; 4420 __len -= __l2 + 1; 4421 } 4422 else if (__comp(__value_, *__m)) 4423 { 4424 __last = __m; 4425 __len = __l2; 4426 } 4427 else 4428 { 4429 _ForwardIterator __mp1 = __m; 4430 return pair<_ForwardIterator, _ForwardIterator> 4431 ( 4432 _VSTD::__lower_bound<_Compare>(__first, __m, __value_, __comp), 4433 _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value_, __comp) 4434 ); 4435 } 4436 } 4437 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 4438} 4439 4440template <class _ForwardIterator, class _Tp, class _Compare> 4441_LIBCPP_NODISCARD_EXT inline 4442_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4443pair<_ForwardIterator, _ForwardIterator> 4444equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4445{ 4446 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4447 return _VSTD::__equal_range<_Comp_ref>(__first, __last, __value_, __comp); 4448} 4449 4450template <class _ForwardIterator, class _Tp> 4451_LIBCPP_NODISCARD_EXT inline 4452_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4453pair<_ForwardIterator, _ForwardIterator> 4454equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4455{ 4456 return _VSTD::equal_range(__first, __last, __value_, 4457 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 4458} 4459 4460// binary_search 4461 4462template <class _Compare, class _ForwardIterator, class _Tp> 4463inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4464bool 4465__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4466{ 4467 __first = _VSTD::__lower_bound<_Compare>(__first, __last, __value_, __comp); 4468 return __first != __last && !__comp(__value_, *__first); 4469} 4470 4471template <class _ForwardIterator, class _Tp, class _Compare> 4472_LIBCPP_NODISCARD_EXT inline 4473_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4474bool 4475binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4476{ 4477 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4478 return _VSTD::__binary_search<_Comp_ref>(__first, __last, __value_, __comp); 4479} 4480 4481template <class _ForwardIterator, class _Tp> 4482_LIBCPP_NODISCARD_EXT inline 4483_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4484bool 4485binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4486{ 4487 return _VSTD::binary_search(__first, __last, __value_, 4488 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 4489} 4490 4491// merge 4492 4493template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 4494_LIBCPP_CONSTEXPR_AFTER_CXX17 4495_OutputIterator 4496__merge(_InputIterator1 __first1, _InputIterator1 __last1, 4497 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 4498{ 4499 for (; __first1 != __last1; ++__result) 4500 { 4501 if (__first2 == __last2) 4502 return _VSTD::copy(__first1, __last1, __result); 4503 if (__comp(*__first2, *__first1)) 4504 { 4505 *__result = *__first2; 4506 ++__first2; 4507 } 4508 else 4509 { 4510 *__result = *__first1; 4511 ++__first1; 4512 } 4513 } 4514 return _VSTD::copy(__first2, __last2, __result); 4515} 4516 4517template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 4518inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4519_OutputIterator 4520merge(_InputIterator1 __first1, _InputIterator1 __last1, 4521 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 4522{ 4523 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4524 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 4525} 4526 4527template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 4528inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4529_OutputIterator 4530merge(_InputIterator1 __first1, _InputIterator1 __last1, 4531 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 4532{ 4533 typedef typename iterator_traits<_InputIterator1>::value_type __v1; 4534 typedef typename iterator_traits<_InputIterator2>::value_type __v2; 4535 return _VSTD::merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>()); 4536} 4537 4538// inplace_merge 4539 4540template <class _Compare, class _InputIterator1, class _InputIterator2, 4541 class _OutputIterator> 4542void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1, 4543 _InputIterator2 __first2, _InputIterator2 __last2, 4544 _OutputIterator __result, _Compare __comp) 4545{ 4546 for (; __first1 != __last1; ++__result) 4547 { 4548 if (__first2 == __last2) 4549 { 4550 _VSTD::move(__first1, __last1, __result); 4551 return; 4552 } 4553 4554 if (__comp(*__first2, *__first1)) 4555 { 4556 *__result = _VSTD::move(*__first2); 4557 ++__first2; 4558 } 4559 else 4560 { 4561 *__result = _VSTD::move(*__first1); 4562 ++__first1; 4563 } 4564 } 4565 // __first2 through __last2 are already in the right spot. 4566} 4567 4568template <class _Compare, class _BidirectionalIterator> 4569void 4570__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4571 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, 4572 typename iterator_traits<_BidirectionalIterator>::difference_type __len2, 4573 typename iterator_traits<_BidirectionalIterator>::value_type* __buff) 4574{ 4575 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 4576 __destruct_n __d(0); 4577 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); 4578 if (__len1 <= __len2) 4579 { 4580 value_type* __p = __buff; 4581 for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p) 4582 ::new ((void*)__p) value_type(_VSTD::move(*__i)); 4583 _VSTD::__half_inplace_merge<_Compare>(__buff, __p, __middle, __last, __first, __comp); 4584 } 4585 else 4586 { 4587 value_type* __p = __buff; 4588 for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p) 4589 ::new ((void*)__p) value_type(_VSTD::move(*__i)); 4590 typedef reverse_iterator<_BidirectionalIterator> _RBi; 4591 typedef reverse_iterator<value_type*> _Rv; 4592 typedef __invert<_Compare> _Inverted; 4593 _VSTD::__half_inplace_merge<_Inverted>(_Rv(__p), _Rv(__buff), 4594 _RBi(__middle), _RBi(__first), 4595 _RBi(__last), _Inverted(__comp)); 4596 } 4597} 4598 4599template <class _Compare, class _BidirectionalIterator> 4600void 4601__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4602 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, 4603 typename iterator_traits<_BidirectionalIterator>::difference_type __len2, 4604 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size) 4605{ 4606 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 4607 while (true) 4608 { 4609 // if __middle == __last, we're done 4610 if (__len2 == 0) 4611 return; 4612 if (__len1 <= __buff_size || __len2 <= __buff_size) 4613 return _VSTD::__buffered_inplace_merge<_Compare> 4614 (__first, __middle, __last, __comp, __len1, __len2, __buff); 4615 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0 4616 for (; true; ++__first, (void) --__len1) 4617 { 4618 if (__len1 == 0) 4619 return; 4620 if (__comp(*__middle, *__first)) 4621 break; 4622 } 4623 // __first < __middle < __last 4624 // *__first > *__middle 4625 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that 4626 // all elements in: 4627 // [__first, __m1) <= [__middle, __m2) 4628 // [__middle, __m2) < [__m1, __middle) 4629 // [__m1, __middle) <= [__m2, __last) 4630 // and __m1 or __m2 is in the middle of its range 4631 _BidirectionalIterator __m1; // "median" of [__first, __middle) 4632 _BidirectionalIterator __m2; // "median" of [__middle, __last) 4633 difference_type __len11; // distance(__first, __m1) 4634 difference_type __len21; // distance(__middle, __m2) 4635 // binary search smaller range 4636 if (__len1 < __len2) 4637 { // __len >= 1, __len2 >= 2 4638 __len21 = __len2 / 2; 4639 __m2 = __middle; 4640 _VSTD::advance(__m2, __len21); 4641 __m1 = _VSTD::__upper_bound<_Compare>(__first, __middle, *__m2, __comp); 4642 __len11 = _VSTD::distance(__first, __m1); 4643 } 4644 else 4645 { 4646 if (__len1 == 1) 4647 { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1 4648 // It is known *__first > *__middle 4649 swap(*__first, *__middle); 4650 return; 4651 } 4652 // __len1 >= 2, __len2 >= 1 4653 __len11 = __len1 / 2; 4654 __m1 = __first; 4655 _VSTD::advance(__m1, __len11); 4656 __m2 = _VSTD::__lower_bound<_Compare>(__middle, __last, *__m1, __comp); 4657 __len21 = _VSTD::distance(__middle, __m2); 4658 } 4659 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle) 4660 difference_type __len22 = __len2 - __len21; // distance(__m2, __last) 4661 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) 4662 // swap middle two partitions 4663 __middle = _VSTD::rotate(__m1, __middle, __m2); 4664 // __len12 and __len21 now have swapped meanings 4665 // merge smaller range with recursive call and larger with tail recursion elimination 4666 if (__len11 + __len21 < __len12 + __len22) 4667 { 4668 _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); 4669// _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); 4670 __first = __middle; 4671 __middle = __m2; 4672 __len1 = __len12; 4673 __len2 = __len22; 4674 } 4675 else 4676 { 4677 _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); 4678// _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); 4679 __last = __middle; 4680 __middle = __m1; 4681 __len1 = __len11; 4682 __len2 = __len21; 4683 } 4684 } 4685} 4686 4687template <class _BidirectionalIterator, class _Compare> 4688inline _LIBCPP_INLINE_VISIBILITY 4689void 4690inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4691 _Compare __comp) 4692{ 4693 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 4694 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 4695 difference_type __len1 = _VSTD::distance(__first, __middle); 4696 difference_type __len2 = _VSTD::distance(__middle, __last); 4697 difference_type __buf_size = _VSTD::min(__len1, __len2); 4698 pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size); 4699 unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first); 4700 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4701 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2, 4702 __buf.first, __buf.second); 4703} 4704 4705template <class _BidirectionalIterator> 4706inline _LIBCPP_INLINE_VISIBILITY 4707void 4708inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) 4709{ 4710 _VSTD::inplace_merge(__first, __middle, __last, 4711 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 4712} 4713 4714// stable_sort 4715 4716template <class _Compare, class _InputIterator1, class _InputIterator2> 4717void 4718__merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1, 4719 _InputIterator2 __first2, _InputIterator2 __last2, 4720 typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp) 4721{ 4722 typedef typename iterator_traits<_InputIterator1>::value_type value_type; 4723 __destruct_n __d(0); 4724 unique_ptr<value_type, __destruct_n&> __h(__result, __d); 4725 for (; true; ++__result) 4726 { 4727 if (__first1 == __last1) 4728 { 4729 for (; __first2 != __last2; ++__first2, ++__result, (void)__d.template __incr<value_type>()) 4730 ::new ((void*)__result) value_type(_VSTD::move(*__first2)); 4731 __h.release(); 4732 return; 4733 } 4734 if (__first2 == __last2) 4735 { 4736 for (; __first1 != __last1; ++__first1, ++__result, (void)__d.template __incr<value_type>()) 4737 ::new ((void*)__result) value_type(_VSTD::move(*__first1)); 4738 __h.release(); 4739 return; 4740 } 4741 if (__comp(*__first2, *__first1)) 4742 { 4743 ::new ((void*)__result) value_type(_VSTD::move(*__first2)); 4744 __d.template __incr<value_type>(); 4745 ++__first2; 4746 } 4747 else 4748 { 4749 ::new ((void*)__result) value_type(_VSTD::move(*__first1)); 4750 __d.template __incr<value_type>(); 4751 ++__first1; 4752 } 4753 } 4754} 4755 4756template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 4757void 4758__merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1, 4759 _InputIterator2 __first2, _InputIterator2 __last2, 4760 _OutputIterator __result, _Compare __comp) 4761{ 4762 for (; __first1 != __last1; ++__result) 4763 { 4764 if (__first2 == __last2) 4765 { 4766 for (; __first1 != __last1; ++__first1, (void) ++__result) 4767 *__result = _VSTD::move(*__first1); 4768 return; 4769 } 4770 if (__comp(*__first2, *__first1)) 4771 { 4772 *__result = _VSTD::move(*__first2); 4773 ++__first2; 4774 } 4775 else 4776 { 4777 *__result = _VSTD::move(*__first1); 4778 ++__first1; 4779 } 4780 } 4781 for (; __first2 != __last2; ++__first2, (void) ++__result) 4782 *__result = _VSTD::move(*__first2); 4783} 4784 4785template <class _Compare, class _RandomAccessIterator> 4786void 4787__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4788 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4789 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size); 4790 4791template <class _Compare, class _RandomAccessIterator> 4792void 4793__stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp, 4794 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4795 typename iterator_traits<_RandomAccessIterator>::value_type* __first2) 4796{ 4797 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4798 switch (__len) 4799 { 4800 case 0: 4801 return; 4802 case 1: 4803 ::new ((void*)__first2) value_type(_VSTD::move(*__first1)); 4804 return; 4805 case 2: 4806 __destruct_n __d(0); 4807 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d); 4808 if (__comp(*--__last1, *__first1)) 4809 { 4810 ::new ((void*)__first2) value_type(_VSTD::move(*__last1)); 4811 __d.template __incr<value_type>(); 4812 ++__first2; 4813 ::new ((void*)__first2) value_type(_VSTD::move(*__first1)); 4814 } 4815 else 4816 { 4817 ::new ((void*)__first2) value_type(_VSTD::move(*__first1)); 4818 __d.template __incr<value_type>(); 4819 ++__first2; 4820 ::new ((void*)__first2) value_type(_VSTD::move(*__last1)); 4821 } 4822 __h2.release(); 4823 return; 4824 } 4825 if (__len <= 8) 4826 { 4827 _VSTD::__insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp); 4828 return; 4829 } 4830 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; 4831 _RandomAccessIterator __m = __first1 + __l2; 4832 _VSTD::__stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2); 4833 _VSTD::__stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2); 4834 _VSTD::__merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp); 4835} 4836 4837template <class _Tp> 4838struct __stable_sort_switch 4839{ 4840 static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value; 4841}; 4842 4843template <class _Compare, class _RandomAccessIterator> 4844void 4845__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4846 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4847 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size) 4848{ 4849 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4850 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4851 switch (__len) 4852 { 4853 case 0: 4854 case 1: 4855 return; 4856 case 2: 4857 if (__comp(*--__last, *__first)) 4858 swap(*__first, *__last); 4859 return; 4860 } 4861 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value)) 4862 { 4863 _VSTD::__insertion_sort<_Compare>(__first, __last, __comp); 4864 return; 4865 } 4866 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; 4867 _RandomAccessIterator __m = __first + __l2; 4868 if (__len <= __buff_size) 4869 { 4870 __destruct_n __d(0); 4871 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); 4872 _VSTD::__stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff); 4873 __d.__set(__l2, (value_type*)nullptr); 4874 _VSTD::__stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2); 4875 __d.__set(__len, (value_type*)nullptr); 4876 _VSTD::__merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp); 4877// _VSTD::__merge<_Compare>(move_iterator<value_type*>(__buff), 4878// move_iterator<value_type*>(__buff + __l2), 4879// move_iterator<_RandomAccessIterator>(__buff + __l2), 4880// move_iterator<_RandomAccessIterator>(__buff + __len), 4881// __first, __comp); 4882 return; 4883 } 4884 _VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size); 4885 _VSTD::__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); 4886 _VSTD::__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); 4887} 4888 4889template <class _RandomAccessIterator, class _Compare> 4890inline _LIBCPP_INLINE_VISIBILITY 4891void 4892stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4893{ 4894 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4895 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4896 difference_type __len = __last - __first; 4897 pair<value_type*, ptrdiff_t> __buf(0, 0); 4898 unique_ptr<value_type, __return_temporary_buffer> __h; 4899 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) 4900 { 4901 __buf = _VSTD::get_temporary_buffer<value_type>(__len); 4902 __h.reset(__buf.first); 4903 } 4904 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4905 _VSTD::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); 4906} 4907 4908template <class _RandomAccessIterator> 4909inline _LIBCPP_INLINE_VISIBILITY 4910void 4911stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 4912{ 4913 _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4914} 4915 4916// is_heap_until 4917 4918template <class _RandomAccessIterator, class _Compare> 4919_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator 4920is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4921{ 4922 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4923 difference_type __len = __last - __first; 4924 difference_type __p = 0; 4925 difference_type __c = 1; 4926 _RandomAccessIterator __pp = __first; 4927 while (__c < __len) 4928 { 4929 _RandomAccessIterator __cp = __first + __c; 4930 if (__comp(*__pp, *__cp)) 4931 return __cp; 4932 ++__c; 4933 ++__cp; 4934 if (__c == __len) 4935 return __last; 4936 if (__comp(*__pp, *__cp)) 4937 return __cp; 4938 ++__p; 4939 ++__pp; 4940 __c = 2 * __p + 1; 4941 } 4942 return __last; 4943} 4944 4945template<class _RandomAccessIterator> 4946_LIBCPP_NODISCARD_EXT inline 4947_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4948_RandomAccessIterator 4949is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) 4950{ 4951 return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4952} 4953 4954// is_heap 4955 4956template <class _RandomAccessIterator, class _Compare> 4957_LIBCPP_NODISCARD_EXT inline 4958_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4959bool 4960is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4961{ 4962 return _VSTD::is_heap_until(__first, __last, __comp) == __last; 4963} 4964 4965template<class _RandomAccessIterator> 4966_LIBCPP_NODISCARD_EXT inline 4967_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4968bool 4969is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 4970{ 4971 return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4972} 4973 4974// push_heap 4975 4976template <class _Compare, class _RandomAccessIterator> 4977_LIBCPP_CONSTEXPR_AFTER_CXX11 void 4978__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4979 typename iterator_traits<_RandomAccessIterator>::difference_type __len) 4980{ 4981 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4982 if (__len > 1) 4983 { 4984 __len = (__len - 2) / 2; 4985 _RandomAccessIterator __ptr = __first + __len; 4986 if (__comp(*__ptr, *--__last)) 4987 { 4988 value_type __t(_VSTD::move(*__last)); 4989 do 4990 { 4991 *__last = _VSTD::move(*__ptr); 4992 __last = __ptr; 4993 if (__len == 0) 4994 break; 4995 __len = (__len - 1) / 2; 4996 __ptr = __first + __len; 4997 } while (__comp(*__ptr, __t)); 4998 *__last = _VSTD::move(__t); 4999 } 5000 } 5001} 5002 5003template <class _RandomAccessIterator, class _Compare> 5004inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5005void 5006push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5007{ 5008 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5009 _VSTD::__sift_up<_Comp_ref>(__first, __last, __comp, __last - __first); 5010} 5011 5012template <class _RandomAccessIterator> 5013inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5014void 5015push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 5016{ 5017 _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5018} 5019 5020// pop_heap 5021 5022template <class _Compare, class _RandomAccessIterator> 5023_LIBCPP_CONSTEXPR_AFTER_CXX11 void 5024__sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/, 5025 _Compare __comp, 5026 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 5027 _RandomAccessIterator __start) 5028{ 5029 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 5030 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 5031 // left-child of __start is at 2 * __start + 1 5032 // right-child of __start is at 2 * __start + 2 5033 difference_type __child = __start - __first; 5034 5035 if (__len < 2 || (__len - 2) / 2 < __child) 5036 return; 5037 5038 __child = 2 * __child + 1; 5039 _RandomAccessIterator __child_i = __first + __child; 5040 5041 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { 5042 // right-child exists and is greater than left-child 5043 ++__child_i; 5044 ++__child; 5045 } 5046 5047 // check if we are in heap-order 5048 if (__comp(*__child_i, *__start)) 5049 // we are, __start is larger than it's largest child 5050 return; 5051 5052 value_type __top(_VSTD::move(*__start)); 5053 do 5054 { 5055 // we are not in heap-order, swap the parent with its largest child 5056 *__start = _VSTD::move(*__child_i); 5057 __start = __child_i; 5058 5059 if ((__len - 2) / 2 < __child) 5060 break; 5061 5062 // recompute the child based off of the updated parent 5063 __child = 2 * __child + 1; 5064 __child_i = __first + __child; 5065 5066 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { 5067 // right-child exists and is greater than left-child 5068 ++__child_i; 5069 ++__child; 5070 } 5071 5072 // check if we are in heap-order 5073 } while (!__comp(*__child_i, __top)); 5074 *__start = _VSTD::move(__top); 5075} 5076 5077template <class _Compare, class _RandomAccessIterator> 5078inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5079void 5080__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 5081 typename iterator_traits<_RandomAccessIterator>::difference_type __len) 5082{ 5083 if (__len > 1) 5084 { 5085 swap(*__first, *--__last); 5086 _VSTD::__sift_down<_Compare>(__first, __last, __comp, __len - 1, __first); 5087 } 5088} 5089 5090template <class _RandomAccessIterator, class _Compare> 5091inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5092void 5093pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5094{ 5095 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5096 _VSTD::__pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first); 5097} 5098 5099template <class _RandomAccessIterator> 5100inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5101void 5102pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 5103{ 5104 _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5105} 5106 5107// make_heap 5108 5109template <class _Compare, class _RandomAccessIterator> 5110_LIBCPP_CONSTEXPR_AFTER_CXX11 void 5111__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5112{ 5113 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 5114 difference_type __n = __last - __first; 5115 if (__n > 1) 5116 { 5117 // start from the first parent, there is no need to consider children 5118 for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) 5119 { 5120 _VSTD::__sift_down<_Compare>(__first, __last, __comp, __n, __first + __start); 5121 } 5122 } 5123} 5124 5125template <class _RandomAccessIterator, class _Compare> 5126inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5127void 5128make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5129{ 5130 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5131 _VSTD::__make_heap<_Comp_ref>(__first, __last, __comp); 5132} 5133 5134template <class _RandomAccessIterator> 5135inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5136void 5137make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 5138{ 5139 _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5140} 5141 5142// sort_heap 5143 5144template <class _Compare, class _RandomAccessIterator> 5145_LIBCPP_CONSTEXPR_AFTER_CXX17 void 5146__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5147{ 5148 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 5149 for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n) 5150 _VSTD::__pop_heap<_Compare>(__first, __last, __comp, __n); 5151} 5152 5153template <class _RandomAccessIterator, class _Compare> 5154inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5155void 5156sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5157{ 5158 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5159 _VSTD::__sort_heap<_Comp_ref>(__first, __last, __comp); 5160} 5161 5162template <class _RandomAccessIterator> 5163inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5164void 5165sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 5166{ 5167 _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5168} 5169 5170// partial_sort 5171 5172template <class _Compare, class _RandomAccessIterator> 5173_LIBCPP_CONSTEXPR_AFTER_CXX17 void 5174__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, 5175 _Compare __comp) 5176{ 5177 _VSTD::__make_heap<_Compare>(__first, __middle, __comp); 5178 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first; 5179 for (_RandomAccessIterator __i = __middle; __i != __last; ++__i) 5180 { 5181 if (__comp(*__i, *__first)) 5182 { 5183 swap(*__i, *__first); 5184 _VSTD::__sift_down<_Compare>(__first, __middle, __comp, __len, __first); 5185 } 5186 } 5187 _VSTD::__sort_heap<_Compare>(__first, __middle, __comp); 5188} 5189 5190template <class _RandomAccessIterator, class _Compare> 5191inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5192void 5193partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, 5194 _Compare __comp) 5195{ 5196 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5197 _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp); 5198} 5199 5200template <class _RandomAccessIterator> 5201inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5202void 5203partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) 5204{ 5205 _VSTD::partial_sort(__first, __middle, __last, 5206 __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5207} 5208 5209// partial_sort_copy 5210 5211template <class _Compare, class _InputIterator, class _RandomAccessIterator> 5212_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator 5213__partial_sort_copy(_InputIterator __first, _InputIterator __last, 5214 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) 5215{ 5216 _RandomAccessIterator __r = __result_first; 5217 if (__r != __result_last) 5218 { 5219 for (; __first != __last && __r != __result_last; ++__first, (void) ++__r) 5220 *__r = *__first; 5221 _VSTD::__make_heap<_Compare>(__result_first, __r, __comp); 5222 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first; 5223 for (; __first != __last; ++__first) 5224 if (__comp(*__first, *__result_first)) 5225 { 5226 *__result_first = *__first; 5227 _VSTD::__sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first); 5228 } 5229 _VSTD::__sort_heap<_Compare>(__result_first, __r, __comp); 5230 } 5231 return __r; 5232} 5233 5234template <class _InputIterator, class _RandomAccessIterator, class _Compare> 5235inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5236_RandomAccessIterator 5237partial_sort_copy(_InputIterator __first, _InputIterator __last, 5238 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) 5239{ 5240 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5241 return _VSTD::__partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp); 5242} 5243 5244template <class _InputIterator, class _RandomAccessIterator> 5245inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5246_RandomAccessIterator 5247partial_sort_copy(_InputIterator __first, _InputIterator __last, 5248 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last) 5249{ 5250 return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last, 5251 __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5252} 5253 5254// nth_element 5255 5256template<class _Compare, class _RandomAccessIterator> 5257_LIBCPP_CONSTEXPR_AFTER_CXX11 bool 5258__nth_element_find_guard(_RandomAccessIterator& __i, _RandomAccessIterator& __j, 5259 _RandomAccessIterator& __m, _Compare __comp) 5260{ 5261 // manually guard downward moving __j against __i 5262 while (--__j != __i) 5263 { 5264 if (__comp(*__j, *__m)) 5265 { 5266 return true; 5267 } 5268 } 5269 return false; 5270} 5271 5272template<class _Compare, class _RandomAccessIterator> 5273_LIBCPP_CONSTEXPR_AFTER_CXX11 bool 5274__nth_element_partloop(_RandomAccessIterator __first, _RandomAccessIterator __last, 5275 _RandomAccessIterator& __i, _RandomAccessIterator& __j, 5276 unsigned& __n_swaps, _Compare __comp) 5277{ 5278 // *__first == *__m, *__m <= all other elements 5279 // Partition instead into [__first, __i) == *__first and *__first < [__i, __last) 5280 ++__i; // __first + 1 5281 __j = __last; 5282 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) 5283 { 5284 while (true) 5285 { 5286 if (__i == __j) 5287 return true; // [__first, __last) all equivalent elements 5288 if (__comp(*__first, *__i)) 5289 { 5290 swap(*__i, *__j); 5291 ++__n_swaps; 5292 ++__i; 5293 break; 5294 } 5295 ++__i; 5296 } 5297 } 5298 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 5299 if (__i == __j) 5300 return true; 5301 while (true) 5302 { 5303 while (!__comp(*__first, *__i)) 5304 ++__i; 5305 while (__comp(*__first, *--__j)) 5306 ; 5307 if (__i >= __j) 5308 break; 5309 swap(*__i, *__j); 5310 ++__n_swaps; 5311 ++__i; 5312 } 5313 // [__first, __i) == *__first and *__first < [__i, __last) 5314 // The first part is sorted. 5315 return false; 5316} 5317 5318template <class _Compare, class _RandomAccessIterator> 5319_LIBCPP_CONSTEXPR_AFTER_CXX11 void 5320__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) 5321{ 5322 // _Compare is known to be a reference type 5323 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 5324 const difference_type __limit = 7; 5325 while (true) 5326 { 5327 // __restart: -- this is the target of a "continue" below 5328 if (__nth == __last) 5329 return; 5330 difference_type __len = __last - __first; 5331 switch (__len) 5332 { 5333 case 0: 5334 case 1: 5335 return; 5336 case 2: 5337 if (__comp(*--__last, *__first)) 5338 swap(*__first, *__last); 5339 return; 5340 case 3: 5341 { 5342 _RandomAccessIterator __m = __first; 5343 _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp); 5344 return; 5345 } 5346 } 5347 if (__len <= __limit) 5348 { 5349 _VSTD::__selection_sort<_Compare>(__first, __last, __comp); 5350 return; 5351 } 5352 // __len > __limit >= 3 5353 _RandomAccessIterator __m = __first + __len/2; 5354 _RandomAccessIterator __lm1 = __last; 5355 unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp); 5356 // *__m is median 5357 // partition [__first, __m) < *__m and *__m <= [__m, __last) 5358 // (this inhibits tossing elements equivalent to __m around unnecessarily) 5359 _RandomAccessIterator __i = __first; 5360 _RandomAccessIterator __j = __lm1; 5361 // j points beyond range to be tested, *__lm1 is known to be <= *__m 5362 // The search going up is known to be guarded but the search coming down isn't. 5363 // Prime the downward search with a guard. 5364 if (!__comp(*__i, *__m)) // if *__first == *__m 5365 { 5366 // *__first == *__m, *__first doesn't go in first part 5367 if (_VSTD::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) { 5368 swap(*__i, *__j); 5369 ++__n_swaps; 5370 // found guard for downward moving __j, now use unguarded partition 5371 } else if (_VSTD::__nth_element_partloop<_Compare>(__first, __last, __i, __j, __n_swaps, __comp)) { 5372 return; 5373 } else if (__nth < __i) { 5374 return; 5375 } else { 5376 // __nth_element the second part 5377 // _VSTD::__nth_element<_Compare>(__i, __nth, __last, __comp); 5378 __first = __i; 5379 continue; // i.e., goto __restart 5380 } 5381 } 5382 ++__i; 5383 // j points beyond range to be tested, *__lm1 is known to be <= *__m 5384 // if not yet partitioned... 5385 if (__i < __j) 5386 { 5387 // known that *(__i - 1) < *__m 5388 while (true) 5389 { 5390 // __m still guards upward moving __i 5391 while (__comp(*__i, *__m)) 5392 ++__i; 5393 // It is now known that a guard exists for downward moving __j 5394 while (!__comp(*--__j, *__m)) 5395 ; 5396 if (__i >= __j) 5397 break; 5398 swap(*__i, *__j); 5399 ++__n_swaps; 5400 // It is known that __m != __j 5401 // If __m just moved, follow it 5402 if (__m == __i) 5403 __m = __j; 5404 ++__i; 5405 } 5406 } 5407 // [__first, __i) < *__m and *__m <= [__i, __last) 5408 if (__i != __m && __comp(*__m, *__i)) 5409 { 5410 swap(*__i, *__m); 5411 ++__n_swaps; 5412 } 5413 // [__first, __i) < *__i and *__i <= [__i+1, __last) 5414 if (__nth == __i) 5415 return; 5416 if (__n_swaps == 0) 5417 { 5418 // We were given a perfectly partitioned sequence. Coincidence? 5419 if (__nth < __i) 5420 { 5421 // Check for [__first, __i) already sorted 5422 __j = __m = __first; 5423 while (true) 5424 { 5425 if (++__j == __i) 5426 // [__first, __i) sorted 5427 return; 5428 if (__comp(*__j, *__m)) 5429 // not yet sorted, so sort 5430 break; 5431 __m = __j; 5432 } 5433 } 5434 else 5435 { 5436 // Check for [__i, __last) already sorted 5437 __j = __m = __i; 5438 while (++__j != __last) 5439 { 5440 if (++__j == __last) 5441 // [__i, __last) sorted 5442 return; 5443 if (__comp(*__j, *__m)) 5444 // not yet sorted, so sort 5445 break; 5446 __m = __j; 5447 } 5448 } 5449 } 5450 // __nth_element on range containing __nth 5451 if (__nth < __i) 5452 { 5453 // _VSTD::__nth_element<_Compare>(__first, __nth, __i, __comp); 5454 __last = __i; 5455 } 5456 else 5457 { 5458 // _VSTD::__nth_element<_Compare>(__i+1, __nth, __last, __comp); 5459 __first = ++__i; 5460 } 5461 } 5462} 5463 5464template <class _RandomAccessIterator, class _Compare> 5465inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5466void 5467nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) 5468{ 5469 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5470 _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp); 5471} 5472 5473template <class _RandomAccessIterator> 5474inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5475void 5476nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) 5477{ 5478 _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5479} 5480 5481// includes 5482 5483template <class _Compare, class _InputIterator1, class _InputIterator2> 5484_LIBCPP_CONSTEXPR_AFTER_CXX17 bool 5485__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, 5486 _Compare __comp) 5487{ 5488 for (; __first2 != __last2; ++__first1) 5489 { 5490 if (__first1 == __last1 || __comp(*__first2, *__first1)) 5491 return false; 5492 if (!__comp(*__first1, *__first2)) 5493 ++__first2; 5494 } 5495 return true; 5496} 5497 5498template <class _InputIterator1, class _InputIterator2, class _Compare> 5499_LIBCPP_NODISCARD_EXT inline 5500_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5501bool 5502includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, 5503 _Compare __comp) 5504{ 5505 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5506 return _VSTD::__includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); 5507} 5508 5509template <class _InputIterator1, class _InputIterator2> 5510_LIBCPP_NODISCARD_EXT inline 5511_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5512bool 5513includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) 5514{ 5515 return _VSTD::includes(__first1, __last1, __first2, __last2, 5516 __less<typename iterator_traits<_InputIterator1>::value_type, 5517 typename iterator_traits<_InputIterator2>::value_type>()); 5518} 5519 5520// set_union 5521 5522template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5523_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 5524__set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5525 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5526{ 5527 for (; __first1 != __last1; ++__result) 5528 { 5529 if (__first2 == __last2) 5530 return _VSTD::copy(__first1, __last1, __result); 5531 if (__comp(*__first2, *__first1)) 5532 { 5533 *__result = *__first2; 5534 ++__first2; 5535 } 5536 else 5537 { 5538 if (!__comp(*__first1, *__first2)) 5539 ++__first2; 5540 *__result = *__first1; 5541 ++__first1; 5542 } 5543 } 5544 return _VSTD::copy(__first2, __last2, __result); 5545} 5546 5547template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5548inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5549_OutputIterator 5550set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5551 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5552{ 5553 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5554 return _VSTD::__set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5555} 5556 5557template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5558inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5559_OutputIterator 5560set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5561 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5562{ 5563 return _VSTD::set_union(__first1, __last1, __first2, __last2, __result, 5564 __less<typename iterator_traits<_InputIterator1>::value_type, 5565 typename iterator_traits<_InputIterator2>::value_type>()); 5566} 5567 5568// set_intersection 5569 5570template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5571_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 5572__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5573 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5574{ 5575 while (__first1 != __last1 && __first2 != __last2) 5576 { 5577 if (__comp(*__first1, *__first2)) 5578 ++__first1; 5579 else 5580 { 5581 if (!__comp(*__first2, *__first1)) 5582 { 5583 *__result = *__first1; 5584 ++__result; 5585 ++__first1; 5586 } 5587 ++__first2; 5588 } 5589 } 5590 return __result; 5591} 5592 5593template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5594inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5595_OutputIterator 5596set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5597 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5598{ 5599 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5600 return _VSTD::__set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5601} 5602 5603template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5604inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5605_OutputIterator 5606set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5607 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5608{ 5609 return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result, 5610 __less<typename iterator_traits<_InputIterator1>::value_type, 5611 typename iterator_traits<_InputIterator2>::value_type>()); 5612} 5613 5614// set_difference 5615 5616template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5617_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 5618__set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5619 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5620{ 5621 while (__first1 != __last1) 5622 { 5623 if (__first2 == __last2) 5624 return _VSTD::copy(__first1, __last1, __result); 5625 if (__comp(*__first1, *__first2)) 5626 { 5627 *__result = *__first1; 5628 ++__result; 5629 ++__first1; 5630 } 5631 else 5632 { 5633 if (!__comp(*__first2, *__first1)) 5634 ++__first1; 5635 ++__first2; 5636 } 5637 } 5638 return __result; 5639} 5640 5641template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5642inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5643_OutputIterator 5644set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5645 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5646{ 5647 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5648 return _VSTD::__set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5649} 5650 5651template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5652inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5653_OutputIterator 5654set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5655 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5656{ 5657 return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result, 5658 __less<typename iterator_traits<_InputIterator1>::value_type, 5659 typename iterator_traits<_InputIterator2>::value_type>()); 5660} 5661 5662// set_symmetric_difference 5663 5664template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5665_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 5666__set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5667 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5668{ 5669 while (__first1 != __last1) 5670 { 5671 if (__first2 == __last2) 5672 return _VSTD::copy(__first1, __last1, __result); 5673 if (__comp(*__first1, *__first2)) 5674 { 5675 *__result = *__first1; 5676 ++__result; 5677 ++__first1; 5678 } 5679 else 5680 { 5681 if (__comp(*__first2, *__first1)) 5682 { 5683 *__result = *__first2; 5684 ++__result; 5685 } 5686 else 5687 ++__first1; 5688 ++__first2; 5689 } 5690 } 5691 return _VSTD::copy(__first2, __last2, __result); 5692} 5693 5694template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5695inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5696_OutputIterator 5697set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5698 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5699{ 5700 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5701 return _VSTD::__set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5702} 5703 5704template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5705inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5706_OutputIterator 5707set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5708 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5709{ 5710 return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, 5711 __less<typename iterator_traits<_InputIterator1>::value_type, 5712 typename iterator_traits<_InputIterator2>::value_type>()); 5713} 5714 5715// lexicographical_compare 5716 5717template <class _Compare, class _InputIterator1, class _InputIterator2> 5718_LIBCPP_CONSTEXPR_AFTER_CXX17 bool 5719__lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5720 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) 5721{ 5722 for (; __first2 != __last2; ++__first1, (void) ++__first2) 5723 { 5724 if (__first1 == __last1 || __comp(*__first1, *__first2)) 5725 return true; 5726 if (__comp(*__first2, *__first1)) 5727 return false; 5728 } 5729 return false; 5730} 5731 5732template <class _InputIterator1, class _InputIterator2, class _Compare> 5733_LIBCPP_NODISCARD_EXT inline 5734_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5735bool 5736lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5737 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) 5738{ 5739 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5740 return _VSTD::__lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); 5741} 5742 5743template <class _InputIterator1, class _InputIterator2> 5744_LIBCPP_NODISCARD_EXT inline 5745_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5746bool 5747lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5748 _InputIterator2 __first2, _InputIterator2 __last2) 5749{ 5750 return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2, 5751 __less<typename iterator_traits<_InputIterator1>::value_type, 5752 typename iterator_traits<_InputIterator2>::value_type>()); 5753} 5754 5755// next_permutation 5756 5757template <class _Compare, class _BidirectionalIterator> 5758_LIBCPP_CONSTEXPR_AFTER_CXX17 bool 5759__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5760{ 5761 _BidirectionalIterator __i = __last; 5762 if (__first == __last || __first == --__i) 5763 return false; 5764 while (true) 5765 { 5766 _BidirectionalIterator __ip1 = __i; 5767 if (__comp(*--__i, *__ip1)) 5768 { 5769 _BidirectionalIterator __j = __last; 5770 while (!__comp(*__i, *--__j)) 5771 ; 5772 swap(*__i, *__j); 5773 _VSTD::reverse(__ip1, __last); 5774 return true; 5775 } 5776 if (__i == __first) 5777 { 5778 _VSTD::reverse(__first, __last); 5779 return false; 5780 } 5781 } 5782} 5783 5784template <class _BidirectionalIterator, class _Compare> 5785inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5786bool 5787next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5788{ 5789 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5790 return _VSTD::__next_permutation<_Comp_ref>(__first, __last, __comp); 5791} 5792 5793template <class _BidirectionalIterator> 5794inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5795bool 5796next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) 5797{ 5798 return _VSTD::next_permutation(__first, __last, 5799 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 5800} 5801 5802// prev_permutation 5803 5804template <class _Compare, class _BidirectionalIterator> 5805_LIBCPP_CONSTEXPR_AFTER_CXX17 bool 5806__prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5807{ 5808 _BidirectionalIterator __i = __last; 5809 if (__first == __last || __first == --__i) 5810 return false; 5811 while (true) 5812 { 5813 _BidirectionalIterator __ip1 = __i; 5814 if (__comp(*__ip1, *--__i)) 5815 { 5816 _BidirectionalIterator __j = __last; 5817 while (!__comp(*--__j, *__i)) 5818 ; 5819 swap(*__i, *__j); 5820 _VSTD::reverse(__ip1, __last); 5821 return true; 5822 } 5823 if (__i == __first) 5824 { 5825 _VSTD::reverse(__first, __last); 5826 return false; 5827 } 5828 } 5829} 5830 5831template <class _BidirectionalIterator, class _Compare> 5832inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5833bool 5834prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5835{ 5836 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5837 return _VSTD::__prev_permutation<_Comp_ref>(__first, __last, __comp); 5838} 5839 5840template <class _BidirectionalIterator> 5841inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5842bool 5843prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) 5844{ 5845 return _VSTD::prev_permutation(__first, __last, 5846 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 5847} 5848 5849_LIBCPP_END_NAMESPACE_STD 5850 5851_LIBCPP_POP_MACROS 5852 5853#if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17 5854# include <__pstl_algorithm> 5855#endif 5856 5857#endif // _LIBCPP_ALGORITHM 5858