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