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