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