contrib/libc++/include/algorithm

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