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