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