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