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