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