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