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