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