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_CXX03_LANG 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_CXX03_LANG 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_CXX03_LANG 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_CXX03_LANG 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_CXX03_LANG 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_CXX03_LANG 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_CXX03_LANG 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) \ 3030 || defined(_LIBCPP_BUILDING_LIBRARY) 3031class _LIBCPP_TYPE_VIS __rs_default; 3032 3033_LIBCPP_FUNC_VIS __rs_default __rs_get(); 3034 3035class _LIBCPP_TYPE_VIS __rs_default 3036{ 3037 static unsigned __c_; 3038 3039 __rs_default(); 3040public: 3041 typedef uint_fast32_t result_type; 3042 3043 static const result_type _Min = 0; 3044 static const result_type _Max = 0xFFFFFFFF; 3045 3046 __rs_default(const __rs_default&); 3047 ~__rs_default(); 3048 3049 result_type operator()(); 3050 3051 static _LIBCPP_CONSTEXPR result_type min() {return _Min;} 3052 static _LIBCPP_CONSTEXPR result_type max() {return _Max;} 3053 3054 friend _LIBCPP_FUNC_VIS __rs_default __rs_get(); 3055}; 3056 3057_LIBCPP_FUNC_VIS __rs_default __rs_get(); 3058 3059template <class _RandomAccessIterator> 3060void 3061random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 3062{ 3063 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 3064 typedef uniform_int_distribution<ptrdiff_t> _Dp; 3065 typedef typename _Dp::param_type _Pp; 3066 difference_type __d = __last - __first; 3067 if (__d > 1) 3068 { 3069 _Dp __uid; 3070 __rs_default __g = __rs_get(); 3071 for (--__last, --__d; __first < __last; ++__first, --__d) 3072 { 3073 difference_type __i = __uid(__g, _Pp(0, __d)); 3074 if (__i != difference_type(0)) 3075 swap(*__first, *(__first + __i)); 3076 } 3077 } 3078} 3079 3080template <class _RandomAccessIterator, class _RandomNumberGenerator> 3081void 3082random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 3083#ifndef _LIBCPP_CXX03_LANG 3084 _RandomNumberGenerator&& __rand) 3085#else 3086 _RandomNumberGenerator& __rand) 3087#endif 3088{ 3089 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 3090 difference_type __d = __last - __first; 3091 if (__d > 1) 3092 { 3093 for (--__last; __first < __last; ++__first, --__d) 3094 { 3095 difference_type __i = __rand(__d); 3096 swap(*__first, *(__first + __i)); 3097 } 3098 } 3099} 3100#endif 3101 3102template <class _PopulationIterator, class _SampleIterator, class _Distance, 3103 class _UniformRandomNumberGenerator> 3104_LIBCPP_INLINE_VISIBILITY 3105_SampleIterator __sample(_PopulationIterator __first, 3106 _PopulationIterator __last, _SampleIterator __output, 3107 _Distance __n, 3108 _UniformRandomNumberGenerator & __g, 3109 input_iterator_tag) { 3110 3111 _Distance __k = 0; 3112 for (; __first != __last && __k < __n; ++__first, (void)++__k) 3113 __output[__k] = *__first; 3114 _Distance __sz = __k; 3115 for (; __first != __last; ++__first, (void)++__k) { 3116 _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g); 3117 if (__r < __sz) 3118 __output[__r] = *__first; 3119 } 3120 return __output + _VSTD::min(__n, __k); 3121} 3122 3123template <class _PopulationIterator, class _SampleIterator, class _Distance, 3124 class _UniformRandomNumberGenerator> 3125_LIBCPP_INLINE_VISIBILITY 3126_SampleIterator __sample(_PopulationIterator __first, 3127 _PopulationIterator __last, _SampleIterator __output, 3128 _Distance __n, 3129 _UniformRandomNumberGenerator& __g, 3130 forward_iterator_tag) { 3131 _Distance __unsampled_sz = _VSTD::distance(__first, __last); 3132 for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) { 3133 _Distance __r = 3134 _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g); 3135 if (__r < __n) { 3136 *__output++ = *__first; 3137 --__n; 3138 } 3139 } 3140 return __output; 3141} 3142 3143template <class _PopulationIterator, class _SampleIterator, class _Distance, 3144 class _UniformRandomNumberGenerator> 3145_LIBCPP_INLINE_VISIBILITY 3146_SampleIterator __sample(_PopulationIterator __first, 3147 _PopulationIterator __last, _SampleIterator __output, 3148 _Distance __n, _UniformRandomNumberGenerator& __g) { 3149 typedef typename iterator_traits<_PopulationIterator>::iterator_category 3150 _PopCategory; 3151 typedef typename iterator_traits<_PopulationIterator>::difference_type 3152 _Difference; 3153 static_assert(__is_forward_iterator<_PopulationIterator>::value || 3154 __is_random_access_iterator<_SampleIterator>::value, 3155 "SampleIterator must meet the requirements of RandomAccessIterator"); 3156 typedef typename common_type<_Distance, _Difference>::type _CommonType; 3157 _LIBCPP_ASSERT(__n >= 0, "N must be a positive number."); 3158 return _VSTD::__sample( 3159 __first, __last, __output, _CommonType(__n), 3160 __g, _PopCategory()); 3161} 3162 3163#if _LIBCPP_STD_VER > 14 3164template <class _PopulationIterator, class _SampleIterator, class _Distance, 3165 class _UniformRandomNumberGenerator> 3166inline _LIBCPP_INLINE_VISIBILITY 3167_SampleIterator sample(_PopulationIterator __first, 3168 _PopulationIterator __last, _SampleIterator __output, 3169 _Distance __n, _UniformRandomNumberGenerator&& __g) { 3170 return _VSTD::__sample(__first, __last, __output, __n, __g); 3171} 3172#endif // _LIBCPP_STD_VER > 14 3173 3174template<class _RandomAccessIterator, class _UniformRandomNumberGenerator> 3175 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 3176#ifndef _LIBCPP_CXX03_LANG 3177 _UniformRandomNumberGenerator&& __g) 3178#else 3179 _UniformRandomNumberGenerator& __g) 3180#endif 3181{ 3182 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 3183 typedef uniform_int_distribution<ptrdiff_t> _Dp; 3184 typedef typename _Dp::param_type _Pp; 3185 difference_type __d = __last - __first; 3186 if (__d > 1) 3187 { 3188 _Dp __uid; 3189 for (--__last, --__d; __first < __last; ++__first, --__d) 3190 { 3191 difference_type __i = __uid(__g, _Pp(0, __d)); 3192 if (__i != difference_type(0)) 3193 swap(*__first, *(__first + __i)); 3194 } 3195 } 3196} 3197 3198template <class _InputIterator, class _Predicate> 3199bool 3200is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred) 3201{ 3202 for (; __first != __last; ++__first) 3203 if (!__pred(*__first)) 3204 break; 3205 if ( __first == __last ) 3206 return true; 3207 ++__first; 3208 for (; __first != __last; ++__first) 3209 if (__pred(*__first)) 3210 return false; 3211 return true; 3212} 3213 3214// partition 3215 3216template <class _Predicate, class _ForwardIterator> 3217_ForwardIterator 3218__partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag) 3219{ 3220 while (true) 3221 { 3222 if (__first == __last) 3223 return __first; 3224 if (!__pred(*__first)) 3225 break; 3226 ++__first; 3227 } 3228 for (_ForwardIterator __p = __first; ++__p != __last;) 3229 { 3230 if (__pred(*__p)) 3231 { 3232 swap(*__first, *__p); 3233 ++__first; 3234 } 3235 } 3236 return __first; 3237} 3238 3239template <class _Predicate, class _BidirectionalIterator> 3240_BidirectionalIterator 3241__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 3242 bidirectional_iterator_tag) 3243{ 3244 while (true) 3245 { 3246 while (true) 3247 { 3248 if (__first == __last) 3249 return __first; 3250 if (!__pred(*__first)) 3251 break; 3252 ++__first; 3253 } 3254 do 3255 { 3256 if (__first == --__last) 3257 return __first; 3258 } while (!__pred(*__last)); 3259 swap(*__first, *__last); 3260 ++__first; 3261 } 3262} 3263 3264template <class _ForwardIterator, class _Predicate> 3265inline _LIBCPP_INLINE_VISIBILITY 3266_ForwardIterator 3267partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 3268{ 3269 return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type> 3270 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); 3271} 3272 3273// partition_copy 3274 3275template <class _InputIterator, class _OutputIterator1, 3276 class _OutputIterator2, class _Predicate> 3277pair<_OutputIterator1, _OutputIterator2> 3278partition_copy(_InputIterator __first, _InputIterator __last, 3279 _OutputIterator1 __out_true, _OutputIterator2 __out_false, 3280 _Predicate __pred) 3281{ 3282 for (; __first != __last; ++__first) 3283 { 3284 if (__pred(*__first)) 3285 { 3286 *__out_true = *__first; 3287 ++__out_true; 3288 } 3289 else 3290 { 3291 *__out_false = *__first; 3292 ++__out_false; 3293 } 3294 } 3295 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false); 3296} 3297 3298// partition_point 3299 3300template<class _ForwardIterator, class _Predicate> 3301_ForwardIterator 3302partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 3303{ 3304 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 3305 difference_type __len = _VSTD::distance(__first, __last); 3306 while (__len != 0) 3307 { 3308 difference_type __l2 = __len / 2; 3309 _ForwardIterator __m = __first; 3310 _VSTD::advance(__m, __l2); 3311 if (__pred(*__m)) 3312 { 3313 __first = ++__m; 3314 __len -= __l2 + 1; 3315 } 3316 else 3317 __len = __l2; 3318 } 3319 return __first; 3320} 3321 3322// stable_partition 3323 3324template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair> 3325_ForwardIterator 3326__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, 3327 _Distance __len, _Pair __p, forward_iterator_tag __fit) 3328{ 3329 // *__first is known to be false 3330 // __len >= 1 3331 if (__len == 1) 3332 return __first; 3333 if (__len == 2) 3334 { 3335 _ForwardIterator __m = __first; 3336 if (__pred(*++__m)) 3337 { 3338 swap(*__first, *__m); 3339 return __m; 3340 } 3341 return __first; 3342 } 3343 if (__len <= __p.second) 3344 { // The buffer is big enough to use 3345 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 3346 __destruct_n __d(0); 3347 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); 3348 // Move the falses into the temporary buffer, and the trues to the front of the line 3349 // Update __first to always point to the end of the trues 3350 value_type* __t = __p.first; 3351 ::new(__t) value_type(_VSTD::move(*__first)); 3352 __d.__incr((value_type*)0); 3353 ++__t; 3354 _ForwardIterator __i = __first; 3355 while (++__i != __last) 3356 { 3357 if (__pred(*__i)) 3358 { 3359 *__first = _VSTD::move(*__i); 3360 ++__first; 3361 } 3362 else 3363 { 3364 ::new(__t) value_type(_VSTD::move(*__i)); 3365 __d.__incr((value_type*)0); 3366 ++__t; 3367 } 3368 } 3369 // All trues now at start of range, all falses in buffer 3370 // Move falses back into range, but don't mess up __first which points to first false 3371 __i = __first; 3372 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i) 3373 *__i = _VSTD::move(*__t2); 3374 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer 3375 return __first; 3376 } 3377 // Else not enough buffer, do in place 3378 // __len >= 3 3379 _ForwardIterator __m = __first; 3380 _Distance __len2 = __len / 2; // __len2 >= 2 3381 _VSTD::advance(__m, __len2); 3382 // recurse on [__first, __m), *__first know to be false 3383 // F????????????????? 3384 // f m l 3385 typedef typename add_lvalue_reference<_Predicate>::type _PredRef; 3386 _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit); 3387 // TTTFFFFF?????????? 3388 // f ff m l 3389 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true 3390 _ForwardIterator __m1 = __m; 3391 _ForwardIterator __second_false = __last; 3392 _Distance __len_half = __len - __len2; 3393 while (__pred(*__m1)) 3394 { 3395 if (++__m1 == __last) 3396 goto __second_half_done; 3397 --__len_half; 3398 } 3399 // TTTFFFFFTTTF?????? 3400 // f ff m m1 l 3401 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit); 3402__second_half_done: 3403 // TTTFFFFFTTTTTFFFFF 3404 // f ff m sf l 3405 return _VSTD::rotate(__first_false, __m, __second_false); 3406 // TTTTTTTTFFFFFFFFFF 3407 // | 3408} 3409 3410struct __return_temporary_buffer 3411{ 3412 template <class _Tp> 3413 _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);} 3414}; 3415 3416template <class _Predicate, class _ForwardIterator> 3417_ForwardIterator 3418__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, 3419 forward_iterator_tag) 3420{ 3421 const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment 3422 // Either prove all true and return __first or point to first false 3423 while (true) 3424 { 3425 if (__first == __last) 3426 return __first; 3427 if (!__pred(*__first)) 3428 break; 3429 ++__first; 3430 } 3431 // We now have a reduced range [__first, __last) 3432 // *__first is known to be false 3433 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 3434 typedef typename iterator_traits<_ForwardIterator>::value_type value_type; 3435 difference_type __len = _VSTD::distance(__first, __last); 3436 pair<value_type*, ptrdiff_t> __p(0, 0); 3437 unique_ptr<value_type, __return_temporary_buffer> __h; 3438 if (__len >= __alloc_limit) 3439 { 3440 __p = _VSTD::get_temporary_buffer<value_type>(__len); 3441 __h.reset(__p.first); 3442 } 3443 return __stable_partition<typename add_lvalue_reference<_Predicate>::type> 3444 (__first, __last, __pred, __len, __p, forward_iterator_tag()); 3445} 3446 3447template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair> 3448_BidirectionalIterator 3449__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 3450 _Distance __len, _Pair __p, bidirectional_iterator_tag __bit) 3451{ 3452 // *__first is known to be false 3453 // *__last is known to be true 3454 // __len >= 2 3455 if (__len == 2) 3456 { 3457 swap(*__first, *__last); 3458 return __last; 3459 } 3460 if (__len == 3) 3461 { 3462 _BidirectionalIterator __m = __first; 3463 if (__pred(*++__m)) 3464 { 3465 swap(*__first, *__m); 3466 swap(*__m, *__last); 3467 return __last; 3468 } 3469 swap(*__m, *__last); 3470 swap(*__first, *__m); 3471 return __m; 3472 } 3473 if (__len <= __p.second) 3474 { // The buffer is big enough to use 3475 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 3476 __destruct_n __d(0); 3477 unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); 3478 // Move the falses into the temporary buffer, and the trues to the front of the line 3479 // Update __first to always point to the end of the trues 3480 value_type* __t = __p.first; 3481 ::new(__t) value_type(_VSTD::move(*__first)); 3482 __d.__incr((value_type*)0); 3483 ++__t; 3484 _BidirectionalIterator __i = __first; 3485 while (++__i != __last) 3486 { 3487 if (__pred(*__i)) 3488 { 3489 *__first = _VSTD::move(*__i); 3490 ++__first; 3491 } 3492 else 3493 { 3494 ::new(__t) value_type(_VSTD::move(*__i)); 3495 __d.__incr((value_type*)0); 3496 ++__t; 3497 } 3498 } 3499 // move *__last, known to be true 3500 *__first = _VSTD::move(*__i); 3501 __i = ++__first; 3502 // All trues now at start of range, all falses in buffer 3503 // Move falses back into range, but don't mess up __first which points to first false 3504 for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i) 3505 *__i = _VSTD::move(*__t2); 3506 // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer 3507 return __first; 3508 } 3509 // Else not enough buffer, do in place 3510 // __len >= 4 3511 _BidirectionalIterator __m = __first; 3512 _Distance __len2 = __len / 2; // __len2 >= 2 3513 _VSTD::advance(__m, __len2); 3514 // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false 3515 // F????????????????T 3516 // f m l 3517 _BidirectionalIterator __m1 = __m; 3518 _BidirectionalIterator __first_false = __first; 3519 _Distance __len_half = __len2; 3520 while (!__pred(*--__m1)) 3521 { 3522 if (__m1 == __first) 3523 goto __first_half_done; 3524 --__len_half; 3525 } 3526 // F???TFFF?????????T 3527 // f m1 m l 3528 typedef typename add_lvalue_reference<_Predicate>::type _PredRef; 3529 __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit); 3530__first_half_done: 3531 // TTTFFFFF?????????T 3532 // f ff m l 3533 // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true 3534 __m1 = __m; 3535 _BidirectionalIterator __second_false = __last; 3536 ++__second_false; 3537 __len_half = __len - __len2; 3538 while (__pred(*__m1)) 3539 { 3540 if (++__m1 == __last) 3541 goto __second_half_done; 3542 --__len_half; 3543 } 3544 // TTTFFFFFTTTF?????T 3545 // f ff m m1 l 3546 __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit); 3547__second_half_done: 3548 // TTTFFFFFTTTTTFFFFF 3549 // f ff m sf l 3550 return _VSTD::rotate(__first_false, __m, __second_false); 3551 // TTTTTTTTFFFFFFFFFF 3552 // | 3553} 3554 3555template <class _Predicate, class _BidirectionalIterator> 3556_BidirectionalIterator 3557__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, 3558 bidirectional_iterator_tag) 3559{ 3560 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 3561 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 3562 const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment 3563 // Either prove all true and return __first or point to first false 3564 while (true) 3565 { 3566 if (__first == __last) 3567 return __first; 3568 if (!__pred(*__first)) 3569 break; 3570 ++__first; 3571 } 3572 // __first points to first false, everything prior to __first is already set. 3573 // Either prove [__first, __last) is all false and return __first, or point __last to last true 3574 do 3575 { 3576 if (__first == --__last) 3577 return __first; 3578 } while (!__pred(*__last)); 3579 // We now have a reduced range [__first, __last] 3580 // *__first is known to be false 3581 // *__last is known to be true 3582 // __len >= 2 3583 difference_type __len = _VSTD::distance(__first, __last) + 1; 3584 pair<value_type*, ptrdiff_t> __p(0, 0); 3585 unique_ptr<value_type, __return_temporary_buffer> __h; 3586 if (__len >= __alloc_limit) 3587 { 3588 __p = _VSTD::get_temporary_buffer<value_type>(__len); 3589 __h.reset(__p.first); 3590 } 3591 return __stable_partition<typename add_lvalue_reference<_Predicate>::type> 3592 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag()); 3593} 3594 3595template <class _ForwardIterator, class _Predicate> 3596inline _LIBCPP_INLINE_VISIBILITY 3597_ForwardIterator 3598stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) 3599{ 3600 return __stable_partition<typename add_lvalue_reference<_Predicate>::type> 3601 (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); 3602} 3603 3604// is_sorted_until 3605 3606template <class _ForwardIterator, class _Compare> 3607_ForwardIterator 3608is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 3609{ 3610 if (__first != __last) 3611 { 3612 _ForwardIterator __i = __first; 3613 while (++__i != __last) 3614 { 3615 if (__comp(*__i, *__first)) 3616 return __i; 3617 __first = __i; 3618 } 3619 } 3620 return __last; 3621} 3622 3623template<class _ForwardIterator> 3624inline _LIBCPP_INLINE_VISIBILITY 3625_ForwardIterator 3626is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) 3627{ 3628 return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); 3629} 3630 3631// is_sorted 3632 3633template <class _ForwardIterator, class _Compare> 3634inline _LIBCPP_INLINE_VISIBILITY 3635bool 3636is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) 3637{ 3638 return _VSTD::is_sorted_until(__first, __last, __comp) == __last; 3639} 3640 3641template<class _ForwardIterator> 3642inline _LIBCPP_INLINE_VISIBILITY 3643bool 3644is_sorted(_ForwardIterator __first, _ForwardIterator __last) 3645{ 3646 return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); 3647} 3648 3649// sort 3650 3651// stable, 2-3 compares, 0-2 swaps 3652 3653template <class _Compare, class _ForwardIterator> 3654unsigned 3655__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c) 3656{ 3657 unsigned __r = 0; 3658 if (!__c(*__y, *__x)) // if x <= y 3659 { 3660 if (!__c(*__z, *__y)) // if y <= z 3661 return __r; // x <= y && y <= z 3662 // x <= y && y > z 3663 swap(*__y, *__z); // x <= z && y < z 3664 __r = 1; 3665 if (__c(*__y, *__x)) // if x > y 3666 { 3667 swap(*__x, *__y); // x < y && y <= z 3668 __r = 2; 3669 } 3670 return __r; // x <= y && y < z 3671 } 3672 if (__c(*__z, *__y)) // x > y, if y > z 3673 { 3674 swap(*__x, *__z); // x < y && y < z 3675 __r = 1; 3676 return __r; 3677 } 3678 swap(*__x, *__y); // x > y && y <= z 3679 __r = 1; // x < y && x <= z 3680 if (__c(*__z, *__y)) // if y > z 3681 { 3682 swap(*__y, *__z); // x <= y && y < z 3683 __r = 2; 3684 } 3685 return __r; 3686} // x <= y && y <= z 3687 3688// stable, 3-6 compares, 0-5 swaps 3689 3690template <class _Compare, class _ForwardIterator> 3691unsigned 3692__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 3693 _ForwardIterator __x4, _Compare __c) 3694{ 3695 unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c); 3696 if (__c(*__x4, *__x3)) 3697 { 3698 swap(*__x3, *__x4); 3699 ++__r; 3700 if (__c(*__x3, *__x2)) 3701 { 3702 swap(*__x2, *__x3); 3703 ++__r; 3704 if (__c(*__x2, *__x1)) 3705 { 3706 swap(*__x1, *__x2); 3707 ++__r; 3708 } 3709 } 3710 } 3711 return __r; 3712} 3713 3714// stable, 4-10 compares, 0-9 swaps 3715 3716template <class _Compare, class _ForwardIterator> 3717unsigned 3718__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 3719 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) 3720{ 3721 unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c); 3722 if (__c(*__x5, *__x4)) 3723 { 3724 swap(*__x4, *__x5); 3725 ++__r; 3726 if (__c(*__x4, *__x3)) 3727 { 3728 swap(*__x3, *__x4); 3729 ++__r; 3730 if (__c(*__x3, *__x2)) 3731 { 3732 swap(*__x2, *__x3); 3733 ++__r; 3734 if (__c(*__x2, *__x1)) 3735 { 3736 swap(*__x1, *__x2); 3737 ++__r; 3738 } 3739 } 3740 } 3741 } 3742 return __r; 3743} 3744 3745// Assumes size > 0 3746template <class _Compare, class _BirdirectionalIterator> 3747void 3748__selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp) 3749{ 3750 _BirdirectionalIterator __lm1 = __last; 3751 for (--__lm1; __first != __lm1; ++__first) 3752 { 3753 _BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator, 3754 typename add_lvalue_reference<_Compare>::type> 3755 (__first, __last, __comp); 3756 if (__i != __first) 3757 swap(*__first, *__i); 3758 } 3759} 3760 3761template <class _Compare, class _BirdirectionalIterator> 3762void 3763__insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp) 3764{ 3765 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type; 3766 if (__first != __last) 3767 { 3768 _BirdirectionalIterator __i = __first; 3769 for (++__i; __i != __last; ++__i) 3770 { 3771 _BirdirectionalIterator __j = __i; 3772 value_type __t(_VSTD::move(*__j)); 3773 for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j) 3774 *__j = _VSTD::move(*__k); 3775 *__j = _VSTD::move(__t); 3776 } 3777 } 3778} 3779 3780template <class _Compare, class _RandomAccessIterator> 3781void 3782__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 3783{ 3784 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 3785 _RandomAccessIterator __j = __first+2; 3786 __sort3<_Compare>(__first, __first+1, __j, __comp); 3787 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) 3788 { 3789 if (__comp(*__i, *__j)) 3790 { 3791 value_type __t(_VSTD::move(*__i)); 3792 _RandomAccessIterator __k = __j; 3793 __j = __i; 3794 do 3795 { 3796 *__j = _VSTD::move(*__k); 3797 __j = __k; 3798 } while (__j != __first && __comp(__t, *--__k)); 3799 *__j = _VSTD::move(__t); 3800 } 3801 __j = __i; 3802 } 3803} 3804 3805template <class _Compare, class _RandomAccessIterator> 3806bool 3807__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 3808{ 3809 switch (__last - __first) 3810 { 3811 case 0: 3812 case 1: 3813 return true; 3814 case 2: 3815 if (__comp(*--__last, *__first)) 3816 swap(*__first, *__last); 3817 return true; 3818 case 3: 3819 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); 3820 return true; 3821 case 4: 3822 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); 3823 return true; 3824 case 5: 3825 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); 3826 return true; 3827 } 3828 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 3829 _RandomAccessIterator __j = __first+2; 3830 __sort3<_Compare>(__first, __first+1, __j, __comp); 3831 const unsigned __limit = 8; 3832 unsigned __count = 0; 3833 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) 3834 { 3835 if (__comp(*__i, *__j)) 3836 { 3837 value_type __t(_VSTD::move(*__i)); 3838 _RandomAccessIterator __k = __j; 3839 __j = __i; 3840 do 3841 { 3842 *__j = _VSTD::move(*__k); 3843 __j = __k; 3844 } while (__j != __first && __comp(__t, *--__k)); 3845 *__j = _VSTD::move(__t); 3846 if (++__count == __limit) 3847 return ++__i == __last; 3848 } 3849 __j = __i; 3850 } 3851 return true; 3852} 3853 3854template <class _Compare, class _BirdirectionalIterator> 3855void 3856__insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1, 3857 typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp) 3858{ 3859 typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type; 3860 if (__first1 != __last1) 3861 { 3862 __destruct_n __d(0); 3863 unique_ptr<value_type, __destruct_n&> __h(__first2, __d); 3864 value_type* __last2 = __first2; 3865 ::new(__last2) value_type(_VSTD::move(*__first1)); 3866 __d.__incr((value_type*)0); 3867 for (++__last2; ++__first1 != __last1; ++__last2) 3868 { 3869 value_type* __j2 = __last2; 3870 value_type* __i2 = __j2; 3871 if (__comp(*__first1, *--__i2)) 3872 { 3873 ::new(__j2) value_type(_VSTD::move(*__i2)); 3874 __d.__incr((value_type*)0); 3875 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) 3876 *__j2 = _VSTD::move(*__i2); 3877 *__j2 = _VSTD::move(*__first1); 3878 } 3879 else 3880 { 3881 ::new(__j2) value_type(_VSTD::move(*__first1)); 3882 __d.__incr((value_type*)0); 3883 } 3884 } 3885 __h.release(); 3886 } 3887} 3888 3889template <class _Compare, class _RandomAccessIterator> 3890void 3891__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 3892{ 3893 // _Compare is known to be a reference type 3894 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 3895 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 3896 const difference_type __limit = is_trivially_copy_constructible<value_type>::value && 3897 is_trivially_copy_assignable<value_type>::value ? 30 : 6; 3898 while (true) 3899 { 3900 __restart: 3901 difference_type __len = __last - __first; 3902 switch (__len) 3903 { 3904 case 0: 3905 case 1: 3906 return; 3907 case 2: 3908 if (__comp(*--__last, *__first)) 3909 swap(*__first, *__last); 3910 return; 3911 case 3: 3912 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); 3913 return; 3914 case 4: 3915 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); 3916 return; 3917 case 5: 3918 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); 3919 return; 3920 } 3921 if (__len <= __limit) 3922 { 3923 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); 3924 return; 3925 } 3926 // __len > 5 3927 _RandomAccessIterator __m = __first; 3928 _RandomAccessIterator __lm1 = __last; 3929 --__lm1; 3930 unsigned __n_swaps; 3931 { 3932 difference_type __delta; 3933 if (__len >= 1000) 3934 { 3935 __delta = __len/2; 3936 __m += __delta; 3937 __delta /= 2; 3938 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp); 3939 } 3940 else 3941 { 3942 __delta = __len/2; 3943 __m += __delta; 3944 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); 3945 } 3946 } 3947 // *__m is median 3948 // partition [__first, __m) < *__m and *__m <= [__m, __last) 3949 // (this inhibits tossing elements equivalent to __m around unnecessarily) 3950 _RandomAccessIterator __i = __first; 3951 _RandomAccessIterator __j = __lm1; 3952 // j points beyond range to be tested, *__m is known to be <= *__lm1 3953 // The search going up is known to be guarded but the search coming down isn't. 3954 // Prime the downward search with a guard. 3955 if (!__comp(*__i, *__m)) // if *__first == *__m 3956 { 3957 // *__first == *__m, *__first doesn't go in first part 3958 // manually guard downward moving __j against __i 3959 while (true) 3960 { 3961 if (__i == --__j) 3962 { 3963 // *__first == *__m, *__m <= all other elements 3964 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) 3965 ++__i; // __first + 1 3966 __j = __last; 3967 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) 3968 { 3969 while (true) 3970 { 3971 if (__i == __j) 3972 return; // [__first, __last) all equivalent elements 3973 if (__comp(*__first, *__i)) 3974 { 3975 swap(*__i, *__j); 3976 ++__n_swaps; 3977 ++__i; 3978 break; 3979 } 3980 ++__i; 3981 } 3982 } 3983 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 3984 if (__i == __j) 3985 return; 3986 while (true) 3987 { 3988 while (!__comp(*__first, *__i)) 3989 ++__i; 3990 while (__comp(*__first, *--__j)) 3991 ; 3992 if (__i >= __j) 3993 break; 3994 swap(*__i, *__j); 3995 ++__n_swaps; 3996 ++__i; 3997 } 3998 // [__first, __i) == *__first and *__first < [__i, __last) 3999 // The first part is sorted, sort the secod part 4000 // _VSTD::__sort<_Compare>(__i, __last, __comp); 4001 __first = __i; 4002 goto __restart; 4003 } 4004 if (__comp(*__j, *__m)) 4005 { 4006 swap(*__i, *__j); 4007 ++__n_swaps; 4008 break; // found guard for downward moving __j, now use unguarded partition 4009 } 4010 } 4011 } 4012 // It is known that *__i < *__m 4013 ++__i; 4014 // j points beyond range to be tested, *__m is known to be <= *__lm1 4015 // if not yet partitioned... 4016 if (__i < __j) 4017 { 4018 // known that *(__i - 1) < *__m 4019 // known that __i <= __m 4020 while (true) 4021 { 4022 // __m still guards upward moving __i 4023 while (__comp(*__i, *__m)) 4024 ++__i; 4025 // It is now known that a guard exists for downward moving __j 4026 while (!__comp(*--__j, *__m)) 4027 ; 4028 if (__i > __j) 4029 break; 4030 swap(*__i, *__j); 4031 ++__n_swaps; 4032 // It is known that __m != __j 4033 // If __m just moved, follow it 4034 if (__m == __i) 4035 __m = __j; 4036 ++__i; 4037 } 4038 } 4039 // [__first, __i) < *__m and *__m <= [__i, __last) 4040 if (__i != __m && __comp(*__m, *__i)) 4041 { 4042 swap(*__i, *__m); 4043 ++__n_swaps; 4044 } 4045 // [__first, __i) < *__i and *__i <= [__i+1, __last) 4046 // If we were given a perfect partition, see if insertion sort is quick... 4047 if (__n_swaps == 0) 4048 { 4049 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); 4050 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp)) 4051 { 4052 if (__fs) 4053 return; 4054 __last = __i; 4055 continue; 4056 } 4057 else 4058 { 4059 if (__fs) 4060 { 4061 __first = ++__i; 4062 continue; 4063 } 4064 } 4065 } 4066 // sort smaller range with recursive call and larger with tail recursion elimination 4067 if (__i - __first < __last - __i) 4068 { 4069 _VSTD::__sort<_Compare>(__first, __i, __comp); 4070 // _VSTD::__sort<_Compare>(__i+1, __last, __comp); 4071 __first = ++__i; 4072 } 4073 else 4074 { 4075 _VSTD::__sort<_Compare>(__i+1, __last, __comp); 4076 // _VSTD::__sort<_Compare>(__first, __i, __comp); 4077 __last = __i; 4078 } 4079 } 4080} 4081 4082// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare 4083template <class _RandomAccessIterator, class _Compare> 4084inline _LIBCPP_INLINE_VISIBILITY 4085void 4086sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4087{ 4088#ifdef _LIBCPP_DEBUG 4089 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4090 __debug_less<_Compare> __c(__comp); 4091 __sort<_Comp_ref>(__first, __last, __c); 4092#else // _LIBCPP_DEBUG 4093 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4094 __sort<_Comp_ref>(__first, __last, __comp); 4095#endif // _LIBCPP_DEBUG 4096} 4097 4098template <class _RandomAccessIterator> 4099inline _LIBCPP_INLINE_VISIBILITY 4100void 4101sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 4102{ 4103 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4104} 4105 4106template <class _Tp> 4107inline _LIBCPP_INLINE_VISIBILITY 4108void 4109sort(_Tp** __first, _Tp** __last) 4110{ 4111 _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>()); 4112} 4113 4114template <class _Tp> 4115inline _LIBCPP_INLINE_VISIBILITY 4116void 4117sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last) 4118{ 4119 _VSTD::sort(__first.base(), __last.base()); 4120} 4121 4122template <class _Tp, class _Compare> 4123inline _LIBCPP_INLINE_VISIBILITY 4124void 4125sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp) 4126{ 4127 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4128 _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp); 4129} 4130 4131#ifdef _LIBCPP_MSVC 4132#pragma warning( push ) 4133#pragma warning( disable: 4231) 4134#endif // _LIBCPP_MSVC 4135_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&)) 4136_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) 4137_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) 4138_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) 4139_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&)) 4140_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) 4141_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&)) 4142_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) 4143_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&)) 4144_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) 4145_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) 4146_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>&)) 4147_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&)) 4148_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&)) 4149_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) 4150 4151_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&)) 4152_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) 4153_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) 4154_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) 4155_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&)) 4156_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) 4157_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&)) 4158_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) 4159_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&)) 4160_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) 4161_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) 4162_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>&)) 4163_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&)) 4164_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&)) 4165_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) 4166 4167_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>&)) 4168#ifdef _LIBCPP_MSVC 4169#pragma warning( pop ) 4170#endif // _LIBCPP_MSVC 4171 4172// lower_bound 4173 4174template <class _Compare, class _ForwardIterator, class _Tp> 4175_ForwardIterator 4176__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4177{ 4178 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 4179 difference_type __len = _VSTD::distance(__first, __last); 4180 while (__len != 0) 4181 { 4182 difference_type __l2 = __len / 2; 4183 _ForwardIterator __m = __first; 4184 _VSTD::advance(__m, __l2); 4185 if (__comp(*__m, __value_)) 4186 { 4187 __first = ++__m; 4188 __len -= __l2 + 1; 4189 } 4190 else 4191 __len = __l2; 4192 } 4193 return __first; 4194} 4195 4196template <class _ForwardIterator, class _Tp, class _Compare> 4197inline _LIBCPP_INLINE_VISIBILITY 4198_ForwardIterator 4199lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4200{ 4201#ifdef _LIBCPP_DEBUG 4202 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4203 __debug_less<_Compare> __c(__comp); 4204 return __lower_bound<_Comp_ref>(__first, __last, __value_, __c); 4205#else // _LIBCPP_DEBUG 4206 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4207 return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp); 4208#endif // _LIBCPP_DEBUG 4209} 4210 4211template <class _ForwardIterator, class _Tp> 4212inline _LIBCPP_INLINE_VISIBILITY 4213_ForwardIterator 4214lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4215{ 4216 return _VSTD::lower_bound(__first, __last, __value_, 4217 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 4218} 4219 4220// upper_bound 4221 4222template <class _Compare, class _ForwardIterator, class _Tp> 4223_ForwardIterator 4224__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4225{ 4226 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 4227 difference_type __len = _VSTD::distance(__first, __last); 4228 while (__len != 0) 4229 { 4230 difference_type __l2 = __len / 2; 4231 _ForwardIterator __m = __first; 4232 _VSTD::advance(__m, __l2); 4233 if (__comp(__value_, *__m)) 4234 __len = __l2; 4235 else 4236 { 4237 __first = ++__m; 4238 __len -= __l2 + 1; 4239 } 4240 } 4241 return __first; 4242} 4243 4244template <class _ForwardIterator, class _Tp, class _Compare> 4245inline _LIBCPP_INLINE_VISIBILITY 4246_ForwardIterator 4247upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4248{ 4249#ifdef _LIBCPP_DEBUG 4250 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4251 __debug_less<_Compare> __c(__comp); 4252 return __upper_bound<_Comp_ref>(__first, __last, __value_, __c); 4253#else // _LIBCPP_DEBUG 4254 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4255 return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp); 4256#endif // _LIBCPP_DEBUG 4257} 4258 4259template <class _ForwardIterator, class _Tp> 4260inline _LIBCPP_INLINE_VISIBILITY 4261_ForwardIterator 4262upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4263{ 4264 return _VSTD::upper_bound(__first, __last, __value_, 4265 __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>()); 4266} 4267 4268// equal_range 4269 4270template <class _Compare, class _ForwardIterator, class _Tp> 4271pair<_ForwardIterator, _ForwardIterator> 4272__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4273{ 4274 typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; 4275 difference_type __len = _VSTD::distance(__first, __last); 4276 while (__len != 0) 4277 { 4278 difference_type __l2 = __len / 2; 4279 _ForwardIterator __m = __first; 4280 _VSTD::advance(__m, __l2); 4281 if (__comp(*__m, __value_)) 4282 { 4283 __first = ++__m; 4284 __len -= __l2 + 1; 4285 } 4286 else if (__comp(__value_, *__m)) 4287 { 4288 __last = __m; 4289 __len = __l2; 4290 } 4291 else 4292 { 4293 _ForwardIterator __mp1 = __m; 4294 return pair<_ForwardIterator, _ForwardIterator> 4295 ( 4296 __lower_bound<_Compare>(__first, __m, __value_, __comp), 4297 __upper_bound<_Compare>(++__mp1, __last, __value_, __comp) 4298 ); 4299 } 4300 } 4301 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 4302} 4303 4304template <class _ForwardIterator, class _Tp, class _Compare> 4305inline _LIBCPP_INLINE_VISIBILITY 4306pair<_ForwardIterator, _ForwardIterator> 4307equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4308{ 4309#ifdef _LIBCPP_DEBUG 4310 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4311 __debug_less<_Compare> __c(__comp); 4312 return __equal_range<_Comp_ref>(__first, __last, __value_, __c); 4313#else // _LIBCPP_DEBUG 4314 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4315 return __equal_range<_Comp_ref>(__first, __last, __value_, __comp); 4316#endif // _LIBCPP_DEBUG 4317} 4318 4319template <class _ForwardIterator, class _Tp> 4320inline _LIBCPP_INLINE_VISIBILITY 4321pair<_ForwardIterator, _ForwardIterator> 4322equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4323{ 4324 return _VSTD::equal_range(__first, __last, __value_, 4325 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 4326} 4327 4328// binary_search 4329 4330template <class _Compare, class _ForwardIterator, class _Tp> 4331inline _LIBCPP_INLINE_VISIBILITY 4332bool 4333__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4334{ 4335 __first = __lower_bound<_Compare>(__first, __last, __value_, __comp); 4336 return __first != __last && !__comp(__value_, *__first); 4337} 4338 4339template <class _ForwardIterator, class _Tp, class _Compare> 4340inline _LIBCPP_INLINE_VISIBILITY 4341bool 4342binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) 4343{ 4344#ifdef _LIBCPP_DEBUG 4345 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4346 __debug_less<_Compare> __c(__comp); 4347 return __binary_search<_Comp_ref>(__first, __last, __value_, __c); 4348#else // _LIBCPP_DEBUG 4349 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4350 return __binary_search<_Comp_ref>(__first, __last, __value_, __comp); 4351#endif // _LIBCPP_DEBUG 4352} 4353 4354template <class _ForwardIterator, class _Tp> 4355inline _LIBCPP_INLINE_VISIBILITY 4356bool 4357binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) 4358{ 4359 return _VSTD::binary_search(__first, __last, __value_, 4360 __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); 4361} 4362 4363// merge 4364 4365template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 4366_OutputIterator 4367__merge(_InputIterator1 __first1, _InputIterator1 __last1, 4368 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 4369{ 4370 for (; __first1 != __last1; ++__result) 4371 { 4372 if (__first2 == __last2) 4373 return _VSTD::copy(__first1, __last1, __result); 4374 if (__comp(*__first2, *__first1)) 4375 { 4376 *__result = *__first2; 4377 ++__first2; 4378 } 4379 else 4380 { 4381 *__result = *__first1; 4382 ++__first1; 4383 } 4384 } 4385 return _VSTD::copy(__first2, __last2, __result); 4386} 4387 4388template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 4389inline _LIBCPP_INLINE_VISIBILITY 4390_OutputIterator 4391merge(_InputIterator1 __first1, _InputIterator1 __last1, 4392 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 4393{ 4394#ifdef _LIBCPP_DEBUG 4395 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4396 __debug_less<_Compare> __c(__comp); 4397 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c); 4398#else // _LIBCPP_DEBUG 4399 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4400 return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 4401#endif // _LIBCPP_DEBUG 4402} 4403 4404template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 4405inline _LIBCPP_INLINE_VISIBILITY 4406_OutputIterator 4407merge(_InputIterator1 __first1, _InputIterator1 __last1, 4408 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 4409{ 4410 typedef typename iterator_traits<_InputIterator1>::value_type __v1; 4411 typedef typename iterator_traits<_InputIterator2>::value_type __v2; 4412 return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>()); 4413} 4414 4415// inplace_merge 4416 4417template <class _Compare, class _InputIterator1, class _InputIterator2, 4418 class _OutputIterator> 4419void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1, 4420 _InputIterator2 __first2, _InputIterator2 __last2, 4421 _OutputIterator __result, _Compare __comp) 4422{ 4423 for (; __first1 != __last1; ++__result) 4424 { 4425 if (__first2 == __last2) 4426 { 4427 _VSTD::move(__first1, __last1, __result); 4428 return; 4429 } 4430 4431 if (__comp(*__first2, *__first1)) 4432 { 4433 *__result = _VSTD::move(*__first2); 4434 ++__first2; 4435 } 4436 else 4437 { 4438 *__result = _VSTD::move(*__first1); 4439 ++__first1; 4440 } 4441 } 4442 // __first2 through __last2 are already in the right spot. 4443} 4444 4445template <class _Compare, class _BidirectionalIterator> 4446void 4447__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4448 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, 4449 typename iterator_traits<_BidirectionalIterator>::difference_type __len2, 4450 typename iterator_traits<_BidirectionalIterator>::value_type* __buff) 4451{ 4452 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 4453 __destruct_n __d(0); 4454 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); 4455 if (__len1 <= __len2) 4456 { 4457 value_type* __p = __buff; 4458 for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p) 4459 ::new(__p) value_type(_VSTD::move(*__i)); 4460 __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp); 4461 } 4462 else 4463 { 4464 value_type* __p = __buff; 4465 for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, ++__p) 4466 ::new(__p) value_type(_VSTD::move(*__i)); 4467 typedef reverse_iterator<_BidirectionalIterator> _RBi; 4468 typedef reverse_iterator<value_type*> _Rv; 4469 __half_inplace_merge(_Rv(__p), _Rv(__buff), 4470 _RBi(__middle), _RBi(__first), 4471 _RBi(__last), __negate<_Compare>(__comp)); 4472 } 4473} 4474 4475template <class _Compare, class _BidirectionalIterator> 4476void 4477__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4478 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, 4479 typename iterator_traits<_BidirectionalIterator>::difference_type __len2, 4480 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size) 4481{ 4482 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 4483 while (true) 4484 { 4485 // if __middle == __last, we're done 4486 if (__len2 == 0) 4487 return; 4488 if (__len1 <= __buff_size || __len2 <= __buff_size) 4489 return __buffered_inplace_merge<_Compare> 4490 (__first, __middle, __last, __comp, __len1, __len2, __buff); 4491 // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0 4492 for (; true; ++__first, (void) --__len1) 4493 { 4494 if (__len1 == 0) 4495 return; 4496 if (__comp(*__middle, *__first)) 4497 break; 4498 } 4499 // __first < __middle < __last 4500 // *__first > *__middle 4501 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that 4502 // all elements in: 4503 // [__first, __m1) <= [__middle, __m2) 4504 // [__middle, __m2) < [__m1, __middle) 4505 // [__m1, __middle) <= [__m2, __last) 4506 // and __m1 or __m2 is in the middle of its range 4507 _BidirectionalIterator __m1; // "median" of [__first, __middle) 4508 _BidirectionalIterator __m2; // "median" of [__middle, __last) 4509 difference_type __len11; // distance(__first, __m1) 4510 difference_type __len21; // distance(__middle, __m2) 4511 // binary search smaller range 4512 if (__len1 < __len2) 4513 { // __len >= 1, __len2 >= 2 4514 __len21 = __len2 / 2; 4515 __m2 = __middle; 4516 _VSTD::advance(__m2, __len21); 4517 __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp); 4518 __len11 = _VSTD::distance(__first, __m1); 4519 } 4520 else 4521 { 4522 if (__len1 == 1) 4523 { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1 4524 // It is known *__first > *__middle 4525 swap(*__first, *__middle); 4526 return; 4527 } 4528 // __len1 >= 2, __len2 >= 1 4529 __len11 = __len1 / 2; 4530 __m1 = __first; 4531 _VSTD::advance(__m1, __len11); 4532 __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp); 4533 __len21 = _VSTD::distance(__middle, __m2); 4534 } 4535 difference_type __len12 = __len1 - __len11; // distance(__m1, __middle) 4536 difference_type __len22 = __len2 - __len21; // distance(__m2, __last) 4537 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) 4538 // swap middle two partitions 4539 __middle = _VSTD::rotate(__m1, __middle, __m2); 4540 // __len12 and __len21 now have swapped meanings 4541 // merge smaller range with recurisve call and larger with tail recursion elimination 4542 if (__len11 + __len21 < __len12 + __len22) 4543 { 4544 __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); 4545// __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); 4546 __first = __middle; 4547 __middle = __m2; 4548 __len1 = __len12; 4549 __len2 = __len22; 4550 } 4551 else 4552 { 4553 __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); 4554// __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); 4555 __last = __middle; 4556 __middle = __m1; 4557 __len1 = __len11; 4558 __len2 = __len21; 4559 } 4560 } 4561} 4562 4563template <class _BidirectionalIterator, class _Compare> 4564inline _LIBCPP_INLINE_VISIBILITY 4565void 4566inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, 4567 _Compare __comp) 4568{ 4569 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 4570 typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; 4571 difference_type __len1 = _VSTD::distance(__first, __middle); 4572 difference_type __len2 = _VSTD::distance(__middle, __last); 4573 difference_type __buf_size = _VSTD::min(__len1, __len2); 4574 pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size); 4575 unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first); 4576 4577#ifdef _LIBCPP_DEBUG 4578 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4579 __debug_less<_Compare> __c(__comp); 4580 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2, 4581 __buf.first, __buf.second); 4582#else // _LIBCPP_DEBUG 4583 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4584 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2, 4585 __buf.first, __buf.second); 4586#endif // _LIBCPP_DEBUG 4587} 4588 4589template <class _BidirectionalIterator> 4590inline _LIBCPP_INLINE_VISIBILITY 4591void 4592inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) 4593{ 4594 _VSTD::inplace_merge(__first, __middle, __last, 4595 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 4596} 4597 4598// stable_sort 4599 4600template <class _Compare, class _InputIterator1, class _InputIterator2> 4601void 4602__merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1, 4603 _InputIterator2 __first2, _InputIterator2 __last2, 4604 typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp) 4605{ 4606 typedef typename iterator_traits<_InputIterator1>::value_type value_type; 4607 __destruct_n __d(0); 4608 unique_ptr<value_type, __destruct_n&> __h(__result, __d); 4609 for (; true; ++__result) 4610 { 4611 if (__first1 == __last1) 4612 { 4613 for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0)) 4614 ::new (__result) value_type(_VSTD::move(*__first2)); 4615 __h.release(); 4616 return; 4617 } 4618 if (__first2 == __last2) 4619 { 4620 for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0)) 4621 ::new (__result) value_type(_VSTD::move(*__first1)); 4622 __h.release(); 4623 return; 4624 } 4625 if (__comp(*__first2, *__first1)) 4626 { 4627 ::new (__result) value_type(_VSTD::move(*__first2)); 4628 __d.__incr((value_type*)0); 4629 ++__first2; 4630 } 4631 else 4632 { 4633 ::new (__result) value_type(_VSTD::move(*__first1)); 4634 __d.__incr((value_type*)0); 4635 ++__first1; 4636 } 4637 } 4638} 4639 4640template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 4641void 4642__merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1, 4643 _InputIterator2 __first2, _InputIterator2 __last2, 4644 _OutputIterator __result, _Compare __comp) 4645{ 4646 for (; __first1 != __last1; ++__result) 4647 { 4648 if (__first2 == __last2) 4649 { 4650 for (; __first1 != __last1; ++__first1, ++__result) 4651 *__result = _VSTD::move(*__first1); 4652 return; 4653 } 4654 if (__comp(*__first2, *__first1)) 4655 { 4656 *__result = _VSTD::move(*__first2); 4657 ++__first2; 4658 } 4659 else 4660 { 4661 *__result = _VSTD::move(*__first1); 4662 ++__first1; 4663 } 4664 } 4665 for (; __first2 != __last2; ++__first2, ++__result) 4666 *__result = _VSTD::move(*__first2); 4667} 4668 4669template <class _Compare, class _RandomAccessIterator> 4670void 4671__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4672 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4673 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size); 4674 4675template <class _Compare, class _RandomAccessIterator> 4676void 4677__stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp, 4678 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4679 typename iterator_traits<_RandomAccessIterator>::value_type* __first2) 4680{ 4681 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4682 switch (__len) 4683 { 4684 case 0: 4685 return; 4686 case 1: 4687 ::new(__first2) value_type(_VSTD::move(*__first1)); 4688 return; 4689 case 2: 4690 __destruct_n __d(0); 4691 unique_ptr<value_type, __destruct_n&> __h2(__first2, __d); 4692 if (__comp(*--__last1, *__first1)) 4693 { 4694 ::new(__first2) value_type(_VSTD::move(*__last1)); 4695 __d.__incr((value_type*)0); 4696 ++__first2; 4697 ::new(__first2) value_type(_VSTD::move(*__first1)); 4698 } 4699 else 4700 { 4701 ::new(__first2) value_type(_VSTD::move(*__first1)); 4702 __d.__incr((value_type*)0); 4703 ++__first2; 4704 ::new(__first2) value_type(_VSTD::move(*__last1)); 4705 } 4706 __h2.release(); 4707 return; 4708 } 4709 if (__len <= 8) 4710 { 4711 __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp); 4712 return; 4713 } 4714 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; 4715 _RandomAccessIterator __m = __first1 + __l2; 4716 __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2); 4717 __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2); 4718 __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp); 4719} 4720 4721template <class _Tp> 4722struct __stable_sort_switch 4723{ 4724 static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value; 4725}; 4726 4727template <class _Compare, class _RandomAccessIterator> 4728void 4729__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4730 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4731 typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size) 4732{ 4733 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4734 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4735 switch (__len) 4736 { 4737 case 0: 4738 case 1: 4739 return; 4740 case 2: 4741 if (__comp(*--__last, *__first)) 4742 swap(*__first, *__last); 4743 return; 4744 } 4745 if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value)) 4746 { 4747 __insertion_sort<_Compare>(__first, __last, __comp); 4748 return; 4749 } 4750 typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; 4751 _RandomAccessIterator __m = __first + __l2; 4752 if (__len <= __buff_size) 4753 { 4754 __destruct_n __d(0); 4755 unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); 4756 __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff); 4757 __d.__set(__l2, (value_type*)0); 4758 __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2); 4759 __d.__set(__len, (value_type*)0); 4760 __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp); 4761// __merge<_Compare>(move_iterator<value_type*>(__buff), 4762// move_iterator<value_type*>(__buff + __l2), 4763// move_iterator<_RandomAccessIterator>(__buff + __l2), 4764// move_iterator<_RandomAccessIterator>(__buff + __len), 4765// __first, __comp); 4766 return; 4767 } 4768 __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size); 4769 __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); 4770 __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); 4771} 4772 4773template <class _RandomAccessIterator, class _Compare> 4774inline _LIBCPP_INLINE_VISIBILITY 4775void 4776stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4777{ 4778 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4779 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4780 difference_type __len = __last - __first; 4781 pair<value_type*, ptrdiff_t> __buf(0, 0); 4782 unique_ptr<value_type, __return_temporary_buffer> __h; 4783 if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) 4784 { 4785 __buf = _VSTD::get_temporary_buffer<value_type>(__len); 4786 __h.reset(__buf.first); 4787 } 4788#ifdef _LIBCPP_DEBUG 4789 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4790 __debug_less<_Compare> __c(__comp); 4791 __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second); 4792#else // _LIBCPP_DEBUG 4793 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4794 __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); 4795#endif // _LIBCPP_DEBUG 4796} 4797 4798template <class _RandomAccessIterator> 4799inline _LIBCPP_INLINE_VISIBILITY 4800void 4801stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 4802{ 4803 _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4804} 4805 4806// is_heap_until 4807 4808template <class _RandomAccessIterator, class _Compare> 4809_RandomAccessIterator 4810is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4811{ 4812 typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4813 difference_type __len = __last - __first; 4814 difference_type __p = 0; 4815 difference_type __c = 1; 4816 _RandomAccessIterator __pp = __first; 4817 while (__c < __len) 4818 { 4819 _RandomAccessIterator __cp = __first + __c; 4820 if (__comp(*__pp, *__cp)) 4821 return __cp; 4822 ++__c; 4823 ++__cp; 4824 if (__c == __len) 4825 return __last; 4826 if (__comp(*__pp, *__cp)) 4827 return __cp; 4828 ++__p; 4829 ++__pp; 4830 __c = 2 * __p + 1; 4831 } 4832 return __last; 4833} 4834 4835template<class _RandomAccessIterator> 4836inline _LIBCPP_INLINE_VISIBILITY 4837_RandomAccessIterator 4838is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) 4839{ 4840 return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4841} 4842 4843// is_heap 4844 4845template <class _RandomAccessIterator, class _Compare> 4846inline _LIBCPP_INLINE_VISIBILITY 4847bool 4848is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4849{ 4850 return _VSTD::is_heap_until(__first, __last, __comp) == __last; 4851} 4852 4853template<class _RandomAccessIterator> 4854inline _LIBCPP_INLINE_VISIBILITY 4855bool 4856is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 4857{ 4858 return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4859} 4860 4861// push_heap 4862 4863template <class _Compare, class _RandomAccessIterator> 4864void 4865__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4866 typename iterator_traits<_RandomAccessIterator>::difference_type __len) 4867{ 4868 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4869 if (__len > 1) 4870 { 4871 __len = (__len - 2) / 2; 4872 _RandomAccessIterator __ptr = __first + __len; 4873 if (__comp(*__ptr, *--__last)) 4874 { 4875 value_type __t(_VSTD::move(*__last)); 4876 do 4877 { 4878 *__last = _VSTD::move(*__ptr); 4879 __last = __ptr; 4880 if (__len == 0) 4881 break; 4882 __len = (__len - 1) / 2; 4883 __ptr = __first + __len; 4884 } while (__comp(*__ptr, __t)); 4885 *__last = _VSTD::move(__t); 4886 } 4887 } 4888} 4889 4890template <class _RandomAccessIterator, class _Compare> 4891inline _LIBCPP_INLINE_VISIBILITY 4892void 4893push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4894{ 4895#ifdef _LIBCPP_DEBUG 4896 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4897 __debug_less<_Compare> __c(__comp); 4898 __sift_up<_Comp_ref>(__first, __last, __c, __last - __first); 4899#else // _LIBCPP_DEBUG 4900 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4901 __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first); 4902#endif // _LIBCPP_DEBUG 4903} 4904 4905template <class _RandomAccessIterator> 4906inline _LIBCPP_INLINE_VISIBILITY 4907void 4908push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 4909{ 4910 _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 4911} 4912 4913// pop_heap 4914 4915template <class _Compare, class _RandomAccessIterator> 4916void 4917__sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/, 4918 _Compare __comp, 4919 typename iterator_traits<_RandomAccessIterator>::difference_type __len, 4920 _RandomAccessIterator __start) 4921{ 4922 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 4923 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 4924 // left-child of __start is at 2 * __start + 1 4925 // right-child of __start is at 2 * __start + 2 4926 difference_type __child = __start - __first; 4927 4928 if (__len < 2 || (__len - 2) / 2 < __child) 4929 return; 4930 4931 __child = 2 * __child + 1; 4932 _RandomAccessIterator __child_i = __first + __child; 4933 4934 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { 4935 // right-child exists and is greater than left-child 4936 ++__child_i; 4937 ++__child; 4938 } 4939 4940 // check if we are in heap-order 4941 if (__comp(*__child_i, *__start)) 4942 // we are, __start is larger than it's largest child 4943 return; 4944 4945 value_type __top(_VSTD::move(*__start)); 4946 do 4947 { 4948 // we are not in heap-order, swap the parent with it's largest child 4949 *__start = _VSTD::move(*__child_i); 4950 __start = __child_i; 4951 4952 if ((__len - 2) / 2 < __child) 4953 break; 4954 4955 // recompute the child based off of the updated parent 4956 __child = 2 * __child + 1; 4957 __child_i = __first + __child; 4958 4959 if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { 4960 // right-child exists and is greater than left-child 4961 ++__child_i; 4962 ++__child; 4963 } 4964 4965 // check if we are in heap-order 4966 } while (!__comp(*__child_i, __top)); 4967 *__start = _VSTD::move(__top); 4968} 4969 4970template <class _Compare, class _RandomAccessIterator> 4971inline _LIBCPP_INLINE_VISIBILITY 4972void 4973__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 4974 typename iterator_traits<_RandomAccessIterator>::difference_type __len) 4975{ 4976 if (__len > 1) 4977 { 4978 swap(*__first, *--__last); 4979 __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first); 4980 } 4981} 4982 4983template <class _RandomAccessIterator, class _Compare> 4984inline _LIBCPP_INLINE_VISIBILITY 4985void 4986pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 4987{ 4988#ifdef _LIBCPP_DEBUG 4989 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 4990 __debug_less<_Compare> __c(__comp); 4991 __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first); 4992#else // _LIBCPP_DEBUG 4993 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 4994 __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first); 4995#endif // _LIBCPP_DEBUG 4996} 4997 4998template <class _RandomAccessIterator> 4999inline _LIBCPP_INLINE_VISIBILITY 5000void 5001pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 5002{ 5003 _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5004} 5005 5006// make_heap 5007 5008template <class _Compare, class _RandomAccessIterator> 5009void 5010__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5011{ 5012 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 5013 difference_type __n = __last - __first; 5014 if (__n > 1) 5015 { 5016 // start from the first parent, there is no need to consider children 5017 for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) 5018 { 5019 __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start); 5020 } 5021 } 5022} 5023 5024template <class _RandomAccessIterator, class _Compare> 5025inline _LIBCPP_INLINE_VISIBILITY 5026void 5027make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5028{ 5029#ifdef _LIBCPP_DEBUG 5030 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5031 __debug_less<_Compare> __c(__comp); 5032 __make_heap<_Comp_ref>(__first, __last, __c); 5033#else // _LIBCPP_DEBUG 5034 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5035 __make_heap<_Comp_ref>(__first, __last, __comp); 5036#endif // _LIBCPP_DEBUG 5037} 5038 5039template <class _RandomAccessIterator> 5040inline _LIBCPP_INLINE_VISIBILITY 5041void 5042make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 5043{ 5044 _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5045} 5046 5047// sort_heap 5048 5049template <class _Compare, class _RandomAccessIterator> 5050void 5051__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5052{ 5053 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 5054 for (difference_type __n = __last - __first; __n > 1; --__last, --__n) 5055 __pop_heap<_Compare>(__first, __last, __comp, __n); 5056} 5057 5058template <class _RandomAccessIterator, class _Compare> 5059inline _LIBCPP_INLINE_VISIBILITY 5060void 5061sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 5062{ 5063#ifdef _LIBCPP_DEBUG 5064 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5065 __debug_less<_Compare> __c(__comp); 5066 __sort_heap<_Comp_ref>(__first, __last, __c); 5067#else // _LIBCPP_DEBUG 5068 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5069 __sort_heap<_Comp_ref>(__first, __last, __comp); 5070#endif // _LIBCPP_DEBUG 5071} 5072 5073template <class _RandomAccessIterator> 5074inline _LIBCPP_INLINE_VISIBILITY 5075void 5076sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 5077{ 5078 _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5079} 5080 5081// partial_sort 5082 5083template <class _Compare, class _RandomAccessIterator> 5084void 5085__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, 5086 _Compare __comp) 5087{ 5088 __make_heap<_Compare>(__first, __middle, __comp); 5089 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first; 5090 for (_RandomAccessIterator __i = __middle; __i != __last; ++__i) 5091 { 5092 if (__comp(*__i, *__first)) 5093 { 5094 swap(*__i, *__first); 5095 __sift_down<_Compare>(__first, __middle, __comp, __len, __first); 5096 } 5097 } 5098 __sort_heap<_Compare>(__first, __middle, __comp); 5099} 5100 5101template <class _RandomAccessIterator, class _Compare> 5102inline _LIBCPP_INLINE_VISIBILITY 5103void 5104partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, 5105 _Compare __comp) 5106{ 5107#ifdef _LIBCPP_DEBUG 5108 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5109 __debug_less<_Compare> __c(__comp); 5110 __partial_sort<_Comp_ref>(__first, __middle, __last, __c); 5111#else // _LIBCPP_DEBUG 5112 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5113 __partial_sort<_Comp_ref>(__first, __middle, __last, __comp); 5114#endif // _LIBCPP_DEBUG 5115} 5116 5117template <class _RandomAccessIterator> 5118inline _LIBCPP_INLINE_VISIBILITY 5119void 5120partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) 5121{ 5122 _VSTD::partial_sort(__first, __middle, __last, 5123 __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5124} 5125 5126// partial_sort_copy 5127 5128template <class _Compare, class _InputIterator, class _RandomAccessIterator> 5129_RandomAccessIterator 5130__partial_sort_copy(_InputIterator __first, _InputIterator __last, 5131 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) 5132{ 5133 _RandomAccessIterator __r = __result_first; 5134 if (__r != __result_last) 5135 { 5136 for (; __first != __last && __r != __result_last; (void) ++__first, ++__r) 5137 *__r = *__first; 5138 __make_heap<_Compare>(__result_first, __r, __comp); 5139 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first; 5140 for (; __first != __last; ++__first) 5141 if (__comp(*__first, *__result_first)) 5142 { 5143 *__result_first = *__first; 5144 __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first); 5145 } 5146 __sort_heap<_Compare>(__result_first, __r, __comp); 5147 } 5148 return __r; 5149} 5150 5151template <class _InputIterator, class _RandomAccessIterator, class _Compare> 5152inline _LIBCPP_INLINE_VISIBILITY 5153_RandomAccessIterator 5154partial_sort_copy(_InputIterator __first, _InputIterator __last, 5155 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) 5156{ 5157#ifdef _LIBCPP_DEBUG 5158 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5159 __debug_less<_Compare> __c(__comp); 5160 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c); 5161#else // _LIBCPP_DEBUG 5162 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5163 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp); 5164#endif // _LIBCPP_DEBUG 5165} 5166 5167template <class _InputIterator, class _RandomAccessIterator> 5168inline _LIBCPP_INLINE_VISIBILITY 5169_RandomAccessIterator 5170partial_sort_copy(_InputIterator __first, _InputIterator __last, 5171 _RandomAccessIterator __result_first, _RandomAccessIterator __result_last) 5172{ 5173 return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last, 5174 __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5175} 5176 5177// nth_element 5178 5179template <class _Compare, class _RandomAccessIterator> 5180void 5181__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) 5182{ 5183 // _Compare is known to be a reference type 5184 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 5185 const difference_type __limit = 7; 5186 while (true) 5187 { 5188 __restart: 5189 if (__nth == __last) 5190 return; 5191 difference_type __len = __last - __first; 5192 switch (__len) 5193 { 5194 case 0: 5195 case 1: 5196 return; 5197 case 2: 5198 if (__comp(*--__last, *__first)) 5199 swap(*__first, *__last); 5200 return; 5201 case 3: 5202 { 5203 _RandomAccessIterator __m = __first; 5204 _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp); 5205 return; 5206 } 5207 } 5208 if (__len <= __limit) 5209 { 5210 __selection_sort<_Compare>(__first, __last, __comp); 5211 return; 5212 } 5213 // __len > __limit >= 3 5214 _RandomAccessIterator __m = __first + __len/2; 5215 _RandomAccessIterator __lm1 = __last; 5216 unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp); 5217 // *__m is median 5218 // partition [__first, __m) < *__m and *__m <= [__m, __last) 5219 // (this inhibits tossing elements equivalent to __m around unnecessarily) 5220 _RandomAccessIterator __i = __first; 5221 _RandomAccessIterator __j = __lm1; 5222 // j points beyond range to be tested, *__lm1 is known to be <= *__m 5223 // The search going up is known to be guarded but the search coming down isn't. 5224 // Prime the downward search with a guard. 5225 if (!__comp(*__i, *__m)) // if *__first == *__m 5226 { 5227 // *__first == *__m, *__first doesn't go in first part 5228 // manually guard downward moving __j against __i 5229 while (true) 5230 { 5231 if (__i == --__j) 5232 { 5233 // *__first == *__m, *__m <= all other elements 5234 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) 5235 ++__i; // __first + 1 5236 __j = __last; 5237 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) 5238 { 5239 while (true) 5240 { 5241 if (__i == __j) 5242 return; // [__first, __last) all equivalent elements 5243 if (__comp(*__first, *__i)) 5244 { 5245 swap(*__i, *__j); 5246 ++__n_swaps; 5247 ++__i; 5248 break; 5249 } 5250 ++__i; 5251 } 5252 } 5253 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 5254 if (__i == __j) 5255 return; 5256 while (true) 5257 { 5258 while (!__comp(*__first, *__i)) 5259 ++__i; 5260 while (__comp(*__first, *--__j)) 5261 ; 5262 if (__i >= __j) 5263 break; 5264 swap(*__i, *__j); 5265 ++__n_swaps; 5266 ++__i; 5267 } 5268 // [__first, __i) == *__first and *__first < [__i, __last) 5269 // The first part is sorted, 5270 if (__nth < __i) 5271 return; 5272 // __nth_element the secod part 5273 // __nth_element<_Compare>(__i, __nth, __last, __comp); 5274 __first = __i; 5275 goto __restart; 5276 } 5277 if (__comp(*__j, *__m)) 5278 { 5279 swap(*__i, *__j); 5280 ++__n_swaps; 5281 break; // found guard for downward moving __j, now use unguarded partition 5282 } 5283 } 5284 } 5285 ++__i; 5286 // j points beyond range to be tested, *__lm1 is known to be <= *__m 5287 // if not yet partitioned... 5288 if (__i < __j) 5289 { 5290 // known that *(__i - 1) < *__m 5291 while (true) 5292 { 5293 // __m still guards upward moving __i 5294 while (__comp(*__i, *__m)) 5295 ++__i; 5296 // It is now known that a guard exists for downward moving __j 5297 while (!__comp(*--__j, *__m)) 5298 ; 5299 if (__i >= __j) 5300 break; 5301 swap(*__i, *__j); 5302 ++__n_swaps; 5303 // It is known that __m != __j 5304 // If __m just moved, follow it 5305 if (__m == __i) 5306 __m = __j; 5307 ++__i; 5308 } 5309 } 5310 // [__first, __i) < *__m and *__m <= [__i, __last) 5311 if (__i != __m && __comp(*__m, *__i)) 5312 { 5313 swap(*__i, *__m); 5314 ++__n_swaps; 5315 } 5316 // [__first, __i) < *__i and *__i <= [__i+1, __last) 5317 if (__nth == __i) 5318 return; 5319 if (__n_swaps == 0) 5320 { 5321 // We were given a perfectly partitioned sequence. Coincidence? 5322 if (__nth < __i) 5323 { 5324 // Check for [__first, __i) already sorted 5325 __j = __m = __first; 5326 while (++__j != __i) 5327 { 5328 if (__comp(*__j, *__m)) 5329 // not yet sorted, so sort 5330 goto not_sorted; 5331 __m = __j; 5332 } 5333 // [__first, __i) sorted 5334 return; 5335 } 5336 else 5337 { 5338 // Check for [__i, __last) already sorted 5339 __j = __m = __i; 5340 while (++__j != __last) 5341 { 5342 if (__comp(*__j, *__m)) 5343 // not yet sorted, so sort 5344 goto not_sorted; 5345 __m = __j; 5346 } 5347 // [__i, __last) sorted 5348 return; 5349 } 5350 } 5351not_sorted: 5352 // __nth_element on range containing __nth 5353 if (__nth < __i) 5354 { 5355 // __nth_element<_Compare>(__first, __nth, __i, __comp); 5356 __last = __i; 5357 } 5358 else 5359 { 5360 // __nth_element<_Compare>(__i+1, __nth, __last, __comp); 5361 __first = ++__i; 5362 } 5363 } 5364} 5365 5366template <class _RandomAccessIterator, class _Compare> 5367inline _LIBCPP_INLINE_VISIBILITY 5368void 5369nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) 5370{ 5371#ifdef _LIBCPP_DEBUG 5372 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5373 __debug_less<_Compare> __c(__comp); 5374 __nth_element<_Comp_ref>(__first, __nth, __last, __c); 5375#else // _LIBCPP_DEBUG 5376 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5377 __nth_element<_Comp_ref>(__first, __nth, __last, __comp); 5378#endif // _LIBCPP_DEBUG 5379} 5380 5381template <class _RandomAccessIterator> 5382inline _LIBCPP_INLINE_VISIBILITY 5383void 5384nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) 5385{ 5386 _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 5387} 5388 5389// includes 5390 5391template <class _Compare, class _InputIterator1, class _InputIterator2> 5392bool 5393__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, 5394 _Compare __comp) 5395{ 5396 for (; __first2 != __last2; ++__first1) 5397 { 5398 if (__first1 == __last1 || __comp(*__first2, *__first1)) 5399 return false; 5400 if (!__comp(*__first1, *__first2)) 5401 ++__first2; 5402 } 5403 return true; 5404} 5405 5406template <class _InputIterator1, class _InputIterator2, class _Compare> 5407inline _LIBCPP_INLINE_VISIBILITY 5408bool 5409includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, 5410 _Compare __comp) 5411{ 5412#ifdef _LIBCPP_DEBUG 5413 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5414 __debug_less<_Compare> __c(__comp); 5415 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c); 5416#else // _LIBCPP_DEBUG 5417 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5418 return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); 5419#endif // _LIBCPP_DEBUG 5420} 5421 5422template <class _InputIterator1, class _InputIterator2> 5423inline _LIBCPP_INLINE_VISIBILITY 5424bool 5425includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) 5426{ 5427 return _VSTD::includes(__first1, __last1, __first2, __last2, 5428 __less<typename iterator_traits<_InputIterator1>::value_type, 5429 typename iterator_traits<_InputIterator2>::value_type>()); 5430} 5431 5432// set_union 5433 5434template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5435_OutputIterator 5436__set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5437 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5438{ 5439 for (; __first1 != __last1; ++__result) 5440 { 5441 if (__first2 == __last2) 5442 return _VSTD::copy(__first1, __last1, __result); 5443 if (__comp(*__first2, *__first1)) 5444 { 5445 *__result = *__first2; 5446 ++__first2; 5447 } 5448 else 5449 { 5450 *__result = *__first1; 5451 if (!__comp(*__first1, *__first2)) 5452 ++__first2; 5453 ++__first1; 5454 } 5455 } 5456 return _VSTD::copy(__first2, __last2, __result); 5457} 5458 5459template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5460inline _LIBCPP_INLINE_VISIBILITY 5461_OutputIterator 5462set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5463 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5464{ 5465#ifdef _LIBCPP_DEBUG 5466 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5467 __debug_less<_Compare> __c(__comp); 5468 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c); 5469#else // _LIBCPP_DEBUG 5470 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5471 return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5472#endif // _LIBCPP_DEBUG 5473} 5474 5475template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5476inline _LIBCPP_INLINE_VISIBILITY 5477_OutputIterator 5478set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5479 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5480{ 5481 return _VSTD::set_union(__first1, __last1, __first2, __last2, __result, 5482 __less<typename iterator_traits<_InputIterator1>::value_type, 5483 typename iterator_traits<_InputIterator2>::value_type>()); 5484} 5485 5486// set_intersection 5487 5488template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5489_OutputIterator 5490__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5491 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5492{ 5493 while (__first1 != __last1 && __first2 != __last2) 5494 { 5495 if (__comp(*__first1, *__first2)) 5496 ++__first1; 5497 else 5498 { 5499 if (!__comp(*__first2, *__first1)) 5500 { 5501 *__result = *__first1; 5502 ++__result; 5503 ++__first1; 5504 } 5505 ++__first2; 5506 } 5507 } 5508 return __result; 5509} 5510 5511template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5512inline _LIBCPP_INLINE_VISIBILITY 5513_OutputIterator 5514set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5515 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5516{ 5517#ifdef _LIBCPP_DEBUG 5518 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5519 __debug_less<_Compare> __c(__comp); 5520 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c); 5521#else // _LIBCPP_DEBUG 5522 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5523 return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5524#endif // _LIBCPP_DEBUG 5525} 5526 5527template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5528inline _LIBCPP_INLINE_VISIBILITY 5529_OutputIterator 5530set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5531 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5532{ 5533 return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result, 5534 __less<typename iterator_traits<_InputIterator1>::value_type, 5535 typename iterator_traits<_InputIterator2>::value_type>()); 5536} 5537 5538// set_difference 5539 5540template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5541_OutputIterator 5542__set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5543 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5544{ 5545 while (__first1 != __last1) 5546 { 5547 if (__first2 == __last2) 5548 return _VSTD::copy(__first1, __last1, __result); 5549 if (__comp(*__first1, *__first2)) 5550 { 5551 *__result = *__first1; 5552 ++__result; 5553 ++__first1; 5554 } 5555 else 5556 { 5557 if (!__comp(*__first2, *__first1)) 5558 ++__first1; 5559 ++__first2; 5560 } 5561 } 5562 return __result; 5563} 5564 5565template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5566inline _LIBCPP_INLINE_VISIBILITY 5567_OutputIterator 5568set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5569 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5570{ 5571#ifdef _LIBCPP_DEBUG 5572 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5573 __debug_less<_Compare> __c(__comp); 5574 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c); 5575#else // _LIBCPP_DEBUG 5576 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5577 return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5578#endif // _LIBCPP_DEBUG 5579} 5580 5581template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5582inline _LIBCPP_INLINE_VISIBILITY 5583_OutputIterator 5584set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5585 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5586{ 5587 return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result, 5588 __less<typename iterator_traits<_InputIterator1>::value_type, 5589 typename iterator_traits<_InputIterator2>::value_type>()); 5590} 5591 5592// set_symmetric_difference 5593 5594template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> 5595_OutputIterator 5596__set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5597 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5598{ 5599 while (__first1 != __last1) 5600 { 5601 if (__first2 == __last2) 5602 return _VSTD::copy(__first1, __last1, __result); 5603 if (__comp(*__first1, *__first2)) 5604 { 5605 *__result = *__first1; 5606 ++__result; 5607 ++__first1; 5608 } 5609 else 5610 { 5611 if (__comp(*__first2, *__first1)) 5612 { 5613 *__result = *__first2; 5614 ++__result; 5615 } 5616 else 5617 ++__first1; 5618 ++__first2; 5619 } 5620 } 5621 return _VSTD::copy(__first2, __last2, __result); 5622} 5623 5624template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> 5625inline _LIBCPP_INLINE_VISIBILITY 5626_OutputIterator 5627set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5628 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) 5629{ 5630#ifdef _LIBCPP_DEBUG 5631 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5632 __debug_less<_Compare> __c(__comp); 5633 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c); 5634#else // _LIBCPP_DEBUG 5635 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5636 return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); 5637#endif // _LIBCPP_DEBUG 5638} 5639 5640template <class _InputIterator1, class _InputIterator2, class _OutputIterator> 5641inline _LIBCPP_INLINE_VISIBILITY 5642_OutputIterator 5643set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5644 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) 5645{ 5646 return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, 5647 __less<typename iterator_traits<_InputIterator1>::value_type, 5648 typename iterator_traits<_InputIterator2>::value_type>()); 5649} 5650 5651// lexicographical_compare 5652 5653template <class _Compare, class _InputIterator1, class _InputIterator2> 5654bool 5655__lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5656 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) 5657{ 5658 for (; __first2 != __last2; ++__first1, (void) ++__first2) 5659 { 5660 if (__first1 == __last1 || __comp(*__first1, *__first2)) 5661 return true; 5662 if (__comp(*__first2, *__first1)) 5663 return false; 5664 } 5665 return false; 5666} 5667 5668template <class _InputIterator1, class _InputIterator2, class _Compare> 5669inline _LIBCPP_INLINE_VISIBILITY 5670bool 5671lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5672 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) 5673{ 5674#ifdef _LIBCPP_DEBUG 5675 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5676 __debug_less<_Compare> __c(__comp); 5677 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c); 5678#else // _LIBCPP_DEBUG 5679 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5680 return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); 5681#endif // _LIBCPP_DEBUG 5682} 5683 5684template <class _InputIterator1, class _InputIterator2> 5685inline _LIBCPP_INLINE_VISIBILITY 5686bool 5687lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 5688 _InputIterator2 __first2, _InputIterator2 __last2) 5689{ 5690 return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2, 5691 __less<typename iterator_traits<_InputIterator1>::value_type, 5692 typename iterator_traits<_InputIterator2>::value_type>()); 5693} 5694 5695// next_permutation 5696 5697template <class _Compare, class _BidirectionalIterator> 5698bool 5699__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5700{ 5701 _BidirectionalIterator __i = __last; 5702 if (__first == __last || __first == --__i) 5703 return false; 5704 while (true) 5705 { 5706 _BidirectionalIterator __ip1 = __i; 5707 if (__comp(*--__i, *__ip1)) 5708 { 5709 _BidirectionalIterator __j = __last; 5710 while (!__comp(*__i, *--__j)) 5711 ; 5712 swap(*__i, *__j); 5713 _VSTD::reverse(__ip1, __last); 5714 return true; 5715 } 5716 if (__i == __first) 5717 { 5718 _VSTD::reverse(__first, __last); 5719 return false; 5720 } 5721 } 5722} 5723 5724template <class _BidirectionalIterator, class _Compare> 5725inline _LIBCPP_INLINE_VISIBILITY 5726bool 5727next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5728{ 5729#ifdef _LIBCPP_DEBUG 5730 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5731 __debug_less<_Compare> __c(__comp); 5732 return __next_permutation<_Comp_ref>(__first, __last, __c); 5733#else // _LIBCPP_DEBUG 5734 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5735 return __next_permutation<_Comp_ref>(__first, __last, __comp); 5736#endif // _LIBCPP_DEBUG 5737} 5738 5739template <class _BidirectionalIterator> 5740inline _LIBCPP_INLINE_VISIBILITY 5741bool 5742next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) 5743{ 5744 return _VSTD::next_permutation(__first, __last, 5745 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 5746} 5747 5748// prev_permutation 5749 5750template <class _Compare, class _BidirectionalIterator> 5751bool 5752__prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5753{ 5754 _BidirectionalIterator __i = __last; 5755 if (__first == __last || __first == --__i) 5756 return false; 5757 while (true) 5758 { 5759 _BidirectionalIterator __ip1 = __i; 5760 if (__comp(*__ip1, *--__i)) 5761 { 5762 _BidirectionalIterator __j = __last; 5763 while (!__comp(*--__j, *__i)) 5764 ; 5765 swap(*__i, *__j); 5766 _VSTD::reverse(__ip1, __last); 5767 return true; 5768 } 5769 if (__i == __first) 5770 { 5771 _VSTD::reverse(__first, __last); 5772 return false; 5773 } 5774 } 5775} 5776 5777template <class _BidirectionalIterator, class _Compare> 5778inline _LIBCPP_INLINE_VISIBILITY 5779bool 5780prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 5781{ 5782#ifdef _LIBCPP_DEBUG 5783 typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; 5784 __debug_less<_Compare> __c(__comp); 5785 return __prev_permutation<_Comp_ref>(__first, __last, __c); 5786#else // _LIBCPP_DEBUG 5787 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; 5788 return __prev_permutation<_Comp_ref>(__first, __last, __comp); 5789#endif // _LIBCPP_DEBUG 5790} 5791 5792template <class _BidirectionalIterator> 5793inline _LIBCPP_INLINE_VISIBILITY 5794bool 5795prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) 5796{ 5797 return _VSTD::prev_permutation(__first, __last, 5798 __less<typename iterator_traits<_BidirectionalIterator>::value_type>()); 5799} 5800 5801_LIBCPP_END_NAMESPACE_STD 5802 5803#endif // _LIBCPP_ALGORITHM 5804