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