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 __negate
 738 {
 739 private:
 740     _Predicate __p_;
 741 public:
 742     _LIBCPP_INLINE_VISIBILITY __negate() {}
 743
 744     _LIBCPP_INLINE_VISIBILITY
 745     explicit __negate(_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_(__x, __y);}
 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, mask))
 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, mask))
 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>(mask)))
 832     return where;
 833   // Scan the High Word.
 834   if (_BitScanForward(&where, static_cast<unsigned long>(mask >> 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, mask))
 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, mask))
 878     return static_cast<int>(63 - where);
 879 #else
 880   // Scan the high 32 bits.
 881   if (_BitScanReverse(&where, static_cast<unsigned long>(mask >> 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>(mask)))
 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     result_type _Sp = 0;
3017     for (size_t __k = 0; __k < __n0_; ++__k)
3018     {
3019         _Engine_result_type __u;
3020         do
3021         {
3022             __u = __e_() - _Engine::min();
3023         } while (__u >= __y0_);
3024         if (__w0_ < _WDt)
3025             _Sp <<= __w0_;
3026         else
3027             _Sp = 0;
3028         _Sp += __u & __mask0_;
3029     }
3030     for (size_t __k = __n0_; __k < __n_; ++__k)
3031     {
3032         _Engine_result_type __u;
3033         do
3034         {
3035             __u = __e_() - _Engine::min();
3036         } while (__u >= __y1_);
3037         if (__w0_ < _WDt - 1)
3038             _Sp <<= __w0_ + 1;
3039         else
3040             _Sp = 0;
3041         _Sp += __u & __mask1_;
3042     }
3043     return _Sp;
3044 }
3045
3046 // uniform_int_distribution
3047
3048 template<class _IntType = int>
3049 class uniform_int_distribution
3050 {
3051 public:
3052     // types
3053     typedef _IntType result_type;
3054
3055     class param_type
3056     {
3057         result_type __a_;
3058         result_type __b_;
3059     public:
3060         typedef uniform_int_distribution distribution_type;
3061
3062         explicit param_type(result_type __a = 0,
3063                             result_type __b = numeric_limits<result_type>::max())
3064             : __a_(__a), __b_(__b) {}
3065
3066         result_type a() const {return __a_;}
3067         result_type b() const {return __b_;}
3068
3069         friend bool operator==(const param_type& __x, const param_type& __y)
3070             {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
3071         friend bool operator!=(const param_type& __x, const param_type& __y)
3072             {return !(__x == __y);}
3073     };
3074
3075 private:
3076     param_type __p_;
3077
3078 public:
3079     // constructors and reset functions
3080     explicit uniform_int_distribution(result_type __a = 0,
3081                                       result_type __b = numeric_limits<result_type>::max())
3082         : __p_(param_type(__a, __b)) {}
3083     explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
3084     void reset() {}
3085
3086     // generating functions
3087     template<class _URNG> result_type operator()(_URNG& __g)
3088         {return (*this)(__g, __p_);}
3089     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3090
3091     // property functions
3092     result_type a() const {return __p_.a();}
3093     result_type b() const {return __p_.b();}
3094
3095     param_type param() const {return __p_;}
3096     void param(const param_type& __p) {__p_ = __p;}
3097
3098     result_type min() const {return a();}
3099     result_type max() const {return b();}
3100
3101     friend bool operator==(const uniform_int_distribution& __x,
3102                            const uniform_int_distribution& __y)
3103         {return __x.__p_ == __y.__p_;}
3104     friend bool operator!=(const uniform_int_distribution& __x,
3105                            const uniform_int_distribution& __y)
3106             {return !(__x == __y);}
3107 };
3108
3109 template<class _IntType>
3110 template<class _URNG>
3111 typename uniform_int_distribution<_IntType>::result_type
3112 uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
3113 {
3114     typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
3115                                             uint32_t, uint64_t>::type _UIntType;
3116     const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1);
3117     if (_Rp == 1)
3118         return __p.a();
3119     const size_t _Dt = numeric_limits<_UIntType>::digits;
3120     typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
3121     if (_Rp == 0)
3122         return static_cast<result_type>(_Eng(__g, _Dt)());
3123     size_t __w = _Dt - __clz(_Rp) - 1;
3124     if ((_Rp & (std::numeric_limits<_UIntType>::max() >> (_Dt - __w))) != 0)
3125         ++__w;
3126     _Eng __e(__g, __w);
3127     _UIntType __u;
3128     do
3129     {
3130         __u = __e();
3131     } while (__u >= _Rp);
3132     return static_cast<result_type>(__u + __p.a());
3133 }
3134
3135 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \
3136   || defined(_LIBCPP_BUILDING_LIBRARY)
3137 class _LIBCPP_TYPE_VIS __rs_default;
3138
3139 _LIBCPP_FUNC_VIS __rs_default __rs_get();
3140
3141 class _LIBCPP_TYPE_VIS __rs_default
3142 {
3143     static unsigned __c_;
3144
3145     __rs_default();
3146 public:
3147     typedef uint_fast32_t result_type;
3148
3149     static const result_type _Min = 0;
3150     static const result_type _Max = 0xFFFFFFFF;
3151
3152     __rs_default(const __rs_default&);
3153     ~__rs_default();
3154
3155     result_type operator()();
3156
3157     static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
3158     static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
3159
3160     friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
3161 };
3162
3163 _LIBCPP_FUNC_VIS __rs_default __rs_get();
3164
3165 template <class _RandomAccessIterator>
3166 void
3167 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
3168 {
3169     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3170     typedef uniform_int_distribution<ptrdiff_t> _Dp;
3171     typedef typename _Dp::param_type _Pp;
3172     difference_type __d = __last - __first;
3173     if (__d > 1)
3174     {
3175         _Dp __uid;
3176         __rs_default __g = __rs_get();
3177         for (--__last, --__d; __first < __last; ++__first, --__d)
3178         {
3179             difference_type __i = __uid(__g, _Pp(0, __d));
3180             if (__i != difference_type(0))
3181                 swap(*__first, *(__first + __i));
3182         }
3183     }
3184 }
3185
3186 template <class _RandomAccessIterator, class _RandomNumberGenerator>
3187 void
3188 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3189 #ifndef _LIBCPP_CXX03_LANG
3190                _RandomNumberGenerator&& __rand)
3191 #else
3192                _RandomNumberGenerator& __rand)
3193 #endif
3194 {
3195     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3196     difference_type __d = __last - __first;
3197     if (__d > 1)
3198     {
3199         for (--__last; __first < __last; ++__first, --__d)
3200         {
3201             difference_type __i = __rand(__d);
3202             swap(*__first, *(__first + __i));
3203         }
3204     }
3205 }
3206 #endif
3207
3208 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3209           class _UniformRandomNumberGenerator>
3210 _LIBCPP_INLINE_VISIBILITY
3211 _SampleIterator __sample(_PopulationIterator __first,
3212                          _PopulationIterator __last, _SampleIterator __output,
3213                          _Distance __n,
3214                          _UniformRandomNumberGenerator & __g,
3215                          input_iterator_tag) {
3216
3217   _Distance __k = 0;
3218   for (; __first != __last && __k < __n; ++__first, (void)++__k)
3219     __output[__k] = *__first;
3220   _Distance __sz = __k;
3221   for (; __first != __last; ++__first, (void)++__k) {
3222     _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g);
3223     if (__r < __sz)
3224       __output[__r] = *__first;
3225   }
3226   return __output + _VSTD::min(__n, __k);
3227 }
3228
3229 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3230           class _UniformRandomNumberGenerator>
3231 _LIBCPP_INLINE_VISIBILITY
3232 _SampleIterator __sample(_PopulationIterator __first,
3233                          _PopulationIterator __last, _SampleIterator __output,
3234                          _Distance __n,
3235                          _UniformRandomNumberGenerator& __g,
3236                          forward_iterator_tag) {
3237   _Distance __unsampled_sz = _VSTD::distance(__first, __last);
3238   for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
3239     _Distance __r =
3240         _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g);
3241     if (__r < __n) {
3242       *__output++ = *__first;
3243       --__n;
3244     }
3245   }
3246   return __output;
3247 }
3248
3249 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3250           class _UniformRandomNumberGenerator>
3251 _LIBCPP_INLINE_VISIBILITY
3252 _SampleIterator __sample(_PopulationIterator __first,
3253                          _PopulationIterator __last, _SampleIterator __output,
3254                          _Distance __n, _UniformRandomNumberGenerator& __g) {
3255   typedef typename iterator_traits<_PopulationIterator>::iterator_category
3256         _PopCategory;
3257   typedef typename iterator_traits<_PopulationIterator>::difference_type
3258         _Difference;
3259   static_assert(__is_forward_iterator<_PopulationIterator>::value ||
3260                 __is_random_access_iterator<_SampleIterator>::value,
3261                 "SampleIterator must meet the requirements of RandomAccessIterator");
3262   typedef typename common_type<_Distance, _Difference>::type _CommonType;
3263   _LIBCPP_ASSERT(__n >= 0, "N must be a positive number.");
3264   return _VSTD::__sample(
3265       __first, __last, __output, _CommonType(__n),
3266       __g, _PopCategory());
3267 }
3268
3269 #if _LIBCPP_STD_VER > 14
3270 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3271           class _UniformRandomNumberGenerator>
3272 inline _LIBCPP_INLINE_VISIBILITY
3273 _SampleIterator sample(_PopulationIterator __first,
3274                        _PopulationIterator __last, _SampleIterator __output,
3275                        _Distance __n, _UniformRandomNumberGenerator&& __g) {
3276     return _VSTD::__sample(__first, __last, __output, __n, __g);
3277 }
3278 #endif // _LIBCPP_STD_VER > 14
3279
3280 template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
3281     void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3282 #ifndef _LIBCPP_CXX03_LANG
3283                  _UniformRandomNumberGenerator&& __g)
3284 #else
3285                  _UniformRandomNumberGenerator& __g)
3286 #endif
3287 {
3288     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3289     typedef uniform_int_distribution<ptrdiff_t> _Dp;
3290     typedef typename _Dp::param_type _Pp;
3291     difference_type __d = __last - __first;
3292     if (__d > 1)
3293     {
3294         _Dp __uid;
3295         for (--__last, --__d; __first < __last; ++__first, --__d)
3296         {
3297             difference_type __i = __uid(__g, _Pp(0, __d));
3298             if (__i != difference_type(0))
3299                 swap(*__first, *(__first + __i));
3300         }
3301     }
3302 }
3303
3304 template <class _InputIterator, class _Predicate>
3305 bool
3306 is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3307 {
3308     for (; __first != __last; ++__first)
3309         if (!__pred(*__first))
3310             break;
3311     if ( __first == __last )
3312         return true;
3313     ++__first;
3314     for (; __first != __last; ++__first)
3315         if (__pred(*__first))
3316             return false;
3317     return true;
3318 }
3319
3320 // partition
3321
3322 template <class _Predicate, class _ForwardIterator>
3323 _ForwardIterator
3324 __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
3325 {
3326     while (true)
3327     {
3328         if (__first == __last)
3329             return __first;
3330         if (!__pred(*__first))
3331             break;
3332         ++__first;
3333     }
3334     for (_ForwardIterator __p = __first; ++__p != __last;)
3335     {
3336         if (__pred(*__p))
3337         {
3338             swap(*__first, *__p);
3339             ++__first;
3340         }
3341     }
3342     return __first;
3343 }
3344
3345 template <class _Predicate, class _BidirectionalIterator>
3346 _BidirectionalIterator
3347 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3348             bidirectional_iterator_tag)
3349 {
3350     while (true)
3351     {
3352         while (true)
3353         {
3354             if (__first == __last)
3355                 return __first;
3356             if (!__pred(*__first))
3357                 break;
3358             ++__first;
3359         }
3360         do
3361         {
3362             if (__first == --__last)
3363                 return __first;
3364         } while (!__pred(*__last));
3365         swap(*__first, *__last);
3366         ++__first;
3367     }
3368 }
3369
3370 template <class _ForwardIterator, class _Predicate>
3371 inline _LIBCPP_INLINE_VISIBILITY
3372 _ForwardIterator
3373 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3374 {
3375     return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>
3376                             (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3377 }
3378
3379 // partition_copy
3380
3381 template <class _InputIterator, class _OutputIterator1,
3382           class _OutputIterator2, class _Predicate>
3383 pair<_OutputIterator1, _OutputIterator2>
3384 partition_copy(_InputIterator __first, _InputIterator __last,
3385                _OutputIterator1 __out_true, _OutputIterator2 __out_false,
3386                _Predicate __pred)
3387 {
3388     for (; __first != __last; ++__first)
3389     {
3390         if (__pred(*__first))
3391         {
3392             *__out_true = *__first;
3393             ++__out_true;
3394         }
3395         else
3396         {
3397             *__out_false = *__first;
3398             ++__out_false;
3399         }
3400     }
3401     return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
3402 }
3403
3404 // partition_point
3405
3406 template<class _ForwardIterator, class _Predicate>
3407 _ForwardIterator
3408 partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3409 {
3410     typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3411     difference_type __len = _VSTD::distance(__first, __last);
3412     while (__len != 0)
3413     {
3414         difference_type __l2 = __len / 2;
3415         _ForwardIterator __m = __first;
3416         _VSTD::advance(__m, __l2);
3417         if (__pred(*__m))
3418         {
3419             __first = ++__m;
3420             __len -= __l2 + 1;
3421         }
3422         else
3423             __len = __l2;
3424     }
3425     return __first;
3426 }
3427
3428 // stable_partition
3429
3430 template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
3431 _ForwardIterator
3432 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3433                    _Distance __len, _Pair __p, forward_iterator_tag __fit)
3434 {
3435     // *__first is known to be false
3436     // __len >= 1
3437     if (__len == 1)
3438         return __first;
3439     if (__len == 2)
3440     {
3441         _ForwardIterator __m = __first;
3442         if (__pred(*++__m))
3443         {
3444             swap(*__first, *__m);
3445             return __m;
3446         }
3447         return __first;
3448     }
3449     if (__len <= __p.second)
3450     {   // The buffer is big enough to use
3451         typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3452         __destruct_n __d(0);
3453         unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3454         // Move the falses into the temporary buffer, and the trues to the front of the line
3455         // Update __first to always point to the end of the trues
3456         value_type* __t = __p.first;
3457         ::new(__t) value_type(_VSTD::move(*__first));
3458         __d.__incr((value_type*)0);
3459         ++__t;
3460         _ForwardIterator __i = __first;
3461         while (++__i != __last)
3462         {
3463             if (__pred(*__i))
3464             {
3465                 *__first = _VSTD::move(*__i);
3466                 ++__first;
3467             }
3468             else
3469             {
3470                 ::new(__t) value_type(_VSTD::move(*__i));
3471                 __d.__incr((value_type*)0);
3472                 ++__t;
3473             }
3474         }
3475         // All trues now at start of range, all falses in buffer
3476         // Move falses back into range, but don't mess up __first which points to first false
3477         __i = __first;
3478         for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3479             *__i = _VSTD::move(*__t2);
3480         // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3481         return __first;
3482     }
3483     // Else not enough buffer, do in place
3484     // __len >= 3
3485     _ForwardIterator __m = __first;
3486     _Distance __len2 = __len / 2;  // __len2 >= 2
3487     _VSTD::advance(__m, __len2);
3488     // recurse on [__first, __m), *__first know to be false
3489     // F?????????????????
3490     // f       m         l
3491     typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3492     _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
3493     // TTTFFFFF??????????
3494     // f  ff   m         l
3495     // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3496     _ForwardIterator __m1 = __m;
3497     _ForwardIterator __second_false = __last;
3498     _Distance __len_half = __len - __len2;
3499     while (__pred(*__m1))
3500     {
3501         if (++__m1 == __last)
3502             goto __second_half_done;
3503         --__len_half;
3504     }
3505     // TTTFFFFFTTTF??????
3506     // f  ff   m  m1     l
3507     __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
3508 __second_half_done:
3509     // TTTFFFFFTTTTTFFFFF
3510     // f  ff   m    sf   l
3511     return _VSTD::rotate(__first_false, __m, __second_false);
3512     // TTTTTTTTFFFFFFFFFF
3513     //         |
3514 }
3515
3516 struct __return_temporary_buffer
3517 {
3518     template <class _Tp>
3519     _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}
3520 };
3521
3522 template <class _Predicate, class _ForwardIterator>
3523 _ForwardIterator
3524 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3525                    forward_iterator_tag)
3526 {
3527     const unsigned __alloc_limit = 3;  // might want to make this a function of trivial assignment
3528     // Either prove all true and return __first or point to first false
3529     while (true)
3530     {
3531         if (__first == __last)
3532             return __first;
3533         if (!__pred(*__first))
3534             break;
3535         ++__first;
3536     }
3537     // We now have a reduced range [__first, __last)
3538     // *__first is known to be false
3539     typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3540     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3541     difference_type __len = _VSTD::distance(__first, __last);
3542     pair<value_type*, ptrdiff_t> __p(0, 0);
3543     unique_ptr<value_type, __return_temporary_buffer> __h;
3544     if (__len >= __alloc_limit)
3545     {
3546         __p = _VSTD::get_temporary_buffer<value_type>(__len);
3547         __h.reset(__p.first);
3548     }
3549     return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3550                              (__first, __last, __pred, __len, __p, forward_iterator_tag());
3551 }
3552
3553 template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
3554 _BidirectionalIterator
3555 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3556                    _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
3557 {
3558     // *__first is known to be false
3559     // *__last is known to be true
3560     // __len >= 2
3561     if (__len == 2)
3562     {
3563         swap(*__first, *__last);
3564         return __last;
3565     }
3566     if (__len == 3)
3567     {
3568         _BidirectionalIterator __m = __first;
3569         if (__pred(*++__m))
3570         {
3571             swap(*__first, *__m);
3572             swap(*__m, *__last);
3573             return __last;
3574         }
3575         swap(*__m, *__last);
3576         swap(*__first, *__m);
3577         return __m;
3578     }
3579     if (__len <= __p.second)
3580     {   // The buffer is big enough to use
3581         typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3582         __destruct_n __d(0);
3583         unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3584         // Move the falses into the temporary buffer, and the trues to the front of the line
3585         // Update __first to always point to the end of the trues
3586         value_type* __t = __p.first;
3587         ::new(__t) value_type(_VSTD::move(*__first));
3588         __d.__incr((value_type*)0);
3589         ++__t;
3590         _BidirectionalIterator __i = __first;
3591         while (++__i != __last)
3592         {
3593             if (__pred(*__i))
3594             {
3595                 *__first = _VSTD::move(*__i);
3596                 ++__first;
3597             }
3598             else
3599             {
3600                 ::new(__t) value_type(_VSTD::move(*__i));
3601                 __d.__incr((value_type*)0);
3602                 ++__t;
3603             }
3604         }
3605         // move *__last, known to be true
3606         *__first = _VSTD::move(*__i);
3607         __i = ++__first;
3608         // All trues now at start of range, all falses in buffer
3609         // Move falses back into range, but don't mess up __first which points to first false
3610         for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3611             *__i = _VSTD::move(*__t2);
3612         // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3613         return __first;
3614     }
3615     // Else not enough buffer, do in place
3616     // __len >= 4
3617     _BidirectionalIterator __m = __first;
3618     _Distance __len2 = __len / 2;  // __len2 >= 2
3619     _VSTD::advance(__m, __len2);
3620     // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
3621     // F????????????????T
3622     // f       m        l
3623     _BidirectionalIterator __m1 = __m;
3624     _BidirectionalIterator __first_false = __first;
3625     _Distance __len_half = __len2;
3626     while (!__pred(*--__m1))
3627     {
3628         if (__m1 == __first)
3629             goto __first_half_done;
3630         --__len_half;
3631     }
3632     // F???TFFF?????????T
3633     // f   m1  m        l
3634     typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3635     __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3636 __first_half_done:
3637     // TTTFFFFF?????????T
3638     // f  ff   m        l
3639     // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3640     __m1 = __m;
3641     _BidirectionalIterator __second_false = __last;
3642     ++__second_false;
3643     __len_half = __len - __len2;
3644     while (__pred(*__m1))
3645     {
3646         if (++__m1 == __last)
3647             goto __second_half_done;
3648         --__len_half;
3649     }
3650     // TTTFFFFFTTTF?????T
3651     // f  ff   m  m1    l
3652     __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
3653 __second_half_done:
3654     // TTTFFFFFTTTTTFFFFF
3655     // f  ff   m    sf  l
3656     return _VSTD::rotate(__first_false, __m, __second_false);
3657     // TTTTTTTTFFFFFFFFFF
3658     //         |
3659 }
3660
3661 template <class _Predicate, class _BidirectionalIterator>
3662 _BidirectionalIterator
3663 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3664                    bidirectional_iterator_tag)
3665 {
3666     typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3667     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3668     const difference_type __alloc_limit = 4;  // might want to make this a function of trivial assignment
3669     // Either prove all true and return __first or point to first false
3670     while (true)
3671     {
3672         if (__first == __last)
3673             return __first;
3674         if (!__pred(*__first))
3675             break;
3676         ++__first;
3677     }
3678     // __first points to first false, everything prior to __first is already set.
3679     // Either prove [__first, __last) is all false and return __first, or point __last to last true
3680     do
3681     {
3682         if (__first == --__last)
3683             return __first;
3684     } while (!__pred(*__last));
3685     // We now have a reduced range [__first, __last]
3686     // *__first is known to be false
3687     // *__last is known to be true
3688     // __len >= 2
3689     difference_type __len = _VSTD::distance(__first, __last) + 1;
3690     pair<value_type*, ptrdiff_t> __p(0, 0);
3691     unique_ptr<value_type, __return_temporary_buffer> __h;
3692     if (__len >= __alloc_limit)
3693     {
3694         __p = _VSTD::get_temporary_buffer<value_type>(__len);
3695         __h.reset(__p.first);
3696     }
3697     return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3698                              (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3699 }
3700
3701 template <class _ForwardIterator, class _Predicate>
3702 inline _LIBCPP_INLINE_VISIBILITY
3703 _ForwardIterator
3704 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3705 {
3706     return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3707                              (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3708 }
3709
3710 // is_sorted_until
3711
3712 template <class _ForwardIterator, class _Compare>
3713 _ForwardIterator
3714 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3715 {
3716     if (__first != __last)
3717     {
3718         _ForwardIterator __i = __first;
3719         while (++__i != __last)
3720         {
3721             if (__comp(*__i, *__first))
3722                 return __i;
3723             __first = __i;
3724         }
3725     }
3726     return __last;
3727 }
3728
3729 template<class _ForwardIterator>
3730 inline _LIBCPP_INLINE_VISIBILITY
3731 _ForwardIterator
3732 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3733 {
3734     return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3735 }
3736
3737 // is_sorted
3738
3739 template <class _ForwardIterator, class _Compare>
3740 inline _LIBCPP_INLINE_VISIBILITY
3741 bool
3742 is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3743 {
3744     return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
3745 }
3746
3747 template<class _ForwardIterator>
3748 inline _LIBCPP_INLINE_VISIBILITY
3749 bool
3750 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3751 {
3752     return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3753 }
3754
3755 // sort
3756
3757 // stable, 2-3 compares, 0-2 swaps
3758
3759 template <class _Compare, class _ForwardIterator>
3760 unsigned
3761 __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
3762 {
3763     unsigned __r = 0;
3764     if (!__c(*__y, *__x))          // if x <= y
3765     {
3766         if (!__c(*__z, *__y))      // if y <= z
3767             return __r;            // x <= y && y <= z
3768                                    // x <= y && y > z
3769         swap(*__y, *__z);          // x <= z && y < z
3770         __r = 1;
3771         if (__c(*__y, *__x))       // if x > y
3772         {
3773             swap(*__x, *__y);      // x < y && y <= z
3774             __r = 2;
3775         }
3776         return __r;                // x <= y && y < z
3777     }
3778     if (__c(*__z, *__y))           // x > y, if y > z
3779     {
3780         swap(*__x, *__z);          // x < y && y < z
3781         __r = 1;
3782         return __r;
3783     }
3784     swap(*__x, *__y);              // x > y && y <= z
3785     __r = 1;                       // x < y && x <= z
3786     if (__c(*__z, *__y))           // if y > z
3787     {
3788         swap(*__y, *__z);          // x <= y && y < z
3789         __r = 2;
3790     }
3791     return __r;
3792 }                                  // x <= y && y <= z
3793
3794 // stable, 3-6 compares, 0-5 swaps
3795
3796 template <class _Compare, class _ForwardIterator>
3797 unsigned
3798 __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3799             _ForwardIterator __x4, _Compare __c)
3800 {
3801     unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
3802     if (__c(*__x4, *__x3))
3803     {
3804         swap(*__x3, *__x4);
3805         ++__r;
3806         if (__c(*__x3, *__x2))
3807         {
3808             swap(*__x2, *__x3);
3809             ++__r;
3810             if (__c(*__x2, *__x1))
3811             {
3812                 swap(*__x1, *__x2);
3813                 ++__r;
3814             }
3815         }
3816     }
3817     return __r;
3818 }
3819
3820 // stable, 4-10 compares, 0-9 swaps
3821
3822 template <class _Compare, class _ForwardIterator>
3823 unsigned
3824 __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3825             _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
3826 {
3827     unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
3828     if (__c(*__x5, *__x4))
3829     {
3830         swap(*__x4, *__x5);
3831         ++__r;
3832         if (__c(*__x4, *__x3))
3833         {
3834             swap(*__x3, *__x4);
3835             ++__r;
3836             if (__c(*__x3, *__x2))
3837             {
3838                 swap(*__x2, *__x3);
3839                 ++__r;
3840                 if (__c(*__x2, *__x1))
3841                 {
3842                     swap(*__x1, *__x2);
3843                     ++__r;
3844                 }
3845             }
3846         }
3847     }
3848     return __r;
3849 }
3850
3851 // Assumes size > 0
3852 template <class _Compare, class _BirdirectionalIterator>
3853 void
3854 __selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3855 {
3856     _BirdirectionalIterator __lm1 = __last;
3857     for (--__lm1; __first != __lm1; ++__first)
3858     {
3859         _BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator,
3860                                                         typename add_lvalue_reference<_Compare>::type>
3861                                                        (__first, __last, __comp);
3862         if (__i != __first)
3863             swap(*__first, *__i);
3864     }
3865 }
3866
3867 template <class _Compare, class _BirdirectionalIterator>
3868 void
3869 __insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3870 {
3871     typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3872     if (__first != __last)
3873     {
3874         _BirdirectionalIterator __i = __first;
3875         for (++__i; __i != __last; ++__i)
3876         {
3877             _BirdirectionalIterator __j = __i;
3878             value_type __t(_VSTD::move(*__j));
3879             for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t,  *--__k); --__j)
3880                 *__j = _VSTD::move(*__k);
3881             *__j = _VSTD::move(__t);
3882         }
3883     }
3884 }
3885
3886 template <class _Compare, class _RandomAccessIterator>
3887 void
3888 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3889 {
3890     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3891     _RandomAccessIterator __j = __first+2;
3892     __sort3<_Compare>(__first, __first+1, __j, __comp);
3893     for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3894     {
3895         if (__comp(*__i, *__j))
3896         {
3897             value_type __t(_VSTD::move(*__i));
3898             _RandomAccessIterator __k = __j;
3899             __j = __i;
3900             do
3901             {
3902                 *__j = _VSTD::move(*__k);
3903                 __j = __k;
3904             } while (__j != __first && __comp(__t, *--__k));
3905             *__j = _VSTD::move(__t);
3906         }
3907         __j = __i;
3908     }
3909 }
3910
3911 template <class _Compare, class _RandomAccessIterator>
3912 bool
3913 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3914 {
3915     switch (__last - __first)
3916     {
3917     case 0:
3918     case 1:
3919         return true;
3920     case 2:
3921         if (__comp(*--__last, *__first))
3922             swap(*__first, *__last);
3923         return true;
3924     case 3:
3925         _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3926         return true;
3927     case 4:
3928         _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3929         return true;
3930     case 5:
3931         _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3932         return true;
3933     }
3934     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3935     _RandomAccessIterator __j = __first+2;
3936     __sort3<_Compare>(__first, __first+1, __j, __comp);
3937     const unsigned __limit = 8;
3938     unsigned __count = 0;
3939     for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3940     {
3941         if (__comp(*__i, *__j))
3942         {
3943             value_type __t(_VSTD::move(*__i));
3944             _RandomAccessIterator __k = __j;
3945             __j = __i;
3946             do
3947             {
3948                 *__j = _VSTD::move(*__k);
3949                 __j = __k;
3950             } while (__j != __first && __comp(__t, *--__k));
3951             *__j = _VSTD::move(__t);
3952             if (++__count == __limit)
3953                 return ++__i == __last;
3954         }
3955         __j = __i;
3956     }
3957     return true;
3958 }
3959
3960 template <class _Compare, class _BirdirectionalIterator>
3961 void
3962 __insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
3963                       typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
3964 {
3965     typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3966     if (__first1 != __last1)
3967     {
3968         __destruct_n __d(0);
3969         unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
3970         value_type* __last2 = __first2;
3971         ::new(__last2) value_type(_VSTD::move(*__first1));
3972         __d.__incr((value_type*)0);
3973         for (++__last2; ++__first1 != __last1; ++__last2)
3974         {
3975             value_type* __j2 = __last2;
3976             value_type* __i2 = __j2;
3977             if (__comp(*__first1, *--__i2))
3978             {
3979                 ::new(__j2) value_type(_VSTD::move(*__i2));
3980                 __d.__incr((value_type*)0);
3981                 for (--__j2; __i2 != __first2 && __comp(*__first1,  *--__i2); --__j2)
3982                     *__j2 = _VSTD::move(*__i2);
3983                 *__j2 = _VSTD::move(*__first1);
3984             }
3985             else
3986             {
3987                 ::new(__j2) value_type(_VSTD::move(*__first1));
3988                 __d.__incr((value_type*)0);
3989             }
3990         }
3991         __h.release();
3992     }
3993 }
3994
3995 template <class _Compare, class _RandomAccessIterator>
3996 void
3997 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3998 {
3999     // _Compare is known to be a reference type
4000     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4001     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4002     const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
4003                                     is_trivially_copy_assignable<value_type>::value ? 30 : 6;
4004     while (true)
4005     {
4006     __restart:
4007         difference_type __len = __last - __first;
4008         switch (__len)
4009         {
4010         case 0:
4011         case 1:
4012             return;
4013         case 2:
4014             if (__comp(*--__last, *__first))
4015                 swap(*__first, *__last);
4016             return;
4017         case 3:
4018             _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
4019             return;
4020         case 4:
4021             _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
4022             return;
4023         case 5:
4024             _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
4025             return;
4026         }
4027         if (__len <= __limit)
4028         {
4029             _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
4030             return;
4031         }
4032         // __len > 5
4033         _RandomAccessIterator __m = __first;
4034         _RandomAccessIterator __lm1 = __last;
4035         --__lm1;
4036         unsigned __n_swaps;
4037         {
4038         difference_type __delta;
4039         if (__len >= 1000)
4040         {
4041             __delta = __len/2;
4042             __m += __delta;
4043             __delta /= 2;
4044             __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
4045         }
4046         else
4047         {
4048             __delta = __len/2;
4049             __m += __delta;
4050             __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
4051         }
4052         }
4053         // *__m is median
4054         // partition [__first, __m) < *__m and *__m <= [__m, __last)
4055         // (this inhibits tossing elements equivalent to __m around unnecessarily)
4056         _RandomAccessIterator __i = __first;
4057         _RandomAccessIterator __j = __lm1;
4058         // j points beyond range to be tested, *__m is known to be <= *__lm1
4059         // The search going up is known to be guarded but the search coming down isn't.
4060         // Prime the downward search with a guard.
4061         if (!__comp(*__i, *__m))  // if *__first == *__m
4062         {
4063             // *__first == *__m, *__first doesn't go in first part
4064             // manually guard downward moving __j against __i
4065             while (true)
4066             {
4067                 if (__i == --__j)
4068                 {
4069                     // *__first == *__m, *__m <= all other elements
4070                     // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
4071                     ++__i;  // __first + 1
4072                     __j = __last;
4073                     if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
4074                     {
4075                         while (true)
4076                         {
4077                             if (__i == __j)
4078                                 return;  // [__first, __last) all equivalent elements
4079                             if (__comp(*__first, *__i))
4080                             {
4081                                 swap(*__i, *__j);
4082                                 ++__n_swaps;
4083                                 ++__i;
4084                                 break;
4085                             }
4086                             ++__i;
4087                         }
4088                     }
4089                     // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
4090                     if (__i == __j)
4091                         return;
4092                     while (true)
4093                     {
4094                         while (!__comp(*__first, *__i))
4095                             ++__i;
4096                         while (__comp(*__first, *--__j))
4097                             ;
4098                         if (__i >= __j)
4099                             break;
4100                         swap(*__i, *__j);
4101                         ++__n_swaps;
4102                         ++__i;
4103                     }
4104                     // [__first, __i) == *__first and *__first < [__i, __last)
4105                     // The first part is sorted, sort the secod part
4106                     // _VSTD::__sort<_Compare>(__i, __last, __comp);
4107                     __first = __i;
4108                     goto __restart;
4109                 }
4110                 if (__comp(*__j, *__m))
4111                 {
4112                     swap(*__i, *__j);
4113                     ++__n_swaps;
4114                     break;  // found guard for downward moving __j, now use unguarded partition
4115                 }
4116             }
4117         }
4118         // It is known that *__i < *__m
4119         ++__i;
4120         // j points beyond range to be tested, *__m is known to be <= *__lm1
4121         // if not yet partitioned...
4122         if (__i < __j)
4123         {
4124             // known that *(__i - 1) < *__m
4125             // known that __i <= __m
4126             while (true)
4127             {
4128                 // __m still guards upward moving __i
4129                 while (__comp(*__i, *__m))
4130                     ++__i;
4131                 // It is now known that a guard exists for downward moving __j
4132                 while (!__comp(*--__j, *__m))
4133                     ;
4134                 if (__i > __j)
4135                     break;
4136                 swap(*__i, *__j);
4137                 ++__n_swaps;
4138                 // It is known that __m != __j
4139                 // If __m just moved, follow it
4140                 if (__m == __i)
4141                     __m = __j;
4142                 ++__i;
4143             }
4144         }
4145         // [__first, __i) < *__m and *__m <= [__i, __last)
4146         if (__i != __m && __comp(*__m, *__i))
4147         {
4148             swap(*__i, *__m);
4149             ++__n_swaps;
4150         }
4151         // [__first, __i) < *__i and *__i <= [__i+1, __last)
4152         // If we were given a perfect partition, see if insertion sort is quick...
4153         if (__n_swaps == 0)
4154         {
4155             bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
4156             if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
4157             {
4158                 if (__fs)
4159                     return;
4160                 __last = __i;
4161                 continue;
4162             }
4163             else
4164             {
4165                 if (__fs)
4166                 {
4167                     __first = ++__i;
4168                     continue;
4169                 }
4170             }
4171         }
4172         // sort smaller range with recursive call and larger with tail recursion elimination
4173         if (__i - __first < __last - __i)
4174         {
4175             _VSTD::__sort<_Compare>(__first, __i, __comp);
4176             // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4177             __first = ++__i;
4178         }
4179         else
4180         {
4181             _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4182             // _VSTD::__sort<_Compare>(__first, __i, __comp);
4183             __last = __i;
4184         }
4185     }
4186 }
4187
4188 // This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
4189 template <class _RandomAccessIterator, class _Compare>
4190 inline _LIBCPP_INLINE_VISIBILITY
4191 void
4192 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4193 {
4194 #ifdef _LIBCPP_DEBUG
4195     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4196     __debug_less<_Compare> __c(__comp);
4197     __sort<_Comp_ref>(__first, __last, __c);
4198 #else  // _LIBCPP_DEBUG
4199     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4200     __sort<_Comp_ref>(__first, __last, __comp);
4201 #endif  // _LIBCPP_DEBUG
4202 }
4203
4204 template <class _RandomAccessIterator>
4205 inline _LIBCPP_INLINE_VISIBILITY
4206 void
4207 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4208 {
4209     _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4210 }
4211
4212 template <class _Tp>
4213 inline _LIBCPP_INLINE_VISIBILITY
4214 void
4215 sort(_Tp** __first, _Tp** __last)
4216 {
4217     _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
4218 }
4219
4220 template <class _Tp>
4221 inline _LIBCPP_INLINE_VISIBILITY
4222 void
4223 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
4224 {
4225     _VSTD::sort(__first.base(), __last.base());
4226 }
4227
4228 template <class _Tp, class _Compare>
4229 inline _LIBCPP_INLINE_VISIBILITY
4230 void
4231 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
4232 {
4233     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4234     _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
4235 }
4236
4237 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
4238 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4239 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4240 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4241 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))
4242 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4243 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&))
4244 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4245 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&))
4246 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4247 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4248 _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>&))
4249 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&))
4250 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&))
4251 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4252
4253 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))
4254 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4255 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4256 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4257 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))
4258 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4259 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&))
4260 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4261 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&))
4262 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4263 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4264 _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>&))
4265 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&))
4266 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&))
4267 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4268
4269 _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>&))
4270
4271 // lower_bound
4272
4273 template <class _Compare, class _ForwardIterator, class _Tp>
4274 _ForwardIterator
4275 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4276 {
4277     typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4278     difference_type __len = _VSTD::distance(__first, __last);
4279     while (__len != 0)
4280     {
4281         difference_type __l2 = __len / 2;
4282         _ForwardIterator __m = __first;
4283         _VSTD::advance(__m, __l2);
4284         if (__comp(*__m, __value_))
4285         {
4286             __first = ++__m;
4287             __len -= __l2 + 1;
4288         }
4289         else
4290             __len = __l2;
4291     }
4292     return __first;
4293 }
4294
4295 template <class _ForwardIterator, class _Tp, class _Compare>
4296 inline _LIBCPP_INLINE_VISIBILITY
4297 _ForwardIterator
4298 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4299 {
4300 #ifdef _LIBCPP_DEBUG
4301     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4302     __debug_less<_Compare> __c(__comp);
4303     return __lower_bound<_Comp_ref>(__first, __last, __value_, __c);
4304 #else  // _LIBCPP_DEBUG
4305     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4306     return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp);
4307 #endif  // _LIBCPP_DEBUG
4308 }
4309
4310 template <class _ForwardIterator, class _Tp>
4311 inline _LIBCPP_INLINE_VISIBILITY
4312 _ForwardIterator
4313 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4314 {
4315     return _VSTD::lower_bound(__first, __last, __value_,
4316                              __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4317 }
4318
4319 // upper_bound
4320
4321 template <class _Compare, class _ForwardIterator, class _Tp>
4322 _ForwardIterator
4323 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4324 {
4325     typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4326     difference_type __len = _VSTD::distance(__first, __last);
4327     while (__len != 0)
4328     {
4329         difference_type __l2 = __len / 2;
4330         _ForwardIterator __m = __first;
4331         _VSTD::advance(__m, __l2);
4332         if (__comp(__value_, *__m))
4333             __len = __l2;
4334         else
4335         {
4336             __first = ++__m;
4337             __len -= __l2 + 1;
4338         }
4339     }
4340     return __first;
4341 }
4342
4343 template <class _ForwardIterator, class _Tp, class _Compare>
4344 inline _LIBCPP_INLINE_VISIBILITY
4345 _ForwardIterator
4346 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4347 {
4348 #ifdef _LIBCPP_DEBUG
4349     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4350     __debug_less<_Compare> __c(__comp);
4351     return __upper_bound<_Comp_ref>(__first, __last, __value_, __c);
4352 #else  // _LIBCPP_DEBUG
4353     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4354     return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp);
4355 #endif  // _LIBCPP_DEBUG
4356 }
4357
4358 template <class _ForwardIterator, class _Tp>
4359 inline _LIBCPP_INLINE_VISIBILITY
4360 _ForwardIterator
4361 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4362 {
4363     return _VSTD::upper_bound(__first, __last, __value_,
4364                              __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
4365 }
4366
4367 // equal_range
4368
4369 template <class _Compare, class _ForwardIterator, class _Tp>
4370 pair<_ForwardIterator, _ForwardIterator>
4371 __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4372 {
4373     typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4374     difference_type __len = _VSTD::distance(__first, __last);
4375     while (__len != 0)
4376     {
4377         difference_type __l2 = __len / 2;
4378         _ForwardIterator __m = __first;
4379         _VSTD::advance(__m, __l2);
4380         if (__comp(*__m, __value_))
4381         {
4382             __first = ++__m;
4383             __len -= __l2 + 1;
4384         }
4385         else if (__comp(__value_, *__m))
4386         {
4387             __last = __m;
4388             __len = __l2;
4389         }
4390         else
4391         {
4392             _ForwardIterator __mp1 = __m;
4393             return pair<_ForwardIterator, _ForwardIterator>
4394                    (
4395                       __lower_bound<_Compare>(__first, __m, __value_, __comp),
4396                       __upper_bound<_Compare>(++__mp1, __last, __value_, __comp)
4397                    );
4398         }
4399     }
4400     return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4401 }
4402
4403 template <class _ForwardIterator, class _Tp, class _Compare>
4404 inline _LIBCPP_INLINE_VISIBILITY
4405 pair<_ForwardIterator, _ForwardIterator>
4406 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4407 {
4408 #ifdef _LIBCPP_DEBUG
4409     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4410     __debug_less<_Compare> __c(__comp);
4411     return __equal_range<_Comp_ref>(__first, __last, __value_, __c);
4412 #else  // _LIBCPP_DEBUG
4413     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4414     return __equal_range<_Comp_ref>(__first, __last, __value_, __comp);
4415 #endif  // _LIBCPP_DEBUG
4416 }
4417
4418 template <class _ForwardIterator, class _Tp>
4419 inline _LIBCPP_INLINE_VISIBILITY
4420 pair<_ForwardIterator, _ForwardIterator>
4421 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4422 {
4423     return _VSTD::equal_range(__first, __last, __value_,
4424                              __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4425 }
4426
4427 // binary_search
4428
4429 template <class _Compare, class _ForwardIterator, class _Tp>
4430 inline _LIBCPP_INLINE_VISIBILITY
4431 bool
4432 __binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4433 {
4434     __first = __lower_bound<_Compare>(__first, __last, __value_, __comp);
4435     return __first != __last && !__comp(__value_, *__first);
4436 }
4437
4438 template <class _ForwardIterator, class _Tp, class _Compare>
4439 inline _LIBCPP_INLINE_VISIBILITY
4440 bool
4441 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4442 {
4443 #ifdef _LIBCPP_DEBUG
4444     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4445     __debug_less<_Compare> __c(__comp);
4446     return __binary_search<_Comp_ref>(__first, __last, __value_, __c);
4447 #else  // _LIBCPP_DEBUG
4448     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4449     return __binary_search<_Comp_ref>(__first, __last, __value_, __comp);
4450 #endif  // _LIBCPP_DEBUG
4451 }
4452
4453 template <class _ForwardIterator, class _Tp>
4454 inline _LIBCPP_INLINE_VISIBILITY
4455 bool
4456 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4457 {
4458     return _VSTD::binary_search(__first, __last, __value_,
4459                              __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4460 }
4461
4462 // merge
4463
4464 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4465 _OutputIterator
4466 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4467         _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4468 {
4469     for (; __first1 != __last1; ++__result)
4470     {
4471         if (__first2 == __last2)
4472             return _VSTD::copy(__first1, __last1, __result);
4473         if (__comp(*__first2, *__first1))
4474         {
4475             *__result = *__first2;
4476             ++__first2;
4477         }
4478         else
4479         {
4480             *__result = *__first1;
4481             ++__first1;
4482         }
4483     }
4484     return _VSTD::copy(__first2, __last2, __result);
4485 }
4486
4487 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4488 inline _LIBCPP_INLINE_VISIBILITY
4489 _OutputIterator
4490 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4491       _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4492 {
4493 #ifdef _LIBCPP_DEBUG
4494     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4495     __debug_less<_Compare> __c(__comp);
4496     return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
4497 #else  // _LIBCPP_DEBUG
4498     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4499     return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4500 #endif  // _LIBCPP_DEBUG
4501 }
4502
4503 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4504 inline _LIBCPP_INLINE_VISIBILITY
4505 _OutputIterator
4506 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4507       _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4508 {
4509     typedef typename iterator_traits<_InputIterator1>::value_type __v1;
4510     typedef typename iterator_traits<_InputIterator2>::value_type __v2;
4511     return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
4512 }
4513
4514 // inplace_merge
4515
4516 template <class _Compare, class _InputIterator1, class _InputIterator2,
4517           class _OutputIterator>
4518 void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
4519                           _InputIterator2 __first2, _InputIterator2 __last2,
4520                           _OutputIterator __result, _Compare __comp)
4521 {
4522     for (; __first1 != __last1; ++__result)
4523     {
4524         if (__first2 == __last2)
4525         {
4526             _VSTD::move(__first1, __last1, __result);
4527             return;
4528         }
4529
4530         if (__comp(*__first2, *__first1))
4531         {
4532             *__result = _VSTD::move(*__first2);
4533             ++__first2;
4534         }
4535         else
4536         {
4537             *__result = _VSTD::move(*__first1);
4538             ++__first1;
4539         }
4540     }
4541     // __first2 through __last2 are already in the right spot.
4542 }
4543
4544 template <class _Compare, class _BidirectionalIterator>
4545 void
4546 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4547                 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4548                                  typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4549                 typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
4550 {
4551     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4552     __destruct_n __d(0);
4553     unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4554     if (__len1 <= __len2)
4555     {
4556         value_type* __p = __buff;
4557         for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4558             ::new(__p) value_type(_VSTD::move(*__i));
4559         __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);
4560     }
4561     else
4562     {
4563         value_type* __p = __buff;
4564         for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4565             ::new(__p) value_type(_VSTD::move(*__i));
4566         typedef reverse_iterator<_BidirectionalIterator> _RBi;
4567         typedef reverse_iterator<value_type*> _Rv;
4568         __half_inplace_merge(_Rv(__p), _Rv(__buff),
4569                              _RBi(__middle), _RBi(__first),
4570                              _RBi(__last), __negate<_Compare>(__comp));
4571     }
4572 }
4573
4574 template <class _Compare, class _BidirectionalIterator>
4575 void
4576 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4577                 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4578                                  typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4579                 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
4580 {
4581     typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4582     while (true)
4583     {
4584         // if __middle == __last, we're done
4585         if (__len2 == 0)
4586             return;
4587         if (__len1 <= __buff_size || __len2 <= __buff_size)
4588             return __buffered_inplace_merge<_Compare>
4589                    (__first, __middle, __last, __comp, __len1, __len2, __buff);
4590         // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
4591         for (; true; ++__first, (void) --__len1)
4592         {
4593             if (__len1 == 0)
4594                 return;
4595             if (__comp(*__middle, *__first))
4596                 break;
4597         }
4598         // __first < __middle < __last
4599         // *__first > *__middle
4600         // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4601         //     all elements in:
4602         //         [__first, __m1)  <= [__middle, __m2)
4603         //         [__middle, __m2) <  [__m1, __middle)
4604         //         [__m1, __middle) <= [__m2, __last)
4605         //     and __m1 or __m2 is in the middle of its range
4606         _BidirectionalIterator __m1;  // "median" of [__first, __middle)
4607         _BidirectionalIterator __m2;  // "median" of [__middle, __last)
4608         difference_type __len11;      // distance(__first, __m1)
4609         difference_type __len21;      // distance(__middle, __m2)
4610         // binary search smaller range
4611         if (__len1 < __len2)
4612         {   // __len >= 1, __len2 >= 2
4613             __len21 = __len2 / 2;
4614             __m2 = __middle;
4615             _VSTD::advance(__m2, __len21);
4616             __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4617             __len11 = _VSTD::distance(__first, __m1);
4618         }
4619         else
4620         {
4621             if (__len1 == 1)
4622             {   // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
4623                 // It is known *__first > *__middle
4624                 swap(*__first, *__middle);
4625                 return;
4626             }
4627             // __len1 >= 2, __len2 >= 1
4628             __len11 = __len1 / 2;
4629             __m1 = __first;
4630             _VSTD::advance(__m1, __len11);
4631             __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp);
4632             __len21 = _VSTD::distance(__middle, __m2);
4633         }
4634         difference_type __len12 = __len1 - __len11;  // distance(__m1, __middle)
4635         difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)
4636         // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4637         // swap middle two partitions
4638         __middle = _VSTD::rotate(__m1, __middle, __m2);
4639         // __len12 and __len21 now have swapped meanings
4640         // merge smaller range with recurisve call and larger with tail recursion elimination
4641         if (__len11 + __len21 < __len12 + __len22)
4642         {
4643             __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4644 //          __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4645             __first = __middle;
4646             __middle = __m2;
4647             __len1 = __len12;
4648             __len2 = __len22;
4649         }
4650         else
4651         {
4652             __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4653 //          __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4654             __last = __middle;
4655             __middle = __m1;
4656             __len1 = __len11;
4657             __len2 = __len21;
4658         }
4659     }
4660 }
4661
4662 template <class _BidirectionalIterator, class _Compare>
4663 inline _LIBCPP_INLINE_VISIBILITY
4664 void
4665 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4666               _Compare __comp)
4667 {
4668     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4669     typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4670     difference_type __len1 = _VSTD::distance(__first, __middle);
4671     difference_type __len2 = _VSTD::distance(__middle, __last);
4672     difference_type __buf_size = _VSTD::min(__len1, __len2);
4673     pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
4674     unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
4675
4676 #ifdef _LIBCPP_DEBUG
4677     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4678     __debug_less<_Compare> __c(__comp);
4679     return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2,
4680                                             __buf.first, __buf.second);
4681 #else  // _LIBCPP_DEBUG
4682     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4683     return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4684                                             __buf.first, __buf.second);
4685 #endif  // _LIBCPP_DEBUG
4686 }
4687
4688 template <class _BidirectionalIterator>
4689 inline _LIBCPP_INLINE_VISIBILITY
4690 void
4691 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
4692 {
4693     _VSTD::inplace_merge(__first, __middle, __last,
4694                         __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4695 }
4696
4697 // stable_sort
4698
4699 template <class _Compare, class _InputIterator1, class _InputIterator2>
4700 void
4701 __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
4702         _InputIterator2 __first2, _InputIterator2 __last2,
4703         typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
4704 {
4705     typedef typename iterator_traits<_InputIterator1>::value_type value_type;
4706     __destruct_n __d(0);
4707     unique_ptr<value_type, __destruct_n&> __h(__result, __d);
4708     for (; true; ++__result)
4709     {
4710         if (__first1 == __last1)
4711         {
4712             for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0))
4713                 ::new (__result) value_type(_VSTD::move(*__first2));
4714             __h.release();
4715             return;
4716         }
4717         if (__first2 == __last2)
4718         {
4719             for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0))
4720                 ::new (__result) value_type(_VSTD::move(*__first1));
4721             __h.release();
4722             return;
4723         }
4724         if (__comp(*__first2, *__first1))
4725         {
4726             ::new (__result) value_type(_VSTD::move(*__first2));
4727             __d.__incr((value_type*)0);
4728             ++__first2;
4729         }
4730         else
4731         {
4732             ::new (__result) value_type(_VSTD::move(*__first1));
4733             __d.__incr((value_type*)0);
4734             ++__first1;
4735         }
4736     }
4737 }
4738
4739 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4740 void
4741 __merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
4742         _InputIterator2 __first2, _InputIterator2 __last2,
4743         _OutputIterator __result, _Compare __comp)
4744 {
4745     for (; __first1 != __last1; ++__result)
4746     {
4747         if (__first2 == __last2)
4748         {
4749             for (; __first1 != __last1; ++__first1, ++__result)
4750                 *__result = _VSTD::move(*__first1);
4751             return;
4752         }
4753         if (__comp(*__first2, *__first1))
4754         {
4755             *__result = _VSTD::move(*__first2);
4756             ++__first2;
4757         }
4758         else
4759         {
4760             *__result = _VSTD::move(*__first1);
4761             ++__first1;
4762         }
4763     }
4764     for (; __first2 != __last2; ++__first2, ++__result)
4765         *__result = _VSTD::move(*__first2);
4766 }
4767
4768 template <class _Compare, class _RandomAccessIterator>
4769 void
4770 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4771               typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4772               typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
4773
4774 template <class _Compare, class _RandomAccessIterator>
4775 void
4776 __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
4777                    typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4778                    typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
4779 {
4780     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4781     switch (__len)
4782     {
4783     case 0:
4784         return;
4785     case 1:
4786         ::new(__first2) value_type(_VSTD::move(*__first1));
4787         return;
4788     case 2:
4789        __destruct_n __d(0);
4790         unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
4791          if (__comp(*--__last1, *__first1))
4792         {
4793             ::new(__first2) value_type(_VSTD::move(*__last1));
4794             __d.__incr((value_type*)0);
4795             ++__first2;
4796             ::new(__first2) value_type(_VSTD::move(*__first1));
4797         }
4798         else
4799         {
4800             ::new(__first2) value_type(_VSTD::move(*__first1));
4801             __d.__incr((value_type*)0);
4802             ++__first2;
4803             ::new(__first2) value_type(_VSTD::move(*__last1));
4804         }
4805         __h2.release();
4806         return;
4807     }
4808     if (__len <= 8)
4809     {
4810         __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
4811         return;
4812     }
4813     typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4814     _RandomAccessIterator __m = __first1 + __l2;
4815     __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
4816     __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
4817     __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
4818 }
4819
4820 template <class _Tp>
4821 struct __stable_sort_switch
4822 {
4823     static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
4824 };
4825
4826 template <class _Compare, class _RandomAccessIterator>
4827 void
4828 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4829               typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4830               typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
4831 {
4832     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4833     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4834     switch (__len)
4835     {
4836     case 0:
4837     case 1:
4838         return;
4839     case 2:
4840         if (__comp(*--__last, *__first))
4841             swap(*__first, *__last);
4842         return;
4843     }
4844     if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4845     {
4846         __insertion_sort<_Compare>(__first, __last, __comp);
4847         return;
4848     }
4849     typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4850     _RandomAccessIterator __m = __first + __l2;
4851     if (__len <= __buff_size)
4852     {
4853         __destruct_n __d(0);
4854         unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4855         __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4856         __d.__set(__l2, (value_type*)0);
4857         __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
4858         __d.__set(__len, (value_type*)0);
4859         __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4860 //         __merge<_Compare>(move_iterator<value_type*>(__buff),
4861 //                           move_iterator<value_type*>(__buff + __l2),
4862 //                           move_iterator<_RandomAccessIterator>(__buff + __l2),
4863 //                           move_iterator<_RandomAccessIterator>(__buff + __len),
4864 //                           __first, __comp);
4865         return;
4866     }
4867     __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4868     __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
4869     __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4870 }
4871
4872 template <class _RandomAccessIterator, class _Compare>
4873 inline _LIBCPP_INLINE_VISIBILITY
4874 void
4875 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4876 {
4877     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4878     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4879     difference_type __len = __last - __first;
4880     pair<value_type*, ptrdiff_t> __buf(0, 0);
4881     unique_ptr<value_type, __return_temporary_buffer> __h;
4882     if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4883     {
4884         __buf = _VSTD::get_temporary_buffer<value_type>(__len);
4885         __h.reset(__buf.first);
4886     }
4887 #ifdef _LIBCPP_DEBUG
4888     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4889     __debug_less<_Compare> __c(__comp);
4890     __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);
4891 #else  // _LIBCPP_DEBUG
4892     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4893     __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4894 #endif  // _LIBCPP_DEBUG
4895 }
4896
4897 template <class _RandomAccessIterator>
4898 inline _LIBCPP_INLINE_VISIBILITY
4899 void
4900 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4901 {
4902     _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4903 }
4904
4905 // is_heap_until
4906
4907 template <class _RandomAccessIterator, class _Compare>
4908 _RandomAccessIterator
4909 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4910 {
4911     typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4912     difference_type __len = __last - __first;
4913     difference_type __p = 0;
4914     difference_type __c = 1;
4915     _RandomAccessIterator __pp = __first;
4916     while (__c < __len)
4917     {
4918         _RandomAccessIterator __cp = __first + __c;
4919         if (__comp(*__pp, *__cp))
4920             return __cp;
4921         ++__c;
4922         ++__cp;
4923         if (__c == __len)
4924             return __last;
4925         if (__comp(*__pp, *__cp))
4926             return __cp;
4927         ++__p;
4928         ++__pp;
4929         __c = 2 * __p + 1;
4930     }
4931     return __last;
4932 }
4933
4934 template<class _RandomAccessIterator>
4935 inline _LIBCPP_INLINE_VISIBILITY
4936 _RandomAccessIterator
4937 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4938 {
4939     return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4940 }
4941
4942 // is_heap
4943
4944 template <class _RandomAccessIterator, class _Compare>
4945 inline _LIBCPP_INLINE_VISIBILITY
4946 bool
4947 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4948 {
4949     return _VSTD::is_heap_until(__first, __last, __comp) == __last;
4950 }
4951
4952 template<class _RandomAccessIterator>
4953 inline _LIBCPP_INLINE_VISIBILITY
4954 bool
4955 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4956 {
4957     return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4958 }
4959
4960 // push_heap
4961
4962 template <class _Compare, class _RandomAccessIterator>
4963 void
4964 __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4965           typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4966 {
4967     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4968     if (__len > 1)
4969     {
4970         __len = (__len - 2) / 2;
4971         _RandomAccessIterator __ptr = __first + __len;
4972         if (__comp(*__ptr, *--__last))
4973         {
4974             value_type __t(_VSTD::move(*__last));
4975             do
4976             {
4977                 *__last = _VSTD::move(*__ptr);
4978                 __last = __ptr;
4979                 if (__len == 0)
4980                     break;
4981                 __len = (__len - 1) / 2;
4982                 __ptr = __first + __len;
4983             } while (__comp(*__ptr, __t));
4984             *__last = _VSTD::move(__t);
4985         }
4986     }
4987 }
4988
4989 template <class _RandomAccessIterator, class _Compare>
4990 inline _LIBCPP_INLINE_VISIBILITY
4991 void
4992 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4993 {
4994 #ifdef _LIBCPP_DEBUG
4995     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4996     __debug_less<_Compare> __c(__comp);
4997     __sift_up<_Comp_ref>(__first, __last, __c, __last - __first);
4998 #else  // _LIBCPP_DEBUG
4999     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5000     __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
5001 #endif  // _LIBCPP_DEBUG
5002 }
5003
5004 template <class _RandomAccessIterator>
5005 inline _LIBCPP_INLINE_VISIBILITY
5006 void
5007 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5008 {
5009     _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5010 }
5011
5012 // pop_heap
5013
5014 template <class _Compare, class _RandomAccessIterator>
5015 void
5016 __sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/,
5017             _Compare __comp,
5018             typename iterator_traits<_RandomAccessIterator>::difference_type __len,
5019             _RandomAccessIterator __start)
5020 {
5021     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5022     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
5023     // left-child of __start is at 2 * __start + 1
5024     // right-child of __start is at 2 * __start + 2
5025     difference_type __child = __start - __first;
5026
5027     if (__len < 2 || (__len - 2) / 2 < __child)
5028         return;
5029
5030     __child = 2 * __child + 1;
5031     _RandomAccessIterator __child_i = __first + __child;
5032
5033     if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
5034         // right-child exists and is greater than left-child
5035         ++__child_i;
5036         ++__child;
5037     }
5038
5039     // check if we are in heap-order
5040     if (__comp(*__child_i, *__start))
5041         // we are, __start is larger than it's largest child
5042         return;
5043
5044     value_type __top(_VSTD::move(*__start));
5045     do
5046     {
5047         // we are not in heap-order, swap the parent with it's largest child
5048         *__start = _VSTD::move(*__child_i);
5049         __start = __child_i;
5050
5051         if ((__len - 2) / 2 < __child)
5052             break;
5053
5054         // recompute the child based off of the updated parent
5055         __child = 2 * __child + 1;
5056         __child_i = __first + __child;
5057
5058         if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
5059             // right-child exists and is greater than left-child
5060             ++__child_i;
5061             ++__child;
5062         }
5063
5064         // check if we are in heap-order
5065     } while (!__comp(*__child_i, __top));
5066     *__start = _VSTD::move(__top);
5067 }
5068
5069 template <class _Compare, class _RandomAccessIterator>
5070 inline _LIBCPP_INLINE_VISIBILITY
5071 void
5072 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
5073            typename iterator_traits<_RandomAccessIterator>::difference_type __len)
5074 {
5075     if (__len > 1)
5076     {
5077         swap(*__first, *--__last);
5078         __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);
5079     }
5080 }
5081
5082 template <class _RandomAccessIterator, class _Compare>
5083 inline _LIBCPP_INLINE_VISIBILITY
5084 void
5085 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5086 {
5087 #ifdef _LIBCPP_DEBUG
5088     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5089     __debug_less<_Compare> __c(__comp);
5090     __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);
5091 #else  // _LIBCPP_DEBUG
5092     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5093     __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
5094 #endif  // _LIBCPP_DEBUG
5095 }
5096
5097 template <class _RandomAccessIterator>
5098 inline _LIBCPP_INLINE_VISIBILITY
5099 void
5100 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5101 {
5102     _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5103 }
5104
5105 // make_heap
5106
5107 template <class _Compare, class _RandomAccessIterator>
5108 void
5109 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5110 {
5111     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5112     difference_type __n = __last - __first;
5113     if (__n > 1)
5114     {
5115         // start from the first parent, there is no need to consider children
5116         for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start)
5117         {
5118             __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start);
5119         }
5120     }
5121 }
5122
5123 template <class _RandomAccessIterator, class _Compare>
5124 inline _LIBCPP_INLINE_VISIBILITY
5125 void
5126 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5127 {
5128 #ifdef _LIBCPP_DEBUG
5129     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5130     __debug_less<_Compare> __c(__comp);
5131     __make_heap<_Comp_ref>(__first, __last, __c);
5132 #else  // _LIBCPP_DEBUG
5133     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5134     __make_heap<_Comp_ref>(__first, __last, __comp);
5135 #endif  // _LIBCPP_DEBUG
5136 }
5137
5138 template <class _RandomAccessIterator>
5139 inline _LIBCPP_INLINE_VISIBILITY
5140 void
5141 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5142 {
5143     _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5144 }
5145
5146 // sort_heap
5147
5148 template <class _Compare, class _RandomAccessIterator>
5149 void
5150 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5151 {
5152     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5153     for (difference_type __n = __last - __first; __n > 1; --__last, --__n)
5154         __pop_heap<_Compare>(__first, __last, __comp, __n);
5155 }
5156
5157 template <class _RandomAccessIterator, class _Compare>
5158 inline _LIBCPP_INLINE_VISIBILITY
5159 void
5160 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5161 {
5162 #ifdef _LIBCPP_DEBUG
5163     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5164     __debug_less<_Compare> __c(__comp);
5165     __sort_heap<_Comp_ref>(__first, __last, __c);
5166 #else  // _LIBCPP_DEBUG
5167     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5168     __sort_heap<_Comp_ref>(__first, __last, __comp);
5169 #endif  // _LIBCPP_DEBUG
5170 }
5171
5172 template <class _RandomAccessIterator>
5173 inline _LIBCPP_INLINE_VISIBILITY
5174 void
5175 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5176 {
5177     _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5178 }
5179
5180 // partial_sort
5181
5182 template <class _Compare, class _RandomAccessIterator>
5183 void
5184 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5185              _Compare __comp)
5186 {
5187     __make_heap<_Compare>(__first, __middle, __comp);
5188     typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
5189     for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
5190     {
5191         if (__comp(*__i, *__first))
5192         {
5193             swap(*__i, *__first);
5194             __sift_down<_Compare>(__first, __middle, __comp, __len, __first);
5195         }
5196     }
5197     __sort_heap<_Compare>(__first, __middle, __comp);
5198 }
5199
5200 template <class _RandomAccessIterator, class _Compare>
5201 inline _LIBCPP_INLINE_VISIBILITY
5202 void
5203 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5204              _Compare __comp)
5205 {
5206 #ifdef _LIBCPP_DEBUG
5207     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5208     __debug_less<_Compare> __c(__comp);
5209     __partial_sort<_Comp_ref>(__first, __middle, __last, __c);
5210 #else  // _LIBCPP_DEBUG
5211     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5212     __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
5213 #endif  // _LIBCPP_DEBUG
5214 }
5215
5216 template <class _RandomAccessIterator>
5217 inline _LIBCPP_INLINE_VISIBILITY
5218 void
5219 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
5220 {
5221     _VSTD::partial_sort(__first, __middle, __last,
5222                        __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5223 }
5224
5225 // partial_sort_copy
5226
5227 template <class _Compare, class _InputIterator, class _RandomAccessIterator>
5228 _RandomAccessIterator
5229 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
5230                     _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5231 {
5232     _RandomAccessIterator __r = __result_first;
5233     if (__r != __result_last)
5234     {
5235         for (; __first != __last && __r != __result_last; (void) ++__first, ++__r)
5236             *__r = *__first;
5237         __make_heap<_Compare>(__result_first, __r, __comp);
5238         typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
5239         for (; __first != __last; ++__first)
5240             if (__comp(*__first, *__result_first))
5241             {
5242                 *__result_first = *__first;
5243                 __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first);
5244             }
5245         __sort_heap<_Compare>(__result_first, __r, __comp);
5246     }
5247     return __r;
5248 }
5249
5250 template <class _InputIterator, class _RandomAccessIterator, class _Compare>
5251 inline _LIBCPP_INLINE_VISIBILITY
5252 _RandomAccessIterator
5253 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5254                   _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5255 {
5256 #ifdef _LIBCPP_DEBUG
5257     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5258     __debug_less<_Compare> __c(__comp);
5259     return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);
5260 #else  // _LIBCPP_DEBUG
5261     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5262     return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
5263 #endif  // _LIBCPP_DEBUG
5264 }
5265
5266 template <class _InputIterator, class _RandomAccessIterator>
5267 inline _LIBCPP_INLINE_VISIBILITY
5268 _RandomAccessIterator
5269 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5270                   _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
5271 {
5272     return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
5273                                    __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5274 }
5275
5276 // nth_element
5277
5278 template <class _Compare, class _RandomAccessIterator>
5279 void
5280 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5281 {
5282     // _Compare is known to be a reference type
5283     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5284     const difference_type __limit = 7;
5285     while (true)
5286     {
5287     __restart:
5288         if (__nth == __last)
5289             return;
5290         difference_type __len = __last - __first;
5291         switch (__len)
5292         {
5293         case 0:
5294         case 1:
5295             return;
5296         case 2:
5297             if (__comp(*--__last, *__first))
5298                 swap(*__first, *__last);
5299             return;
5300         case 3:
5301             {
5302             _RandomAccessIterator __m = __first;
5303             _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
5304             return;
5305             }
5306         }
5307         if (__len <= __limit)
5308         {
5309             __selection_sort<_Compare>(__first, __last, __comp);
5310             return;
5311         }
5312         // __len > __limit >= 3
5313         _RandomAccessIterator __m = __first + __len/2;
5314         _RandomAccessIterator __lm1 = __last;
5315         unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
5316         // *__m is median
5317         // partition [__first, __m) < *__m and *__m <= [__m, __last)
5318         // (this inhibits tossing elements equivalent to __m around unnecessarily)
5319         _RandomAccessIterator __i = __first;
5320         _RandomAccessIterator __j = __lm1;
5321         // j points beyond range to be tested, *__lm1 is known to be <= *__m
5322         // The search going up is known to be guarded but the search coming down isn't.
5323         // Prime the downward search with a guard.
5324         if (!__comp(*__i, *__m))  // if *__first == *__m
5325         {
5326             // *__first == *__m, *__first doesn't go in first part
5327             // manually guard downward moving __j against __i
5328             while (true)
5329             {
5330                 if (__i == --__j)
5331                 {
5332                     // *__first == *__m, *__m <= all other elements
5333                     // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
5334                     ++__i;  // __first + 1
5335                     __j = __last;
5336                     if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
5337                     {
5338                         while (true)
5339                         {
5340                             if (__i == __j)
5341                                 return;  // [__first, __last) all equivalent elements
5342                             if (__comp(*__first, *__i))
5343                             {
5344                                 swap(*__i, *__j);
5345                                 ++__n_swaps;
5346                                 ++__i;
5347                                 break;
5348                             }
5349                             ++__i;
5350                         }
5351                     }
5352                     // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
5353                     if (__i == __j)
5354                         return;
5355                     while (true)
5356                     {
5357                         while (!__comp(*__first, *__i))
5358                             ++__i;
5359                         while (__comp(*__first, *--__j))
5360                             ;
5361                         if (__i >= __j)
5362                             break;
5363                         swap(*__i, *__j);
5364                         ++__n_swaps;
5365                         ++__i;
5366                     }
5367                     // [__first, __i) == *__first and *__first < [__i, __last)
5368                     // The first part is sorted,
5369                     if (__nth < __i)
5370                         return;
5371                     // __nth_element the secod part
5372                     // __nth_element<_Compare>(__i, __nth, __last, __comp);
5373                     __first = __i;
5374                     goto __restart;
5375                 }
5376                 if (__comp(*__j, *__m))
5377                 {
5378                     swap(*__i, *__j);
5379                     ++__n_swaps;
5380                     break;  // found guard for downward moving __j, now use unguarded partition
5381                 }
5382             }
5383         }
5384         ++__i;
5385         // j points beyond range to be tested, *__lm1 is known to be <= *__m
5386         // if not yet partitioned...
5387         if (__i < __j)
5388         {
5389             // known that *(__i - 1) < *__m
5390             while (true)
5391             {
5392                 // __m still guards upward moving __i
5393                 while (__comp(*__i, *__m))
5394                     ++__i;
5395                 // It is now known that a guard exists for downward moving __j
5396                 while (!__comp(*--__j, *__m))
5397                     ;
5398                 if (__i >= __j)
5399                     break;
5400                 swap(*__i, *__j);
5401                 ++__n_swaps;
5402                 // It is known that __m != __j
5403                 // If __m just moved, follow it
5404                 if (__m == __i)
5405                     __m = __j;
5406                 ++__i;
5407             }
5408         }
5409         // [__first, __i) < *__m and *__m <= [__i, __last)
5410         if (__i != __m && __comp(*__m, *__i))
5411         {
5412             swap(*__i, *__m);
5413             ++__n_swaps;
5414         }
5415         // [__first, __i) < *__i and *__i <= [__i+1, __last)
5416         if (__nth == __i)
5417             return;
5418         if (__n_swaps == 0)
5419         {
5420             // We were given a perfectly partitioned sequence.  Coincidence?
5421             if (__nth < __i)
5422             {
5423                 // Check for [__first, __i) already sorted
5424                 __j = __m = __first;
5425                 while (++__j != __i)
5426                 {
5427                     if (__comp(*__j, *__m))
5428                         // not yet sorted, so sort
5429                         goto not_sorted;
5430                     __m = __j;
5431                 }
5432                 // [__first, __i) sorted
5433                 return;
5434             }
5435             else
5436             {
5437                 // Check for [__i, __last) already sorted
5438                 __j = __m = __i;
5439                 while (++__j != __last)
5440                 {
5441                     if (__comp(*__j, *__m))
5442                         // not yet sorted, so sort
5443                         goto not_sorted;
5444                     __m = __j;
5445                 }
5446                 // [__i, __last) sorted
5447                 return;
5448             }
5449         }
5450 not_sorted:
5451         // __nth_element on range containing __nth
5452         if (__nth < __i)
5453         {
5454             // __nth_element<_Compare>(__first, __nth, __i, __comp);
5455             __last = __i;
5456         }
5457         else
5458         {
5459             // __nth_element<_Compare>(__i+1, __nth, __last, __comp);
5460             __first = ++__i;
5461         }
5462     }
5463 }
5464
5465 template <class _RandomAccessIterator, class _Compare>
5466 inline _LIBCPP_INLINE_VISIBILITY
5467 void
5468 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5469 {
5470 #ifdef _LIBCPP_DEBUG
5471     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5472     __debug_less<_Compare> __c(__comp);
5473     __nth_element<_Comp_ref>(__first, __nth, __last, __c);
5474 #else  // _LIBCPP_DEBUG
5475     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5476     __nth_element<_Comp_ref>(__first, __nth, __last, __comp);
5477 #endif  // _LIBCPP_DEBUG
5478 }
5479
5480 template <class _RandomAccessIterator>
5481 inline _LIBCPP_INLINE_VISIBILITY
5482 void
5483 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
5484 {
5485     _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5486 }
5487
5488 // includes
5489
5490 template <class _Compare, class _InputIterator1, class _InputIterator2>
5491 bool
5492 __includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5493            _Compare __comp)
5494 {
5495     for (; __first2 != __last2; ++__first1)
5496     {
5497         if (__first1 == __last1 || __comp(*__first2, *__first1))
5498             return false;
5499         if (!__comp(*__first1, *__first2))
5500             ++__first2;
5501     }
5502     return true;
5503 }
5504
5505 template <class _InputIterator1, class _InputIterator2, class _Compare>
5506 inline _LIBCPP_INLINE_VISIBILITY
5507 bool
5508 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5509          _Compare __comp)
5510 {
5511 #ifdef _LIBCPP_DEBUG
5512     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5513     __debug_less<_Compare> __c(__comp);
5514     return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5515 #else  // _LIBCPP_DEBUG
5516     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5517     return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5518 #endif  // _LIBCPP_DEBUG
5519 }
5520
5521 template <class _InputIterator1, class _InputIterator2>
5522 inline _LIBCPP_INLINE_VISIBILITY
5523 bool
5524 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
5525 {
5526     return _VSTD::includes(__first1, __last1, __first2, __last2,
5527                           __less<typename iterator_traits<_InputIterator1>::value_type,
5528                                  typename iterator_traits<_InputIterator2>::value_type>());
5529 }
5530
5531 // set_union
5532
5533 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5534 _OutputIterator
5535 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5536             _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5537 {
5538     for (; __first1 != __last1; ++__result)
5539     {
5540         if (__first2 == __last2)
5541             return _VSTD::copy(__first1, __last1, __result);
5542         if (__comp(*__first2, *__first1))
5543         {
5544             *__result = *__first2;
5545             ++__first2;
5546         }
5547         else
5548         {
5549             *__result = *__first1;
5550             if (!__comp(*__first1, *__first2))
5551                 ++__first2;
5552             ++__first1;
5553         }
5554     }
5555     return _VSTD::copy(__first2, __last2, __result);
5556 }
5557
5558 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5559 inline _LIBCPP_INLINE_VISIBILITY
5560 _OutputIterator
5561 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5562           _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5563 {
5564 #ifdef _LIBCPP_DEBUG
5565     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5566     __debug_less<_Compare> __c(__comp);
5567     return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5568 #else  // _LIBCPP_DEBUG
5569     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5570     return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5571 #endif  // _LIBCPP_DEBUG
5572 }
5573
5574 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5575 inline _LIBCPP_INLINE_VISIBILITY
5576 _OutputIterator
5577 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5578           _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5579 {
5580     return _VSTD::set_union(__first1, __last1, __first2, __last2, __result,
5581                           __less<typename iterator_traits<_InputIterator1>::value_type,
5582                                  typename iterator_traits<_InputIterator2>::value_type>());
5583 }
5584
5585 // set_intersection
5586
5587 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5588 _OutputIterator
5589 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5590                    _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5591 {
5592     while (__first1 != __last1 && __first2 != __last2)
5593     {
5594         if (__comp(*__first1, *__first2))
5595             ++__first1;
5596         else
5597         {
5598             if (!__comp(*__first2, *__first1))
5599             {
5600                 *__result = *__first1;
5601                 ++__result;
5602                 ++__first1;
5603             }
5604             ++__first2;
5605         }
5606     }
5607     return __result;
5608 }
5609
5610 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5611 inline _LIBCPP_INLINE_VISIBILITY
5612 _OutputIterator
5613 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5614                  _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5615 {
5616 #ifdef _LIBCPP_DEBUG
5617     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5618     __debug_less<_Compare> __c(__comp);
5619     return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5620 #else  // _LIBCPP_DEBUG
5621     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5622     return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5623 #endif  // _LIBCPP_DEBUG
5624 }
5625
5626 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5627 inline _LIBCPP_INLINE_VISIBILITY
5628 _OutputIterator
5629 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5630                  _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5631 {
5632     return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result,
5633                                   __less<typename iterator_traits<_InputIterator1>::value_type,
5634                                          typename iterator_traits<_InputIterator2>::value_type>());
5635 }
5636
5637 // set_difference
5638
5639 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5640 _OutputIterator
5641 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5642                  _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5643 {
5644     while (__first1 != __last1)
5645     {
5646         if (__first2 == __last2)
5647             return _VSTD::copy(__first1, __last1, __result);
5648         if (__comp(*__first1, *__first2))
5649         {
5650             *__result = *__first1;
5651             ++__result;
5652             ++__first1;
5653         }
5654         else
5655         {
5656             if (!__comp(*__first2, *__first1))
5657                 ++__first1;
5658             ++__first2;
5659         }
5660     }
5661     return __result;
5662 }
5663
5664 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5665 inline _LIBCPP_INLINE_VISIBILITY
5666 _OutputIterator
5667 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5668                _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5669 {
5670 #ifdef _LIBCPP_DEBUG
5671     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5672     __debug_less<_Compare> __c(__comp);
5673     return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5674 #else  // _LIBCPP_DEBUG
5675     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5676     return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5677 #endif  // _LIBCPP_DEBUG
5678 }
5679
5680 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5681 inline _LIBCPP_INLINE_VISIBILITY
5682 _OutputIterator
5683 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5684                _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5685 {
5686     return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result,
5687                                 __less<typename iterator_traits<_InputIterator1>::value_type,
5688                                        typename iterator_traits<_InputIterator2>::value_type>());
5689 }
5690
5691 // set_symmetric_difference
5692
5693 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5694 _OutputIterator
5695 __set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5696                            _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5697 {
5698     while (__first1 != __last1)
5699     {
5700         if (__first2 == __last2)
5701             return _VSTD::copy(__first1, __last1, __result);
5702         if (__comp(*__first1, *__first2))
5703         {
5704             *__result = *__first1;
5705             ++__result;
5706             ++__first1;
5707         }
5708         else
5709         {
5710             if (__comp(*__first2, *__first1))
5711             {
5712                 *__result = *__first2;
5713                 ++__result;
5714             }
5715             else
5716                 ++__first1;
5717             ++__first2;
5718         }
5719     }
5720     return _VSTD::copy(__first2, __last2, __result);
5721 }
5722
5723 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5724 inline _LIBCPP_INLINE_VISIBILITY
5725 _OutputIterator
5726 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5727                          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5728 {
5729 #ifdef _LIBCPP_DEBUG
5730     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5731     __debug_less<_Compare> __c(__comp);
5732     return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5733 #else  // _LIBCPP_DEBUG
5734     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5735     return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5736 #endif  // _LIBCPP_DEBUG
5737 }
5738
5739 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5740 inline _LIBCPP_INLINE_VISIBILITY
5741 _OutputIterator
5742 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5743                          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5744 {
5745     return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
5746                                           __less<typename iterator_traits<_InputIterator1>::value_type,
5747                                                  typename iterator_traits<_InputIterator2>::value_type>());
5748 }
5749
5750 // lexicographical_compare
5751
5752 template <class _Compare, class _InputIterator1, class _InputIterator2>
5753 bool
5754 __lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5755                           _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5756 {
5757     for (; __first2 != __last2; ++__first1, (void) ++__first2)
5758     {
5759         if (__first1 == __last1 || __comp(*__first1, *__first2))
5760             return true;
5761         if (__comp(*__first2, *__first1))
5762             return false;
5763     }
5764     return false;
5765 }
5766
5767 template <class _InputIterator1, class _InputIterator2, class _Compare>
5768 inline _LIBCPP_INLINE_VISIBILITY
5769 bool
5770 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5771                         _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5772 {
5773 #ifdef _LIBCPP_DEBUG
5774     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5775     __debug_less<_Compare> __c(__comp);
5776     return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5777 #else  // _LIBCPP_DEBUG
5778     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5779     return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5780 #endif  // _LIBCPP_DEBUG
5781 }
5782
5783 template <class _InputIterator1, class _InputIterator2>
5784 inline _LIBCPP_INLINE_VISIBILITY
5785 bool
5786 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5787                         _InputIterator2 __first2, _InputIterator2 __last2)
5788 {
5789     return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,
5790                                          __less<typename iterator_traits<_InputIterator1>::value_type,
5791                                                 typename iterator_traits<_InputIterator2>::value_type>());
5792 }
5793
5794 // next_permutation
5795
5796 template <class _Compare, class _BidirectionalIterator>
5797 bool
5798 __next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5799 {
5800     _BidirectionalIterator __i = __last;
5801     if (__first == __last || __first == --__i)
5802         return false;
5803     while (true)
5804     {
5805         _BidirectionalIterator __ip1 = __i;
5806         if (__comp(*--__i, *__ip1))
5807         {
5808             _BidirectionalIterator __j = __last;
5809             while (!__comp(*__i, *--__j))
5810                 ;
5811             swap(*__i, *__j);
5812             _VSTD::reverse(__ip1, __last);
5813             return true;
5814         }
5815         if (__i == __first)
5816         {
5817             _VSTD::reverse(__first, __last);
5818             return false;
5819         }
5820     }
5821 }
5822
5823 template <class _BidirectionalIterator, class _Compare>
5824 inline _LIBCPP_INLINE_VISIBILITY
5825 bool
5826 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5827 {
5828 #ifdef _LIBCPP_DEBUG
5829     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5830     __debug_less<_Compare> __c(__comp);
5831     return __next_permutation<_Comp_ref>(__first, __last, __c);
5832 #else  // _LIBCPP_DEBUG
5833     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5834     return __next_permutation<_Comp_ref>(__first, __last, __comp);
5835 #endif  // _LIBCPP_DEBUG
5836 }
5837
5838 template <class _BidirectionalIterator>
5839 inline _LIBCPP_INLINE_VISIBILITY
5840 bool
5841 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5842 {
5843     return _VSTD::next_permutation(__first, __last,
5844                                   __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5845 }
5846
5847 // prev_permutation
5848
5849 template <class _Compare, class _BidirectionalIterator>
5850 bool
5851 __prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5852 {
5853     _BidirectionalIterator __i = __last;
5854     if (__first == __last || __first == --__i)
5855         return false;
5856     while (true)
5857     {
5858         _BidirectionalIterator __ip1 = __i;
5859         if (__comp(*__ip1, *--__i))
5860         {
5861             _BidirectionalIterator __j = __last;
5862             while (!__comp(*--__j, *__i))
5863                 ;
5864             swap(*__i, *__j);
5865             _VSTD::reverse(__ip1, __last);
5866             return true;
5867         }
5868         if (__i == __first)
5869         {
5870             _VSTD::reverse(__first, __last);
5871             return false;
5872         }
5873     }
5874 }
5875
5876 template <class _BidirectionalIterator, class _Compare>
5877 inline _LIBCPP_INLINE_VISIBILITY
5878 bool
5879 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5880 {
5881 #ifdef _LIBCPP_DEBUG
5882     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5883     __debug_less<_Compare> __c(__comp);
5884     return __prev_permutation<_Comp_ref>(__first, __last, __c);
5885 #else  // _LIBCPP_DEBUG
5886     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5887     return __prev_permutation<_Comp_ref>(__first, __last, __comp);
5888 #endif  // _LIBCPP_DEBUG
5889 }
5890
5891 template <class _BidirectionalIterator>
5892 inline _LIBCPP_INLINE_VISIBILITY
5893 bool
5894 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5895 {
5896     return _VSTD::prev_permutation(__first, __last,
5897                                   __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5898 }
5899
5900 _LIBCPP_END_NAMESPACE_STD
5901
5902 _LIBCPP_POP_MACROS
5903
5904 #endif  // _LIBCPP_ALGORITHM