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