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