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