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