contrib/libc++/include/algorithm

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