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