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