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