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