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