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 18 namespace std 19 { 20 21 template <class InputIterator, class Predicate> 22 constexpr bool // constexpr in C++20 23 all_of(InputIterator first, InputIterator last, Predicate pred); 24 25 template <class InputIterator, class Predicate> 26 constexpr bool // constexpr in C++20 27 any_of(InputIterator first, InputIterator last, Predicate pred); 28 29 template <class InputIterator, class Predicate> 30 constexpr bool // constexpr in C++20 31 none_of(InputIterator first, InputIterator last, Predicate pred); 32 33 template <class InputIterator, class Function> 34 constexpr Function // constexpr in C++20 35 for_each(InputIterator first, InputIterator last, Function f); 36 37 template<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 41 template <class InputIterator, class T> 42 constexpr InputIterator // constexpr in C++20 43 find(InputIterator first, InputIterator last, const T& value); 44 45 template <class InputIterator, class Predicate> 46 constexpr InputIterator // constexpr in C++20 47 find_if(InputIterator first, InputIterator last, Predicate pred); 48 49 template<class InputIterator, class Predicate> 50 constexpr InputIterator // constexpr in C++20 51 find_if_not(InputIterator first, InputIterator last, Predicate pred); 52 53 template <class ForwardIterator1, class ForwardIterator2> 54 constexpr ForwardIterator1 // constexpr in C++20 55 find_end(ForwardIterator1 first1, ForwardIterator1 last1, 56 ForwardIterator2 first2, ForwardIterator2 last2); 57 58 template <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 63 template <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 68 template <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 73 template <class ForwardIterator> 74 constexpr ForwardIterator // constexpr in C++20 75 adjacent_find(ForwardIterator first, ForwardIterator last); 76 77 template <class ForwardIterator, class BinaryPredicate> 78 constexpr ForwardIterator // constexpr in C++20 79 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); 80 81 template <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 85 template <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 89 template <class InputIterator1, class InputIterator2> 90 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 91 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); 92 93 template <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 98 template <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 103 template <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 109 template <class InputIterator1, class InputIterator2> 110 constexpr bool // constexpr in C++20 111 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); 112 113 template <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 118 template <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 123 template <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 129 template<class ForwardIterator1, class ForwardIterator2> 130 constexpr bool // constexpr in C++20 131 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 132 ForwardIterator2 first2); 133 134 template<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 139 template<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 144 template<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 150 template <class ForwardIterator1, class ForwardIterator2> 151 constexpr ForwardIterator1 // constexpr in C++20 152 search(ForwardIterator1 first1, ForwardIterator1 last1, 153 ForwardIterator2 first2, ForwardIterator2 last2); 154 155 template <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 160 template <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 164 template <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 169 template <class InputIterator, class OutputIterator> 170 constexpr OutputIterator // constexpr in C++20 171 copy(InputIterator first, InputIterator last, OutputIterator result); 172 173 template<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 178 template<class InputIterator, class Size, class OutputIterator> 179 constexpr OutputIterator // constexpr in C++20 180 copy_n(InputIterator first, Size n, OutputIterator result); 181 182 template <class BidirectionalIterator1, class BidirectionalIterator2> 183 constexpr BidirectionalIterator2 // constexpr in C++20 184 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, 185 BidirectionalIterator2 result); 186 187 template <class ForwardIterator1, class ForwardIterator2> 188 constexpr ForwardIterator2 // constexpr in C++20 189 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); 190 191 template <class ForwardIterator1, class ForwardIterator2> 192 constexpr void // constexpr in C++20 193 iter_swap(ForwardIterator1 a, ForwardIterator2 b); 194 195 template <class InputIterator, class OutputIterator, class UnaryOperation> 196 constexpr OutputIterator // constexpr in C++20 197 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op); 198 199 template <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 204 template <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 208 template <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 212 template <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 217 template <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 221 template <class ForwardIterator, class T> 222 constexpr void // constexpr in C++20 223 fill(ForwardIterator first, ForwardIterator last, const T& value); 224 225 template <class OutputIterator, class Size, class T> 226 constexpr OutputIterator // constexpr in C++20 227 fill_n(OutputIterator first, Size n, const T& value); 228 229 template <class ForwardIterator, class Generator> 230 constexpr void // constexpr in C++20 231 generate(ForwardIterator first, ForwardIterator last, Generator gen); 232 233 template <class OutputIterator, class Size, class Generator> 234 constexpr OutputIterator // constexpr in C++20 235 generate_n(OutputIterator first, Size n, Generator gen); 236 237 template <class ForwardIterator, class T> 238 constexpr ForwardIterator // constexpr in C++20 239 remove(ForwardIterator first, ForwardIterator last, const T& value); 240 241 template <class ForwardIterator, class Predicate> 242 constexpr ForwardIterator // constexpr in C++20 243 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred); 244 245 template <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 249 template <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 253 template <class ForwardIterator> 254 constexpr ForwardIterator // constexpr in C++20 255 unique(ForwardIterator first, ForwardIterator last); 256 257 template <class ForwardIterator, class BinaryPredicate> 258 constexpr ForwardIterator // constexpr in C++20 259 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); 260 261 template <class InputIterator, class OutputIterator> 262 constexpr OutputIterator // constexpr in C++20 263 unique_copy(InputIterator first, InputIterator last, OutputIterator result); 264 265 template <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 269 template <class BidirectionalIterator> 270 constexpr void // constexpr in C++20 271 reverse(BidirectionalIterator first, BidirectionalIterator last); 272 273 template <class BidirectionalIterator, class OutputIterator> 274 constexpr OutputIterator // constexpr in C++20 275 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result); 276 277 template <class ForwardIterator> 278 constexpr ForwardIterator // constexpr in C++20 279 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); 280 281 template <class ForwardIterator, class OutputIterator> 282 constexpr OutputIterator // constexpr in C++20 283 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result); 284 285 template <class RandomAccessIterator> 286 void 287 random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17 288 289 template <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 294 template<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 300 template<class RandomAccessIterator, class UniformRandomNumberGenerator> 301 void shuffle(RandomAccessIterator first, RandomAccessIterator last, 302 UniformRandomNumberGenerator&& g); 303 304 template<class ForwardIterator> 305 constexpr ForwardIterator 306 shift_left(ForwardIterator first, ForwardIterator last, 307 typename iterator_traits<ForwardIterator>::difference_type n); // C++20 308 309 template<class ForwardIterator> 310 constexpr ForwardIterator 311 shift_right(ForwardIterator first, ForwardIterator last, 312 typename iterator_traits<ForwardIterator>::difference_type n); // C++20 313 314 template <class InputIterator, class Predicate> 315 constexpr bool // constexpr in C++20 316 is_partitioned(InputIterator first, InputIterator last, Predicate pred); 317 318 template <class ForwardIterator, class Predicate> 319 constexpr ForwardIterator // constexpr in C++20 320 partition(ForwardIterator first, ForwardIterator last, Predicate pred); 321 322 template <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 329 template <class ForwardIterator, class Predicate> 330 ForwardIterator 331 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred); 332 333 template<class ForwardIterator, class Predicate> 334 constexpr ForwardIterator // constexpr in C++20 335 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred); 336 337 template <class ForwardIterator> 338 constexpr bool // constexpr in C++20 339 is_sorted(ForwardIterator first, ForwardIterator last); 340 341 template <class ForwardIterator, class Compare> 342 constexpr bool // constexpr in C++20 343 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp); 344 345 template<class ForwardIterator> 346 constexpr ForwardIterator // constexpr in C++20 347 is_sorted_until(ForwardIterator first, ForwardIterator last); 348 349 template <class ForwardIterator, class Compare> 350 constexpr ForwardIterator // constexpr in C++20 351 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp); 352 353 template <class RandomAccessIterator> 354 constexpr void // constexpr in C++20 355 sort(RandomAccessIterator first, RandomAccessIterator last); 356 357 template <class RandomAccessIterator, class Compare> 358 constexpr void // constexpr in C++20 359 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 360 361 template <class RandomAccessIterator> 362 void 363 stable_sort(RandomAccessIterator first, RandomAccessIterator last); 364 365 template <class RandomAccessIterator, class Compare> 366 void 367 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 368 369 template <class RandomAccessIterator> 370 constexpr void // constexpr in C++20 371 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); 372 373 template <class RandomAccessIterator, class Compare> 374 constexpr void // constexpr in C++20 375 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); 376 377 template <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 382 template <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 387 template <class RandomAccessIterator> 388 constexpr void // constexpr in C++20 389 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); 390 391 template <class RandomAccessIterator, class Compare> 392 constexpr void // constexpr in C++20 393 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); 394 395 template <class ForwardIterator, class T> 396 constexpr ForwardIterator // constexpr in C++20 397 lower_bound(ForwardIterator first, ForwardIterator last, const T& value); 398 399 template <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 403 template <class ForwardIterator, class T> 404 constexpr ForwardIterator // constexpr in C++20 405 upper_bound(ForwardIterator first, ForwardIterator last, const T& value); 406 407 template <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 411 template <class ForwardIterator, class T> 412 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20 413 equal_range(ForwardIterator first, ForwardIterator last, const T& value); 414 415 template <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 419 template <class ForwardIterator, class T> 420 constexpr bool // constexpr in C++20 421 binary_search(ForwardIterator first, ForwardIterator last, const T& value); 422 423 template <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 427 template <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 432 template <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 437 template <class BidirectionalIterator> 438 void 439 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); 440 441 template <class BidirectionalIterator, class Compare> 442 void 443 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); 444 445 template <class InputIterator1, class InputIterator2> 446 constexpr bool // constexpr in C++20 447 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); 448 449 template <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 453 template <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 458 template <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 463 template <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 468 template <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 473 template <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 478 template <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 483 template <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 488 template <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 493 template <class RandomAccessIterator> 494 constexpr void // constexpr in C++20 495 push_heap(RandomAccessIterator first, RandomAccessIterator last); 496 497 template <class RandomAccessIterator, class Compare> 498 constexpr void // constexpr in C++20 499 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 500 501 template <class RandomAccessIterator> 502 constexpr void // constexpr in C++20 503 pop_heap(RandomAccessIterator first, RandomAccessIterator last); 504 505 template <class RandomAccessIterator, class Compare> 506 constexpr void // constexpr in C++20 507 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 508 509 template <class RandomAccessIterator> 510 constexpr void // constexpr in C++20 511 make_heap(RandomAccessIterator first, RandomAccessIterator last); 512 513 template <class RandomAccessIterator, class Compare> 514 constexpr void // constexpr in C++20 515 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 516 517 template <class RandomAccessIterator> 518 constexpr void // constexpr in C++20 519 sort_heap(RandomAccessIterator first, RandomAccessIterator last); 520 521 template <class RandomAccessIterator, class Compare> 522 constexpr void // constexpr in C++20 523 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 524 525 template <class RandomAccessIterator> 526 constexpr bool // constexpr in C++20 527 is_heap(RandomAccessIterator first, RandomAccessiterator last); 528 529 template <class RandomAccessIterator, class Compare> 530 constexpr bool // constexpr in C++20 531 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp); 532 533 template <class RandomAccessIterator> 534 constexpr RandomAccessIterator // constexpr in C++20 535 is_heap_until(RandomAccessIterator first, RandomAccessiterator last); 536 537 template <class RandomAccessIterator, class Compare> 538 constexpr RandomAccessIterator // constexpr in C++20 539 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp); 540 541 template <class ForwardIterator> 542 constexpr ForwardIterator // constexpr in C++14 543 min_element(ForwardIterator first, ForwardIterator last); 544 545 template <class ForwardIterator, class Compare> 546 constexpr ForwardIterator // constexpr in C++14 547 min_element(ForwardIterator first, ForwardIterator last, Compare comp); 548 549 template <class T> 550 constexpr const T& // constexpr in C++14 551 min(const T& a, const T& b); 552 553 template <class T, class Compare> 554 constexpr const T& // constexpr in C++14 555 min(const T& a, const T& b, Compare comp); 556 557 template<class T> 558 constexpr T // constexpr in C++14 559 min(initializer_list<T> t); 560 561 template<class T, class Compare> 562 constexpr T // constexpr in C++14 563 min(initializer_list<T> t, Compare comp); 564 565 template<class T> 566 constexpr const T& clamp(const T& v, const T& lo, const T& hi); // C++17 567 568 template<class T, class Compare> 569 constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp); // C++17 570 571 template <class ForwardIterator> 572 constexpr ForwardIterator // constexpr in C++14 573 max_element(ForwardIterator first, ForwardIterator last); 574 575 template <class ForwardIterator, class Compare> 576 constexpr ForwardIterator // constexpr in C++14 577 max_element(ForwardIterator first, ForwardIterator last, Compare comp); 578 579 template <class T> 580 constexpr const T& // constexpr in C++14 581 max(const T& a, const T& b); 582 583 template <class T, class Compare> 584 constexpr const T& // constexpr in C++14 585 max(const T& a, const T& b, Compare comp); 586 587 template<class T> 588 constexpr T // constexpr in C++14 589 max(initializer_list<T> t); 590 591 template<class T, class Compare> 592 constexpr T // constexpr in C++14 593 max(initializer_list<T> t, Compare comp); 594 595 template<class ForwardIterator> 596 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14 597 minmax_element(ForwardIterator first, ForwardIterator last); 598 599 template<class ForwardIterator, class Compare> 600 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14 601 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); 602 603 template<class T> 604 constexpr pair<const T&, const T&> // constexpr in C++14 605 minmax(const T& a, const T& b); 606 607 template<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 611 template<class T> 612 constexpr pair<T, T> // constexpr in C++14 613 minmax(initializer_list<T> t); 614 615 template<class T, class Compare> 616 constexpr pair<T, T> // constexpr in C++14 617 minmax(initializer_list<T> t, Compare comp); 618 619 template <class InputIterator1, class InputIterator2> 620 constexpr bool // constexpr in C++20 621 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); 622 623 template <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 628 template <class BidirectionalIterator> 629 constexpr bool // constexpr in C++20 630 next_permutation(BidirectionalIterator first, BidirectionalIterator last); 631 632 template <class BidirectionalIterator, class Compare> 633 constexpr bool // constexpr in C++20 634 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); 635 636 template <class BidirectionalIterator> 637 constexpr bool // constexpr in C++20 638 prev_permutation(BidirectionalIterator first, BidirectionalIterator last); 639 640 template <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. 675 template <class _T1, class _T2 = _T1> 676 struct __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 684 template <class _T1> 685 struct __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 691 template <class _T1> 692 struct __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 698 template <class _T1> 699 struct __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 705 template <class _T1, class _T2 = _T1> 706 struct __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 721 template <class _T1> 722 struct __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 728 template <class _T1> 729 struct __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 735 template <class _T1> 736 struct __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 742 template <class _Predicate> 743 class __invert // invert the sense of a comparison 744 { 745 private: 746 _Predicate __p_; 747 public: 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 764 template <typename _Integral> 765 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 766 typename 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 776 template <typename _Tp> 777 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 778 typename 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 790 template <class _Compare> 791 struct __debug_less 792 { 793 _Compare &__comp_; 794 _LIBCPP_CONSTEXPR_AFTER_CXX17 795 __debug_less(_Compare& __c) : __comp_(__c) {} 796 797 template <class _Tp, class _Up> 798 _LIBCPP_CONSTEXPR_AFTER_CXX17 799 bool operator()(const _Tp& __x, const _Up& __y) 800 { 801 bool __r = __comp_(__x, __y); 802 if (__r) 803 __do_compare_assert(0, __y, __x); 804 return __r; 805 } 806 807 template <class _Tp, class _Up> 808 _LIBCPP_CONSTEXPR_AFTER_CXX17 809 bool operator()(_Tp& __x, _Up& __y) 810 { 811 bool __r = __comp_(__x, __y); 812 if (__r) 813 __do_compare_assert(0, __y, __x); 814 return __r; 815 } 816 817 template <class _LHS, class _RHS> 818 _LIBCPP_CONSTEXPR_AFTER_CXX17 819 inline _LIBCPP_INLINE_VISIBILITY 820 decltype((void)declval<_Compare&>()( 821 declval<_LHS &>(), declval<_RHS &>())) 822 __do_compare_assert(int, _LHS & __l, _RHS & __r) { 823 _LIBCPP_ASSERT(!__comp_(__l, __r), 824 "Comparator does not induce a strict weak ordering"); 825 } 826 827 template <class _LHS, class _RHS> 828 _LIBCPP_CONSTEXPR_AFTER_CXX17 829 inline _LIBCPP_INLINE_VISIBILITY 830 void __do_compare_assert(long, _LHS &, _RHS &) {} 831 }; 832 833 #endif // _LIBCPP_DEBUG 834 835 template <class _Comp> 836 struct __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 848 template <class _InputIterator, class _Predicate> 849 _LIBCPP_NODISCARD_EXT inline 850 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 851 bool 852 all_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 862 template <class _InputIterator, class _Predicate> 863 _LIBCPP_NODISCARD_EXT inline 864 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 865 bool 866 any_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 876 template <class _InputIterator, class _Predicate> 877 _LIBCPP_NODISCARD_EXT inline 878 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 879 bool 880 none_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 890 template <class _InputIterator, class _Function> 891 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 892 _Function 893 for_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 903 template <class _InputIterator, class _Size, class _Function> 904 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 905 _InputIterator 906 for_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 922 template <class _InputIterator, class _Tp> 923 _LIBCPP_NODISCARD_EXT inline 924 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 925 _InputIterator 926 find(_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 936 template <class _InputIterator, class _Predicate> 937 _LIBCPP_NODISCARD_EXT inline 938 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 939 _InputIterator 940 find_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 950 template<class _InputIterator, class _Predicate> 951 _LIBCPP_NODISCARD_EXT inline 952 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 953 _InputIterator 954 find_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 964 template <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 1006 template <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 1045 template <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 1086 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 1087 _LIBCPP_NODISCARD_EXT inline 1088 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1089 _ForwardIterator1 1090 find_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 1099 template <class _ForwardIterator1, class _ForwardIterator2> 1100 _LIBCPP_NODISCARD_EXT inline 1101 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1102 _ForwardIterator1 1103 find_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 1113 template <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 1126 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 1127 _LIBCPP_NODISCARD_EXT inline 1128 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1129 _ForwardIterator1 1130 find_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 1136 template <class _ForwardIterator1, class _ForwardIterator2> 1137 _LIBCPP_NODISCARD_EXT inline 1138 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1139 _ForwardIterator1 1140 find_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 1150 template <class _ForwardIterator, class _BinaryPredicate> 1151 _LIBCPP_NODISCARD_EXT inline 1152 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1153 _ForwardIterator 1154 adjacent_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 1169 template <class _ForwardIterator> 1170 _LIBCPP_NODISCARD_EXT inline 1171 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1172 _ForwardIterator 1173 adjacent_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 1181 template <class _InputIterator, class _Tp> 1182 _LIBCPP_NODISCARD_EXT inline 1183 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1184 typename iterator_traits<_InputIterator>::difference_type 1185 count(_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 1196 template <class _InputIterator, class _Predicate> 1197 _LIBCPP_NODISCARD_EXT inline 1198 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1199 typename iterator_traits<_InputIterator>::difference_type 1200 count_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 1211 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 1212 _LIBCPP_NODISCARD_EXT inline 1213 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1214 pair<_InputIterator1, _InputIterator2> 1215 mismatch(_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 1224 template <class _InputIterator1, class _InputIterator2> 1225 _LIBCPP_NODISCARD_EXT inline 1226 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1227 pair<_InputIterator1, _InputIterator2> 1228 mismatch(_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 1236 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 1237 _LIBCPP_NODISCARD_EXT inline 1238 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1239 pair<_InputIterator1, _InputIterator2> 1240 mismatch(_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 1250 template <class _InputIterator1, class _InputIterator2> 1251 _LIBCPP_NODISCARD_EXT inline 1252 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1253 pair<_InputIterator1, _InputIterator2> 1254 mismatch(_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 1265 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 1266 _LIBCPP_NODISCARD_EXT inline 1267 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1268 bool 1269 equal(_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 1277 template <class _InputIterator1, class _InputIterator2> 1278 _LIBCPP_NODISCARD_EXT inline 1279 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1280 bool 1281 equal(_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 1289 template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2> 1290 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1291 bool 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 1302 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> 1303 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1304 bool 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 1316 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 1317 _LIBCPP_NODISCARD_EXT inline 1318 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1319 bool 1320 equal(_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 1329 template <class _InputIterator1, class _InputIterator2> 1330 _LIBCPP_NODISCARD_EXT inline 1331 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1332 bool 1333 equal(_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 1346 template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 1347 _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool 1348 is_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 1393 template<class _ForwardIterator1, class _ForwardIterator2> 1394 _LIBCPP_NODISCARD_EXT inline 1395 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1396 bool 1397 is_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 1406 template<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 1459 template<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 1473 template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 1474 _LIBCPP_NODISCARD_EXT inline 1475 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1476 bool 1477 is_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 1487 template<class _ForwardIterator1, class _ForwardIterator2> 1488 _LIBCPP_NODISCARD_EXT inline 1489 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1490 bool 1491 is_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 1506 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 1507 _LIBCPP_NODISCARD_EXT inline 1508 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1509 _ForwardIterator1 1510 search(_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 1520 template <class _ForwardIterator1, class _ForwardIterator2> 1521 _LIBCPP_NODISCARD_EXT inline 1522 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1523 _ForwardIterator1 1524 search(_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 1534 template <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 1542 template <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 1579 template <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 1619 template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate> 1620 _LIBCPP_NODISCARD_EXT inline 1621 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1622 _ForwardIterator 1623 search_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 1631 template <class _ForwardIterator, class _Size, class _Tp> 1632 _LIBCPP_NODISCARD_EXT inline 1633 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1634 _ForwardIterator 1635 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) 1636 { 1637 typedef typename iterator_traits<_ForwardIterator>::value_type __v; 1638 return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count), 1639 __value_, __equal_to<__v, _Tp>()); 1640 } 1641 1642 // __unwrap_iter, __rewrap_iter 1643 1644 // The job of __unwrap_iter is to lower contiguous iterators (such as 1645 // vector<T>::iterator) into pointers, to reduce the number of template 1646 // instantiations and to enable pointer-based optimizations e.g. in std::copy. 1647 // For iterators that are not contiguous, it must be a no-op. 1648 // In debug mode, we don't do this. 1649 // 1650 // __unwrap_iter is non-constexpr for user-defined iterators whose 1651 // `to_address` and/or `operator->` is non-constexpr. This is okay; but we 1652 // try to avoid doing __unwrap_iter in constant-evaluated contexts anyway. 1653 // 1654 // Some algorithms (e.g. std::copy, but not std::sort) need to convert an 1655 // "unwrapped" result back into a contiguous iterator. Since contiguous iterators 1656 // are random-access, we can do this portably using iterator arithmetic; this 1657 // is the job of __rewrap_iter. 1658 1659 template <class _Iter, bool = __is_cpp17_contiguous_iterator<_Iter>::value> 1660 struct __unwrap_iter_impl { 1661 static _LIBCPP_CONSTEXPR _Iter 1662 __apply(_Iter __i) _NOEXCEPT { 1663 return __i; 1664 } 1665 }; 1666 1667 #if _LIBCPP_DEBUG_LEVEL < 2 1668 1669 template <class _Iter> 1670 struct __unwrap_iter_impl<_Iter, true> { 1671 static _LIBCPP_CONSTEXPR decltype(_VSTD::__to_address(declval<_Iter>())) 1672 __apply(_Iter __i) _NOEXCEPT { 1673 return _VSTD::__to_address(__i); 1674 } 1675 }; 1676 1677 #endif // _LIBCPP_DEBUG_LEVEL < 2 1678 1679 template<class _Iter, class _Impl = __unwrap_iter_impl<_Iter> > 1680 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 1681 decltype(_Impl::__apply(declval<_Iter>())) 1682 __unwrap_iter(_Iter __i) _NOEXCEPT 1683 { 1684 return _Impl::__apply(__i); 1685 } 1686 1687 template<class _OrigIter> 1688 _OrigIter __rewrap_iter(_OrigIter, _OrigIter __result) 1689 { 1690 return __result; 1691 } 1692 1693 template<class _OrigIter, class _UnwrappedIter> 1694 _OrigIter __rewrap_iter(_OrigIter __first, _UnwrappedIter __result) 1695 { 1696 // Precondition: __result is reachable from __first 1697 // Precondition: _OrigIter is a contiguous iterator 1698 return __first + (__result - _VSTD::__unwrap_iter(__first)); 1699 } 1700 1701 // copy 1702 1703 template <class _InputIterator, class _OutputIterator> 1704 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1705 _OutputIterator 1706 __copy_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 1707 { 1708 for (; __first != __last; ++__first, (void) ++__result) 1709 *__result = *__first; 1710 return __result; 1711 } 1712 1713 template <class _InputIterator, class _OutputIterator> 1714 inline _LIBCPP_INLINE_VISIBILITY 1715 _OutputIterator 1716 __copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 1717 { 1718 return _VSTD::__copy_constexpr(__first, __last, __result); 1719 } 1720 1721 template <class _Tp, class _Up> 1722 inline _LIBCPP_INLINE_VISIBILITY 1723 typename enable_if 1724 < 1725 is_same<typename remove_const<_Tp>::type, _Up>::value && 1726 is_trivially_copy_assignable<_Up>::value, 1727 _Up* 1728 >::type 1729 __copy(_Tp* __first, _Tp* __last, _Up* __result) 1730 { 1731 const size_t __n = static_cast<size_t>(__last - __first); 1732 if (__n > 0) 1733 _VSTD::memmove(__result, __first, __n * sizeof(_Up)); 1734 return __result + __n; 1735 } 1736 1737 template <class _InputIterator, class _OutputIterator> 1738 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1739 _OutputIterator 1740 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 1741 { 1742 if (__libcpp_is_constant_evaluated()) { 1743 return _VSTD::__copy_constexpr(__first, __last, __result); 1744 } else { 1745 return _VSTD::__rewrap_iter(__result, 1746 _VSTD::__copy(_VSTD::__unwrap_iter(__first), 1747 _VSTD::__unwrap_iter(__last), 1748 _VSTD::__unwrap_iter(__result))); 1749 } 1750 } 1751 1752 // copy_backward 1753 1754 template <class _BidirectionalIterator, class _OutputIterator> 1755 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1756 _OutputIterator 1757 __copy_backward_constexpr(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result) 1758 { 1759 while (__first != __last) 1760 *--__result = *--__last; 1761 return __result; 1762 } 1763 1764 template <class _BidirectionalIterator, class _OutputIterator> 1765 inline _LIBCPP_INLINE_VISIBILITY 1766 _OutputIterator 1767 __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result) 1768 { 1769 return _VSTD::__copy_backward_constexpr(__first, __last, __result); 1770 } 1771 1772 template <class _Tp, class _Up> 1773 inline _LIBCPP_INLINE_VISIBILITY 1774 typename enable_if 1775 < 1776 is_same<typename remove_const<_Tp>::type, _Up>::value && 1777 is_trivially_copy_assignable<_Up>::value, 1778 _Up* 1779 >::type 1780 __copy_backward(_Tp* __first, _Tp* __last, _Up* __result) 1781 { 1782 const size_t __n = static_cast<size_t>(__last - __first); 1783 if (__n > 0) 1784 { 1785 __result -= __n; 1786 _VSTD::memmove(__result, __first, __n * sizeof(_Up)); 1787 } 1788 return __result; 1789 } 1790 1791 template <class _BidirectionalIterator1, class _BidirectionalIterator2> 1792 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1793 _BidirectionalIterator2 1794 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, 1795 _BidirectionalIterator2 __result) 1796 { 1797 if (__libcpp_is_constant_evaluated()) { 1798 return _VSTD::__copy_backward_constexpr(__first, __last, __result); 1799 } else { 1800 return _VSTD::__rewrap_iter(__result, 1801 _VSTD::__copy_backward(_VSTD::__unwrap_iter(__first), 1802 _VSTD::__unwrap_iter(__last), 1803 _VSTD::__unwrap_iter(__result))); 1804 } 1805 } 1806 1807 // copy_if 1808 1809 template<class _InputIterator, class _OutputIterator, class _Predicate> 1810 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1811 _OutputIterator 1812 copy_if(_InputIterator __first, _InputIterator __last, 1813 _OutputIterator __result, _Predicate __pred) 1814 { 1815 for (; __first != __last; ++__first) 1816 { 1817 if (__pred(*__first)) 1818 { 1819 *__result = *__first; 1820 ++__result; 1821 } 1822 } 1823 return __result; 1824 } 1825 1826 // copy_n 1827 1828 template<class _InputIterator, class _Size, class _OutputIterator> 1829 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1830 typename enable_if 1831 < 1832 __is_cpp17_input_iterator<_InputIterator>::value && 1833 !__is_cpp17_random_access_iterator<_InputIterator>::value, 1834 _OutputIterator 1835 >::type 1836 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result) 1837 { 1838 typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize; 1839 _IntegralSize __n = __orig_n; 1840 if (__n > 0) 1841 { 1842 *__result = *__first; 1843 ++__result; 1844 for (--__n; __n > 0; --__n) 1845 { 1846 ++__first; 1847 *__result = *__first; 1848 ++__result; 1849 } 1850 } 1851 return __result; 1852 } 1853 1854 template<class _InputIterator, class _Size, class _OutputIterator> 1855 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1856 typename enable_if 1857 < 1858 __is_cpp17_random_access_iterator<_InputIterator>::value, 1859 _OutputIterator 1860 >::type 1861 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result) 1862 { 1863 typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize; 1864 _IntegralSize __n = __orig_n; 1865 return _VSTD::copy(__first, __first + __n, __result); 1866 } 1867 1868 // move 1869 1870 template <class _InputIterator, class _OutputIterator> 1871 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1872 _OutputIterator 1873 __move_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 1874 { 1875 for (; __first != __last; ++__first, (void) ++__result) 1876 *__result = _VSTD::move(*__first); 1877 return __result; 1878 } 1879 1880 template <class _InputIterator, class _OutputIterator> 1881 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1882 _OutputIterator 1883 __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 1884 { 1885 return _VSTD::__move_constexpr(__first, __last, __result); 1886 } 1887 1888 template <class _Tp, class _Up> 1889 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1890 typename enable_if 1891 < 1892 is_same<typename remove_const<_Tp>::type, _Up>::value && 1893 is_trivially_move_assignable<_Up>::value, 1894 _Up* 1895 >::type 1896 __move(_Tp* __first, _Tp* __last, _Up* __result) 1897 { 1898 const size_t __n = static_cast<size_t>(__last - __first); 1899 if (__n > 0) 1900 _VSTD::memmove(__result, __first, __n * sizeof(_Up)); 1901 return __result + __n; 1902 } 1903 1904 template <class _InputIterator, class _OutputIterator> 1905 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1906 _OutputIterator 1907 move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 1908 { 1909 if (__libcpp_is_constant_evaluated()) { 1910 return _VSTD::__move_constexpr(__first, __last, __result); 1911 } else { 1912 return _VSTD::__rewrap_iter(__result, 1913 _VSTD::__move(_VSTD::__unwrap_iter(__first), 1914 _VSTD::__unwrap_iter(__last), 1915 _VSTD::__unwrap_iter(__result))); 1916 } 1917 } 1918 1919 // move_backward 1920 1921 template <class _InputIterator, class _OutputIterator> 1922 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1923 _OutputIterator 1924 __move_backward_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 1925 { 1926 while (__first != __last) 1927 *--__result = _VSTD::move(*--__last); 1928 return __result; 1929 } 1930 1931 template <class _InputIterator, class _OutputIterator> 1932 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1933 _OutputIterator 1934 __move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 1935 { 1936 return _VSTD::__move_backward_constexpr(__first, __last, __result); 1937 } 1938 1939 template <class _Tp, class _Up> 1940 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1941 typename enable_if 1942 < 1943 is_same<typename remove_const<_Tp>::type, _Up>::value && 1944 is_trivially_move_assignable<_Up>::value, 1945 _Up* 1946 >::type 1947 __move_backward(_Tp* __first, _Tp* __last, _Up* __result) 1948 { 1949 const size_t __n = static_cast<size_t>(__last - __first); 1950 if (__n > 0) 1951 { 1952 __result -= __n; 1953 _VSTD::memmove(__result, __first, __n * sizeof(_Up)); 1954 } 1955 return __result; 1956 } 1957 1958 template <class _BidirectionalIterator1, class _BidirectionalIterator2> 1959 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1960 _BidirectionalIterator2 1961 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, 1962 _BidirectionalIterator2 __result) 1963 { 1964 if (__libcpp_is_constant_evaluated()) { 1965 return _VSTD::__move_backward_constexpr(__first, __last, __result); 1966 } else { 1967 return _VSTD::__rewrap_iter(__result, 1968 _VSTD::__move_backward(_VSTD::__unwrap_iter(__first), 1969 _VSTD::__unwrap_iter(__last), 1970 _VSTD::__unwrap_iter(__result))); 1971 } 1972 } 1973 1974 // iter_swap 1975 1976 // moved to <type_traits> for better swap / noexcept support 1977 1978 // transform 1979 1980 template <class _InputIterator, class _OutputIterator, class _UnaryOperation> 1981 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1982 _OutputIterator 1983 transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op) 1984 { 1985 for (; __first != __last; ++__first, (void) ++__result) 1986 *__result = __op(*__first); 1987 return __result; 1988 } 1989 1990 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation> 1991 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1992 _OutputIterator 1993 transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, 1994 _OutputIterator __result, _BinaryOperation __binary_op) 1995 { 1996 for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result) 1997 *__result = __binary_op(*__first1, *__first2); 1998 return __result; 1999 } 2000 2001 // replace 2002 2003 template <class _ForwardIterator, class _Tp> 2004 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2005 void 2006 replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value) 2007 { 2008 for (; __first != __last; ++__first) 2009 if (*__first == __old_value) 2010 *__first = __new_value; 2011 } 2012 2013 // replace_if 2014 2015 template <class _ForwardIterator, class _Predicate, class _Tp> 2016 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2017 void 2018 replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value) 2019 { 2020 for (; __first != __last; ++__first) 2021 if (__pred(*__first)) 2022 *__first = __new_value; 2023 } 2024 2025 // replace_copy 2026 2027 template <class _InputIterator, class _OutputIterator, class _Tp> 2028 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2029 _OutputIterator 2030 replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, 2031 const _Tp& __old_value, const _Tp& __new_value) 2032 { 2033 for (; __first != __last; ++__first, (void) ++__result) 2034 if (*__first == __old_value) 2035 *__result = __new_value; 2036 else 2037 *__result = *__first; 2038 return __result; 2039 } 2040 2041 // replace_copy_if 2042 2043 template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp> 2044 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2045 _OutputIterator 2046 replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, 2047 _Predicate __pred, const _Tp& __new_value) 2048 { 2049 for (; __first != __last; ++__first, (void) ++__result) 2050 if (__pred(*__first)) 2051 *__result = __new_value; 2052 else 2053 *__result = *__first; 2054 return __result; 2055 } 2056 2057 // fill_n 2058 2059 template <class _OutputIterator, class _Size, class _Tp> 2060 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2061 _OutputIterator 2062 __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) 2063 { 2064 for (; __n > 0; ++__first, (void) --__n) 2065 *__first = __value_; 2066 return __first; 2067 } 2068 2069 template <class _OutputIterator, class _Size, class _Tp> 2070 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2071 _OutputIterator 2072 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) 2073 { 2074 return _VSTD::__fill_n(__first, _VSTD::__convert_to_integral(__n), __value_); 2075 } 2076 2077 // fill 2078 2079 template <class _ForwardIterator, class _Tp> 2080 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2081 void 2082 __fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag) 2083 { 2084 for (; __first != __last; ++__first) 2085 *__first = __value_; 2086 } 2087 2088 template <class _RandomAccessIterator, class _Tp> 2089 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2090 void 2091 __fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag) 2092 { 2093 _VSTD::fill_n(__first, __last - __first, __value_); 2094 } 2095 2096 template <class _ForwardIterator, class _Tp> 2097 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2098 void 2099 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 2100 { 2101 _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category()); 2102 } 2103 2104 // generate 2105 2106 template <class _ForwardIterator, class _Generator> 2107 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2108 void 2109 generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen) 2110 { 2111 for (; __first != __last; ++__first) 2112 *__first = __gen(); 2113 } 2114 2115 // generate_n 2116 2117 template <class _OutputIterator, class _Size, class _Generator> 2118 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2119 _OutputIterator 2120 generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen) 2121 { 2122 typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize; 2123 _IntegralSize __n = __orig_n; 2124 for (; __n > 0; ++__first, (void) --__n) 2125 *__first = __gen(); 2126 return __first; 2127 } 2128 2129 // remove 2130 2131 template <class _ForwardIterator, class _Tp> 2132 _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 2133 remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 2134 { 2135 __first = _VSTD::find(__first, __last, __value_); 2136 if (__first != __last) 2137 { 2138 _ForwardIterator __i = __first; 2139 while (++__i != __last) 2140 { 2141 if (!(*__i == __value_)) 2142 { 2143 *__first = _VSTD::move(*__i); 2144 ++__first; 2145 } 2146 } 2147 } 2148 return __first; 2149 } 2150 2151 // remove_if 2152 2153 template <class _ForwardIterator, class _Predicate> 2154 _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 2155 remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 2156 { 2157 __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type> 2158 (__first, __last, __pred); 2159 if (__first != __last) 2160 { 2161 _ForwardIterator __i = __first; 2162 while (++__i != __last) 2163 { 2164 if (!__pred(*__i)) 2165 { 2166 *__first = _VSTD::move(*__i); 2167 ++__first; 2168 } 2169 } 2170 } 2171 return __first; 2172 } 2173 2174 // remove_copy 2175 2176 template <class _InputIterator, class _OutputIterator, class _Tp> 2177 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2178 _OutputIterator 2179 remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_) 2180 { 2181 for (; __first != __last; ++__first) 2182 { 2183 if (!(*__first == __value_)) 2184 { 2185 *__result = *__first; 2186 ++__result; 2187 } 2188 } 2189 return __result; 2190 } 2191 2192 // remove_copy_if 2193 2194 template <class _InputIterator, class _OutputIterator, class _Predicate> 2195 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2196 _OutputIterator 2197 remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred) 2198 { 2199 for (; __first != __last; ++__first) 2200 { 2201 if (!__pred(*__first)) 2202 { 2203 *__result = *__first; 2204 ++__result; 2205 } 2206 } 2207 return __result; 2208 } 2209 2210 // unique 2211 2212 template <class _ForwardIterator, class _BinaryPredicate> 2213 _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 2214 unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) 2215 { 2216 __first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type> 2217 (__first, __last, __pred); 2218 if (__first != __last) 2219 { 2220 // ... a a ? ... 2221 // f i 2222 _ForwardIterator __i = __first; 2223 for (++__i; ++__i != __last;) 2224 if (!__pred(*__first, *__i)) 2225 *++__first = _VSTD::move(*__i); 2226 ++__first; 2227 } 2228 return __first; 2229 } 2230 2231 template <class _ForwardIterator> 2232 _LIBCPP_NODISCARD_EXT inline 2233 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2234 _ForwardIterator 2235 unique(_ForwardIterator __first, _ForwardIterator __last) 2236 { 2237 typedef typename iterator_traits<_ForwardIterator>::value_type __v; 2238 return _VSTD::unique(__first, __last, __equal_to<__v>()); 2239 } 2240 2241 // unique_copy 2242 2243 template <class _BinaryPredicate, class _InputIterator, class _OutputIterator> 2244 _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 2245 __unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred, 2246 input_iterator_tag, output_iterator_tag) 2247 { 2248 if (__first != __last) 2249 { 2250 typename iterator_traits<_InputIterator>::value_type __t(*__first); 2251 *__result = __t; 2252 ++__result; 2253 while (++__first != __last) 2254 { 2255 if (!__pred(__t, *__first)) 2256 { 2257 __t = *__first; 2258 *__result = __t; 2259 ++__result; 2260 } 2261 } 2262 } 2263 return __result; 2264 } 2265 2266 template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator> 2267 _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 2268 __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred, 2269 forward_iterator_tag, output_iterator_tag) 2270 { 2271 if (__first != __last) 2272 { 2273 _ForwardIterator __i = __first; 2274 *__result = *__i; 2275 ++__result; 2276 while (++__first != __last) 2277 { 2278 if (!__pred(*__i, *__first)) 2279 { 2280 *__result = *__first; 2281 ++__result; 2282 __i = __first; 2283 } 2284 } 2285 } 2286 return __result; 2287 } 2288 2289 template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator> 2290 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 2291 __unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred, 2292 input_iterator_tag, forward_iterator_tag) 2293 { 2294 if (__first != __last) 2295 { 2296 *__result = *__first; 2297 while (++__first != __last) 2298 if (!__pred(*__result, *__first)) 2299 *++__result = *__first; 2300 ++__result; 2301 } 2302 return __result; 2303 } 2304 2305 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate> 2306 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2307 _OutputIterator 2308 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred) 2309 { 2310 return _VSTD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type> 2311 (__first, __last, __result, __pred, 2312 typename iterator_traits<_InputIterator>::iterator_category(), 2313 typename iterator_traits<_OutputIterator>::iterator_category()); 2314 } 2315 2316 template <class _InputIterator, class _OutputIterator> 2317 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2318 _OutputIterator 2319 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 2320 { 2321 typedef typename iterator_traits<_InputIterator>::value_type __v; 2322 return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>()); 2323 } 2324 2325 // reverse 2326 2327 template <class _BidirectionalIterator> 2328 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2329 void 2330 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag) 2331 { 2332 while (__first != __last) 2333 { 2334 if (__first == --__last) 2335 break; 2336 _VSTD::iter_swap(__first, __last); 2337 ++__first; 2338 } 2339 } 2340 2341 template <class _RandomAccessIterator> 2342 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2343 void 2344 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag) 2345 { 2346 if (__first != __last) 2347 for (; __first < --__last; ++__first) 2348 _VSTD::iter_swap(__first, __last); 2349 } 2350 2351 template <class _BidirectionalIterator> 2352 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2353 void 2354 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) 2355 { 2356 _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category()); 2357 } 2358 2359 // reverse_copy 2360 2361 template <class _BidirectionalIterator, class _OutputIterator> 2362 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2363 _OutputIterator 2364 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result) 2365 { 2366 for (; __first != __last; ++__result) 2367 *__result = *--__last; 2368 return __result; 2369 } 2370 2371 // rotate 2372 2373 template <class _ForwardIterator> 2374 _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator 2375 __rotate_left(_ForwardIterator __first, _ForwardIterator __last) 2376 { 2377 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 2378 value_type __tmp = _VSTD::move(*__first); 2379 _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first); 2380 *__lm1 = _VSTD::move(__tmp); 2381 return __lm1; 2382 } 2383 2384 template <class _BidirectionalIterator> 2385 _LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator 2386 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last) 2387 { 2388 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 2389 _BidirectionalIterator __lm1 = _VSTD::prev(__last); 2390 value_type __tmp = _VSTD::move(*__lm1); 2391 _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last); 2392 *__first = _VSTD::move(__tmp); 2393 return __fp1; 2394 } 2395 2396 template <class _ForwardIterator> 2397 _LIBCPP_CONSTEXPR_AFTER_CXX14 _ForwardIterator 2398 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) 2399 { 2400 _ForwardIterator __i = __middle; 2401 while (true) 2402 { 2403 swap(*__first, *__i); 2404 ++__first; 2405 if (++__i == __last) 2406 break; 2407 if (__first == __middle) 2408 __middle = __i; 2409 } 2410 _ForwardIterator __r = __first; 2411 if (__first != __middle) 2412 { 2413 __i = __middle; 2414 while (true) 2415 { 2416 swap(*__first, *__i); 2417 ++__first; 2418 if (++__i == __last) 2419 { 2420 if (__first == __middle) 2421 break; 2422 __i = __middle; 2423 } 2424 else if (__first == __middle) 2425 __middle = __i; 2426 } 2427 } 2428 return __r; 2429 } 2430 2431 template<typename _Integral> 2432 inline _LIBCPP_INLINE_VISIBILITY 2433 _LIBCPP_CONSTEXPR_AFTER_CXX14 _Integral 2434 __algo_gcd(_Integral __x, _Integral __y) 2435 { 2436 do 2437 { 2438 _Integral __t = __x % __y; 2439 __x = __y; 2440 __y = __t; 2441 } while (__y); 2442 return __x; 2443 } 2444 2445 template<typename _RandomAccessIterator> 2446 _LIBCPP_CONSTEXPR_AFTER_CXX14 _RandomAccessIterator 2447 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) 2448 { 2449 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 2450 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 2451 2452 const difference_type __m1 = __middle - __first; 2453 const difference_type __m2 = __last - __middle; 2454 if (__m1 == __m2) 2455 { 2456 _VSTD::swap_ranges(__first, __middle, __middle); 2457 return __middle; 2458 } 2459 const difference_type __g = _VSTD::__algo_gcd(__m1, __m2); 2460 for (_RandomAccessIterator __p = __first + __g; __p != __first;) 2461 { 2462 value_type __t(_VSTD::move(*--__p)); 2463 _RandomAccessIterator __p1 = __p; 2464 _RandomAccessIterator __p2 = __p1 + __m1; 2465 do 2466 { 2467 *__p1 = _VSTD::move(*__p2); 2468 __p1 = __p2; 2469 const difference_type __d = __last - __p2; 2470 if (__m1 < __d) 2471 __p2 += __m1; 2472 else 2473 __p2 = __first + (__m1 - __d); 2474 } while (__p2 != __p); 2475 *__p1 = _VSTD::move(__t); 2476 } 2477 return __first + __m2; 2478 } 2479 2480 template <class _ForwardIterator> 2481 inline _LIBCPP_INLINE_VISIBILITY 2482 _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator 2483 __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, 2484 _VSTD::forward_iterator_tag) 2485 { 2486 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 2487 if (is_trivially_move_assignable<value_type>::value) 2488 { 2489 if (_VSTD::next(__first) == __middle) 2490 return _VSTD::__rotate_left(__first, __last); 2491 } 2492 return _VSTD::__rotate_forward(__first, __middle, __last); 2493 } 2494 2495 template <class _BidirectionalIterator> 2496 inline _LIBCPP_INLINE_VISIBILITY 2497 _LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator 2498 __rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 2499 bidirectional_iterator_tag) 2500 { 2501 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 2502 if (is_trivially_move_assignable<value_type>::value) 2503 { 2504 if (_VSTD::next(__first) == __middle) 2505 return _VSTD::__rotate_left(__first, __last); 2506 if (_VSTD::next(__middle) == __last) 2507 return _VSTD::__rotate_right(__first, __last); 2508 } 2509 return _VSTD::__rotate_forward(__first, __middle, __last); 2510 } 2511 2512 template <class _RandomAccessIterator> 2513 inline _LIBCPP_INLINE_VISIBILITY 2514 _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator 2515 __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, 2516 random_access_iterator_tag) 2517 { 2518 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 2519 if (is_trivially_move_assignable<value_type>::value) 2520 { 2521 if (_VSTD::next(__first) == __middle) 2522 return _VSTD::__rotate_left(__first, __last); 2523 if (_VSTD::next(__middle) == __last) 2524 return _VSTD::__rotate_right(__first, __last); 2525 return _VSTD::__rotate_gcd(__first, __middle, __last); 2526 } 2527 return _VSTD::__rotate_forward(__first, __middle, __last); 2528 } 2529 2530 template <class _ForwardIterator> 2531 inline _LIBCPP_INLINE_VISIBILITY 2532 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 2533 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) 2534 { 2535 if (__first == __middle) 2536 return __last; 2537 if (__middle == __last) 2538 return __first; 2539 return _VSTD::__rotate(__first, __middle, __last, 2540 typename iterator_traits<_ForwardIterator>::iterator_category()); 2541 } 2542 2543 // rotate_copy 2544 2545 template <class _ForwardIterator, class _OutputIterator> 2546 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2547 _OutputIterator 2548 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result) 2549 { 2550 return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result)); 2551 } 2552 2553 // min_element 2554 2555 template <class _ForwardIterator, class _Compare> 2556 _LIBCPP_NODISCARD_EXT inline 2557 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2558 _ForwardIterator 2559 min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 2560 { 2561 static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value, 2562 "std::min_element requires a ForwardIterator"); 2563 if (__first != __last) 2564 { 2565 _ForwardIterator __i = __first; 2566 while (++__i != __last) 2567 if (__comp(*__i, *__first)) 2568 __first = __i; 2569 } 2570 return __first; 2571 } 2572 2573 template <class _ForwardIterator> 2574 _LIBCPP_NODISCARD_EXT inline 2575 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2576 _ForwardIterator 2577 min_element(_ForwardIterator __first, _ForwardIterator __last) 2578 { 2579 return _VSTD::min_element(__first, __last, 2580 __less<typename iterator_traits<_ForwardIterator>::value_type>()); 2581 } 2582 2583 // min 2584 2585 template <class _Tp, class _Compare> 2586 _LIBCPP_NODISCARD_EXT inline 2587 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2588 const _Tp& 2589 min(const _Tp& __a, const _Tp& __b, _Compare __comp) 2590 { 2591 return __comp(__b, __a) ? __b : __a; 2592 } 2593 2594 template <class _Tp> 2595 _LIBCPP_NODISCARD_EXT inline 2596 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2597 const _Tp& 2598 min(const _Tp& __a, const _Tp& __b) 2599 { 2600 return _VSTD::min(__a, __b, __less<_Tp>()); 2601 } 2602 2603 #ifndef _LIBCPP_CXX03_LANG 2604 2605 template<class _Tp, class _Compare> 2606 _LIBCPP_NODISCARD_EXT inline 2607 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2608 _Tp 2609 min(initializer_list<_Tp> __t, _Compare __comp) 2610 { 2611 return *_VSTD::min_element(__t.begin(), __t.end(), __comp); 2612 } 2613 2614 template<class _Tp> 2615 _LIBCPP_NODISCARD_EXT inline 2616 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2617 _Tp 2618 min(initializer_list<_Tp> __t) 2619 { 2620 return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>()); 2621 } 2622 2623 #endif // _LIBCPP_CXX03_LANG 2624 2625 // max_element 2626 2627 template <class _ForwardIterator, class _Compare> 2628 _LIBCPP_NODISCARD_EXT inline 2629 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2630 _ForwardIterator 2631 max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 2632 { 2633 static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value, 2634 "std::max_element requires a ForwardIterator"); 2635 if (__first != __last) 2636 { 2637 _ForwardIterator __i = __first; 2638 while (++__i != __last) 2639 if (__comp(*__first, *__i)) 2640 __first = __i; 2641 } 2642 return __first; 2643 } 2644 2645 2646 template <class _ForwardIterator> 2647 _LIBCPP_NODISCARD_EXT inline 2648 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2649 _ForwardIterator 2650 max_element(_ForwardIterator __first, _ForwardIterator __last) 2651 { 2652 return _VSTD::max_element(__first, __last, 2653 __less<typename iterator_traits<_ForwardIterator>::value_type>()); 2654 } 2655 2656 // max 2657 2658 template <class _Tp, class _Compare> 2659 _LIBCPP_NODISCARD_EXT inline 2660 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2661 const _Tp& 2662 max(const _Tp& __a, const _Tp& __b, _Compare __comp) 2663 { 2664 return __comp(__a, __b) ? __b : __a; 2665 } 2666 2667 template <class _Tp> 2668 _LIBCPP_NODISCARD_EXT inline 2669 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2670 const _Tp& 2671 max(const _Tp& __a, const _Tp& __b) 2672 { 2673 return _VSTD::max(__a, __b, __less<_Tp>()); 2674 } 2675 2676 #ifndef _LIBCPP_CXX03_LANG 2677 2678 template<class _Tp, class _Compare> 2679 _LIBCPP_NODISCARD_EXT inline 2680 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2681 _Tp 2682 max(initializer_list<_Tp> __t, _Compare __comp) 2683 { 2684 return *_VSTD::max_element(__t.begin(), __t.end(), __comp); 2685 } 2686 2687 template<class _Tp> 2688 _LIBCPP_NODISCARD_EXT inline 2689 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2690 _Tp 2691 max(initializer_list<_Tp> __t) 2692 { 2693 return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>()); 2694 } 2695 2696 #endif // _LIBCPP_CXX03_LANG 2697 2698 #if _LIBCPP_STD_VER > 14 2699 // clamp 2700 template<class _Tp, class _Compare> 2701 _LIBCPP_NODISCARD_EXT inline 2702 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 2703 const _Tp& 2704 clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi, _Compare __comp) 2705 { 2706 _LIBCPP_ASSERT(!__comp(__hi, __lo), "Bad bounds passed to std::clamp"); 2707 return __comp(__v, __lo) ? __lo : __comp(__hi, __v) ? __hi : __v; 2708 2709 } 2710 2711 template<class _Tp> 2712 _LIBCPP_NODISCARD_EXT inline 2713 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 2714 const _Tp& 2715 clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi) 2716 { 2717 return _VSTD::clamp(__v, __lo, __hi, __less<_Tp>()); 2718 } 2719 #endif 2720 2721 // minmax_element 2722 2723 template <class _ForwardIterator, class _Compare> 2724 _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX11 2725 pair<_ForwardIterator, _ForwardIterator> 2726 minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 2727 { 2728 static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value, 2729 "std::minmax_element requires a ForwardIterator"); 2730 pair<_ForwardIterator, _ForwardIterator> __result(__first, __first); 2731 if (__first != __last) 2732 { 2733 if (++__first != __last) 2734 { 2735 if (__comp(*__first, *__result.first)) 2736 __result.first = __first; 2737 else 2738 __result.second = __first; 2739 while (++__first != __last) 2740 { 2741 _ForwardIterator __i = __first; 2742 if (++__first == __last) 2743 { 2744 if (__comp(*__i, *__result.first)) 2745 __result.first = __i; 2746 else if (!__comp(*__i, *__result.second)) 2747 __result.second = __i; 2748 break; 2749 } 2750 else 2751 { 2752 if (__comp(*__first, *__i)) 2753 { 2754 if (__comp(*__first, *__result.first)) 2755 __result.first = __first; 2756 if (!__comp(*__i, *__result.second)) 2757 __result.second = __i; 2758 } 2759 else 2760 { 2761 if (__comp(*__i, *__result.first)) 2762 __result.first = __i; 2763 if (!__comp(*__first, *__result.second)) 2764 __result.second = __first; 2765 } 2766 } 2767 } 2768 } 2769 } 2770 return __result; 2771 } 2772 2773 template <class _ForwardIterator> 2774 _LIBCPP_NODISCARD_EXT inline 2775 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2776 pair<_ForwardIterator, _ForwardIterator> 2777 minmax_element(_ForwardIterator __first, _ForwardIterator __last) 2778 { 2779 return _VSTD::minmax_element(__first, __last, 2780 __less<typename iterator_traits<_ForwardIterator>::value_type>()); 2781 } 2782 2783 // minmax 2784 2785 template<class _Tp, class _Compare> 2786 _LIBCPP_NODISCARD_EXT inline 2787 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2788 pair<const _Tp&, const _Tp&> 2789 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) 2790 { 2791 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) : 2792 pair<const _Tp&, const _Tp&>(__a, __b); 2793 } 2794 2795 template<class _Tp> 2796 _LIBCPP_NODISCARD_EXT inline 2797 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2798 pair<const _Tp&, const _Tp&> 2799 minmax(const _Tp& __a, const _Tp& __b) 2800 { 2801 return _VSTD::minmax(__a, __b, __less<_Tp>()); 2802 } 2803 2804 #ifndef _LIBCPP_CXX03_LANG 2805 2806 template<class _Tp, class _Compare> 2807 _LIBCPP_NODISCARD_EXT inline 2808 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2809 pair<_Tp, _Tp> 2810 minmax(initializer_list<_Tp> __t, _Compare __comp) 2811 { 2812 typedef typename initializer_list<_Tp>::const_iterator _Iter; 2813 _Iter __first = __t.begin(); 2814 _Iter __last = __t.end(); 2815 pair<_Tp, _Tp> __result(*__first, *__first); 2816 2817 ++__first; 2818 if (__t.size() % 2 == 0) 2819 { 2820 if (__comp(*__first, __result.first)) 2821 __result.first = *__first; 2822 else 2823 __result.second = *__first; 2824 ++__first; 2825 } 2826 2827 while (__first != __last) 2828 { 2829 _Tp __prev = *__first++; 2830 if (__comp(*__first, __prev)) { 2831 if ( __comp(*__first, __result.first)) __result.first = *__first; 2832 if (!__comp(__prev, __result.second)) __result.second = __prev; 2833 } 2834 else { 2835 if ( __comp(__prev, __result.first)) __result.first = __prev; 2836 if (!__comp(*__first, __result.second)) __result.second = *__first; 2837 } 2838 2839 __first++; 2840 } 2841 return __result; 2842 } 2843 2844 template<class _Tp> 2845 _LIBCPP_NODISCARD_EXT inline 2846 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2847 pair<_Tp, _Tp> 2848 minmax(initializer_list<_Tp> __t) 2849 { 2850 return _VSTD::minmax(__t, __less<_Tp>()); 2851 } 2852 2853 #endif // _LIBCPP_CXX03_LANG 2854 2855 // random_shuffle 2856 2857 // __independent_bits_engine 2858 2859 template <unsigned long long _Xp, size_t _Rp> 2860 struct __log2_imp 2861 { 2862 static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp 2863 : __log2_imp<_Xp, _Rp - 1>::value; 2864 }; 2865 2866 template <unsigned long long _Xp> 2867 struct __log2_imp<_Xp, 0> 2868 { 2869 static const size_t value = 0; 2870 }; 2871 2872 template <size_t _Rp> 2873 struct __log2_imp<0, _Rp> 2874 { 2875 static const size_t value = _Rp + 1; 2876 }; 2877 2878 template <class _UIntType, _UIntType _Xp> 2879 struct __log2 2880 { 2881 static const size_t value = __log2_imp<_Xp, 2882 sizeof(_UIntType) * __CHAR_BIT__ - 1>::value; 2883 }; 2884 2885 template<class _Engine, class _UIntType> 2886 class __independent_bits_engine 2887 { 2888 public: 2889 // types 2890 typedef _UIntType result_type; 2891 2892 private: 2893 typedef typename _Engine::result_type _Engine_result_type; 2894 typedef typename conditional 2895 < 2896 sizeof(_Engine_result_type) <= sizeof(result_type), 2897 result_type, 2898 _Engine_result_type 2899 >::type _Working_result_type; 2900 2901 _Engine& __e_; 2902 size_t __w_; 2903 size_t __w0_; 2904 size_t __n_; 2905 size_t __n0_; 2906 _Working_result_type __y0_; 2907 _Working_result_type __y1_; 2908 _Engine_result_type __mask0_; 2909 _Engine_result_type __mask1_; 2910 2911 #ifdef _LIBCPP_CXX03_LANG 2912 static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min 2913 + _Working_result_type(1); 2914 #else 2915 static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min() 2916 + _Working_result_type(1); 2917 #endif 2918 static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value; 2919 static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits; 2920 static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits; 2921 2922 public: 2923 // constructors and seeding functions 2924 __independent_bits_engine(_Engine& __e, size_t __w); 2925 2926 // generating functions 2927 result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());} 2928 2929 private: 2930 result_type __eval(false_type); 2931 result_type __eval(true_type); 2932 }; 2933 2934 template<class _Engine, class _UIntType> 2935 __independent_bits_engine<_Engine, _UIntType> 2936 ::__independent_bits_engine(_Engine& __e, size_t __w) 2937 : __e_(__e), 2938 __w_(__w) 2939 { 2940 __n_ = __w_ / __m + (__w_ % __m != 0); 2941 __w0_ = __w_ / __n_; 2942 if (_Rp == 0) 2943 __y0_ = _Rp; 2944 else if (__w0_ < _WDt) 2945 __y0_ = (_Rp >> __w0_) << __w0_; 2946 else 2947 __y0_ = 0; 2948 if (_Rp - __y0_ > __y0_ / __n_) 2949 { 2950 ++__n_; 2951 __w0_ = __w_ / __n_; 2952 if (__w0_ < _WDt) 2953 __y0_ = (_Rp >> __w0_) << __w0_; 2954 else 2955 __y0_ = 0; 2956 } 2957 __n0_ = __n_ - __w_ % __n_; 2958 if (__w0_ < _WDt - 1) 2959 __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1); 2960 else 2961 __y1_ = 0; 2962 __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) : 2963 _Engine_result_type(0); 2964 __mask1_ = __w0_ < _EDt - 1 ? 2965 _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) : 2966 _Engine_result_type(~0); 2967 } 2968 2969 template<class _Engine, class _UIntType> 2970 inline 2971 _UIntType 2972 __independent_bits_engine<_Engine, _UIntType>::__eval(false_type) 2973 { 2974 return static_cast<result_type>(__e_() & __mask0_); 2975 } 2976 2977 template<class _Engine, class _UIntType> 2978 _UIntType 2979 __independent_bits_engine<_Engine, _UIntType>::__eval(true_type) 2980 { 2981 const size_t _WRt = numeric_limits<result_type>::digits; 2982 result_type _Sp = 0; 2983 for (size_t __k = 0; __k < __n0_; ++__k) 2984 { 2985 _Engine_result_type __u; 2986 do 2987 { 2988 __u = __e_() - _Engine::min(); 2989 } while (__u >= __y0_); 2990 if (__w0_ < _WRt) 2991 _Sp <<= __w0_; 2992 else 2993 _Sp = 0; 2994 _Sp += __u & __mask0_; 2995 } 2996 for (size_t __k = __n0_; __k < __n_; ++__k) 2997 { 2998 _Engine_result_type __u; 2999 do 3000 { 3001 __u = __e_() - _Engine::min(); 3002 } while (__u >= __y1_); 3003 if (__w0_ < _WRt - 1) 3004 _Sp <<= __w0_ + 1; 3005 else 3006 _Sp = 0; 3007 _Sp += __u & __mask1_; 3008 } 3009 return _Sp; 3010 } 3011 3012 // uniform_int_distribution 3013 3014 template<class _IntType = int> 3015 class uniform_int_distribution 3016 { 3017 public: 3018 // types 3019 typedef _IntType result_type; 3020 3021 class param_type 3022 { 3023 result_type __a_; 3024 result_type __b_; 3025 public: 3026 typedef uniform_int_distribution distribution_type; 3027 3028 explicit param_type(result_type __a = 0, 3029 result_type __b = numeric_limits<result_type>::max()) 3030 : __a_(__a), __b_(__b) {} 3031 3032 result_type a() const {return __a_;} 3033 result_type b() const {return __b_;} 3034 3035 friend bool operator==(const param_type& __x, const param_type& __y) 3036 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;} 3037 friend bool operator!=(const param_type& __x, const param_type& __y) 3038 {return !(__x == __y);} 3039 }; 3040 3041 private: 3042 param_type __p_; 3043 3044 public: 3045 // constructors and reset functions 3046 #ifndef _LIBCPP_CXX03_LANG 3047 uniform_int_distribution() : uniform_int_distribution(0) {} 3048 explicit uniform_int_distribution( 3049 result_type __a, result_type __b = numeric_limits<result_type>::max()) 3050 : __p_(param_type(__a, __b)) {} 3051 #else 3052 explicit uniform_int_distribution( 3053 result_type __a = 0, 3054 result_type __b = numeric_limits<result_type>::max()) 3055 : __p_(param_type(__a, __b)) {} 3056 #endif 3057 explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {} 3058 void reset() {} 3059 3060 // generating functions 3061 template<class _URNG> result_type operator()(_URNG& __g) 3062 {return (*this)(__g, __p_);} 3063 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p); 3064 3065 // property functions 3066 result_type a() const {return __p_.a();} 3067 result_type b() const {return __p_.b();} 3068 3069 param_type param() const {return __p_;} 3070 void param(const param_type& __p) {__p_ = __p;} 3071 3072 result_type min() const {return a();} 3073 result_type max() const {return b();} 3074 3075 friend bool operator==(const uniform_int_distribution& __x, 3076 const uniform_int_distribution& __y) 3077 {return __x.__p_ == __y.__p_;} 3078 friend bool operator!=(const uniform_int_distribution& __x, 3079 const uniform_int_distribution& __y) 3080 {return !(__x == __y);} 3081 }; 3082 3083 template<class _IntType> 3084 template<class _URNG> 3085 typename uniform_int_distribution<_IntType>::result_type 3086 uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p) 3087 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 3088 { 3089 typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t), 3090 uint32_t, uint64_t>::type _UIntType; 3091 const _UIntType _Rp = _UIntType(__p.b()) - _UIntType(__p.a()) + _UIntType(1); 3092 if (_Rp == 1) 3093 return __p.a(); 3094 const size_t _Dt = numeric_limits<_UIntType>::digits; 3095 typedef __independent_bits_engine<_URNG, _UIntType> _Eng; 3096 if (_Rp == 0) 3097 return static_cast<result_type>(_Eng(__g, _Dt)()); 3098 size_t __w = _Dt - __libcpp_clz(_Rp) - 1; 3099 if ((_Rp & (numeric_limits<_UIntType>::max() >> (_Dt - __w))) != 0) 3100 ++__w; 3101 _Eng __e(__g, __w); 3102 _UIntType __u; 3103 do 3104 { 3105 __u = __e(); 3106 } while (__u >= _Rp); 3107 return static_cast<result_type>(__u + __p.a()); 3108 } 3109 3110 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \ 3111 || defined(_LIBCPP_BUILDING_LIBRARY) 3112 class _LIBCPP_TYPE_VIS __rs_default; 3113 3114 _LIBCPP_FUNC_VIS __rs_default __rs_get(); 3115 3116 class _LIBCPP_TYPE_VIS __rs_default 3117 { 3118 static unsigned __c_; 3119 3120 __rs_default(); 3121 public: 3122 typedef uint_fast32_t result_type; 3123 3124 static const result_type _Min = 0; 3125 static const result_type _Max = 0xFFFFFFFF; 3126 3127 __rs_default(const __rs_default&); 3128 ~__rs_default(); 3129 3130 result_type operator()(); 3131 3132 static _LIBCPP_CONSTEXPR result_type min() {return _Min;} 3133 static _LIBCPP_CONSTEXPR result_type max() {return _Max;} 3134 3135 friend _LIBCPP_FUNC_VIS __rs_default __rs_get(); 3136 }; 3137 3138 _LIBCPP_FUNC_VIS __rs_default __rs_get(); 3139 3140 template <class _RandomAccessIterator> 3141 _LIBCPP_DEPRECATED_IN_CXX14 void 3142 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 3143 { 3144 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 3145 typedef uniform_int_distribution<ptrdiff_t> _Dp; 3146 typedef typename _Dp::param_type _Pp; 3147 difference_type __d = __last - __first; 3148 if (__d > 1) 3149 { 3150 _Dp __uid; 3151 __rs_default __g = __rs_get(); 3152 for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d) 3153 { 3154 difference_type __i = __uid(__g, _Pp(0, __d)); 3155 if (__i != difference_type(0)) 3156 swap(*__first, *(__first + __i)); 3157 } 3158 } 3159 } 3160 3161 template <class _RandomAccessIterator, class _RandomNumberGenerator> 3162 _LIBCPP_DEPRECATED_IN_CXX14 void 3163 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 3164 #ifndef _LIBCPP_CXX03_LANG 3165 _RandomNumberGenerator&& __rand) 3166 #else 3167 _RandomNumberGenerator& __rand) 3168 #endif 3169 { 3170 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 3171 difference_type __d = __last - __first; 3172 if (__d > 1) 3173 { 3174 for (--__last; __first < __last; ++__first, (void) --__d) 3175 { 3176 difference_type __i = __rand(__d); 3177 if (__i != difference_type(0)) 3178 swap(*__first, *(__first + __i)); 3179 } 3180 } 3181 } 3182 #endif 3183 3184 template <class _PopulationIterator, class _SampleIterator, class _Distance, 3185 class _UniformRandomNumberGenerator> 3186 _LIBCPP_INLINE_VISIBILITY 3187 _SampleIterator __sample(_PopulationIterator __first, 3188 _PopulationIterator __last, _SampleIterator __output_iter, 3189 _Distance __n, 3190 _UniformRandomNumberGenerator & __g, 3191 input_iterator_tag) { 3192 3193 _Distance __k = 0; 3194 for (; __first != __last && __k < __n; ++__first, (void) ++__k) 3195 __output_iter[__k] = *__first; 3196 _Distance __sz = __k; 3197 for (; __first != __last; ++__first, (void) ++__k) { 3198 _Distance __r = uniform_int_distribution<_Distance>(0, __k)(__g); 3199 if (__r < __sz) 3200 __output_iter[__r] = *__first; 3201 } 3202 return __output_iter + _VSTD::min(__n, __k); 3203 } 3204 3205 template <class _PopulationIterator, class _SampleIterator, class _Distance, 3206 class _UniformRandomNumberGenerator> 3207 _LIBCPP_INLINE_VISIBILITY 3208 _SampleIterator __sample(_PopulationIterator __first, 3209 _PopulationIterator __last, _SampleIterator __output_iter, 3210 _Distance __n, 3211 _UniformRandomNumberGenerator& __g, 3212 forward_iterator_tag) { 3213 _Distance __unsampled_sz = _VSTD::distance(__first, __last); 3214 for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) { 3215 _Distance __r = uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g); 3216 if (__r < __n) { 3217 *__output_iter++ = *__first; 3218 --__n; 3219 } 3220 } 3221 return __output_iter; 3222 } 3223 3224 template <class _PopulationIterator, class _SampleIterator, class _Distance, 3225 class _UniformRandomNumberGenerator> 3226 _LIBCPP_INLINE_VISIBILITY 3227 _SampleIterator __sample(_PopulationIterator __first, 3228 _PopulationIterator __last, _SampleIterator __output_iter, 3229 _Distance __n, _UniformRandomNumberGenerator& __g) { 3230 typedef typename iterator_traits<_PopulationIterator>::iterator_category 3231 _PopCategory; 3232 typedef typename iterator_traits<_PopulationIterator>::difference_type 3233 _Difference; 3234 static_assert(__is_cpp17_forward_iterator<_PopulationIterator>::value || 3235 __is_cpp17_random_access_iterator<_SampleIterator>::value, 3236 "SampleIterator must meet the requirements of RandomAccessIterator"); 3237 typedef typename common_type<_Distance, _Difference>::type _CommonType; 3238 _LIBCPP_ASSERT(__n >= 0, "N must be a positive number."); 3239 return _VSTD::__sample( 3240 __first, __last, __output_iter, _CommonType(__n), 3241 __g, _PopCategory()); 3242 } 3243 3244 #if _LIBCPP_STD_VER > 14 3245 template <class _PopulationIterator, class _SampleIterator, class _Distance, 3246 class _UniformRandomNumberGenerator> 3247 inline _LIBCPP_INLINE_VISIBILITY 3248 _SampleIterator sample(_PopulationIterator __first, 3249 _PopulationIterator __last, _SampleIterator __output_iter, 3250 _Distance __n, _UniformRandomNumberGenerator&& __g) { 3251 return _VSTD::__sample(__first, __last, __output_iter, __n, __g); 3252 } 3253 #endif // _LIBCPP_STD_VER > 14 3254 3255 template<class _RandomAccessIterator, class _UniformRandomNumberGenerator> 3256 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 3257 _UniformRandomNumberGenerator&& __g) 3258 { 3259 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 3260 typedef uniform_int_distribution<ptrdiff_t> _Dp; 3261 typedef typename _Dp::param_type _Pp; 3262 difference_type __d = __last - __first; 3263 if (__d > 1) 3264 { 3265 _Dp __uid; 3266 for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d) 3267 { 3268 difference_type __i = __uid(__g, _Pp(0, __d)); 3269 if (__i != difference_type(0)) 3270 swap(*__first, *(__first + __i)); 3271 } 3272 } 3273 } 3274 3275 #if _LIBCPP_STD_VER > 17 3276 3277 // shift_left, shift_right 3278 3279 template <class _ForwardIterator> 3280 inline _LIBCPP_INLINE_VISIBILITY constexpr 3281 _ForwardIterator 3282 shift_left(_ForwardIterator __first, _ForwardIterator __last, 3283 typename iterator_traits<_ForwardIterator>::difference_type __n) 3284 { 3285 if (__n == 0) { 3286 return __last; 3287 } 3288 3289 _ForwardIterator __m = __first; 3290 if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value) { 3291 if (__n >= __last - __first) { 3292 return __first; 3293 } 3294 __m += __n; 3295 } else { 3296 for (; __n > 0; --__n) { 3297 if (__m == __last) { 3298 return __first; 3299 } 3300 ++__m; 3301 } 3302 } 3303 return _VSTD::move(__m, __last, __first); 3304 } 3305 3306 template <class _ForwardIterator> 3307 inline _LIBCPP_INLINE_VISIBILITY constexpr 3308 _ForwardIterator 3309 shift_right(_ForwardIterator __first, _ForwardIterator __last, 3310 typename iterator_traits<_ForwardIterator>::difference_type __n) 3311 { 3312 if (__n == 0) { 3313 return __first; 3314 } 3315 3316 if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value) { 3317 decltype(__n) __d = __last - __first; 3318 if (__n >= __d) { 3319 return __last; 3320 } 3321 _ForwardIterator __m = __first + (__d - __n); 3322 return _VSTD::move_backward(__first, __m, __last); 3323 } else if constexpr (__is_cpp17_bidirectional_iterator<_ForwardIterator>::value) { 3324 _ForwardIterator __m = __last; 3325 for (; __n > 0; --__n) { 3326 if (__m == __first) { 3327 return __last; 3328 } 3329 --__m; 3330 } 3331 return _VSTD::move_backward(__first, __m, __last); 3332 } else { 3333 _ForwardIterator __ret = __first; 3334 for (; __n > 0; --__n) { 3335 if (__ret == __last) { 3336 return __last; 3337 } 3338 ++__ret; 3339 } 3340 3341 // We have an __n-element scratch space from __first to __ret. 3342 // Slide an __n-element window [__trail, __lead) from left to right. 3343 // We're essentially doing swap_ranges(__first, __ret, __trail, __lead) 3344 // over and over; but once __lead reaches __last we needn't bother 3345 // to save the values of elements [__trail, __last). 3346 3347 auto __trail = __first; 3348 auto __lead = __ret; 3349 while (__trail != __ret) { 3350 if (__lead == __last) { 3351 _VSTD::move(__first, __trail, __ret); 3352 return __ret; 3353 } 3354 ++__trail; 3355 ++__lead; 3356 } 3357 3358 _ForwardIterator __mid = __first; 3359 while (true) { 3360 if (__lead == __last) { 3361 __trail = _VSTD::move(__mid, __ret, __trail); 3362 _VSTD::move(__first, __mid, __trail); 3363 return __ret; 3364 } 3365 swap(*__mid, *__trail); 3366 ++__mid; 3367 ++__trail; 3368 ++__lead; 3369 if (__mid == __ret) { 3370 __mid = __first; 3371 } 3372 } 3373 } 3374 } 3375 3376 #endif // _LIBCPP_STD_VER > 17 3377 3378 // is_partitioned 3379 3380 template <class _InputIterator, class _Predicate> 3381 _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool 3382 is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred) 3383 { 3384 for (; __first != __last; ++__first) 3385 if (!__pred(*__first)) 3386 break; 3387 if ( __first == __last ) 3388 return true; 3389 ++__first; 3390 for (; __first != __last; ++__first) 3391 if (__pred(*__first)) 3392 return false; 3393 return true; 3394 } 3395 3396 // partition 3397 3398 template <class _Predicate, class _ForwardIterator> 3399 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 3400 __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag) 3401 { 3402 while (true) 3403 { 3404 if (__first == __last) 3405 return __first; 3406 if (!__pred(*__first)) 3407 break; 3408 ++__first; 3409 } 3410 for (_ForwardIterator __p = __first; ++__p != __last;) 3411 { 3412 if (__pred(*__p)) 3413 { 3414 swap(*__first, *__p); 3415 ++__first; 3416 } 3417 } 3418 return __first; 3419 } 3420 3421 template <class _Predicate, class _BidirectionalIterator> 3422 _LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator 3423 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 3424 bidirectional_iterator_tag) 3425 { 3426 while (true) 3427 { 3428 while (true) 3429 { 3430 if (__first == __last) 3431 return __first; 3432 if (!__pred(*__first)) 3433 break; 3434 ++__first; 3435 } 3436 do 3437 { 3438 if (__first == --__last) 3439 return __first; 3440 } while (!__pred(*__last)); 3441 swap(*__first, *__last); 3442 ++__first; 3443 } 3444 } 3445 3446 template <class _ForwardIterator, class _Predicate> 3447 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 3448 _ForwardIterator 3449 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 3450 { 3451 return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type> 3452 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); 3453 } 3454 3455 // partition_copy 3456 3457 template <class _InputIterator, class _OutputIterator1, 3458 class _OutputIterator2, class _Predicate> 3459 _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_OutputIterator1, _OutputIterator2> 3460 partition_copy(_InputIterator __first, _InputIterator __last, 3461 _OutputIterator1 __out_true, _OutputIterator2 __out_false, 3462 _Predicate __pred) 3463 { 3464 for (; __first != __last; ++__first) 3465 { 3466 if (__pred(*__first)) 3467 { 3468 *__out_true = *__first; 3469 ++__out_true; 3470 } 3471 else 3472 { 3473 *__out_false = *__first; 3474 ++__out_false; 3475 } 3476 } 3477 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false); 3478 } 3479 3480 // partition_point 3481 3482 template<class _ForwardIterator, class _Predicate> 3483 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 3484 partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 3485 { 3486 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 3487 difference_type __len = _VSTD::distance(__first, __last); 3488 while (__len != 0) 3489 { 3490 difference_type __l2 = _VSTD::__half_positive(__len); 3491 _ForwardIterator __m = __first; 3492 _VSTD::advance(__m, __l2); 3493 if (__pred(*__m)) 3494 { 3495 __first = ++__m; 3496 __len -= __l2 + 1; 3497 } 3498 else 3499 __len = __l2; 3500 } 3501 return __first; 3502 } 3503 3504 // stable_partition 3505 3506 template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair> 3507 _ForwardIterator 3508 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, 3509 _Distance __len, _Pair __p, forward_iterator_tag __fit) 3510 { 3511 // *__first is known to be false 3512 // __len >= 1 3513 if (__len == 1) 3514 return __first; 3515 if (__len == 2) 3516 { 3517 _ForwardIterator __m = __first; 3518 if (__pred(*++__m)) 3519 { 3520 swap(*__first, *__m); 3521 return __m; 3522 } 3523 return __first; 3524 } 3525 if (__len <= __p.second) 3526 { // The buffer is big enough to use 3527 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 3528 __destruct_n __d(0); 3529 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); 3530 // Move the falses into the temporary buffer, and the trues to the front of the line 3531 // Update __first to always point to the end of the trues 3532 value_type* __t = __p.first; 3533 ::new ((void*)__t) value_type(_VSTD::move(*__first)); 3534 __d.template __incr<value_type>(); 3535 ++__t; 3536 _ForwardIterator __i = __first; 3537 while (++__i != __last) 3538 { 3539 if (__pred(*__i)) 3540 { 3541 *__first = _VSTD::move(*__i); 3542 ++__first; 3543 } 3544 else 3545 { 3546 ::new ((void*)__t) value_type(_VSTD::move(*__i)); 3547 __d.template __incr<value_type>(); 3548 ++__t; 3549 } 3550 } 3551 // All trues now at start of range, all falses in buffer 3552 // Move falses back into range, but don't mess up __first which points to first false 3553 __i = __first; 3554 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i) 3555 *__i = _VSTD::move(*__t2); 3556 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer 3557 return __first; 3558 } 3559 // Else not enough buffer, do in place 3560 // __len >= 3 3561 _ForwardIterator __m = __first; 3562 _Distance __len2 = __len / 2; // __len2 >= 2 3563 _VSTD::advance(__m, __len2); 3564 // recurse on [__first, __m), *__first know to be false 3565 // F????????????????? 3566 // f m l 3567 typedef typename add_lvalue_reference<_Predicate>::type _PredRef; 3568 _ForwardIterator __first_false = _VSTD::__stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit); 3569 // TTTFFFFF?????????? 3570 // f ff m l 3571 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true 3572 _ForwardIterator __m1 = __m; 3573 _ForwardIterator __second_false = __last; 3574 _Distance __len_half = __len - __len2; 3575 while (__pred(*__m1)) 3576 { 3577 if (++__m1 == __last) 3578 goto __second_half_done; 3579 --__len_half; 3580 } 3581 // TTTFFFFFTTTF?????? 3582 // f ff m m1 l 3583 __second_false = _VSTD::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit); 3584 __second_half_done: 3585 // TTTFFFFFTTTTTFFFFF 3586 // f ff m sf l 3587 return _VSTD::rotate(__first_false, __m, __second_false); 3588 // TTTTTTTTFFFFFFFFFF 3589 // | 3590 } 3591 3592 struct __return_temporary_buffer 3593 { 3594 template <class _Tp> 3595 _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);} 3596 }; 3597 3598 template <class _Predicate, class _ForwardIterator> 3599 _ForwardIterator 3600 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, 3601 forward_iterator_tag) 3602 { 3603 const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment 3604 // Either prove all true and return __first or point to first false 3605 while (true) 3606 { 3607 if (__first == __last) 3608 return __first; 3609 if (!__pred(*__first)) 3610 break; 3611 ++__first; 3612 } 3613 // We now have a reduced range [__first, __last) 3614 // *__first is known to be false 3615 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 3616 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 3617 difference_type __len = _VSTD::distance(__first, __last); 3618 pair<value_type*, ptrdiff_t> __p(0, 0); 3619 unique_ptr<value_type, __return_temporary_buffer> __h; 3620 if (__len >= __alloc_limit) 3621 { 3622 __p = _VSTD::get_temporary_buffer<value_type>(__len); 3623 __h.reset(__p.first); 3624 } 3625 return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type> 3626 (__first, __last, __pred, __len, __p, forward_iterator_tag()); 3627 } 3628 3629 template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair> 3630 _BidirectionalIterator 3631 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 3632 _Distance __len, _Pair __p, bidirectional_iterator_tag __bit) 3633 { 3634 // *__first is known to be false 3635 // *__last is known to be true 3636 // __len >= 2 3637 if (__len == 2) 3638 { 3639 swap(*__first, *__last); 3640 return __last; 3641 } 3642 if (__len == 3) 3643 { 3644 _BidirectionalIterator __m = __first; 3645 if (__pred(*++__m)) 3646 { 3647 swap(*__first, *__m); 3648 swap(*__m, *__last); 3649 return __last; 3650 } 3651 swap(*__m, *__last); 3652 swap(*__first, *__m); 3653 return __m; 3654 } 3655 if (__len <= __p.second) 3656 { // The buffer is big enough to use 3657 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 3658 __destruct_n __d(0); 3659 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); 3660 // Move the falses into the temporary buffer, and the trues to the front of the line 3661 // Update __first to always point to the end of the trues 3662 value_type* __t = __p.first; 3663 ::new ((void*)__t) value_type(_VSTD::move(*__first)); 3664 __d.template __incr<value_type>(); 3665 ++__t; 3666 _BidirectionalIterator __i = __first; 3667 while (++__i != __last) 3668 { 3669 if (__pred(*__i)) 3670 { 3671 *__first = _VSTD::move(*__i); 3672 ++__first; 3673 } 3674 else 3675 { 3676 ::new ((void*)__t) value_type(_VSTD::move(*__i)); 3677 __d.template __incr<value_type>(); 3678 ++__t; 3679 } 3680 } 3681 // move *__last, known to be true 3682 *__first = _VSTD::move(*__i); 3683 __i = ++__first; 3684 // All trues now at start of range, all falses in buffer 3685 // Move falses back into range, but don't mess up __first which points to first false 3686 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i) 3687 *__i = _VSTD::move(*__t2); 3688 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer 3689 return __first; 3690 } 3691 // Else not enough buffer, do in place 3692 // __len >= 4 3693 _BidirectionalIterator __m = __first; 3694 _Distance __len2 = __len / 2; // __len2 >= 2 3695 _VSTD::advance(__m, __len2); 3696 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false 3697 // F????????????????T 3698 // f m l 3699 _BidirectionalIterator __m1 = __m; 3700 _BidirectionalIterator __first_false = __first; 3701 _Distance __len_half = __len2; 3702 while (!__pred(*--__m1)) 3703 { 3704 if (__m1 == __first) 3705 goto __first_half_done; 3706 --__len_half; 3707 } 3708 // F???TFFF?????????T 3709 // f m1 m l 3710 typedef typename add_lvalue_reference<_Predicate>::type _PredRef; 3711 __first_false = _VSTD::__stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit); 3712 __first_half_done: 3713 // TTTFFFFF?????????T 3714 // f ff m l 3715 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true 3716 __m1 = __m; 3717 _BidirectionalIterator __second_false = __last; 3718 ++__second_false; 3719 __len_half = __len - __len2; 3720 while (__pred(*__m1)) 3721 { 3722 if (++__m1 == __last) 3723 goto __second_half_done; 3724 --__len_half; 3725 } 3726 // TTTFFFFFTTTF?????T 3727 // f ff m m1 l 3728 __second_false = _VSTD::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit); 3729 __second_half_done: 3730 // TTTFFFFFTTTTTFFFFF 3731 // f ff m sf l 3732 return _VSTD::rotate(__first_false, __m, __second_false); 3733 // TTTTTTTTFFFFFFFFFF 3734 // | 3735 } 3736 3737 template <class _Predicate, class _BidirectionalIterator> 3738 _BidirectionalIterator 3739 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 3740 bidirectional_iterator_tag) 3741 { 3742 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 3743 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 3744 const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment 3745 // Either prove all true and return __first or point to first false 3746 while (true) 3747 { 3748 if (__first == __last) 3749 return __first; 3750 if (!__pred(*__first)) 3751 break; 3752 ++__first; 3753 } 3754 // __first points to first false, everything prior to __first is already set. 3755 // Either prove [__first, __last) is all false and return __first, or point __last to last true 3756 do 3757 { 3758 if (__first == --__last) 3759 return __first; 3760 } while (!__pred(*__last)); 3761 // We now have a reduced range [__first, __last] 3762 // *__first is known to be false 3763 // *__last is known to be true 3764 // __len >= 2 3765 difference_type __len = _VSTD::distance(__first, __last) + 1; 3766 pair<value_type*, ptrdiff_t> __p(0, 0); 3767 unique_ptr<value_type, __return_temporary_buffer> __h; 3768 if (__len >= __alloc_limit) 3769 { 3770 __p = _VSTD::get_temporary_buffer<value_type>(__len); 3771 __h.reset(__p.first); 3772 } 3773 return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type> 3774 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag()); 3775 } 3776 3777 template <class _ForwardIterator, class _Predicate> 3778 inline _LIBCPP_INLINE_VISIBILITY 3779 _ForwardIterator 3780 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 3781 { 3782 return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type> 3783 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); 3784 } 3785 3786 // is_sorted_until 3787 3788 template <class _ForwardIterator, class _Compare> 3789 _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 3790 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 3791 { 3792 if (__first != __last) 3793 { 3794 _ForwardIterator __i = __first; 3795 while (++__i != __last) 3796 { 3797 if (__comp(*__i, *__first)) 3798 return __i; 3799 __first = __i; 3800 } 3801 } 3802 return __last; 3803 } 3804 3805 template<class _ForwardIterator> 3806 _LIBCPP_NODISCARD_EXT inline 3807 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 3808 _ForwardIterator 3809 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) 3810 { 3811 return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); 3812 } 3813 3814 // is_sorted 3815 3816 template <class _ForwardIterator, class _Compare> 3817 _LIBCPP_NODISCARD_EXT inline 3818 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 3819 bool 3820 is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 3821 { 3822 return _VSTD::is_sorted_until(__first, __last, __comp) == __last; 3823 } 3824 3825 template<class _ForwardIterator> 3826 _LIBCPP_NODISCARD_EXT inline 3827 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 3828 bool 3829 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 3830 { 3831 return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); 3832 } 3833 3834 // sort 3835 3836 // stable, 2-3 compares, 0-2 swaps 3837 3838 template <class _Compare, class _ForwardIterator> 3839 _LIBCPP_CONSTEXPR_AFTER_CXX11 unsigned 3840 __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c) 3841 { 3842 unsigned __r = 0; 3843 if (!__c(*__y, *__x)) // if x <= y 3844 { 3845 if (!__c(*__z, *__y)) // if y <= z 3846 return __r; // x <= y && y <= z 3847 // x <= y && y > z 3848 swap(*__y, *__z); // x <= z && y < z 3849 __r = 1; 3850 if (__c(*__y, *__x)) // if x > y 3851 { 3852 swap(*__x, *__y); // x < y && y <= z 3853 __r = 2; 3854 } 3855 return __r; // x <= y && y < z 3856 } 3857 if (__c(*__z, *__y)) // x > y, if y > z 3858 { 3859 swap(*__x, *__z); // x < y && y < z 3860 __r = 1; 3861 return __r; 3862 } 3863 swap(*__x, *__y); // x > y && y <= z 3864 __r = 1; // x < y && x <= z 3865 if (__c(*__z, *__y)) // if y > z 3866 { 3867 swap(*__y, *__z); // x <= y && y < z 3868 __r = 2; 3869 } 3870 return __r; 3871 } // x <= y && y <= z 3872 3873 // stable, 3-6 compares, 0-5 swaps 3874 3875 template <class _Compare, class _ForwardIterator> 3876 unsigned 3877 __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 3878 _ForwardIterator __x4, _Compare __c) 3879 { 3880 unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c); 3881 if (__c(*__x4, *__x3)) 3882 { 3883 swap(*__x3, *__x4); 3884 ++__r; 3885 if (__c(*__x3, *__x2)) 3886 { 3887 swap(*__x2, *__x3); 3888 ++__r; 3889 if (__c(*__x2, *__x1)) 3890 { 3891 swap(*__x1, *__x2); 3892 ++__r; 3893 } 3894 } 3895 } 3896 return __r; 3897 } 3898 3899 // stable, 4-10 compares, 0-9 swaps 3900 3901 template <class _Compare, class _ForwardIterator> 3902 _LIBCPP_HIDDEN 3903 unsigned 3904 __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 3905 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) 3906 { 3907 unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c); 3908 if (__c(*__x5, *__x4)) 3909 { 3910 swap(*__x4, *__x5); 3911 ++__r; 3912 if (__c(*__x4, *__x3)) 3913 { 3914 swap(*__x3, *__x4); 3915 ++__r; 3916 if (__c(*__x3, *__x2)) 3917 { 3918 swap(*__x2, *__x3); 3919 ++__r; 3920 if (__c(*__x2, *__x1)) 3921 { 3922 swap(*__x1, *__x2); 3923 ++__r; 3924 } 3925 } 3926 } 3927 } 3928 return __r; 3929 } 3930 3931 // Assumes size > 0 3932 template <class _Compare, class _BidirectionalIterator> 3933 _LIBCPP_CONSTEXPR_AFTER_CXX11 void 3934 __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 3935 { 3936 _BidirectionalIterator __lm1 = __last; 3937 for (--__lm1; __first != __lm1; ++__first) 3938 { 3939 _BidirectionalIterator __i = _VSTD::min_element<_BidirectionalIterator, 3940 typename add_lvalue_reference<_Compare>::type> 3941 (__first, __last, __comp); 3942 if (__i != __first) 3943 swap(*__first, *__i); 3944 } 3945 } 3946 3947 template <class _Compare, class _BidirectionalIterator> 3948 void 3949 __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 3950 { 3951 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 3952 if (__first != __last) 3953 { 3954 _BidirectionalIterator __i = __first; 3955 for (++__i; __i != __last; ++__i) 3956 { 3957 _BidirectionalIterator __j = __i; 3958 value_type __t(_VSTD::move(*__j)); 3959 for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j) 3960 *__j = _VSTD::move(*__k); 3961 *__j = _VSTD::move(__t); 3962 } 3963 } 3964 } 3965 3966 template <class _Compare, class _RandomAccessIterator> 3967 void 3968 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 3969 { 3970 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 3971 _RandomAccessIterator __j = __first+2; 3972 _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp); 3973 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) 3974 { 3975 if (__comp(*__i, *__j)) 3976 { 3977 value_type __t(_VSTD::move(*__i)); 3978 _RandomAccessIterator __k = __j; 3979 __j = __i; 3980 do 3981 { 3982 *__j = _VSTD::move(*__k); 3983 __j = __k; 3984 } while (__j != __first && __comp(__t, *--__k)); 3985 *__j = _VSTD::move(__t); 3986 } 3987 __j = __i; 3988 } 3989 } 3990 3991 template <class _Compare, class _RandomAccessIterator> 3992 bool 3993 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 3994 { 3995 switch (__last - __first) 3996 { 3997 case 0: 3998 case 1: 3999 return true; 4000 case 2: 4001 if (__comp(*--__last, *__first)) 4002 swap(*__first, *__last); 4003 return true; 4004 case 3: 4005 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); 4006 return true; 4007 case 4: 4008 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); 4009 return true; 4010 case 5: 4011 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); 4012 return true; 4013 } 4014 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4015 _RandomAccessIterator __j = __first+2; 4016 _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp); 4017 const unsigned __limit = 8; 4018 unsigned __count = 0; 4019 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) 4020 { 4021 if (__comp(*__i, *__j)) 4022 { 4023 value_type __t(_VSTD::move(*__i)); 4024 _RandomAccessIterator __k = __j; 4025 __j = __i; 4026 do 4027 { 4028 *__j = _VSTD::move(*__k); 4029 __j = __k; 4030 } while (__j != __first && __comp(__t, *--__k)); 4031 *__j = _VSTD::move(__t); 4032 if (++__count == __limit) 4033 return ++__i == __last; 4034 } 4035 __j = __i; 4036 } 4037 return true; 4038 } 4039 4040 template <class _Compare, class _BidirectionalIterator> 4041 void 4042 __insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1, 4043 typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp) 4044 { 4045 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 4046 if (__first1 != __last1) 4047 { 4048 __destruct_n __d(0); 4049 unique_ptr<value_type, __destruct_n&> __h(__first2, __d); 4050 value_type* __last2 = __first2; 4051 ::new ((void*)__last2) value_type(_VSTD::move(*__first1)); 4052 __d.template __incr<value_type>(); 4053 for (++__last2; ++__first1 != __last1; ++__last2) 4054 { 4055 value_type* __j2 = __last2; 4056 value_type* __i2 = __j2; 4057 if (__comp(*__first1, *--__i2)) 4058 { 4059 ::new ((void*)__j2) value_type(_VSTD::move(*__i2)); 4060 __d.template __incr<value_type>(); 4061 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) 4062 *__j2 = _VSTD::move(*__i2); 4063 *__j2 = _VSTD::move(*__first1); 4064 } 4065 else 4066 { 4067 ::new ((void*)__j2) value_type(_VSTD::move(*__first1)); 4068 __d.template __incr<value_type>(); 4069 } 4070 } 4071 __h.release(); 4072 } 4073 } 4074 4075 template <class _Compare, class _RandomAccessIterator> 4076 void 4077 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4078 { 4079 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4080 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4081 const difference_type __limit = is_trivially_copy_constructible<value_type>::value && 4082 is_trivially_copy_assignable<value_type>::value ? 30 : 6; 4083 while (true) 4084 { 4085 __restart: 4086 difference_type __len = __last - __first; 4087 switch (__len) 4088 { 4089 case 0: 4090 case 1: 4091 return; 4092 case 2: 4093 if (__comp(*--__last, *__first)) 4094 swap(*__first, *__last); 4095 return; 4096 case 3: 4097 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); 4098 return; 4099 case 4: 4100 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); 4101 return; 4102 case 5: 4103 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); 4104 return; 4105 } 4106 if (__len <= __limit) 4107 { 4108 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); 4109 return; 4110 } 4111 // __len > 5 4112 _RandomAccessIterator __m = __first; 4113 _RandomAccessIterator __lm1 = __last; 4114 --__lm1; 4115 unsigned __n_swaps; 4116 { 4117 difference_type __delta; 4118 if (__len >= 1000) 4119 { 4120 __delta = __len/2; 4121 __m += __delta; 4122 __delta /= 2; 4123 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp); 4124 } 4125 else 4126 { 4127 __delta = __len/2; 4128 __m += __delta; 4129 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); 4130 } 4131 } 4132 // *__m is median 4133 // partition [__first, __m) < *__m and *__m <= [__m, __last) 4134 // (this inhibits tossing elements equivalent to __m around unnecessarily) 4135 _RandomAccessIterator __i = __first; 4136 _RandomAccessIterator __j = __lm1; 4137 // j points beyond range to be tested, *__m is known to be <= *__lm1 4138 // The search going up is known to be guarded but the search coming down isn't. 4139 // Prime the downward search with a guard. 4140 if (!__comp(*__i, *__m)) // if *__first == *__m 4141 { 4142 // *__first == *__m, *__first doesn't go in first part 4143 // manually guard downward moving __j against __i 4144 while (true) 4145 { 4146 if (__i == --__j) 4147 { 4148 // *__first == *__m, *__m <= all other elements 4149 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) 4150 ++__i; // __first + 1 4151 __j = __last; 4152 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) 4153 { 4154 while (true) 4155 { 4156 if (__i == __j) 4157 return; // [__first, __last) all equivalent elements 4158 if (__comp(*__first, *__i)) 4159 { 4160 swap(*__i, *__j); 4161 ++__n_swaps; 4162 ++__i; 4163 break; 4164 } 4165 ++__i; 4166 } 4167 } 4168 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 4169 if (__i == __j) 4170 return; 4171 while (true) 4172 { 4173 while (!__comp(*__first, *__i)) 4174 ++__i; 4175 while (__comp(*__first, *--__j)) 4176 ; 4177 if (__i >= __j) 4178 break; 4179 swap(*__i, *__j); 4180 ++__n_swaps; 4181 ++__i; 4182 } 4183 // [__first, __i) == *__first and *__first < [__i, __last) 4184 // The first part is sorted, sort the second part 4185 // _VSTD::__sort<_Compare>(__i, __last, __comp); 4186 __first = __i; 4187 goto __restart; 4188 } 4189 if (__comp(*__j, *__m)) 4190 { 4191 swap(*__i, *__j); 4192 ++__n_swaps; 4193 break; // found guard for downward moving __j, now use unguarded partition 4194 } 4195 } 4196 } 4197 // It is known that *__i < *__m 4198 ++__i; 4199 // j points beyond range to be tested, *__m is known to be <= *__lm1 4200 // if not yet partitioned... 4201 if (__i < __j) 4202 { 4203 // known that *(__i - 1) < *__m 4204 // known that __i <= __m 4205 while (true) 4206 { 4207 // __m still guards upward moving __i 4208 while (__comp(*__i, *__m)) 4209 ++__i; 4210 // It is now known that a guard exists for downward moving __j 4211 while (!__comp(*--__j, *__m)) 4212 ; 4213 if (__i > __j) 4214 break; 4215 swap(*__i, *__j); 4216 ++__n_swaps; 4217 // It is known that __m != __j 4218 // If __m just moved, follow it 4219 if (__m == __i) 4220 __m = __j; 4221 ++__i; 4222 } 4223 } 4224 // [__first, __i) < *__m and *__m <= [__i, __last) 4225 if (__i != __m && __comp(*__m, *__i)) 4226 { 4227 swap(*__i, *__m); 4228 ++__n_swaps; 4229 } 4230 // [__first, __i) < *__i and *__i <= [__i+1, __last) 4231 // If we were given a perfect partition, see if insertion sort is quick... 4232 if (__n_swaps == 0) 4233 { 4234 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); 4235 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp)) 4236 { 4237 if (__fs) 4238 return; 4239 __last = __i; 4240 continue; 4241 } 4242 else 4243 { 4244 if (__fs) 4245 { 4246 __first = ++__i; 4247 continue; 4248 } 4249 } 4250 } 4251 // sort smaller range with recursive call and larger with tail recursion elimination 4252 if (__i - __first < __last - __i) 4253 { 4254 _VSTD::__sort<_Compare>(__first, __i, __comp); 4255 // _VSTD::__sort<_Compare>(__i+1, __last, __comp); 4256 __first = ++__i; 4257 } 4258 else 4259 { 4260 _VSTD::__sort<_Compare>(__i+1, __last, __comp); 4261 // _VSTD::__sort<_Compare>(__first, __i, __comp); 4262 __last = __i; 4263 } 4264 } 4265 } 4266 4267 template <class _Compare, class _Tp> 4268 inline _LIBCPP_INLINE_VISIBILITY 4269 void 4270 __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) 4271 { 4272 __less<uintptr_t> __comp; 4273 _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp); 4274 } 4275 4276 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&)) 4277 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) 4278 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) 4279 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) 4280 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&)) 4281 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) 4282 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&)) 4283 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) 4284 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&)) 4285 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) 4286 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) 4287 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&)) 4288 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&)) 4289 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&)) 4290 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) 4291 4292 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&)) 4293 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) 4294 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) 4295 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) 4296 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&)) 4297 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) 4298 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&)) 4299 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) 4300 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&)) 4301 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) 4302 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) 4303 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&)) 4304 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&)) 4305 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&)) 4306 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) 4307 4308 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&)) 4309 4310 // lower_bound 4311 4312 template <class _Compare, class _ForwardIterator, class _Tp> 4313 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 4314 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4315 { 4316 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 4317 difference_type __len = _VSTD::distance(__first, __last); 4318 while (__len != 0) 4319 { 4320 difference_type __l2 = _VSTD::__half_positive(__len); 4321 _ForwardIterator __m = __first; 4322 _VSTD::advance(__m, __l2); 4323 if (__comp(*__m, __value_)) 4324 { 4325 __first = ++__m; 4326 __len -= __l2 + 1; 4327 } 4328 else 4329 __len = __l2; 4330 } 4331 return __first; 4332 } 4333 4334 template <class _ForwardIterator, class _Tp, class _Compare> 4335 _LIBCPP_NODISCARD_EXT inline 4336 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4337 _ForwardIterator 4338 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4339 { 4340 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4341 return _VSTD::__lower_bound<_Comp_ref>(__first, __last, __value_, __comp); 4342 } 4343 4344 template <class _ForwardIterator, class _Tp> 4345 _LIBCPP_NODISCARD_EXT inline 4346 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4347 _ForwardIterator 4348 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4349 { 4350 return _VSTD::lower_bound(__first, __last, __value_, 4351 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 4352 } 4353 4354 // upper_bound 4355 4356 template <class _Compare, class _ForwardIterator, class _Tp> 4357 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 4358 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4359 { 4360 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 4361 difference_type __len = _VSTD::distance(__first, __last); 4362 while (__len != 0) 4363 { 4364 difference_type __l2 = _VSTD::__half_positive(__len); 4365 _ForwardIterator __m = __first; 4366 _VSTD::advance(__m, __l2); 4367 if (__comp(__value_, *__m)) 4368 __len = __l2; 4369 else 4370 { 4371 __first = ++__m; 4372 __len -= __l2 + 1; 4373 } 4374 } 4375 return __first; 4376 } 4377 4378 template <class _ForwardIterator, class _Tp, class _Compare> 4379 _LIBCPP_NODISCARD_EXT inline 4380 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4381 _ForwardIterator 4382 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4383 { 4384 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4385 return _VSTD::__upper_bound<_Comp_ref>(__first, __last, __value_, __comp); 4386 } 4387 4388 template <class _ForwardIterator, class _Tp> 4389 _LIBCPP_NODISCARD_EXT inline 4390 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4391 _ForwardIterator 4392 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4393 { 4394 return _VSTD::upper_bound(__first, __last, __value_, 4395 __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>()); 4396 } 4397 4398 // equal_range 4399 4400 template <class _Compare, class _ForwardIterator, class _Tp> 4401 _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator> 4402 __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4403 { 4404 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 4405 difference_type __len = _VSTD::distance(__first, __last); 4406 while (__len != 0) 4407 { 4408 difference_type __l2 = _VSTD::__half_positive(__len); 4409 _ForwardIterator __m = __first; 4410 _VSTD::advance(__m, __l2); 4411 if (__comp(*__m, __value_)) 4412 { 4413 __first = ++__m; 4414 __len -= __l2 + 1; 4415 } 4416 else if (__comp(__value_, *__m)) 4417 { 4418 __last = __m; 4419 __len = __l2; 4420 } 4421 else 4422 { 4423 _ForwardIterator __mp1 = __m; 4424 return pair<_ForwardIterator, _ForwardIterator> 4425 ( 4426 _VSTD::__lower_bound<_Compare>(__first, __m, __value_, __comp), 4427 _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value_, __comp) 4428 ); 4429 } 4430 } 4431 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 4432 } 4433 4434 template <class _ForwardIterator, class _Tp, class _Compare> 4435 _LIBCPP_NODISCARD_EXT inline 4436 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4437 pair<_ForwardIterator, _ForwardIterator> 4438 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4439 { 4440 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4441 return _VSTD::__equal_range<_Comp_ref>(__first, __last, __value_, __comp); 4442 } 4443 4444 template <class _ForwardIterator, class _Tp> 4445 _LIBCPP_NODISCARD_EXT inline 4446 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4447 pair<_ForwardIterator, _ForwardIterator> 4448 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4449 { 4450 return _VSTD::equal_range(__first, __last, __value_, 4451 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 4452 } 4453 4454 // binary_search 4455 4456 template <class _Compare, class _ForwardIterator, class _Tp> 4457 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4458 bool 4459 __binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4460 { 4461 __first = _VSTD::__lower_bound<_Compare>(__first, __last, __value_, __comp); 4462 return __first != __last && !__comp(__value_, *__first); 4463 } 4464 4465 template <class _ForwardIterator, class _Tp, class _Compare> 4466 _LIBCPP_NODISCARD_EXT inline 4467 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4468 bool 4469 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4470 { 4471 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4472 return _VSTD::__binary_search<_Comp_ref>(__first, __last, __value_, __comp); 4473 } 4474 4475 template <class _ForwardIterator, class _Tp> 4476 _LIBCPP_NODISCARD_EXT inline 4477 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4478 bool 4479 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4480 { 4481 return _VSTD::binary_search(__first, __last, __value_, 4482 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 4483 } 4484 4485 // merge 4486 4487 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 4488 _LIBCPP_CONSTEXPR_AFTER_CXX17 4489 _OutputIterator 4490 __merge(_InputIterator1 __first1, _InputIterator1 __last1, 4491 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 4492 { 4493 for (; __first1 != __last1; ++__result) 4494 { 4495 if (__first2 == __last2) 4496 return _VSTD::copy(__first1, __last1, __result); 4497 if (__comp(*__first2, *__first1)) 4498 { 4499 *__result = *__first2; 4500 ++__first2; 4501 } 4502 else 4503 { 4504 *__result = *__first1; 4505 ++__first1; 4506 } 4507 } 4508 return _VSTD::copy(__first2, __last2, __result); 4509 } 4510 4511 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 4512 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4513 _OutputIterator 4514 merge(_InputIterator1 __first1, _InputIterator1 __last1, 4515 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 4516 { 4517 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4518 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 4519 } 4520 4521 template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 4522 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4523 _OutputIterator 4524 merge(_InputIterator1 __first1, _InputIterator1 __last1, 4525 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 4526 { 4527 typedef typename iterator_traits<_InputIterator1>::value_type __v1; 4528 typedef typename iterator_traits<_InputIterator2>::value_type __v2; 4529 return _VSTD::merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>()); 4530 } 4531 4532 // inplace_merge 4533 4534 template <class _Compare, class _InputIterator1, class _InputIterator2, 4535 class _OutputIterator> 4536 void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1, 4537 _InputIterator2 __first2, _InputIterator2 __last2, 4538 _OutputIterator __result, _Compare __comp) 4539 { 4540 for (; __first1 != __last1; ++__result) 4541 { 4542 if (__first2 == __last2) 4543 { 4544 _VSTD::move(__first1, __last1, __result); 4545 return; 4546 } 4547 4548 if (__comp(*__first2, *__first1)) 4549 { 4550 *__result = _VSTD::move(*__first2); 4551 ++__first2; 4552 } 4553 else 4554 { 4555 *__result = _VSTD::move(*__first1); 4556 ++__first1; 4557 } 4558 } 4559 // __first2 through __last2 are already in the right spot. 4560 } 4561 4562 template <class _Compare, class _BidirectionalIterator> 4563 void 4564 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4565 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, 4566 typename iterator_traits<_BidirectionalIterator>::difference_type __len2, 4567 typename iterator_traits<_BidirectionalIterator>::value_type* __buff) 4568 { 4569 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 4570 __destruct_n __d(0); 4571 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); 4572 if (__len1 <= __len2) 4573 { 4574 value_type* __p = __buff; 4575 for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p) 4576 ::new ((void*)__p) value_type(_VSTD::move(*__i)); 4577 _VSTD::__half_inplace_merge<_Compare>(__buff, __p, __middle, __last, __first, __comp); 4578 } 4579 else 4580 { 4581 value_type* __p = __buff; 4582 for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p) 4583 ::new ((void*)__p) value_type(_VSTD::move(*__i)); 4584 typedef reverse_iterator<_BidirectionalIterator> _RBi; 4585 typedef reverse_iterator<value_type*> _Rv; 4586 typedef __invert<_Compare> _Inverted; 4587 _VSTD::__half_inplace_merge<_Inverted>(_Rv(__p), _Rv(__buff), 4588 _RBi(__middle), _RBi(__first), 4589 _RBi(__last), _Inverted(__comp)); 4590 } 4591 } 4592 4593 template <class _Compare, class _BidirectionalIterator> 4594 void 4595 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4596 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, 4597 typename iterator_traits<_BidirectionalIterator>::difference_type __len2, 4598 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size) 4599 { 4600 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 4601 while (true) 4602 { 4603 // if __middle == __last, we're done 4604 if (__len2 == 0) 4605 return; 4606 if (__len1 <= __buff_size || __len2 <= __buff_size) 4607 return _VSTD::__buffered_inplace_merge<_Compare> 4608 (__first, __middle, __last, __comp, __len1, __len2, __buff); 4609 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0 4610 for (; true; ++__first, (void) --__len1) 4611 { 4612 if (__len1 == 0) 4613 return; 4614 if (__comp(*__middle, *__first)) 4615 break; 4616 } 4617 // __first < __middle < __last 4618 // *__first > *__middle 4619 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that 4620 // all elements in: 4621 // [__first, __m1) <= [__middle, __m2) 4622 // [__middle, __m2) < [__m1, __middle) 4623 // [__m1, __middle) <= [__m2, __last) 4624 // and __m1 or __m2 is in the middle of its range 4625 _BidirectionalIterator __m1; // "median" of [__first, __middle) 4626 _BidirectionalIterator __m2; // "median" of [__middle, __last) 4627 difference_type __len11; // distance(__first, __m1) 4628 difference_type __len21; // distance(__middle, __m2) 4629 // binary search smaller range 4630 if (__len1 < __len2) 4631 { // __len >= 1, __len2 >= 2 4632 __len21 = __len2 / 2; 4633 __m2 = __middle; 4634 _VSTD::advance(__m2, __len21); 4635 __m1 = _VSTD::__upper_bound<_Compare>(__first, __middle, *__m2, __comp); 4636 __len11 = _VSTD::distance(__first, __m1); 4637 } 4638 else 4639 { 4640 if (__len1 == 1) 4641 { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1 4642 // It is known *__first > *__middle 4643 swap(*__first, *__middle); 4644 return; 4645 } 4646 // __len1 >= 2, __len2 >= 1 4647 __len11 = __len1 / 2; 4648 __m1 = __first; 4649 _VSTD::advance(__m1, __len11); 4650 __m2 = _VSTD::__lower_bound<_Compare>(__middle, __last, *__m1, __comp); 4651 __len21 = _VSTD::distance(__middle, __m2); 4652 } 4653 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle) 4654 difference_type __len22 = __len2 - __len21; // distance(__m2, __last) 4655 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) 4656 // swap middle two partitions 4657 __middle = _VSTD::rotate(__m1, __middle, __m2); 4658 // __len12 and __len21 now have swapped meanings 4659 // merge smaller range with recursive call and larger with tail recursion elimination 4660 if (__len11 + __len21 < __len12 + __len22) 4661 { 4662 _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); 4663 // _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); 4664 __first = __middle; 4665 __middle = __m2; 4666 __len1 = __len12; 4667 __len2 = __len22; 4668 } 4669 else 4670 { 4671 _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); 4672 // _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); 4673 __last = __middle; 4674 __middle = __m1; 4675 __len1 = __len11; 4676 __len2 = __len21; 4677 } 4678 } 4679 } 4680 4681 template <class _BidirectionalIterator, class _Compare> 4682 inline _LIBCPP_INLINE_VISIBILITY 4683 void 4684 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4685 _Compare __comp) 4686 { 4687 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 4688 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 4689 difference_type __len1 = _VSTD::distance(__first, __middle); 4690 difference_type __len2 = _VSTD::distance(__middle, __last); 4691 difference_type __buf_size = _VSTD::min(__len1, __len2); 4692 pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size); 4693 unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first); 4694 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4695 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2, 4696 __buf.first, __buf.second); 4697 } 4698 4699 template <class _BidirectionalIterator> 4700 inline _LIBCPP_INLINE_VISIBILITY 4701 void 4702 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) 4703 { 4704 _VSTD::inplace_merge(__first, __middle, __last, 4705 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 4706 } 4707 4708 // stable_sort 4709 4710 template <class _Compare, class _InputIterator1, class _InputIterator2> 4711 void 4712 __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1, 4713 _InputIterator2 __first2, _InputIterator2 __last2, 4714 typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp) 4715 { 4716 typedef typename iterator_traits<_InputIterator1>::value_type value_type; 4717 __destruct_n __d(0); 4718 unique_ptr<value_type, __destruct_n&> __h(__result, __d); 4719 for (; true; ++__result) 4720 { 4721 if (__first1 == __last1) 4722 { 4723 for (; __first2 != __last2; ++__first2, ++__result, (void)__d.template __incr<value_type>()) 4724 ::new ((void*)__result) value_type(_VSTD::move(*__first2)); 4725 __h.release(); 4726 return; 4727 } 4728 if (__first2 == __last2) 4729 { 4730 for (; __first1 != __last1; ++__first1, ++__result, (void)__d.template __incr<value_type>()) 4731 ::new ((void*)__result) value_type(_VSTD::move(*__first1)); 4732 __h.release(); 4733 return; 4734 } 4735 if (__comp(*__first2, *__first1)) 4736 { 4737 ::new ((void*)__result) value_type(_VSTD::move(*__first2)); 4738 __d.template __incr<value_type>(); 4739 ++__first2; 4740 } 4741 else 4742 { 4743 ::new ((void*)__result) value_type(_VSTD::move(*__first1)); 4744 __d.template __incr<value_type>(); 4745 ++__first1; 4746 } 4747 } 4748 } 4749 4750 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 4751 void 4752 __merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1, 4753 _InputIterator2 __first2, _InputIterator2 __last2, 4754 _OutputIterator __result, _Compare __comp) 4755 { 4756 for (; __first1 != __last1; ++__result) 4757 { 4758 if (__first2 == __last2) 4759 { 4760 for (; __first1 != __last1; ++__first1, (void) ++__result) 4761 *__result = _VSTD::move(*__first1); 4762 return; 4763 } 4764 if (__comp(*__first2, *__first1)) 4765 { 4766 *__result = _VSTD::move(*__first2); 4767 ++__first2; 4768 } 4769 else 4770 { 4771 *__result = _VSTD::move(*__first1); 4772 ++__first1; 4773 } 4774 } 4775 for (; __first2 != __last2; ++__first2, (void) ++__result) 4776 *__result = _VSTD::move(*__first2); 4777 } 4778 4779 template <class _Compare, class _RandomAccessIterator> 4780 void 4781 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4782 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4783 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size); 4784 4785 template <class _Compare, class _RandomAccessIterator> 4786 void 4787 __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp, 4788 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4789 typename iterator_traits<_RandomAccessIterator>::value_type* __first2) 4790 { 4791 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4792 switch (__len) 4793 { 4794 case 0: 4795 return; 4796 case 1: 4797 ::new ((void*)__first2) value_type(_VSTD::move(*__first1)); 4798 return; 4799 case 2: 4800 __destruct_n __d(0); 4801 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d); 4802 if (__comp(*--__last1, *__first1)) 4803 { 4804 ::new ((void*)__first2) value_type(_VSTD::move(*__last1)); 4805 __d.template __incr<value_type>(); 4806 ++__first2; 4807 ::new ((void*)__first2) value_type(_VSTD::move(*__first1)); 4808 } 4809 else 4810 { 4811 ::new ((void*)__first2) value_type(_VSTD::move(*__first1)); 4812 __d.template __incr<value_type>(); 4813 ++__first2; 4814 ::new ((void*)__first2) value_type(_VSTD::move(*__last1)); 4815 } 4816 __h2.release(); 4817 return; 4818 } 4819 if (__len <= 8) 4820 { 4821 _VSTD::__insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp); 4822 return; 4823 } 4824 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; 4825 _RandomAccessIterator __m = __first1 + __l2; 4826 _VSTD::__stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2); 4827 _VSTD::__stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2); 4828 _VSTD::__merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp); 4829 } 4830 4831 template <class _Tp> 4832 struct __stable_sort_switch 4833 { 4834 static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value; 4835 }; 4836 4837 template <class _Compare, class _RandomAccessIterator> 4838 void 4839 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4840 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4841 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size) 4842 { 4843 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4844 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4845 switch (__len) 4846 { 4847 case 0: 4848 case 1: 4849 return; 4850 case 2: 4851 if (__comp(*--__last, *__first)) 4852 swap(*__first, *__last); 4853 return; 4854 } 4855 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value)) 4856 { 4857 _VSTD::__insertion_sort<_Compare>(__first, __last, __comp); 4858 return; 4859 } 4860 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; 4861 _RandomAccessIterator __m = __first + __l2; 4862 if (__len <= __buff_size) 4863 { 4864 __destruct_n __d(0); 4865 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); 4866 _VSTD::__stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff); 4867 __d.__set(__l2, (value_type*)nullptr); 4868 _VSTD::__stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2); 4869 __d.__set(__len, (value_type*)nullptr); 4870 _VSTD::__merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp); 4871 // _VSTD::__merge<_Compare>(move_iterator<value_type*>(__buff), 4872 // move_iterator<value_type*>(__buff + __l2), 4873 // move_iterator<_RandomAccessIterator>(__buff + __l2), 4874 // move_iterator<_RandomAccessIterator>(__buff + __len), 4875 // __first, __comp); 4876 return; 4877 } 4878 _VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size); 4879 _VSTD::__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); 4880 _VSTD::__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); 4881 } 4882 4883 template <class _RandomAccessIterator, class _Compare> 4884 inline _LIBCPP_INLINE_VISIBILITY 4885 void 4886 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4887 { 4888 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4889 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4890 difference_type __len = __last - __first; 4891 pair<value_type*, ptrdiff_t> __buf(0, 0); 4892 unique_ptr<value_type, __return_temporary_buffer> __h; 4893 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) 4894 { 4895 __buf = _VSTD::get_temporary_buffer<value_type>(__len); 4896 __h.reset(__buf.first); 4897 } 4898 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 4899 _VSTD::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); 4900 } 4901 4902 template <class _RandomAccessIterator> 4903 inline _LIBCPP_INLINE_VISIBILITY 4904 void 4905 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 4906 { 4907 _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4908 } 4909 4910 // is_heap_until 4911 4912 template <class _RandomAccessIterator, class _Compare> 4913 _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator 4914 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4915 { 4916 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4917 difference_type __len = __last - __first; 4918 difference_type __p = 0; 4919 difference_type __c = 1; 4920 _RandomAccessIterator __pp = __first; 4921 while (__c < __len) 4922 { 4923 _RandomAccessIterator __cp = __first + __c; 4924 if (__comp(*__pp, *__cp)) 4925 return __cp; 4926 ++__c; 4927 ++__cp; 4928 if (__c == __len) 4929 return __last; 4930 if (__comp(*__pp, *__cp)) 4931 return __cp; 4932 ++__p; 4933 ++__pp; 4934 __c = 2 * __p + 1; 4935 } 4936 return __last; 4937 } 4938 4939 template<class _RandomAccessIterator> 4940 _LIBCPP_NODISCARD_EXT inline 4941 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4942 _RandomAccessIterator 4943 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) 4944 { 4945 return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4946 } 4947 4948 // is_heap 4949 4950 template <class _RandomAccessIterator, class _Compare> 4951 _LIBCPP_NODISCARD_EXT inline 4952 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4953 bool 4954 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4955 { 4956 return _VSTD::is_heap_until(__first, __last, __comp) == __last; 4957 } 4958 4959 template<class _RandomAccessIterator> 4960 _LIBCPP_NODISCARD_EXT inline 4961 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4962 bool 4963 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 4964 { 4965 return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4966 } 4967 4968 // push_heap 4969 4970 template <class _Compare, class _RandomAccessIterator> 4971 _LIBCPP_CONSTEXPR_AFTER_CXX11 void 4972 __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4973 typename iterator_traits<_RandomAccessIterator>::difference_type __len) 4974 { 4975 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4976 if (__len > 1) 4977 { 4978 __len = (__len - 2) / 2; 4979 _RandomAccessIterator __ptr = __first + __len; 4980 if (__comp(*__ptr, *--__last)) 4981 { 4982 value_type __t(_VSTD::move(*__last)); 4983 do 4984 { 4985 *__last = _VSTD::move(*__ptr); 4986 __last = __ptr; 4987 if (__len == 0) 4988 break; 4989 __len = (__len - 1) / 2; 4990 __ptr = __first + __len; 4991 } while (__comp(*__ptr, __t)); 4992 *__last = _VSTD::move(__t); 4993 } 4994 } 4995 } 4996 4997 template <class _RandomAccessIterator, class _Compare> 4998 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4999 void 5000 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5001 { 5002 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5003 _VSTD::__sift_up<_Comp_ref>(__first, __last, __comp, __last - __first); 5004 } 5005 5006 template <class _RandomAccessIterator> 5007 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5008 void 5009 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 5010 { 5011 _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5012 } 5013 5014 // pop_heap 5015 5016 template <class _Compare, class _RandomAccessIterator> 5017 _LIBCPP_CONSTEXPR_AFTER_CXX11 void 5018 __sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/, 5019 _Compare __comp, 5020 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 5021 _RandomAccessIterator __start) 5022 { 5023 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 5024 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 5025 // left-child of __start is at 2 * __start + 1 5026 // right-child of __start is at 2 * __start + 2 5027 difference_type __child = __start - __first; 5028 5029 if (__len < 2 || (__len - 2) / 2 < __child) 5030 return; 5031 5032 __child = 2 * __child + 1; 5033 _RandomAccessIterator __child_i = __first + __child; 5034 5035 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { 5036 // right-child exists and is greater than left-child 5037 ++__child_i; 5038 ++__child; 5039 } 5040 5041 // check if we are in heap-order 5042 if (__comp(*__child_i, *__start)) 5043 // we are, __start is larger than it's largest child 5044 return; 5045 5046 value_type __top(_VSTD::move(*__start)); 5047 do 5048 { 5049 // we are not in heap-order, swap the parent with its largest child 5050 *__start = _VSTD::move(*__child_i); 5051 __start = __child_i; 5052 5053 if ((__len - 2) / 2 < __child) 5054 break; 5055 5056 // recompute the child based off of the updated parent 5057 __child = 2 * __child + 1; 5058 __child_i = __first + __child; 5059 5060 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { 5061 // right-child exists and is greater than left-child 5062 ++__child_i; 5063 ++__child; 5064 } 5065 5066 // check if we are in heap-order 5067 } while (!__comp(*__child_i, __top)); 5068 *__start = _VSTD::move(__top); 5069 } 5070 5071 template <class _Compare, class _RandomAccessIterator> 5072 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5073 void 5074 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 5075 typename iterator_traits<_RandomAccessIterator>::difference_type __len) 5076 { 5077 if (__len > 1) 5078 { 5079 swap(*__first, *--__last); 5080 _VSTD::__sift_down<_Compare>(__first, __last, __comp, __len - 1, __first); 5081 } 5082 } 5083 5084 template <class _RandomAccessIterator, class _Compare> 5085 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5086 void 5087 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5088 { 5089 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5090 _VSTD::__pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first); 5091 } 5092 5093 template <class _RandomAccessIterator> 5094 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5095 void 5096 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 5097 { 5098 _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5099 } 5100 5101 // make_heap 5102 5103 template <class _Compare, class _RandomAccessIterator> 5104 _LIBCPP_CONSTEXPR_AFTER_CXX11 void 5105 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5106 { 5107 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 5108 difference_type __n = __last - __first; 5109 if (__n > 1) 5110 { 5111 // start from the first parent, there is no need to consider children 5112 for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) 5113 { 5114 _VSTD::__sift_down<_Compare>(__first, __last, __comp, __n, __first + __start); 5115 } 5116 } 5117 } 5118 5119 template <class _RandomAccessIterator, class _Compare> 5120 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5121 void 5122 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5123 { 5124 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5125 _VSTD::__make_heap<_Comp_ref>(__first, __last, __comp); 5126 } 5127 5128 template <class _RandomAccessIterator> 5129 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5130 void 5131 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 5132 { 5133 _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5134 } 5135 5136 // sort_heap 5137 5138 template <class _Compare, class _RandomAccessIterator> 5139 _LIBCPP_CONSTEXPR_AFTER_CXX17 void 5140 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5141 { 5142 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 5143 for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n) 5144 _VSTD::__pop_heap<_Compare>(__first, __last, __comp, __n); 5145 } 5146 5147 template <class _RandomAccessIterator, class _Compare> 5148 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5149 void 5150 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5151 { 5152 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5153 _VSTD::__sort_heap<_Comp_ref>(__first, __last, __comp); 5154 } 5155 5156 template <class _RandomAccessIterator> 5157 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5158 void 5159 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 5160 { 5161 _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5162 } 5163 5164 // partial_sort 5165 5166 template <class _Compare, class _RandomAccessIterator> 5167 _LIBCPP_CONSTEXPR_AFTER_CXX17 void 5168 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, 5169 _Compare __comp) 5170 { 5171 _VSTD::__make_heap<_Compare>(__first, __middle, __comp); 5172 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first; 5173 for (_RandomAccessIterator __i = __middle; __i != __last; ++__i) 5174 { 5175 if (__comp(*__i, *__first)) 5176 { 5177 swap(*__i, *__first); 5178 _VSTD::__sift_down<_Compare>(__first, __middle, __comp, __len, __first); 5179 } 5180 } 5181 _VSTD::__sort_heap<_Compare>(__first, __middle, __comp); 5182 } 5183 5184 template <class _RandomAccessIterator, class _Compare> 5185 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5186 void 5187 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, 5188 _Compare __comp) 5189 { 5190 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5191 _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp); 5192 } 5193 5194 template <class _RandomAccessIterator> 5195 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5196 void 5197 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) 5198 { 5199 _VSTD::partial_sort(__first, __middle, __last, 5200 __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5201 } 5202 5203 // partial_sort_copy 5204 5205 template <class _Compare, class _InputIterator, class _RandomAccessIterator> 5206 _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator 5207 __partial_sort_copy(_InputIterator __first, _InputIterator __last, 5208 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) 5209 { 5210 _RandomAccessIterator __r = __result_first; 5211 if (__r != __result_last) 5212 { 5213 for (; __first != __last && __r != __result_last; ++__first, (void) ++__r) 5214 *__r = *__first; 5215 _VSTD::__make_heap<_Compare>(__result_first, __r, __comp); 5216 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first; 5217 for (; __first != __last; ++__first) 5218 if (__comp(*__first, *__result_first)) 5219 { 5220 *__result_first = *__first; 5221 _VSTD::__sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first); 5222 } 5223 _VSTD::__sort_heap<_Compare>(__result_first, __r, __comp); 5224 } 5225 return __r; 5226 } 5227 5228 template <class _InputIterator, class _RandomAccessIterator, class _Compare> 5229 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5230 _RandomAccessIterator 5231 partial_sort_copy(_InputIterator __first, _InputIterator __last, 5232 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) 5233 { 5234 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5235 return _VSTD::__partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp); 5236 } 5237 5238 template <class _InputIterator, class _RandomAccessIterator> 5239 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5240 _RandomAccessIterator 5241 partial_sort_copy(_InputIterator __first, _InputIterator __last, 5242 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last) 5243 { 5244 return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last, 5245 __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5246 } 5247 5248 // nth_element 5249 5250 template<class _Compare, class _RandomAccessIterator> 5251 _LIBCPP_CONSTEXPR_AFTER_CXX11 bool 5252 __nth_element_find_guard(_RandomAccessIterator& __i, _RandomAccessIterator& __j, 5253 _RandomAccessIterator __m, _Compare __comp) 5254 { 5255 // manually guard downward moving __j against __i 5256 while (true) { 5257 if (__i == --__j) { 5258 return false; 5259 } 5260 if (__comp(*__j, *__m)) { 5261 return true; // found guard for downward moving __j, now use unguarded partition 5262 } 5263 } 5264 } 5265 5266 template <class _Compare, class _RandomAccessIterator> 5267 _LIBCPP_CONSTEXPR_AFTER_CXX11 void 5268 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) 5269 { 5270 // _Compare is known to be a reference type 5271 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 5272 const difference_type __limit = 7; 5273 while (true) 5274 { 5275 if (__nth == __last) 5276 return; 5277 difference_type __len = __last - __first; 5278 switch (__len) 5279 { 5280 case 0: 5281 case 1: 5282 return; 5283 case 2: 5284 if (__comp(*--__last, *__first)) 5285 swap(*__first, *__last); 5286 return; 5287 case 3: 5288 { 5289 _RandomAccessIterator __m = __first; 5290 _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp); 5291 return; 5292 } 5293 } 5294 if (__len <= __limit) 5295 { 5296 _VSTD::__selection_sort<_Compare>(__first, __last, __comp); 5297 return; 5298 } 5299 // __len > __limit >= 3 5300 _RandomAccessIterator __m = __first + __len/2; 5301 _RandomAccessIterator __lm1 = __last; 5302 unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp); 5303 // *__m is median 5304 // partition [__first, __m) < *__m and *__m <= [__m, __last) 5305 // (this inhibits tossing elements equivalent to __m around unnecessarily) 5306 _RandomAccessIterator __i = __first; 5307 _RandomAccessIterator __j = __lm1; 5308 // j points beyond range to be tested, *__lm1 is known to be <= *__m 5309 // The search going up is known to be guarded but the search coming down isn't. 5310 // Prime the downward search with a guard. 5311 if (!__comp(*__i, *__m)) // if *__first == *__m 5312 { 5313 // *__first == *__m, *__first doesn't go in first part 5314 if (_VSTD::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) { 5315 swap(*__i, *__j); 5316 ++__n_swaps; 5317 } else { 5318 // *__first == *__m, *__m <= all other elements 5319 // Partition instead into [__first, __i) == *__first and *__first < [__i, __last) 5320 ++__i; // __first + 1 5321 __j = __last; 5322 if (!__comp(*__first, *--__j)) { // we need a guard if *__first == *(__last-1) 5323 while (true) { 5324 if (__i == __j) { 5325 return; // [__first, __last) all equivalent elements 5326 } else if (__comp(*__first, *__i)) { 5327 swap(*__i, *__j); 5328 ++__n_swaps; 5329 ++__i; 5330 break; 5331 } 5332 ++__i; 5333 } 5334 } 5335 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 5336 if (__i == __j) { 5337 return; 5338 } 5339 while (true) { 5340 while (!__comp(*__first, *__i)) 5341 ++__i; 5342 while (__comp(*__first, *--__j)) 5343 ; 5344 if (__i >= __j) 5345 break; 5346 swap(*__i, *__j); 5347 ++__n_swaps; 5348 ++__i; 5349 } 5350 // [__first, __i) == *__first and *__first < [__i, __last) 5351 // The first part is sorted, 5352 if (__nth < __i) { 5353 return; 5354 } 5355 // __nth_element the second part 5356 // _VSTD::__nth_element<_Compare>(__i, __nth, __last, __comp); 5357 __first = __i; 5358 continue; 5359 } 5360 } 5361 ++__i; 5362 // j points beyond range to be tested, *__lm1 is known to be <= *__m 5363 // if not yet partitioned... 5364 if (__i < __j) 5365 { 5366 // known that *(__i - 1) < *__m 5367 while (true) 5368 { 5369 // __m still guards upward moving __i 5370 while (__comp(*__i, *__m)) 5371 ++__i; 5372 // It is now known that a guard exists for downward moving __j 5373 while (!__comp(*--__j, *__m)) 5374 ; 5375 if (__i >= __j) 5376 break; 5377 swap(*__i, *__j); 5378 ++__n_swaps; 5379 // It is known that __m != __j 5380 // If __m just moved, follow it 5381 if (__m == __i) 5382 __m = __j; 5383 ++__i; 5384 } 5385 } 5386 // [__first, __i) < *__m and *__m <= [__i, __last) 5387 if (__i != __m && __comp(*__m, *__i)) 5388 { 5389 swap(*__i, *__m); 5390 ++__n_swaps; 5391 } 5392 // [__first, __i) < *__i and *__i <= [__i+1, __last) 5393 if (__nth == __i) 5394 return; 5395 if (__n_swaps == 0) 5396 { 5397 // We were given a perfectly partitioned sequence. Coincidence? 5398 if (__nth < __i) 5399 { 5400 // Check for [__first, __i) already sorted 5401 __j = __m = __first; 5402 while (true) { 5403 if (++__j == __i) { 5404 // [__first, __i) sorted 5405 return; 5406 } 5407 if (__comp(*__j, *__m)) { 5408 // not yet sorted, so sort 5409 break; 5410 } 5411 __m = __j; 5412 } 5413 } 5414 else 5415 { 5416 // Check for [__i, __last) already sorted 5417 __j = __m = __i; 5418 while (true) { 5419 if (++__j == __last) { 5420 // [__i, __last) sorted 5421 return; 5422 } 5423 if (__comp(*__j, *__m)) { 5424 // not yet sorted, so sort 5425 break; 5426 } 5427 __m = __j; 5428 } 5429 } 5430 } 5431 // __nth_element on range containing __nth 5432 if (__nth < __i) 5433 { 5434 // _VSTD::__nth_element<_Compare>(__first, __nth, __i, __comp); 5435 __last = __i; 5436 } 5437 else 5438 { 5439 // _VSTD::__nth_element<_Compare>(__i+1, __nth, __last, __comp); 5440 __first = ++__i; 5441 } 5442 } 5443 } 5444 5445 template <class _RandomAccessIterator, class _Compare> 5446 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5447 void 5448 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) 5449 { 5450 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5451 _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp); 5452 } 5453 5454 template <class _RandomAccessIterator> 5455 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5456 void 5457 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) 5458 { 5459 _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5460 } 5461 5462 // sort 5463 5464 template <class _RandomAccessIterator, class _Compare> 5465 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5466 void 5467 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5468 { 5469 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5470 if (__libcpp_is_constant_evaluated()) { 5471 _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); 5472 } else { 5473 _VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _Comp_ref(__comp)); 5474 } 5475 } 5476 5477 template <class _RandomAccessIterator> 5478 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5479 void 5480 sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 5481 { 5482 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5483 } 5484 5485 // includes 5486 5487 template <class _Compare, class _InputIterator1, class _InputIterator2> 5488 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool 5489 __includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, 5490 _Compare __comp) 5491 { 5492 for (; __first2 != __last2; ++__first1) 5493 { 5494 if (__first1 == __last1 || __comp(*__first2, *__first1)) 5495 return false; 5496 if (!__comp(*__first1, *__first2)) 5497 ++__first2; 5498 } 5499 return true; 5500 } 5501 5502 template <class _InputIterator1, class _InputIterator2, class _Compare> 5503 _LIBCPP_NODISCARD_EXT inline 5504 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5505 bool 5506 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, 5507 _Compare __comp) 5508 { 5509 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5510 return _VSTD::__includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); 5511 } 5512 5513 template <class _InputIterator1, class _InputIterator2> 5514 _LIBCPP_NODISCARD_EXT inline 5515 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5516 bool 5517 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) 5518 { 5519 return _VSTD::includes(__first1, __last1, __first2, __last2, 5520 __less<typename iterator_traits<_InputIterator1>::value_type, 5521 typename iterator_traits<_InputIterator2>::value_type>()); 5522 } 5523 5524 // set_union 5525 5526 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5527 _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 5528 __set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5529 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5530 { 5531 for (; __first1 != __last1; ++__result) 5532 { 5533 if (__first2 == __last2) 5534 return _VSTD::copy(__first1, __last1, __result); 5535 if (__comp(*__first2, *__first1)) 5536 { 5537 *__result = *__first2; 5538 ++__first2; 5539 } 5540 else 5541 { 5542 if (!__comp(*__first1, *__first2)) 5543 ++__first2; 5544 *__result = *__first1; 5545 ++__first1; 5546 } 5547 } 5548 return _VSTD::copy(__first2, __last2, __result); 5549 } 5550 5551 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5552 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5553 _OutputIterator 5554 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5555 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5556 { 5557 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5558 return _VSTD::__set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5559 } 5560 5561 template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5562 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5563 _OutputIterator 5564 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5565 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5566 { 5567 return _VSTD::set_union(__first1, __last1, __first2, __last2, __result, 5568 __less<typename iterator_traits<_InputIterator1>::value_type, 5569 typename iterator_traits<_InputIterator2>::value_type>()); 5570 } 5571 5572 // set_intersection 5573 5574 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5575 _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 5576 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5577 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5578 { 5579 while (__first1 != __last1 && __first2 != __last2) 5580 { 5581 if (__comp(*__first1, *__first2)) 5582 ++__first1; 5583 else 5584 { 5585 if (!__comp(*__first2, *__first1)) 5586 { 5587 *__result = *__first1; 5588 ++__result; 5589 ++__first1; 5590 } 5591 ++__first2; 5592 } 5593 } 5594 return __result; 5595 } 5596 5597 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5598 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5599 _OutputIterator 5600 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5601 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5602 { 5603 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5604 return _VSTD::__set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5605 } 5606 5607 template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5608 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5609 _OutputIterator 5610 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5611 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5612 { 5613 return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result, 5614 __less<typename iterator_traits<_InputIterator1>::value_type, 5615 typename iterator_traits<_InputIterator2>::value_type>()); 5616 } 5617 5618 // set_difference 5619 5620 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5621 _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 5622 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5623 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5624 { 5625 while (__first1 != __last1) 5626 { 5627 if (__first2 == __last2) 5628 return _VSTD::copy(__first1, __last1, __result); 5629 if (__comp(*__first1, *__first2)) 5630 { 5631 *__result = *__first1; 5632 ++__result; 5633 ++__first1; 5634 } 5635 else 5636 { 5637 if (!__comp(*__first2, *__first1)) 5638 ++__first1; 5639 ++__first2; 5640 } 5641 } 5642 return __result; 5643 } 5644 5645 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5646 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5647 _OutputIterator 5648 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5649 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5650 { 5651 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5652 return _VSTD::__set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5653 } 5654 5655 template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5656 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5657 _OutputIterator 5658 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5659 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5660 { 5661 return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result, 5662 __less<typename iterator_traits<_InputIterator1>::value_type, 5663 typename iterator_traits<_InputIterator2>::value_type>()); 5664 } 5665 5666 // set_symmetric_difference 5667 5668 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5669 _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator 5670 __set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5671 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5672 { 5673 while (__first1 != __last1) 5674 { 5675 if (__first2 == __last2) 5676 return _VSTD::copy(__first1, __last1, __result); 5677 if (__comp(*__first1, *__first2)) 5678 { 5679 *__result = *__first1; 5680 ++__result; 5681 ++__first1; 5682 } 5683 else 5684 { 5685 if (__comp(*__first2, *__first1)) 5686 { 5687 *__result = *__first2; 5688 ++__result; 5689 } 5690 else 5691 ++__first1; 5692 ++__first2; 5693 } 5694 } 5695 return _VSTD::copy(__first2, __last2, __result); 5696 } 5697 5698 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5699 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5700 _OutputIterator 5701 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5702 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5703 { 5704 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5705 return _VSTD::__set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5706 } 5707 5708 template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5709 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5710 _OutputIterator 5711 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5712 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5713 { 5714 return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, 5715 __less<typename iterator_traits<_InputIterator1>::value_type, 5716 typename iterator_traits<_InputIterator2>::value_type>()); 5717 } 5718 5719 // lexicographical_compare 5720 5721 template <class _Compare, class _InputIterator1, class _InputIterator2> 5722 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool 5723 __lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5724 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) 5725 { 5726 for (; __first2 != __last2; ++__first1, (void) ++__first2) 5727 { 5728 if (__first1 == __last1 || __comp(*__first1, *__first2)) 5729 return true; 5730 if (__comp(*__first2, *__first1)) 5731 return false; 5732 } 5733 return false; 5734 } 5735 5736 template <class _InputIterator1, class _InputIterator2, class _Compare> 5737 _LIBCPP_NODISCARD_EXT inline 5738 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5739 bool 5740 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5741 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) 5742 { 5743 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5744 return _VSTD::__lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); 5745 } 5746 5747 template <class _InputIterator1, class _InputIterator2> 5748 _LIBCPP_NODISCARD_EXT inline 5749 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5750 bool 5751 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5752 _InputIterator2 __first2, _InputIterator2 __last2) 5753 { 5754 return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2, 5755 __less<typename iterator_traits<_InputIterator1>::value_type, 5756 typename iterator_traits<_InputIterator2>::value_type>()); 5757 } 5758 5759 // next_permutation 5760 5761 template <class _Compare, class _BidirectionalIterator> 5762 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool 5763 __next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5764 { 5765 _BidirectionalIterator __i = __last; 5766 if (__first == __last || __first == --__i) 5767 return false; 5768 while (true) 5769 { 5770 _BidirectionalIterator __ip1 = __i; 5771 if (__comp(*--__i, *__ip1)) 5772 { 5773 _BidirectionalIterator __j = __last; 5774 while (!__comp(*__i, *--__j)) 5775 ; 5776 swap(*__i, *__j); 5777 _VSTD::reverse(__ip1, __last); 5778 return true; 5779 } 5780 if (__i == __first) 5781 { 5782 _VSTD::reverse(__first, __last); 5783 return false; 5784 } 5785 } 5786 } 5787 5788 template <class _BidirectionalIterator, class _Compare> 5789 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5790 bool 5791 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5792 { 5793 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5794 return _VSTD::__next_permutation<_Comp_ref>(__first, __last, __comp); 5795 } 5796 5797 template <class _BidirectionalIterator> 5798 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5799 bool 5800 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) 5801 { 5802 return _VSTD::next_permutation(__first, __last, 5803 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 5804 } 5805 5806 // prev_permutation 5807 5808 template <class _Compare, class _BidirectionalIterator> 5809 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool 5810 __prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5811 { 5812 _BidirectionalIterator __i = __last; 5813 if (__first == __last || __first == --__i) 5814 return false; 5815 while (true) 5816 { 5817 _BidirectionalIterator __ip1 = __i; 5818 if (__comp(*__ip1, *--__i)) 5819 { 5820 _BidirectionalIterator __j = __last; 5821 while (!__comp(*--__j, *__i)) 5822 ; 5823 swap(*__i, *__j); 5824 _VSTD::reverse(__ip1, __last); 5825 return true; 5826 } 5827 if (__i == __first) 5828 { 5829 _VSTD::reverse(__first, __last); 5830 return false; 5831 } 5832 } 5833 } 5834 5835 template <class _BidirectionalIterator, class _Compare> 5836 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5837 bool 5838 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5839 { 5840 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 5841 return _VSTD::__prev_permutation<_Comp_ref>(__first, __last, __comp); 5842 } 5843 5844 template <class _BidirectionalIterator> 5845 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5846 bool 5847 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) 5848 { 5849 return _VSTD::prev_permutation(__first, __last, 5850 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 5851 } 5852 5853 _LIBCPP_END_NAMESPACE_STD 5854 5855 _LIBCPP_POP_MACROS 5856 5857 #if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17 5858 # include <__pstl_algorithm> 5859 #endif 5860 5861 #endif // _LIBCPP_ALGORITHM 5862
Indexes created Tue Apr 28 00:22:25 UTC 2026