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