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