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 19namespace std 20{ 21 22template <class InputIterator, class Predicate> 23 constexpr bool // constexpr in C++20 24 all_of(InputIterator first, InputIterator last, Predicate pred); 25 26template <class InputIterator, class Predicate> 27 constexpr bool // constexpr in C++20 28 any_of(InputIterator first, InputIterator last, Predicate pred); 29 30template <class InputIterator, class Predicate> 31 constexpr bool // constexpr in C++20 32 none_of(InputIterator first, InputIterator last, Predicate pred); 33 34template <class InputIterator, class Function> 35 constexpr Function // constexpr in C++20 36 for_each(InputIterator first, InputIterator last, Function f); 37 38template<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 42template <class InputIterator, class T> 43 constexpr InputIterator // constexpr in C++20 44 find(InputIterator first, InputIterator last, const T& value); 45 46template <class InputIterator, class Predicate> 47 constexpr InputIterator // constexpr in C++20 48 find_if(InputIterator first, InputIterator last, Predicate pred); 49 50template<class InputIterator, class Predicate> 51 InputIterator // constexpr in C++20 52 find_if_not(InputIterator first, InputIterator last, Predicate pred); 53 54template <class ForwardIterator1, class ForwardIterator2> 55 ForwardIterator1 // constexpr in C++20 56 find_end(ForwardIterator1 first1, ForwardIterator1 last1, 57 ForwardIterator2 first2, ForwardIterator2 last2); 58 59template <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 64template <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 69template <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 74template <class ForwardIterator> 75 constexpr ForwardIterator // constexpr in C++20 76 adjacent_find(ForwardIterator first, ForwardIterator last); 77 78template <class ForwardIterator, class BinaryPredicate> 79 constexpr ForwardIterator // constexpr in C++20 80 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); 81 82template <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 86template <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 90template <class InputIterator1, class InputIterator2> 91 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 92 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); 93 94template <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 99template <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 104template <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 110template <class InputIterator1, class InputIterator2> 111 constexpr bool // constexpr in C++20 112 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); 113 114template <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 119template <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 124template <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 130template<class ForwardIterator1, class ForwardIterator2> 131 constexpr bool // constexpr in C++20 132 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 133 ForwardIterator2 first2); 134 135template<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 140template<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 145template<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 151template <class ForwardIterator1, class ForwardIterator2> 152 constexpr ForwardIterator1 // constexpr in C++20 153 search(ForwardIterator1 first1, ForwardIterator1 last1, 154 ForwardIterator2 first2, ForwardIterator2 last2); 155 156template <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 161template <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 165template <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 170template <class InputIterator, class OutputIterator> 171 OutputIterator 172 copy(InputIterator first, InputIterator last, OutputIterator result); 173 174template<class InputIterator, class OutputIterator, class Predicate> 175 OutputIterator 176 copy_if(InputIterator first, InputIterator last, 177 OutputIterator result, Predicate pred); 178 179template<class InputIterator, class Size, class OutputIterator> 180 OutputIterator 181 copy_n(InputIterator first, Size n, OutputIterator result); 182 183template <class BidirectionalIterator1, class BidirectionalIterator2> 184 BidirectionalIterator2 185 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, 186 BidirectionalIterator2 result); 187 188template <class ForwardIterator1, class ForwardIterator2> 189 ForwardIterator2 190 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); 191 192template <class ForwardIterator1, class ForwardIterator2> 193 void 194 iter_swap(ForwardIterator1 a, ForwardIterator2 b); 195 196template <class InputIterator, class OutputIterator, class UnaryOperation> 197 constexpr OutputIterator // constexpr in C++20 198 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op); 199 200template <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 205template <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 209template <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 213template <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 218template <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 222template <class ForwardIterator, class T> 223 constexpr void // constexpr in C++20 224 fill(ForwardIterator first, ForwardIterator last, const T& value); 225 226template <class OutputIterator, class Size, class T> 227 constexpr OutputIterator // constexpr in C++20 228 fill_n(OutputIterator first, Size n, const T& value); 229 230template <class ForwardIterator, class Generator> 231 constexpr void // constexpr in C++20 232 generate(ForwardIterator first, ForwardIterator last, Generator gen); 233 234template <class OutputIterator, class Size, class Generator> 235 constexpr OutputIterator // constexpr in C++20 236 generate_n(OutputIterator first, Size n, Generator gen); 237 238template <class ForwardIterator, class T> 239 constexpr ForwardIterator // constexpr in C++20 240 remove(ForwardIterator first, ForwardIterator last, const T& value); 241 242template <class ForwardIterator, class Predicate> 243 constexpr ForwardIterator // constexpr in C++20 244 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred); 245 246template <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 250template <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 254template <class ForwardIterator> 255 ForwardIterator 256 unique(ForwardIterator first, ForwardIterator last); 257 258template <class ForwardIterator, class BinaryPredicate> 259 ForwardIterator 260 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); 261 262template <class InputIterator, class OutputIterator> 263 OutputIterator 264 unique_copy(InputIterator first, InputIterator last, OutputIterator result); 265 266template <class InputIterator, class OutputIterator, class BinaryPredicate> 267 OutputIterator 268 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred); 269 270template <class BidirectionalIterator> 271 void 272 reverse(BidirectionalIterator first, BidirectionalIterator last); 273 274template <class BidirectionalIterator, class OutputIterator> 275 constexpr OutputIterator // constexpr in C++20 276 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result); 277 278template <class ForwardIterator> 279 ForwardIterator 280 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); 281 282template <class ForwardIterator, class OutputIterator> 283 OutputIterator 284 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result); 285 286template <class RandomAccessIterator> 287 void 288 random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17 289 290template <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 295template<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 301template<class RandomAccessIterator, class UniformRandomNumberGenerator> 302 void shuffle(RandomAccessIterator first, RandomAccessIterator last, 303 UniformRandomNumberGenerator&& g); 304 305template <class InputIterator, class Predicate> 306 constexpr bool // constexpr in C++20 307 is_partitioned(InputIterator first, InputIterator last, Predicate pred); 308 309template <class ForwardIterator, class Predicate> 310 ForwardIterator 311 partition(ForwardIterator first, ForwardIterator last, Predicate pred); 312 313template <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 320template <class ForwardIterator, class Predicate> 321 ForwardIterator 322 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred); 323 324template<class ForwardIterator, class Predicate> 325 constexpr ForwardIterator // constexpr in C++20 326 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred); 327 328template <class ForwardIterator> 329 constexpr bool // constexpr in C++20 330 is_sorted(ForwardIterator first, ForwardIterator last); 331 332template <class ForwardIterator, class Compare> 333 bool 334 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp); 335 336template<class ForwardIterator> 337 constexpr ForwardIterator // constexpr in C++20 338 is_sorted_until(ForwardIterator first, ForwardIterator last); 339 340template <class ForwardIterator, class Compare> 341 constexpr ForwardIterator // constexpr in C++20 342 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp); 343 344template <class RandomAccessIterator> 345 void 346 sort(RandomAccessIterator first, RandomAccessIterator last); 347 348template <class RandomAccessIterator, class Compare> 349 void 350 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 351 352template <class RandomAccessIterator> 353 void 354 stable_sort(RandomAccessIterator first, RandomAccessIterator last); 355 356template <class RandomAccessIterator, class Compare> 357 void 358 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 359 360template <class RandomAccessIterator> 361 void 362 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); 363 364template <class RandomAccessIterator, class Compare> 365 void 366 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); 367 368template <class InputIterator, class RandomAccessIterator> 369 RandomAccessIterator 370 partial_sort_copy(InputIterator first, InputIterator last, 371 RandomAccessIterator result_first, RandomAccessIterator result_last); 372 373template <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 378template <class RandomAccessIterator> 379 void 380 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); 381 382template <class RandomAccessIterator, class Compare> 383 void 384 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); 385 386template <class ForwardIterator, class T> 387 constexpr ForwardIterator // constexpr in C++20 388 lower_bound(ForwardIterator first, ForwardIterator last, const T& value); 389 390template <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 394template <class ForwardIterator, class T> 395 constexpr ForwardIterator // constexpr in C++20 396 upper_bound(ForwardIterator first, ForwardIterator last, const T& value); 397 398template <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 402template <class ForwardIterator, class T> 403 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20 404 equal_range(ForwardIterator first, ForwardIterator last, const T& value); 405 406template <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 410template <class ForwardIterator, class T> 411 constexpr bool // constexpr in C++20 412 binary_search(ForwardIterator first, ForwardIterator last, const T& value); 413 414template <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 418template <class InputIterator1, class InputIterator2, class OutputIterator> 419 OutputIterator 420 merge(InputIterator1 first1, InputIterator1 last1, 421 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 422 423template <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 428template <class BidirectionalIterator> 429 void 430 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); 431 432template <class BidirectionalIterator, class Compare> 433 void 434 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); 435 436template <class InputIterator1, class InputIterator2> 437 constexpr bool // constexpr in C++20 438 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); 439 440template <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 444template <class InputIterator1, class InputIterator2, class OutputIterator> 445 OutputIterator 446 set_union(InputIterator1 first1, InputIterator1 last1, 447 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 448 449template <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 454template <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 459template <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 464template <class InputIterator1, class InputIterator2, class OutputIterator> 465 OutputIterator 466 set_difference(InputIterator1 first1, InputIterator1 last1, 467 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 468 469template <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 474template <class InputIterator1, class InputIterator2, class OutputIterator> 475 OutputIterator 476 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, 477 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 478 479template <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 484template <class RandomAccessIterator> 485 void 486 push_heap(RandomAccessIterator first, RandomAccessIterator last); 487 488template <class RandomAccessIterator, class Compare> 489 void 490 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 491 492template <class RandomAccessIterator> 493 void 494 pop_heap(RandomAccessIterator first, RandomAccessIterator last); 495 496template <class RandomAccessIterator, class Compare> 497 void 498 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 499 500template <class RandomAccessIterator> 501 void 502 make_heap(RandomAccessIterator first, RandomAccessIterator last); 503 504template <class RandomAccessIterator, class Compare> 505 void 506 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 507 508template <class RandomAccessIterator> 509 void 510 sort_heap(RandomAccessIterator first, RandomAccessIterator last); 511 512template <class RandomAccessIterator, class Compare> 513 void 514 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 515 516template <class RandomAccessIterator> 517 constexpr bool // constexpr in C++20 518 is_heap(RandomAccessIterator first, RandomAccessiterator last); 519 520template <class RandomAccessIterator, class Compare> 521 constexpr bool // constexpr in C++20 522 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp); 523 524template <class RandomAccessIterator> 525 constexpr RandomAccessIterator // constexpr in C++20 526 is_heap_until(RandomAccessIterator first, RandomAccessiterator last); 527 528template <class RandomAccessIterator, class Compare> 529 constexpr RandomAccessIterator // constexpr in C++20 530 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp); 531 532template <class ForwardIterator> 533 ForwardIterator 534 min_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14 535 536template <class ForwardIterator, class Compare> 537 ForwardIterator 538 min_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14 539 540template <class T> 541 const T& 542 min(const T& a, const T& b); // constexpr in C++14 543 544template <class T, class Compare> 545 const T& 546 min(const T& a, const T& b, Compare comp); // constexpr in C++14 547 548template<class T> 549 T 550 min(initializer_list<T> t); // constexpr in C++14 551 552template<class T, class Compare> 553 T 554 min(initializer_list<T> t, Compare comp); // constexpr in C++14 555 556template<class T> 557 constexpr const T& clamp( const T& v, const T& lo, const T& hi ); // C++17 558 559template<class T, class Compare> 560 constexpr const T& clamp( const T& v, const T& lo, const T& hi, Compare comp ); // C++17 561 562template <class ForwardIterator> 563 ForwardIterator 564 max_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14 565 566template <class ForwardIterator, class Compare> 567 ForwardIterator 568 max_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14 569 570template <class T> 571 const T& 572 max(const T& a, const T& b); // constexpr in C++14 573 574template <class T, class Compare> 575 const T& 576 max(const T& a, const T& b, Compare comp); // constexpr in C++14 577 578template<class T> 579 T 580 max(initializer_list<T> t); // constexpr in C++14 581 582template<class T, class Compare> 583 T 584 max(initializer_list<T> t, Compare comp); // constexpr in C++14 585 586template<class ForwardIterator> 587 pair<ForwardIterator, ForwardIterator> 588 minmax_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14 589 590template<class ForwardIterator, class Compare> 591 pair<ForwardIterator, ForwardIterator> 592 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14 593 594template<class T> 595 pair<const T&, const T&> 596 minmax(const T& a, const T& b); // constexpr in C++14 597 598template<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 602template<class T> 603 pair<T, T> 604 minmax(initializer_list<T> t); // constexpr in C++14 605 606template<class T, class Compare> 607 pair<T, T> 608 minmax(initializer_list<T> t, Compare comp); // constexpr in C++14 609 610template <class InputIterator1, class InputIterator2> 611 constexpr bool // constexpr in C++20 612 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); 613 614template <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 619template <class BidirectionalIterator> 620 bool 621 next_permutation(BidirectionalIterator first, BidirectionalIterator last); 622 623template <class BidirectionalIterator, class Compare> 624 bool 625 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); 626 627template <class BidirectionalIterator> 628 bool 629 prev_permutation(BidirectionalIterator first, BidirectionalIterator last); 630 631template <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. 671template <class _T1, class _T2 = _T1> 672struct __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 680template <class _T1> 681struct __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 687template <class _T1> 688struct __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 694template <class _T1> 695struct __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 701template <class _T1, class _T2 = _T1> 702struct __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 717template <class _T1> 718struct __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 724template <class _T1> 725struct __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 731template <class _T1> 732struct __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 738template <class _Predicate> 739class __invert // invert the sense of a comparison 740{ 741private: 742 _Predicate __p_; 743public: 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 760template <class _Compare> 761struct __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 792inline _LIBCPP_INLINE_VISIBILITY 793unsigned __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 808inline _LIBCPP_INLINE_VISIBILITY 809unsigned 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 818inline _LIBCPP_INLINE_VISIBILITY 819unsigned 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 844inline _LIBCPP_INLINE_VISIBILITY 845unsigned __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 860inline _LIBCPP_INLINE_VISIBILITY 861unsigned 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 870inline _LIBCPP_INLINE_VISIBILITY 871unsigned 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 893inline _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 902inline _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 911inline _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 922template <class _InputIterator, class _Predicate> 923inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 924bool 925all_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 935template <class _InputIterator, class _Predicate> 936inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 937bool 938any_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 948template <class _InputIterator, class _Predicate> 949inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 950bool 951none_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 961template <class _InputIterator, class _Function> 962inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 963_Function 964for_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 974template <class _InputIterator, class _Size, class _Function> 975inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 976_InputIterator 977for_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 993template <class _InputIterator, class _Tp> 994inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 995_InputIterator 996find(_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 1006template <class _InputIterator, class _Predicate> 1007inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1008_InputIterator 1009find_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 1019template<class _InputIterator, class _Predicate> 1020inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1021_InputIterator 1022find_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 1032template <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 1074template <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 1113template <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 1154template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 1155inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1156_ForwardIterator1 1157find_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 1166template <class _ForwardIterator1, class _ForwardIterator2> 1167inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1168_ForwardIterator1 1169find_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 1179template <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 1192template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 1193inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1194_ForwardIterator1 1195find_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 1201template <class _ForwardIterator1, class _ForwardIterator2> 1202inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1203_ForwardIterator1 1204find_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 1214template <class _ForwardIterator, class _BinaryPredicate> 1215inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1216_ForwardIterator 1217adjacent_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 1232template <class _ForwardIterator> 1233inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1234_ForwardIterator 1235adjacent_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 1243template <class _InputIterator, class _Tp> 1244inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1245typename iterator_traits<_InputIterator>::difference_type 1246count(_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 1257template <class _InputIterator, class _Predicate> 1258inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1259typename iterator_traits<_InputIterator>::difference_type 1260count_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 1271template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 1272inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1273pair<_InputIterator1, _InputIterator2> 1274mismatch(_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 1283template <class _InputIterator1, class _InputIterator2> 1284inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1285pair<_InputIterator1, _InputIterator2> 1286mismatch(_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 1294template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 1295inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1296pair<_InputIterator1, _InputIterator2> 1297mismatch(_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 1307template <class _InputIterator1, class _InputIterator2> 1308inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1309pair<_InputIterator1, _InputIterator2> 1310mismatch(_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 1321template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 1322inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1323bool 1324equal(_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 1332template <class _InputIterator1, class _InputIterator2> 1333inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1334bool 1335equal(_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 1343template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2> 1344inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1345bool 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 1356template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> 1357inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1358bool 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 1370template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 1371inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1372bool 1373equal(_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 1382template <class _InputIterator1, class _InputIterator2> 1383inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1384bool 1385equal(_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 1398template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 1399_LIBCPP_CONSTEXPR_AFTER_CXX17 bool 1400is_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 1445template<class _ForwardIterator1, class _ForwardIterator2> 1446inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1447bool 1448is_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 1457template<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 1510template<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 1524template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 1525inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1526bool 1527is_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 1537template<class _ForwardIterator1, class _ForwardIterator2> 1538inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1539bool 1540is_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 1555template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 1556inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1557_ForwardIterator1 1558search(_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 1568template <class _ForwardIterator1, class _ForwardIterator2> 1569inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1570_ForwardIterator1 1571search(_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 1581template <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 1589template <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 1626template <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 1666template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate> 1667inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1668_ForwardIterator 1669search_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 1677template <class _ForwardIterator, class _Size, class _Tp> 1678inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1679_ForwardIterator 1680search_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 1688template <class _Iter> 1689inline _LIBCPP_INLINE_VISIBILITY 1690_Iter 1691__unwrap_iter(_Iter __i) 1692{ 1693 return __i; 1694} 1695 1696template <class _Tp> 1697inline _LIBCPP_INLINE_VISIBILITY 1698typename 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 1710template <class _Tp> 1711inline _LIBCPP_INLINE_VISIBILITY 1712typename 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 1724template <class _Tp> 1725inline _LIBCPP_INLINE_VISIBILITY 1726typename 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 1738template <class _InputIterator, class _OutputIterator> 1739inline _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 1748template <class _Tp, class _Up> 1749inline _LIBCPP_INLINE_VISIBILITY 1750typename 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 1764template <class _InputIterator, class _OutputIterator> 1765inline _LIBCPP_INLINE_VISIBILITY 1766_OutputIterator 1767copy(_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 1774template <class _BidirectionalIterator, class _OutputIterator> 1775inline _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 1784template <class _Tp, class _Up> 1785inline _LIBCPP_INLINE_VISIBILITY 1786typename 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 1803template <class _BidirectionalIterator1, class _BidirectionalIterator2> 1804inline _LIBCPP_INLINE_VISIBILITY 1805_BidirectionalIterator2 1806copy_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 1816template<class _InputIterator, class _OutputIterator, class _Predicate> 1817inline _LIBCPP_INLINE_VISIBILITY 1818_OutputIterator 1819copy_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 1835template<class _InputIterator, class _Size, class _OutputIterator> 1836inline _LIBCPP_INLINE_VISIBILITY 1837typename enable_if 1838< 1839 __is_input_iterator<_InputIterator>::value && 1840 !__is_random_access_iterator<_InputIterator>::value, 1841 _OutputIterator 1842>::type 1843copy_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 1861template<class _InputIterator, class _Size, class _OutputIterator> 1862inline _LIBCPP_INLINE_VISIBILITY 1863typename enable_if 1864< 1865 __is_random_access_iterator<_InputIterator>::value, 1866 _OutputIterator 1867>::type 1868copy_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 1877template <class _InputIterator, class _OutputIterator> 1878inline _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 1887template <class _Tp, class _Up> 1888inline _LIBCPP_INLINE_VISIBILITY 1889typename 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 1903template <class _InputIterator, class _OutputIterator> 1904inline _LIBCPP_INLINE_VISIBILITY 1905_OutputIterator 1906move(_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 1913template <class _InputIterator, class _OutputIterator> 1914inline _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 1923template <class _Tp, class _Up> 1924inline _LIBCPP_INLINE_VISIBILITY 1925typename 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 1942template <class _BidirectionalIterator1, class _BidirectionalIterator2> 1943inline _LIBCPP_INLINE_VISIBILITY 1944_BidirectionalIterator2 1945move_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 1957template <class _InputIterator, class _OutputIterator, class _UnaryOperation> 1958inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1959_OutputIterator 1960transform(_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 1967template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation> 1968inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1969_OutputIterator 1970transform(_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 1980template <class _ForwardIterator, class _Tp> 1981inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1982void 1983replace(_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 1992template <class _ForwardIterator, class _Predicate, class _Tp> 1993inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1994void 1995replace_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 2004template <class _InputIterator, class _OutputIterator, class _Tp> 2005inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2006_OutputIterator 2007replace_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 2020template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp> 2021inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2022_OutputIterator 2023replace_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 2036template <class _OutputIterator, class _Size, class _Tp> 2037inline _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 2046template <class _OutputIterator, class _Size, class _Tp> 2047inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2048_OutputIterator 2049fill_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 2056template <class _ForwardIterator, class _Tp> 2057inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2058void 2059__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag) 2060{ 2061 for (; __first != __last; ++__first) 2062 *__first = __value_; 2063} 2064 2065template <class _RandomAccessIterator, class _Tp> 2066inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2067void 2068__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag) 2069{ 2070 _VSTD::fill_n(__first, __last - __first, __value_); 2071} 2072 2073template <class _ForwardIterator, class _Tp> 2074inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2075void 2076fill(_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 2083template <class _ForwardIterator, class _Generator> 2084inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2085void 2086generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen) 2087{ 2088 for (; __first != __last; ++__first) 2089 *__first = __gen(); 2090} 2091 2092// generate_n 2093 2094template <class _OutputIterator, class _Size, class _Generator> 2095inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2096_OutputIterator 2097generate_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 2108template <class _ForwardIterator, class _Tp> 2109_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 2110remove(_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 2130template <class _ForwardIterator, class _Predicate> 2131_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 2132remove_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 2153template <class _InputIterator, class _OutputIterator, class _Tp> 2154inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2155_OutputIterator 2156remove_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 2171template <class _InputIterator, class _OutputIterator, class _Predicate> 2172inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2173_OutputIterator 2174remove_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 2189template <class _ForwardIterator, class _BinaryPredicate> 2190_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 2191unique(_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 2208template <class _ForwardIterator> 2209inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2210_ForwardIterator 2211unique(_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 2219template <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 2242template <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 2265template <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 2281template <class _InputIterator, class _OutputIterator, class _BinaryPredicate> 2282inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2283_OutputIterator 2284unique_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 2292template <class _InputIterator, class _OutputIterator> 2293inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2294_OutputIterator 2295unique_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 2303template <class _BidirectionalIterator> 2304inline _LIBCPP_INLINE_VISIBILITY 2305void 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 2317template <class _RandomAccessIterator> 2318inline _LIBCPP_INLINE_VISIBILITY 2319void 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 2327template <class _BidirectionalIterator> 2328inline _LIBCPP_INLINE_VISIBILITY 2329void 2330reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) 2331{ 2332 _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category()); 2333} 2334 2335// reverse_copy 2336 2337template <class _BidirectionalIterator, class _OutputIterator> 2338inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 2339_OutputIterator 2340reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result) 2341{ 2342 for (; __first != __last; ++__result) 2343 *__result = *--__last; 2344 return __result; 2345} 2346 2347// rotate 2348 2349template <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 2360template <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 2372template <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 2407template<typename _Integral> 2408inline _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 2421template<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 2456template <class _ForwardIterator> 2457inline _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 2471template <class _BidirectionalIterator> 2472inline _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 2488template <class _RandomAccessIterator> 2489inline _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 2506template <class _ForwardIterator> 2507inline _LIBCPP_INLINE_VISIBILITY 2508_ForwardIterator 2509rotate(_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 2521template <class _ForwardIterator, class _OutputIterator> 2522inline _LIBCPP_INLINE_VISIBILITY 2523_OutputIterator 2524rotate_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 2531template <class _ForwardIterator, class _Compare> 2532inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2533_ForwardIterator 2534min_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 2546template <class _ForwardIterator> 2547inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2548_ForwardIterator 2549min_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 2557template <class _Tp, class _Compare> 2558inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2559const _Tp& 2560min(const _Tp& __a, const _Tp& __b, _Compare __comp) 2561{ 2562 return __comp(__b, __a) ? __b : __a; 2563} 2564 2565template <class _Tp> 2566inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2567const _Tp& 2568min(const _Tp& __a, const _Tp& __b) 2569{ 2570 return _VSTD::min(__a, __b, __less<_Tp>()); 2571} 2572 2573#ifndef _LIBCPP_CXX03_LANG 2574 2575template<class _Tp, class _Compare> 2576inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2577_Tp 2578min(initializer_list<_Tp> __t, _Compare __comp) 2579{ 2580 return *_VSTD::min_element(__t.begin(), __t.end(), __comp); 2581} 2582 2583template<class _Tp> 2584inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2585_Tp 2586min(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 2595template <class _ForwardIterator, class _Compare> 2596inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2597_ForwardIterator 2598max_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 2611template <class _ForwardIterator> 2612inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2613_ForwardIterator 2614max_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 2622template <class _Tp, class _Compare> 2623inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2624const _Tp& 2625max(const _Tp& __a, const _Tp& __b, _Compare __comp) 2626{ 2627 return __comp(__a, __b) ? __b : __a; 2628} 2629 2630template <class _Tp> 2631inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2632const _Tp& 2633max(const _Tp& __a, const _Tp& __b) 2634{ 2635 return _VSTD::max(__a, __b, __less<_Tp>()); 2636} 2637 2638#ifndef _LIBCPP_CXX03_LANG 2639 2640template<class _Tp, class _Compare> 2641inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2642_Tp 2643max(initializer_list<_Tp> __t, _Compare __comp) 2644{ 2645 return *_VSTD::max_element(__t.begin(), __t.end(), __comp); 2646} 2647 2648template<class _Tp> 2649inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2650_Tp 2651max(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 2660template<class _Tp, class _Compare> 2661inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 2662const _Tp& 2663clamp(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 2670template<class _Tp> 2671inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 2672const _Tp& 2673clamp(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 2681template <class _ForwardIterator, class _Compare> 2682_LIBCPP_CONSTEXPR_AFTER_CXX11 2683std::pair<_ForwardIterator, _ForwardIterator> 2684minmax_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 2729template <class _ForwardIterator> 2730inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2731std::pair<_ForwardIterator, _ForwardIterator> 2732minmax_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 2740template<class _Tp, class _Compare> 2741inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2742pair<const _Tp&, const _Tp&> 2743minmax(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 2749template<class _Tp> 2750inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2751pair<const _Tp&, const _Tp&> 2752minmax(const _Tp& __a, const _Tp& __b) 2753{ 2754 return _VSTD::minmax(__a, __b, __less<_Tp>()); 2755} 2756 2757#ifndef _LIBCPP_CXX03_LANG 2758 2759template<class _Tp, class _Compare> 2760inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2761pair<_Tp, _Tp> 2762minmax(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 2796template<class _Tp> 2797inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 2798pair<_Tp, _Tp> 2799minmax(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 2810template <unsigned long long _Xp, size_t _Rp> 2811struct __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 2817template <unsigned long long _Xp> 2818struct __log2_imp<_Xp, 0> 2819{ 2820 static const size_t value = 0; 2821}; 2822 2823template <size_t _Rp> 2824struct __log2_imp<0, _Rp> 2825{ 2826 static const size_t value = _Rp + 1; 2827}; 2828 2829template <class _UIntType, _UIntType _Xp> 2830struct __log2 2831{ 2832 static const size_t value = __log2_imp<_Xp, 2833 sizeof(_UIntType) * __CHAR_BIT__ - 1>::value; 2834}; 2835 2836template<class _Engine, class _UIntType> 2837class __independent_bits_engine 2838{ 2839public: 2840 // types 2841 typedef _UIntType result_type; 2842 2843private: 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 2873public: 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 2880private: 2881 result_type __eval(false_type); 2882 result_type __eval(true_type); 2883}; 2884 2885template<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 2920template<class _Engine, class _UIntType> 2921inline 2922_UIntType 2923__independent_bits_engine<_Engine, _UIntType>::__eval(false_type) 2924{ 2925 return static_cast<result_type>(__e_() & __mask0_); 2926} 2927 2928template<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 2965template<class _IntType = int> 2966class uniform_int_distribution 2967{ 2968public: 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 2992private: 2993 param_type __p_; 2994 2995public: 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 3026template<class _IntType> 3027template<class _URNG> 3028typename uniform_int_distribution<_IntType>::result_type 3029uniform_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) 3054class _LIBCPP_TYPE_VIS __rs_default; 3055 3056_LIBCPP_FUNC_VIS __rs_default __rs_get(); 3057 3058class _LIBCPP_TYPE_VIS __rs_default 3059{ 3060 static unsigned __c_; 3061 3062 __rs_default(); 3063public: 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 3082template <class _RandomAccessIterator> 3083void 3084random_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 3103template <class _RandomAccessIterator, class _RandomNumberGenerator> 3104void 3105random_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 3125template <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 3146template <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 3166template <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 3187template <class _PopulationIterator, class _SampleIterator, class _Distance, 3188 class _UniformRandomNumberGenerator> 3189inline _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 3197template<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 3221template <class _InputIterator, class _Predicate> 3222_LIBCPP_CONSTEXPR_AFTER_CXX17 bool 3223is_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 3239template <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 3262template <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 3287template <class _ForwardIterator, class _Predicate> 3288inline _LIBCPP_INLINE_VISIBILITY 3289_ForwardIterator 3290partition(_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 3298template <class _InputIterator, class _OutputIterator1, 3299 class _OutputIterator2, class _Predicate> 3300_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_OutputIterator1, _OutputIterator2> 3301partition_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 3323template<class _ForwardIterator, class _Predicate> 3324_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 3325partition_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 3347template <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 3433struct __return_temporary_buffer 3434{ 3435 template <class _Tp> 3436 _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);} 3437}; 3438 3439template <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 3470template <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 3578template <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 3618template <class _ForwardIterator, class _Predicate> 3619inline _LIBCPP_INLINE_VISIBILITY 3620_ForwardIterator 3621stable_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 3629template <class _ForwardIterator, class _Compare> 3630_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator 3631is_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 3646template<class _ForwardIterator> 3647inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 3648_ForwardIterator 3649is_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 3656template <class _ForwardIterator, class _Compare> 3657inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 3658bool 3659is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 3660{ 3661 return _VSTD::is_sorted_until(__first, __last, __comp) == __last; 3662} 3663 3664template<class _ForwardIterator> 3665inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 3666bool 3667is_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 3676template <class _Compare, class _ForwardIterator> 3677unsigned 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 3713template <class _Compare, class _ForwardIterator> 3714unsigned 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 3739template <class _Compare, class _ForwardIterator> 3740unsigned 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 3769template <class _Compare, class _BirdirectionalIterator> 3770void 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 3784template <class _Compare, class _BirdirectionalIterator> 3785void 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 3803template <class _Compare, class _RandomAccessIterator> 3804void 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 3828template <class _Compare, class _RandomAccessIterator> 3829bool 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 3877template <class _Compare, class _BirdirectionalIterator> 3878void 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 3912template <class _Compare, class _RandomAccessIterator> 3913void 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 4106template <class _RandomAccessIterator, class _Compare> 4107inline _LIBCPP_INLINE_VISIBILITY 4108void 4109sort(_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 4121template <class _RandomAccessIterator> 4122inline _LIBCPP_INLINE_VISIBILITY 4123void 4124sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 4125{ 4126 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4127} 4128 4129template <class _Tp> 4130inline _LIBCPP_INLINE_VISIBILITY 4131void 4132sort(_Tp** __first, _Tp** __last) 4133{ 4134 _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>()); 4135} 4136 4137template <class _Tp> 4138inline _LIBCPP_INLINE_VISIBILITY 4139void 4140sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last) 4141{ 4142 _VSTD::sort(__first.base(), __last.base()); 4143} 4144 4145template <class _Tp, class _Compare> 4146inline _LIBCPP_INLINE_VISIBILITY 4147void 4148sort(__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 4190template <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 4212template <class _ForwardIterator, class _Tp, class _Compare> 4213inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4214_ForwardIterator 4215lower_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 4227template <class _ForwardIterator, class _Tp> 4228inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4229_ForwardIterator 4230lower_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 4238template <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 4260template <class _ForwardIterator, class _Tp, class _Compare> 4261inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4262_ForwardIterator 4263upper_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 4275template <class _ForwardIterator, class _Tp> 4276inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4277_ForwardIterator 4278upper_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 4286template <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 4320template <class _ForwardIterator, class _Tp, class _Compare> 4321inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4322pair<_ForwardIterator, _ForwardIterator> 4323equal_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 4335template <class _ForwardIterator, class _Tp> 4336inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4337pair<_ForwardIterator, _ForwardIterator> 4338equal_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 4346template <class _Compare, class _ForwardIterator, class _Tp> 4347inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4348bool 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 4355template <class _ForwardIterator, class _Tp, class _Compare> 4356inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4357bool 4358binary_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 4370template <class _ForwardIterator, class _Tp> 4371inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4372bool 4373binary_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 4381template <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 4404template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 4405inline _LIBCPP_INLINE_VISIBILITY 4406_OutputIterator 4407merge(_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 4420template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 4421inline _LIBCPP_INLINE_VISIBILITY 4422_OutputIterator 4423merge(_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 4433template <class _Compare, class _InputIterator1, class _InputIterator2, 4434 class _OutputIterator> 4435void __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 4461template <class _Compare, class _BidirectionalIterator> 4462void 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 4491template <class _Compare, class _BidirectionalIterator> 4492void 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 4579template <class _BidirectionalIterator, class _Compare> 4580inline _LIBCPP_INLINE_VISIBILITY 4581void 4582inplace_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 4605template <class _BidirectionalIterator> 4606inline _LIBCPP_INLINE_VISIBILITY 4607void 4608inplace_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 4616template <class _Compare, class _InputIterator1, class _InputIterator2> 4617void 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 4656template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 4657void 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 4685template <class _Compare, class _RandomAccessIterator> 4686void 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 4691template <class _Compare, class _RandomAccessIterator> 4692void 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 4737template <class _Tp> 4738struct __stable_sort_switch 4739{ 4740 static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value; 4741}; 4742 4743template <class _Compare, class _RandomAccessIterator> 4744void 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 4789template <class _RandomAccessIterator, class _Compare> 4790inline _LIBCPP_INLINE_VISIBILITY 4791void 4792stable_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 4814template <class _RandomAccessIterator> 4815inline _LIBCPP_INLINE_VISIBILITY 4816void 4817stable_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 4824template <class _RandomAccessIterator, class _Compare> 4825_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator 4826is_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 4851template<class _RandomAccessIterator> 4852inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4853_RandomAccessIterator 4854is_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 4861template <class _RandomAccessIterator, class _Compare> 4862inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4863bool 4864is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4865{ 4866 return _VSTD::is_heap_until(__first, __last, __comp) == __last; 4867} 4868 4869template<class _RandomAccessIterator> 4870inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 4871bool 4872is_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 4879template <class _Compare, class _RandomAccessIterator> 4880void 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 4906template <class _RandomAccessIterator, class _Compare> 4907inline _LIBCPP_INLINE_VISIBILITY 4908void 4909push_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 4921template <class _RandomAccessIterator> 4922inline _LIBCPP_INLINE_VISIBILITY 4923void 4924push_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 4931template <class _Compare, class _RandomAccessIterator> 4932void 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 4986template <class _Compare, class _RandomAccessIterator> 4987inline _LIBCPP_INLINE_VISIBILITY 4988void 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 4999template <class _RandomAccessIterator, class _Compare> 5000inline _LIBCPP_INLINE_VISIBILITY 5001void 5002pop_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 5014template <class _RandomAccessIterator> 5015inline _LIBCPP_INLINE_VISIBILITY 5016void 5017pop_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 5024template <class _Compare, class _RandomAccessIterator> 5025void 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 5040template <class _RandomAccessIterator, class _Compare> 5041inline _LIBCPP_INLINE_VISIBILITY 5042void 5043make_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 5055template <class _RandomAccessIterator> 5056inline _LIBCPP_INLINE_VISIBILITY 5057void 5058make_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 5065template <class _Compare, class _RandomAccessIterator> 5066void 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 5074template <class _RandomAccessIterator, class _Compare> 5075inline _LIBCPP_INLINE_VISIBILITY 5076void 5077sort_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 5089template <class _RandomAccessIterator> 5090inline _LIBCPP_INLINE_VISIBILITY 5091void 5092sort_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 5099template <class _Compare, class _RandomAccessIterator> 5100void 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 5117template <class _RandomAccessIterator, class _Compare> 5118inline _LIBCPP_INLINE_VISIBILITY 5119void 5120partial_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 5133template <class _RandomAccessIterator> 5134inline _LIBCPP_INLINE_VISIBILITY 5135void 5136partial_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 5144template <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 5167template <class _InputIterator, class _RandomAccessIterator, class _Compare> 5168inline _LIBCPP_INLINE_VISIBILITY 5169_RandomAccessIterator 5170partial_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 5183template <class _InputIterator, class _RandomAccessIterator> 5184inline _LIBCPP_INLINE_VISIBILITY 5185_RandomAccessIterator 5186partial_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 5195template <class _Compare, class _RandomAccessIterator> 5196void 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 } 5367not_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 5382template <class _RandomAccessIterator, class _Compare> 5383inline _LIBCPP_INLINE_VISIBILITY 5384void 5385nth_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 5397template <class _RandomAccessIterator> 5398inline _LIBCPP_INLINE_VISIBILITY 5399void 5400nth_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 5407template <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 5422template <class _InputIterator1, class _InputIterator2, class _Compare> 5423inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5424bool 5425includes(_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 5438template <class _InputIterator1, class _InputIterator2> 5439inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5440bool 5441includes(_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 5450template <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 5475template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5476inline _LIBCPP_INLINE_VISIBILITY 5477_OutputIterator 5478set_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 5491template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5492inline _LIBCPP_INLINE_VISIBILITY 5493_OutputIterator 5494set_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 5504template <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 5527template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5528inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5529_OutputIterator 5530set_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 5543template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5544inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5545_OutputIterator 5546set_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 5556template <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 5581template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5582inline _LIBCPP_INLINE_VISIBILITY 5583_OutputIterator 5584set_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 5597template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5598inline _LIBCPP_INLINE_VISIBILITY 5599_OutputIterator 5600set_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 5610template <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 5640template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5641inline _LIBCPP_INLINE_VISIBILITY 5642_OutputIterator 5643set_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 5656template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5657inline _LIBCPP_INLINE_VISIBILITY 5658_OutputIterator 5659set_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 5669template <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 5684template <class _InputIterator1, class _InputIterator2, class _Compare> 5685inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5686bool 5687lexicographical_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 5700template <class _InputIterator1, class _InputIterator2> 5701inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 5702bool 5703lexicographical_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 5713template <class _Compare, class _BidirectionalIterator> 5714bool 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 5740template <class _BidirectionalIterator, class _Compare> 5741inline _LIBCPP_INLINE_VISIBILITY 5742bool 5743next_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 5755template <class _BidirectionalIterator> 5756inline _LIBCPP_INLINE_VISIBILITY 5757bool 5758next_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 5766template <class _Compare, class _BidirectionalIterator> 5767bool 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 5793template <class _BidirectionalIterator, class _Compare> 5794inline _LIBCPP_INLINE_VISIBILITY 5795bool 5796prev_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 5808template <class _BidirectionalIterator> 5809inline _LIBCPP_INLINE_VISIBILITY 5810bool 5811prev_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