include/algorithm

   1 // -*- C++ -*-
   2 //===-------------------------- algorithm ---------------------------------===//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file is dual licensed under the MIT and the University of Illinois Open
   7 // Source Licenses. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef _LIBCPP_ALGORITHM
  12 #define _LIBCPP_ALGORITHM
  13
  14 /*
  15     algorithm synopsis
  16
  17 #include <initializer_list>
  18
  19 namespace std
  20 {
  21
  22 template <class InputIterator, class Predicate>
  23     bool
  24     all_of(InputIterator first, InputIterator last, Predicate pred);
  25
  26 template <class InputIterator, class Predicate>
  27     bool
  28     any_of(InputIterator first, InputIterator last, Predicate pred);
  29
  30 template <class InputIterator, class Predicate>
  31     bool
  32     none_of(InputIterator first, InputIterator last, Predicate pred);
  33
  34 template <class InputIterator, class Function>
  35     Function
  36     for_each(InputIterator first, InputIterator last, Function f);
  37
  38 template <class InputIterator, class T>
  39     InputIterator
  40     find(InputIterator first, InputIterator last, const T& value);
  41
  42 template <class InputIterator, class Predicate>
  43     InputIterator
  44     find_if(InputIterator first, InputIterator last, Predicate pred);
  45
  46 template<class InputIterator, class Predicate>
  47     InputIterator
  48     find_if_not(InputIterator first, InputIterator last, Predicate pred);
  49
  50 template <class ForwardIterator1, class ForwardIterator2>
  51     ForwardIterator1
  52     find_end(ForwardIterator1 first1, ForwardIterator1 last1,
  53              ForwardIterator2 first2, ForwardIterator2 last2);
  54
  55 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
  56     ForwardIterator1
  57     find_end(ForwardIterator1 first1, ForwardIterator1 last1,
  58              ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
  59
  60 template <class ForwardIterator1, class ForwardIterator2>
  61     ForwardIterator1
  62     find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
  63                   ForwardIterator2 first2, ForwardIterator2 last2);
  64
  65 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
  66     ForwardIterator1
  67     find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
  68                   ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
  69
  70 template <class ForwardIterator>
  71     ForwardIterator
  72     adjacent_find(ForwardIterator first, ForwardIterator last);
  73
  74 template <class ForwardIterator, class BinaryPredicate>
  75     ForwardIterator
  76     adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
  77
  78 template <class InputIterator, class T>
  79     typename iterator_traits<InputIterator>::difference_type
  80     count(InputIterator first, InputIterator last, const T& value);
  81
  82 template <class InputIterator, class Predicate>
  83     typename iterator_traits<InputIterator>::difference_type
  84     count_if(InputIterator first, InputIterator last, Predicate pred);
  85
  86 template <class InputIterator1, class InputIterator2>
  87     pair<InputIterator1, InputIterator2>
  88     mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
  89
  90 template <class InputIterator1, class InputIterator2>
  91     pair<InputIterator1, InputIterator2>
  92     mismatch(InputIterator1 first1, InputIterator1 last1,
  93              InputIterator2 first2, InputIterator2 last2); // **C++14**
  94
  95 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
  96     pair<InputIterator1, InputIterator2>
  97     mismatch(InputIterator1 first1, InputIterator1 last1,
  98              InputIterator2 first2, BinaryPredicate pred);
  99
 100 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
 101     pair<InputIterator1, InputIterator2>
 102     mismatch(InputIterator1 first1, InputIterator1 last1,
 103              InputIterator2 first2, InputIterator2 last2,
 104              BinaryPredicate pred); // **C++14**
 105
 106 template <class InputIterator1, class InputIterator2>
 107     bool
 108     equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
 109
 110 template <class InputIterator1, class InputIterator2>
 111     bool
 112     equal(InputIterator1 first1, InputIterator1 last1,
 113           InputIterator2 first2, InputIterator2 last2); // **C++14**
 114
 115 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
 116     bool
 117     equal(InputIterator1 first1, InputIterator1 last1,
 118           InputIterator2 first2, BinaryPredicate pred);
 119
 120 template <class InputIterator1, class InputIterator2, class BinaryPredicate>
 121     bool
 122     equal(InputIterator1 first1, InputIterator1 last1,
 123           InputIterator2 first2, InputIterator2 last2,
 124           BinaryPredicate pred); // **C++14**
 125
 126 template<class ForwardIterator1, class ForwardIterator2>
 127     bool
 128     is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
 129                    ForwardIterator2 first2);
 130
 131 template<class ForwardIterator1, class ForwardIterator2>
 132     bool
 133     is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
 134                    ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**
 135
 136 template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
 137     bool
 138     is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
 139                    ForwardIterator2 first2, BinaryPredicate pred);
 140
 141 template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
 142     bool
 143     is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
 144                    ForwardIterator2 first2, ForwardIterator2 last2,
 145                    BinaryPredicate pred);  // **C++14**
 146
 147 template <class ForwardIterator1, class ForwardIterator2>
 148     ForwardIterator1
 149     search(ForwardIterator1 first1, ForwardIterator1 last1,
 150            ForwardIterator2 first2, ForwardIterator2 last2);
 151
 152 template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
 153     ForwardIterator1
 154     search(ForwardIterator1 first1, ForwardIterator1 last1,
 155            ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
 156
 157 template <class ForwardIterator, class Size, class T>
 158     ForwardIterator
 159     search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
 160
 161 template <class ForwardIterator, class Size, class T, class BinaryPredicate>
 162     ForwardIterator
 163     search_n(ForwardIterator first, ForwardIterator last,
 164              Size count, const T& value, BinaryPredicate pred);
 165
 166 template <class InputIterator, class OutputIterator>
 167     OutputIterator
 168     copy(InputIterator first, InputIterator last, OutputIterator result);
 169
 170 template<class InputIterator, class OutputIterator, class Predicate>
 171     OutputIterator
 172     copy_if(InputIterator first, InputIterator last,
 173             OutputIterator result, Predicate pred);
 174
 175 template<class InputIterator, class Size, class OutputIterator>
 176     OutputIterator
 177     copy_n(InputIterator first, Size n, OutputIterator result);
 178
 179 template <class BidirectionalIterator1, class BidirectionalIterator2>
 180     BidirectionalIterator2
 181     copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
 182                   BidirectionalIterator2 result);
 183
 184 template <class ForwardIterator1, class ForwardIterator2>
 185     ForwardIterator2
 186     swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
 187
 188 template <class ForwardIterator1, class ForwardIterator2>
 189     void
 190     iter_swap(ForwardIterator1 a, ForwardIterator2 b);
 191
 192 template <class InputIterator, class OutputIterator, class UnaryOperation>
 193     OutputIterator
 194     transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
 195
 196 template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
 197     OutputIterator
 198     transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
 199               OutputIterator result, BinaryOperation binary_op);
 200
 201 template <class ForwardIterator, class T>
 202     void
 203     replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
 204
 205 template <class ForwardIterator, class Predicate, class T>
 206     void
 207     replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
 208
 209 template <class InputIterator, class OutputIterator, class T>
 210     OutputIterator
 211     replace_copy(InputIterator first, InputIterator last, OutputIterator result,
 212                  const T& old_value, const T& new_value);
 213
 214 template <class InputIterator, class OutputIterator, class Predicate, class T>
 215     OutputIterator
 216     replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
 217
 218 template <class ForwardIterator, class T>
 219     void
 220     fill(ForwardIterator first, ForwardIterator last, const T& value);
 221
 222 template <class OutputIterator, class Size, class T>
 223     OutputIterator
 224     fill_n(OutputIterator first, Size n, const T& value);
 225
 226 template <class ForwardIterator, class Generator>
 227     void
 228     generate(ForwardIterator first, ForwardIterator last, Generator gen);
 229
 230 template <class OutputIterator, class Size, class Generator>
 231     OutputIterator
 232     generate_n(OutputIterator first, Size n, Generator gen);
 233
 234 template <class ForwardIterator, class T>
 235     ForwardIterator
 236     remove(ForwardIterator first, ForwardIterator last, const T& value);
 237
 238 template <class ForwardIterator, class Predicate>
 239     ForwardIterator
 240     remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
 241
 242 template <class InputIterator, class OutputIterator, class T>
 243     OutputIterator
 244     remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
 245
 246 template <class InputIterator, class OutputIterator, class Predicate>
 247     OutputIterator
 248     remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
 249
 250 template <class ForwardIterator>
 251     ForwardIterator
 252     unique(ForwardIterator first, ForwardIterator last);
 253
 254 template <class ForwardIterator, class BinaryPredicate>
 255     ForwardIterator
 256     unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
 257
 258 template <class InputIterator, class OutputIterator>
 259     OutputIterator
 260     unique_copy(InputIterator first, InputIterator last, OutputIterator result);
 261
 262 template <class InputIterator, class OutputIterator, class BinaryPredicate>
 263     OutputIterator
 264     unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
 265
 266 template <class BidirectionalIterator>
 267     void
 268     reverse(BidirectionalIterator first, BidirectionalIterator last);
 269
 270 template <class BidirectionalIterator, class OutputIterator>
 271     OutputIterator
 272     reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
 273
 274 template <class ForwardIterator>
 275     ForwardIterator
 276     rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
 277
 278 template <class ForwardIterator, class OutputIterator>
 279     OutputIterator
 280     rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
 281
 282 template <class RandomAccessIterator>
 283     void
 284     random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17
 285
 286 template <class RandomAccessIterator, class RandomNumberGenerator>
 287     void
 288     random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
 289                    RandomNumberGenerator& rand);  // deprecated in C++14, removed in C++17
 290
 291 template<class PopulationIterator, class SampleIterator,
 292          class Distance, class UniformRandomBitGenerator>
 293     SampleIterator sample(PopulationIterator first, PopulationIterator last,
 294                           SampleIterator out, Distance n,
 295                           UniformRandomBitGenerator&& g); // C++17
 296
 297 template<class RandomAccessIterator, class UniformRandomNumberGenerator>
 298     void shuffle(RandomAccessIterator first, RandomAccessIterator last,
 299                  UniformRandomNumberGenerator&& g);
 300
 301 template <class InputIterator, class Predicate>
 302     bool
 303     is_partitioned(InputIterator first, InputIterator last, Predicate pred);
 304
 305 template <class ForwardIterator, class Predicate>
 306     ForwardIterator
 307     partition(ForwardIterator first, ForwardIterator last, Predicate pred);
 308
 309 template <class InputIterator, class OutputIterator1,
 310           class OutputIterator2, class Predicate>
 311     pair<OutputIterator1, OutputIterator2>
 312     partition_copy(InputIterator first, InputIterator last,
 313                    OutputIterator1 out_true, OutputIterator2 out_false,
 314                    Predicate pred);
 315
 316 template <class ForwardIterator, class Predicate>
 317     ForwardIterator
 318     stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
 319
 320 template<class ForwardIterator, class Predicate>
 321     ForwardIterator
 322     partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
 323
 324 template <class ForwardIterator>
 325     bool
 326     is_sorted(ForwardIterator first, ForwardIterator last);
 327
 328 template <class ForwardIterator, class Compare>
 329     bool
 330     is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
 331
 332 template<class ForwardIterator>
 333     ForwardIterator
 334     is_sorted_until(ForwardIterator first, ForwardIterator last);
 335
 336 template <class ForwardIterator, class Compare>
 337     ForwardIterator
 338     is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
 339
 340 template <class RandomAccessIterator>
 341     void
 342     sort(RandomAccessIterator first, RandomAccessIterator last);
 343
 344 template <class RandomAccessIterator, class Compare>
 345     void
 346     sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 347
 348 template <class RandomAccessIterator>
 349     void
 350     stable_sort(RandomAccessIterator first, RandomAccessIterator last);
 351
 352 template <class RandomAccessIterator, class Compare>
 353     void
 354     stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 355
 356 template <class RandomAccessIterator>
 357     void
 358     partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
 359
 360 template <class RandomAccessIterator, class Compare>
 361     void
 362     partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
 363
 364 template <class InputIterator, class RandomAccessIterator>
 365     RandomAccessIterator
 366     partial_sort_copy(InputIterator first, InputIterator last,
 367                       RandomAccessIterator result_first, RandomAccessIterator result_last);
 368
 369 template <class InputIterator, class RandomAccessIterator, class Compare>
 370     RandomAccessIterator
 371     partial_sort_copy(InputIterator first, InputIterator last,
 372                       RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
 373
 374 template <class RandomAccessIterator>
 375     void
 376     nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
 377
 378 template <class RandomAccessIterator, class Compare>
 379     void
 380     nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
 381
 382 template <class ForwardIterator, class T>
 383     ForwardIterator
 384     lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
 385
 386 template <class ForwardIterator, class T, class Compare>
 387     ForwardIterator
 388     lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
 389
 390 template <class ForwardIterator, class T>
 391     ForwardIterator
 392     upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
 393
 394 template <class ForwardIterator, class T, class Compare>
 395     ForwardIterator
 396     upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
 397
 398 template <class ForwardIterator, class T>
 399     pair<ForwardIterator, ForwardIterator>
 400     equal_range(ForwardIterator first, ForwardIterator last, const T& value);
 401
 402 template <class ForwardIterator, class T, class Compare>
 403     pair<ForwardIterator, ForwardIterator>
 404     equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
 405
 406 template <class ForwardIterator, class T>
 407     bool
 408     binary_search(ForwardIterator first, ForwardIterator last, const T& value);
 409
 410 template <class ForwardIterator, class T, class Compare>
 411     bool
 412     binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
 413
 414 template <class InputIterator1, class InputIterator2, class OutputIterator>
 415     OutputIterator
 416     merge(InputIterator1 first1, InputIterator1 last1,
 417           InputIterator2 first2, InputIterator2 last2, OutputIterator result);
 418
 419 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
 420     OutputIterator
 421     merge(InputIterator1 first1, InputIterator1 last1,
 422           InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
 423
 424 template <class BidirectionalIterator>
 425     void
 426     inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
 427
 428 template <class BidirectionalIterator, class Compare>
 429     void
 430     inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
 431
 432 template <class InputIterator1, class InputIterator2>
 433     bool
 434     includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
 435
 436 template <class InputIterator1, class InputIterator2, class Compare>
 437     bool
 438     includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
 439
 440 template <class InputIterator1, class InputIterator2, class OutputIterator>
 441     OutputIterator
 442     set_union(InputIterator1 first1, InputIterator1 last1,
 443               InputIterator2 first2, InputIterator2 last2, OutputIterator result);
 444
 445 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
 446     OutputIterator
 447     set_union(InputIterator1 first1, InputIterator1 last1,
 448               InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
 449
 450 template <class InputIterator1, class InputIterator2, class OutputIterator>
 451     OutputIterator
 452     set_intersection(InputIterator1 first1, InputIterator1 last1,
 453                      InputIterator2 first2, InputIterator2 last2, OutputIterator result);
 454
 455 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
 456     OutputIterator
 457     set_intersection(InputIterator1 first1, InputIterator1 last1,
 458                      InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
 459
 460 template <class InputIterator1, class InputIterator2, class OutputIterator>
 461     OutputIterator
 462     set_difference(InputIterator1 first1, InputIterator1 last1,
 463                    InputIterator2 first2, InputIterator2 last2, OutputIterator result);
 464
 465 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
 466     OutputIterator
 467     set_difference(InputIterator1 first1, InputIterator1 last1,
 468                    InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
 469
 470 template <class InputIterator1, class InputIterator2, class OutputIterator>
 471     OutputIterator
 472     set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
 473                              InputIterator2 first2, InputIterator2 last2, OutputIterator result);
 474
 475 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
 476     OutputIterator
 477     set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
 478                              InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
 479
 480 template <class RandomAccessIterator>
 481     void
 482     push_heap(RandomAccessIterator first, RandomAccessIterator last);
 483
 484 template <class RandomAccessIterator, class Compare>
 485     void
 486     push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 487
 488 template <class RandomAccessIterator>
 489     void
 490     pop_heap(RandomAccessIterator first, RandomAccessIterator last);
 491
 492 template <class RandomAccessIterator, class Compare>
 493     void
 494     pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 495
 496 template <class RandomAccessIterator>
 497     void
 498     make_heap(RandomAccessIterator first, RandomAccessIterator last);
 499
 500 template <class RandomAccessIterator, class Compare>
 501     void
 502     make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 503
 504 template <class RandomAccessIterator>
 505     void
 506     sort_heap(RandomAccessIterator first, RandomAccessIterator last);
 507
 508 template <class RandomAccessIterator, class Compare>
 509     void
 510     sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 511
 512 template <class RandomAccessIterator>
 513     bool
 514     is_heap(RandomAccessIterator first, RandomAccessiterator last);
 515
 516 template <class RandomAccessIterator, class Compare>
 517     bool
 518     is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
 519
 520 template <class RandomAccessIterator>
 521     RandomAccessIterator
 522     is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
 523
 524 template <class RandomAccessIterator, class Compare>
 525     RandomAccessIterator
 526     is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
 527
 528 template <class ForwardIterator>
 529     ForwardIterator
 530     min_element(ForwardIterator first, ForwardIterator last);  // constexpr in C++14
 531
 532 template <class ForwardIterator, class Compare>
 533     ForwardIterator
 534     min_element(ForwardIterator first, ForwardIterator last, Compare comp);  // constexpr in C++14
 535
 536 template <class T>
 537     const T&
 538     min(const T& a, const T& b);  // constexpr in C++14
 539
 540 template <class T, class Compare>
 541     const T&
 542     min(const T& a, const T& b, Compare comp);  // constexpr in C++14
 543
 544 template<class T>
 545     T
 546     min(initializer_list<T> t);  // constexpr in C++14
 547
 548 template<class T, class Compare>
 549     T
 550     min(initializer_list<T> t, Compare comp);  // constexpr in C++14
 551
 552 template<class T>
 553     constexpr const T& clamp( const T& v, const T& lo, const T& hi );               // C++17
 554
 555 template<class T, class Compare>
 556     constexpr const T& clamp( const T& v, const T& lo, const T& hi, Compare comp ); // C++17
 557
 558 template <class ForwardIterator>
 559     ForwardIterator
 560     max_element(ForwardIterator first, ForwardIterator last);  // constexpr in C++14
 561
 562 template <class ForwardIterator, class Compare>
 563     ForwardIterator
 564     max_element(ForwardIterator first, ForwardIterator last, Compare comp);  // constexpr in C++14
 565
 566 template <class T>
 567     const T&
 568     max(const T& a, const T& b); // constexpr in C++14
 569
 570 template <class T, class Compare>
 571     const T&
 572     max(const T& a, const T& b, Compare comp);  // constexpr in C++14
 573
 574 template<class T>
 575     T
 576     max(initializer_list<T> t);  // constexpr in C++14
 577
 578 template<class T, class Compare>
 579     T
 580     max(initializer_list<T> t, Compare comp);  // constexpr in C++14
 581
 582 template<class ForwardIterator>
 583     pair<ForwardIterator, ForwardIterator>
 584     minmax_element(ForwardIterator first, ForwardIterator last);   // constexpr in C++14
 585
 586 template<class ForwardIterator, class Compare>
 587     pair<ForwardIterator, ForwardIterator>
 588     minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);   // constexpr in C++14
 589
 590 template<class T>
 591     pair<const T&, const T&>
 592     minmax(const T& a, const T& b);  // constexpr in C++14
 593
 594 template<class T, class Compare>
 595     pair<const T&, const T&>
 596     minmax(const T& a, const T& b, Compare comp);  // constexpr in C++14
 597
 598 template<class T>
 599     pair<T, T>
 600     minmax(initializer_list<T> t);  // constexpr in C++14
 601
 602 template<class T, class Compare>
 603     pair<T, T>
 604     minmax(initializer_list<T> t, Compare comp);  // constexpr in C++14
 605
 606 template <class InputIterator1, class InputIterator2>
 607     bool
 608     lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
 609
 610 template <class InputIterator1, class InputIterator2, class Compare>
 611     bool
 612     lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
 613                             InputIterator2 first2, InputIterator2 last2, Compare comp);
 614
 615 template <class BidirectionalIterator>
 616     bool
 617     next_permutation(BidirectionalIterator first, BidirectionalIterator last);
 618
 619 template <class BidirectionalIterator, class Compare>
 620     bool
 621     next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
 622
 623 template <class BidirectionalIterator>
 624     bool
 625     prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
 626
 627 template <class BidirectionalIterator, class Compare>
 628     bool
 629     prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
 630
 631 }  // std
 632
 633 */
 634
 635 #include <__config>
 636 #include <initializer_list>
 637 #include <type_traits>
 638 #include <cstring>
 639 #include <utility> // needed to provide swap_ranges.
 640 #include <memory>
 641 #include <iterator>
 642 #include <cstddef>
 643
 644 #if defined(__IBMCPP__)
 645 #include "support/ibm/support.h"
 646 #endif
 647 #if defined(_LIBCPP_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 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \
3030   || defined(_LIBCPP_BUILDING_LIBRARY)
3031 class _LIBCPP_TYPE_VIS __rs_default;
3032
3033 _LIBCPP_FUNC_VIS __rs_default __rs_get();
3034
3035 class _LIBCPP_TYPE_VIS __rs_default
3036 {
3037     static unsigned __c_;
3038
3039     __rs_default();
3040 public:
3041     typedef uint_fast32_t result_type;
3042
3043     static const result_type _Min = 0;
3044     static const result_type _Max = 0xFFFFFFFF;
3045
3046     __rs_default(const __rs_default&);
3047     ~__rs_default();
3048
3049     result_type operator()();
3050
3051     static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
3052     static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
3053
3054     friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
3055 };
3056
3057 _LIBCPP_FUNC_VIS __rs_default __rs_get();
3058
3059 template <class _RandomAccessIterator>
3060 void
3061 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
3062 {
3063     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3064     typedef uniform_int_distribution<ptrdiff_t> _Dp;
3065     typedef typename _Dp::param_type _Pp;
3066     difference_type __d = __last - __first;
3067     if (__d > 1)
3068     {
3069         _Dp __uid;
3070         __rs_default __g = __rs_get();
3071         for (--__last, --__d; __first < __last; ++__first, --__d)
3072         {
3073             difference_type __i = __uid(__g, _Pp(0, __d));
3074             if (__i != difference_type(0))
3075                 swap(*__first, *(__first + __i));
3076         }
3077     }
3078 }
3079
3080 template <class _RandomAccessIterator, class _RandomNumberGenerator>
3081 void
3082 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3083 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3084                _RandomNumberGenerator&& __rand)
3085 #else
3086                _RandomNumberGenerator& __rand)
3087 #endif
3088 {
3089     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3090     difference_type __d = __last - __first;
3091     if (__d > 1)
3092     {
3093         for (--__last; __first < __last; ++__first, --__d)
3094         {
3095             difference_type __i = __rand(__d);
3096             swap(*__first, *(__first + __i));
3097         }
3098     }
3099 }
3100 #endif
3101
3102 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3103           class _UniformRandomNumberGenerator>
3104 _LIBCPP_INLINE_VISIBILITY
3105 _SampleIterator __sample(_PopulationIterator __first,
3106                          _PopulationIterator __last, _SampleIterator __output,
3107                          _Distance __n,
3108                          _UniformRandomNumberGenerator & __g,
3109                          input_iterator_tag) {
3110
3111   _Distance __k = 0;
3112   for (; __first != __last && __k < __n; ++__first, (void)++__k)
3113     __output[__k] = *__first;
3114   _Distance __sz = __k;
3115   for (; __first != __last; ++__first, (void)++__k) {
3116     _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g);
3117     if (__r < __sz)
3118       __output[__r] = *__first;
3119   }
3120   return __output + _VSTD::min(__n, __k);
3121 }
3122
3123 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3124           class _UniformRandomNumberGenerator>
3125 _LIBCPP_INLINE_VISIBILITY
3126 _SampleIterator __sample(_PopulationIterator __first,
3127                          _PopulationIterator __last, _SampleIterator __output,
3128                          _Distance __n,
3129                          _UniformRandomNumberGenerator& __g,
3130                          forward_iterator_tag) {
3131   _Distance __unsampled_sz = _VSTD::distance(__first, __last);
3132   for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
3133     _Distance __r =
3134         _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g);
3135     if (__r < __n) {
3136       *__output++ = *__first;
3137       --__n;
3138     }
3139   }
3140   return __output;
3141 }
3142
3143 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3144           class _UniformRandomNumberGenerator>
3145 _LIBCPP_INLINE_VISIBILITY
3146 _SampleIterator __sample(_PopulationIterator __first,
3147                          _PopulationIterator __last, _SampleIterator __output,
3148                          _Distance __n, _UniformRandomNumberGenerator& __g) {
3149   typedef typename iterator_traits<_PopulationIterator>::iterator_category
3150         _PopCategory;
3151   typedef typename iterator_traits<_PopulationIterator>::difference_type
3152         _Difference;
3153   static_assert(__is_forward_iterator<_PopulationIterator>::value ||
3154                 __is_random_access_iterator<_SampleIterator>::value,
3155                 "SampleIterator must meet the requirements of RandomAccessIterator");
3156   typedef typename common_type<_Distance, _Difference>::type _CommonType;
3157   _LIBCPP_ASSERT(__n >= 0, "N must be a positive number.");
3158   return _VSTD::__sample(
3159       __first, __last, __output, _CommonType(__n),
3160       __g, _PopCategory());
3161 }
3162
3163 #if _LIBCPP_STD_VER > 14
3164 template <class _PopulationIterator, class _SampleIterator, class _Distance,
3165           class _UniformRandomNumberGenerator>
3166 inline _LIBCPP_INLINE_VISIBILITY
3167 _SampleIterator sample(_PopulationIterator __first,
3168                        _PopulationIterator __last, _SampleIterator __output,
3169                        _Distance __n, _UniformRandomNumberGenerator&& __g) {
3170     return _VSTD::__sample(__first, __last, __output, __n, __g);
3171 }
3172 #endif // _LIBCPP_STD_VER > 14
3173
3174 template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
3175     void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3176 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3177                  _UniformRandomNumberGenerator&& __g)
3178 #else
3179                  _UniformRandomNumberGenerator& __g)
3180 #endif
3181 {
3182     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3183     typedef uniform_int_distribution<ptrdiff_t> _Dp;
3184     typedef typename _Dp::param_type _Pp;
3185     difference_type __d = __last - __first;
3186     if (__d > 1)
3187     {
3188         _Dp __uid;
3189         for (--__last, --__d; __first < __last; ++__first, --__d)
3190         {
3191             difference_type __i = __uid(__g, _Pp(0, __d));
3192             if (__i != difference_type(0))
3193                 swap(*__first, *(__first + __i));
3194         }
3195     }
3196 }
3197
3198 template <class _InputIterator, class _Predicate>
3199 bool
3200 is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3201 {
3202     for (; __first != __last; ++__first)
3203         if (!__pred(*__first))
3204             break;
3205     if ( __first == __last )
3206         return true;
3207     ++__first;
3208     for (; __first != __last; ++__first)
3209         if (__pred(*__first))
3210             return false;
3211     return true;
3212 }
3213
3214 // partition
3215
3216 template <class _Predicate, class _ForwardIterator>
3217 _ForwardIterator
3218 __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
3219 {
3220     while (true)
3221     {
3222         if (__first == __last)
3223             return __first;
3224         if (!__pred(*__first))
3225             break;
3226         ++__first;
3227     }
3228     for (_ForwardIterator __p = __first; ++__p != __last;)
3229     {
3230         if (__pred(*__p))
3231         {
3232             swap(*__first, *__p);
3233             ++__first;
3234         }
3235     }
3236     return __first;
3237 }
3238
3239 template <class _Predicate, class _BidirectionalIterator>
3240 _BidirectionalIterator
3241 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3242             bidirectional_iterator_tag)
3243 {
3244     while (true)
3245     {
3246         while (true)
3247         {
3248             if (__first == __last)
3249                 return __first;
3250             if (!__pred(*__first))
3251                 break;
3252             ++__first;
3253         }
3254         do
3255         {
3256             if (__first == --__last)
3257                 return __first;
3258         } while (!__pred(*__last));
3259         swap(*__first, *__last);
3260         ++__first;
3261     }
3262 }
3263
3264 template <class _ForwardIterator, class _Predicate>
3265 inline _LIBCPP_INLINE_VISIBILITY
3266 _ForwardIterator
3267 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3268 {
3269     return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>
3270                             (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3271 }
3272
3273 // partition_copy
3274
3275 template <class _InputIterator, class _OutputIterator1,
3276           class _OutputIterator2, class _Predicate>
3277 pair<_OutputIterator1, _OutputIterator2>
3278 partition_copy(_InputIterator __first, _InputIterator __last,
3279                _OutputIterator1 __out_true, _OutputIterator2 __out_false,
3280                _Predicate __pred)
3281 {
3282     for (; __first != __last; ++__first)
3283     {
3284         if (__pred(*__first))
3285         {
3286             *__out_true = *__first;
3287             ++__out_true;
3288         }
3289         else
3290         {
3291             *__out_false = *__first;
3292             ++__out_false;
3293         }
3294     }
3295     return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
3296 }
3297
3298 // partition_point
3299
3300 template<class _ForwardIterator, class _Predicate>
3301 _ForwardIterator
3302 partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3303 {
3304     typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3305     difference_type __len = _VSTD::distance(__first, __last);
3306     while (__len != 0)
3307     {
3308         difference_type __l2 = __len / 2;
3309         _ForwardIterator __m = __first;
3310         _VSTD::advance(__m, __l2);
3311         if (__pred(*__m))
3312         {
3313             __first = ++__m;
3314             __len -= __l2 + 1;
3315         }
3316         else
3317             __len = __l2;
3318     }
3319     return __first;
3320 }
3321
3322 // stable_partition
3323
3324 template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
3325 _ForwardIterator
3326 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3327                    _Distance __len, _Pair __p, forward_iterator_tag __fit)
3328 {
3329     // *__first is known to be false
3330     // __len >= 1
3331     if (__len == 1)
3332         return __first;
3333     if (__len == 2)
3334     {
3335         _ForwardIterator __m = __first;
3336         if (__pred(*++__m))
3337         {
3338             swap(*__first, *__m);
3339             return __m;
3340         }
3341         return __first;
3342     }
3343     if (__len <= __p.second)
3344     {   // The buffer is big enough to use
3345         typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3346         __destruct_n __d(0);
3347         unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3348         // Move the falses into the temporary buffer, and the trues to the front of the line
3349         // Update __first to always point to the end of the trues
3350         value_type* __t = __p.first;
3351         ::new(__t) value_type(_VSTD::move(*__first));
3352         __d.__incr((value_type*)0);
3353         ++__t;
3354         _ForwardIterator __i = __first;
3355         while (++__i != __last)
3356         {
3357             if (__pred(*__i))
3358             {
3359                 *__first = _VSTD::move(*__i);
3360                 ++__first;
3361             }
3362             else
3363             {
3364                 ::new(__t) value_type(_VSTD::move(*__i));
3365                 __d.__incr((value_type*)0);
3366                 ++__t;
3367             }
3368         }
3369         // All trues now at start of range, all falses in buffer
3370         // Move falses back into range, but don't mess up __first which points to first false
3371         __i = __first;
3372         for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3373             *__i = _VSTD::move(*__t2);
3374         // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3375         return __first;
3376     }
3377     // Else not enough buffer, do in place
3378     // __len >= 3
3379     _ForwardIterator __m = __first;
3380     _Distance __len2 = __len / 2;  // __len2 >= 2
3381     _VSTD::advance(__m, __len2);
3382     // recurse on [__first, __m), *__first know to be false
3383     // F?????????????????
3384     // f       m         l
3385     typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3386     _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
3387     // TTTFFFFF??????????
3388     // f  ff   m         l
3389     // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3390     _ForwardIterator __m1 = __m;
3391     _ForwardIterator __second_false = __last;
3392     _Distance __len_half = __len - __len2;
3393     while (__pred(*__m1))
3394     {
3395         if (++__m1 == __last)
3396             goto __second_half_done;
3397         --__len_half;
3398     }
3399     // TTTFFFFFTTTF??????
3400     // f  ff   m  m1     l
3401     __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
3402 __second_half_done:
3403     // TTTFFFFFTTTTTFFFFF
3404     // f  ff   m    sf   l
3405     return _VSTD::rotate(__first_false, __m, __second_false);
3406     // TTTTTTTTFFFFFFFFFF
3407     //         |
3408 }
3409
3410 struct __return_temporary_buffer
3411 {
3412     template <class _Tp>
3413     _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}
3414 };
3415
3416 template <class _Predicate, class _ForwardIterator>
3417 _ForwardIterator
3418 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3419                    forward_iterator_tag)
3420 {
3421     const unsigned __alloc_limit = 3;  // might want to make this a function of trivial assignment
3422     // Either prove all true and return __first or point to first false
3423     while (true)
3424     {
3425         if (__first == __last)
3426             return __first;
3427         if (!__pred(*__first))
3428             break;
3429         ++__first;
3430     }
3431     // We now have a reduced range [__first, __last)
3432     // *__first is known to be false
3433     typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
3434     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3435     difference_type __len = _VSTD::distance(__first, __last);
3436     pair<value_type*, ptrdiff_t> __p(0, 0);
3437     unique_ptr<value_type, __return_temporary_buffer> __h;
3438     if (__len >= __alloc_limit)
3439     {
3440         __p = _VSTD::get_temporary_buffer<value_type>(__len);
3441         __h.reset(__p.first);
3442     }
3443     return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3444                              (__first, __last, __pred, __len, __p, forward_iterator_tag());
3445 }
3446
3447 template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
3448 _BidirectionalIterator
3449 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3450                    _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
3451 {
3452     // *__first is known to be false
3453     // *__last is known to be true
3454     // __len >= 2
3455     if (__len == 2)
3456     {
3457         swap(*__first, *__last);
3458         return __last;
3459     }
3460     if (__len == 3)
3461     {
3462         _BidirectionalIterator __m = __first;
3463         if (__pred(*++__m))
3464         {
3465             swap(*__first, *__m);
3466             swap(*__m, *__last);
3467             return __last;
3468         }
3469         swap(*__m, *__last);
3470         swap(*__first, *__m);
3471         return __m;
3472     }
3473     if (__len <= __p.second)
3474     {   // The buffer is big enough to use
3475         typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3476         __destruct_n __d(0);
3477         unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
3478         // Move the falses into the temporary buffer, and the trues to the front of the line
3479         // Update __first to always point to the end of the trues
3480         value_type* __t = __p.first;
3481         ::new(__t) value_type(_VSTD::move(*__first));
3482         __d.__incr((value_type*)0);
3483         ++__t;
3484         _BidirectionalIterator __i = __first;
3485         while (++__i != __last)
3486         {
3487             if (__pred(*__i))
3488             {
3489                 *__first = _VSTD::move(*__i);
3490                 ++__first;
3491             }
3492             else
3493             {
3494                 ::new(__t) value_type(_VSTD::move(*__i));
3495                 __d.__incr((value_type*)0);
3496                 ++__t;
3497             }
3498         }
3499         // move *__last, known to be true
3500         *__first = _VSTD::move(*__i);
3501         __i = ++__first;
3502         // All trues now at start of range, all falses in buffer
3503         // Move falses back into range, but don't mess up __first which points to first false
3504         for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i)
3505             *__i = _VSTD::move(*__t2);
3506         // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
3507         return __first;
3508     }
3509     // Else not enough buffer, do in place
3510     // __len >= 4
3511     _BidirectionalIterator __m = __first;
3512     _Distance __len2 = __len / 2;  // __len2 >= 2
3513     _VSTD::advance(__m, __len2);
3514     // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
3515     // F????????????????T
3516     // f       m        l
3517     _BidirectionalIterator __m1 = __m;
3518     _BidirectionalIterator __first_false = __first;
3519     _Distance __len_half = __len2;
3520     while (!__pred(*--__m1))
3521     {
3522         if (__m1 == __first)
3523             goto __first_half_done;
3524         --__len_half;
3525     }
3526     // F???TFFF?????????T
3527     // f   m1  m        l
3528     typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
3529     __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3530 __first_half_done:
3531     // TTTFFFFF?????????T
3532     // f  ff   m        l
3533     // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
3534     __m1 = __m;
3535     _BidirectionalIterator __second_false = __last;
3536     ++__second_false;
3537     __len_half = __len - __len2;
3538     while (__pred(*__m1))
3539     {
3540         if (++__m1 == __last)
3541             goto __second_half_done;
3542         --__len_half;
3543     }
3544     // TTTFFFFFTTTF?????T
3545     // f  ff   m  m1    l
3546     __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
3547 __second_half_done:
3548     // TTTFFFFFTTTTTFFFFF
3549     // f  ff   m    sf  l
3550     return _VSTD::rotate(__first_false, __m, __second_false);
3551     // TTTTTTTTFFFFFFFFFF
3552     //         |
3553 }
3554
3555 template <class _Predicate, class _BidirectionalIterator>
3556 _BidirectionalIterator
3557 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3558                    bidirectional_iterator_tag)
3559 {
3560     typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
3561     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
3562     const difference_type __alloc_limit = 4;  // might want to make this a function of trivial assignment
3563     // Either prove all true and return __first or point to first false
3564     while (true)
3565     {
3566         if (__first == __last)
3567             return __first;
3568         if (!__pred(*__first))
3569             break;
3570         ++__first;
3571     }
3572     // __first points to first false, everything prior to __first is already set.
3573     // Either prove [__first, __last) is all false and return __first, or point __last to last true
3574     do
3575     {
3576         if (__first == --__last)
3577             return __first;
3578     } while (!__pred(*__last));
3579     // We now have a reduced range [__first, __last]
3580     // *__first is known to be false
3581     // *__last is known to be true
3582     // __len >= 2
3583     difference_type __len = _VSTD::distance(__first, __last) + 1;
3584     pair<value_type*, ptrdiff_t> __p(0, 0);
3585     unique_ptr<value_type, __return_temporary_buffer> __h;
3586     if (__len >= __alloc_limit)
3587     {
3588         __p = _VSTD::get_temporary_buffer<value_type>(__len);
3589         __h.reset(__p.first);
3590     }
3591     return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3592                              (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3593 }
3594
3595 template <class _ForwardIterator, class _Predicate>
3596 inline _LIBCPP_INLINE_VISIBILITY
3597 _ForwardIterator
3598 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3599 {
3600     return __stable_partition<typename add_lvalue_reference<_Predicate>::type>
3601                              (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3602 }
3603
3604 // is_sorted_until
3605
3606 template <class _ForwardIterator, class _Compare>
3607 _ForwardIterator
3608 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3609 {
3610     if (__first != __last)
3611     {
3612         _ForwardIterator __i = __first;
3613         while (++__i != __last)
3614         {
3615             if (__comp(*__i, *__first))
3616                 return __i;
3617             __first = __i;
3618         }
3619     }
3620     return __last;
3621 }
3622
3623 template<class _ForwardIterator>
3624 inline _LIBCPP_INLINE_VISIBILITY
3625 _ForwardIterator
3626 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3627 {
3628     return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3629 }
3630
3631 // is_sorted
3632
3633 template <class _ForwardIterator, class _Compare>
3634 inline _LIBCPP_INLINE_VISIBILITY
3635 bool
3636 is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3637 {
3638     return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
3639 }
3640
3641 template<class _ForwardIterator>
3642 inline _LIBCPP_INLINE_VISIBILITY
3643 bool
3644 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3645 {
3646     return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
3647 }
3648
3649 // sort
3650
3651 // stable, 2-3 compares, 0-2 swaps
3652
3653 template <class _Compare, class _ForwardIterator>
3654 unsigned
3655 __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
3656 {
3657     unsigned __r = 0;
3658     if (!__c(*__y, *__x))          // if x <= y
3659     {
3660         if (!__c(*__z, *__y))      // if y <= z
3661             return __r;            // x <= y && y <= z
3662                                    // x <= y && y > z
3663         swap(*__y, *__z);          // x <= z && y < z
3664         __r = 1;
3665         if (__c(*__y, *__x))       // if x > y
3666         {
3667             swap(*__x, *__y);      // x < y && y <= z
3668             __r = 2;
3669         }
3670         return __r;                // x <= y && y < z
3671     }
3672     if (__c(*__z, *__y))           // x > y, if y > z
3673     {
3674         swap(*__x, *__z);          // x < y && y < z
3675         __r = 1;
3676         return __r;
3677     }
3678     swap(*__x, *__y);              // x > y && y <= z
3679     __r = 1;                       // x < y && x <= z
3680     if (__c(*__z, *__y))           // if y > z
3681     {
3682         swap(*__y, *__z);          // x <= y && y < z
3683         __r = 2;
3684     }
3685     return __r;
3686 }                                  // x <= y && y <= z
3687
3688 // stable, 3-6 compares, 0-5 swaps
3689
3690 template <class _Compare, class _ForwardIterator>
3691 unsigned
3692 __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3693             _ForwardIterator __x4, _Compare __c)
3694 {
3695     unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
3696     if (__c(*__x4, *__x3))
3697     {
3698         swap(*__x3, *__x4);
3699         ++__r;
3700         if (__c(*__x3, *__x2))
3701         {
3702             swap(*__x2, *__x3);
3703             ++__r;
3704             if (__c(*__x2, *__x1))
3705             {
3706                 swap(*__x1, *__x2);
3707                 ++__r;
3708             }
3709         }
3710     }
3711     return __r;
3712 }
3713
3714 // stable, 4-10 compares, 0-9 swaps
3715
3716 template <class _Compare, class _ForwardIterator>
3717 unsigned
3718 __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
3719             _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
3720 {
3721     unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
3722     if (__c(*__x5, *__x4))
3723     {
3724         swap(*__x4, *__x5);
3725         ++__r;
3726         if (__c(*__x4, *__x3))
3727         {
3728             swap(*__x3, *__x4);
3729             ++__r;
3730             if (__c(*__x3, *__x2))
3731             {
3732                 swap(*__x2, *__x3);
3733                 ++__r;
3734                 if (__c(*__x2, *__x1))
3735                 {
3736                     swap(*__x1, *__x2);
3737                     ++__r;
3738                 }
3739             }
3740         }
3741     }
3742     return __r;
3743 }
3744
3745 // Assumes size > 0
3746 template <class _Compare, class _BirdirectionalIterator>
3747 void
3748 __selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3749 {
3750     _BirdirectionalIterator __lm1 = __last;
3751     for (--__lm1; __first != __lm1; ++__first)
3752     {
3753         _BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator,
3754                                                         typename add_lvalue_reference<_Compare>::type>
3755                                                        (__first, __last, __comp);
3756         if (__i != __first)
3757             swap(*__first, *__i);
3758     }
3759 }
3760
3761 template <class _Compare, class _BirdirectionalIterator>
3762 void
3763 __insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3764 {
3765     typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3766     if (__first != __last)
3767     {
3768         _BirdirectionalIterator __i = __first;
3769         for (++__i; __i != __last; ++__i)
3770         {
3771             _BirdirectionalIterator __j = __i;
3772             value_type __t(_VSTD::move(*__j));
3773             for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t,  *--__k); --__j)
3774                 *__j = _VSTD::move(*__k);
3775             *__j = _VSTD::move(__t);
3776         }
3777     }
3778 }
3779
3780 template <class _Compare, class _RandomAccessIterator>
3781 void
3782 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3783 {
3784     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3785     _RandomAccessIterator __j = __first+2;
3786     __sort3<_Compare>(__first, __first+1, __j, __comp);
3787     for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3788     {
3789         if (__comp(*__i, *__j))
3790         {
3791             value_type __t(_VSTD::move(*__i));
3792             _RandomAccessIterator __k = __j;
3793             __j = __i;
3794             do
3795             {
3796                 *__j = _VSTD::move(*__k);
3797                 __j = __k;
3798             } while (__j != __first && __comp(__t, *--__k));
3799             *__j = _VSTD::move(__t);
3800         }
3801         __j = __i;
3802     }
3803 }
3804
3805 template <class _Compare, class _RandomAccessIterator>
3806 bool
3807 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3808 {
3809     switch (__last - __first)
3810     {
3811     case 0:
3812     case 1:
3813         return true;
3814     case 2:
3815         if (__comp(*--__last, *__first))
3816             swap(*__first, *__last);
3817         return true;
3818     case 3:
3819         _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3820         return true;
3821     case 4:
3822         _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3823         return true;
3824     case 5:
3825         _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3826         return true;
3827     }
3828     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3829     _RandomAccessIterator __j = __first+2;
3830     __sort3<_Compare>(__first, __first+1, __j, __comp);
3831     const unsigned __limit = 8;
3832     unsigned __count = 0;
3833     for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
3834     {
3835         if (__comp(*__i, *__j))
3836         {
3837             value_type __t(_VSTD::move(*__i));
3838             _RandomAccessIterator __k = __j;
3839             __j = __i;
3840             do
3841             {
3842                 *__j = _VSTD::move(*__k);
3843                 __j = __k;
3844             } while (__j != __first && __comp(__t, *--__k));
3845             *__j = _VSTD::move(__t);
3846             if (++__count == __limit)
3847                 return ++__i == __last;
3848         }
3849         __j = __i;
3850     }
3851     return true;
3852 }
3853
3854 template <class _Compare, class _BirdirectionalIterator>
3855 void
3856 __insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1,
3857                       typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp)
3858 {
3859     typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type;
3860     if (__first1 != __last1)
3861     {
3862         __destruct_n __d(0);
3863         unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
3864         value_type* __last2 = __first2;
3865         ::new(__last2) value_type(_VSTD::move(*__first1));
3866         __d.__incr((value_type*)0);
3867         for (++__last2; ++__first1 != __last1; ++__last2)
3868         {
3869             value_type* __j2 = __last2;
3870             value_type* __i2 = __j2;
3871             if (__comp(*__first1, *--__i2))
3872             {
3873                 ::new(__j2) value_type(_VSTD::move(*__i2));
3874                 __d.__incr((value_type*)0);
3875                 for (--__j2; __i2 != __first2 && __comp(*__first1,  *--__i2); --__j2)
3876                     *__j2 = _VSTD::move(*__i2);
3877                 *__j2 = _VSTD::move(*__first1);
3878             }
3879             else
3880             {
3881                 ::new(__j2) value_type(_VSTD::move(*__first1));
3882                 __d.__incr((value_type*)0);
3883             }
3884         }
3885         __h.release();
3886     }
3887 }
3888
3889 template <class _Compare, class _RandomAccessIterator>
3890 void
3891 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3892 {
3893     // _Compare is known to be a reference type
3894     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
3895     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
3896     const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
3897                                     is_trivially_copy_assignable<value_type>::value ? 30 : 6;
3898     while (true)
3899     {
3900     __restart:
3901         difference_type __len = __last - __first;
3902         switch (__len)
3903         {
3904         case 0:
3905         case 1:
3906             return;
3907         case 2:
3908             if (__comp(*--__last, *__first))
3909                 swap(*__first, *__last);
3910             return;
3911         case 3:
3912             _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3913             return;
3914         case 4:
3915             _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3916             return;
3917         case 5:
3918             _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3919             return;
3920         }
3921         if (__len <= __limit)
3922         {
3923             _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
3924             return;
3925         }
3926         // __len > 5
3927         _RandomAccessIterator __m = __first;
3928         _RandomAccessIterator __lm1 = __last;
3929         --__lm1;
3930         unsigned __n_swaps;
3931         {
3932         difference_type __delta;
3933         if (__len >= 1000)
3934         {
3935             __delta = __len/2;
3936             __m += __delta;
3937             __delta /= 2;
3938             __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
3939         }
3940         else
3941         {
3942             __delta = __len/2;
3943             __m += __delta;
3944             __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
3945         }
3946         }
3947         // *__m is median
3948         // partition [__first, __m) < *__m and *__m <= [__m, __last)
3949         // (this inhibits tossing elements equivalent to __m around unnecessarily)
3950         _RandomAccessIterator __i = __first;
3951         _RandomAccessIterator __j = __lm1;
3952         // j points beyond range to be tested, *__m is known to be <= *__lm1
3953         // The search going up is known to be guarded but the search coming down isn't.
3954         // Prime the downward search with a guard.
3955         if (!__comp(*__i, *__m))  // if *__first == *__m
3956         {
3957             // *__first == *__m, *__first doesn't go in first part
3958             // manually guard downward moving __j against __i
3959             while (true)
3960             {
3961                 if (__i == --__j)
3962                 {
3963                     // *__first == *__m, *__m <= all other elements
3964                     // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
3965                     ++__i;  // __first + 1
3966                     __j = __last;
3967                     if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
3968                     {
3969                         while (true)
3970                         {
3971                             if (__i == __j)
3972                                 return;  // [__first, __last) all equivalent elements
3973                             if (__comp(*__first, *__i))
3974                             {
3975                                 swap(*__i, *__j);
3976                                 ++__n_swaps;
3977                                 ++__i;
3978                                 break;
3979                             }
3980                             ++__i;
3981                         }
3982                     }
3983                     // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
3984                     if (__i == __j)
3985                         return;
3986                     while (true)
3987                     {
3988                         while (!__comp(*__first, *__i))
3989                             ++__i;
3990                         while (__comp(*__first, *--__j))
3991                             ;
3992                         if (__i >= __j)
3993                             break;
3994                         swap(*__i, *__j);
3995                         ++__n_swaps;
3996                         ++__i;
3997                     }
3998                     // [__first, __i) == *__first and *__first < [__i, __last)
3999                     // The first part is sorted, sort the secod part
4000                     // _VSTD::__sort<_Compare>(__i, __last, __comp);
4001                     __first = __i;
4002                     goto __restart;
4003                 }
4004                 if (__comp(*__j, *__m))
4005                 {
4006                     swap(*__i, *__j);
4007                     ++__n_swaps;
4008                     break;  // found guard for downward moving __j, now use unguarded partition
4009                 }
4010             }
4011         }
4012         // It is known that *__i < *__m
4013         ++__i;
4014         // j points beyond range to be tested, *__m is known to be <= *__lm1
4015         // if not yet partitioned...
4016         if (__i < __j)
4017         {
4018             // known that *(__i - 1) < *__m
4019             // known that __i <= __m
4020             while (true)
4021             {
4022                 // __m still guards upward moving __i
4023                 while (__comp(*__i, *__m))
4024                     ++__i;
4025                 // It is now known that a guard exists for downward moving __j
4026                 while (!__comp(*--__j, *__m))
4027                     ;
4028                 if (__i > __j)
4029                     break;
4030                 swap(*__i, *__j);
4031                 ++__n_swaps;
4032                 // It is known that __m != __j
4033                 // If __m just moved, follow it
4034                 if (__m == __i)
4035                     __m = __j;
4036                 ++__i;
4037             }
4038         }
4039         // [__first, __i) < *__m and *__m <= [__i, __last)
4040         if (__i != __m && __comp(*__m, *__i))
4041         {
4042             swap(*__i, *__m);
4043             ++__n_swaps;
4044         }
4045         // [__first, __i) < *__i and *__i <= [__i+1, __last)
4046         // If we were given a perfect partition, see if insertion sort is quick...
4047         if (__n_swaps == 0)
4048         {
4049             bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
4050             if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
4051             {
4052                 if (__fs)
4053                     return;
4054                 __last = __i;
4055                 continue;
4056             }
4057             else
4058             {
4059                 if (__fs)
4060                 {
4061                     __first = ++__i;
4062                     continue;
4063                 }
4064             }
4065         }
4066         // sort smaller range with recursive call and larger with tail recursion elimination
4067         if (__i - __first < __last - __i)
4068         {
4069             _VSTD::__sort<_Compare>(__first, __i, __comp);
4070             // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4071             __first = ++__i;
4072         }
4073         else
4074         {
4075             _VSTD::__sort<_Compare>(__i+1, __last, __comp);
4076             // _VSTD::__sort<_Compare>(__first, __i, __comp);
4077             __last = __i;
4078         }
4079     }
4080 }
4081
4082 // This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
4083 template <class _RandomAccessIterator, class _Compare>
4084 inline _LIBCPP_INLINE_VISIBILITY
4085 void
4086 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4087 {
4088 #ifdef _LIBCPP_DEBUG
4089     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4090     __debug_less<_Compare> __c(__comp);
4091     __sort<_Comp_ref>(__first, __last, __c);
4092 #else  // _LIBCPP_DEBUG
4093     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4094     __sort<_Comp_ref>(__first, __last, __comp);
4095 #endif  // _LIBCPP_DEBUG
4096 }
4097
4098 template <class _RandomAccessIterator>
4099 inline _LIBCPP_INLINE_VISIBILITY
4100 void
4101 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4102 {
4103     _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4104 }
4105
4106 template <class _Tp>
4107 inline _LIBCPP_INLINE_VISIBILITY
4108 void
4109 sort(_Tp** __first, _Tp** __last)
4110 {
4111     _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
4112 }
4113
4114 template <class _Tp>
4115 inline _LIBCPP_INLINE_VISIBILITY
4116 void
4117 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
4118 {
4119     _VSTD::sort(__first.base(), __last.base());
4120 }
4121
4122 template <class _Tp, class _Compare>
4123 inline _LIBCPP_INLINE_VISIBILITY
4124 void
4125 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
4126 {
4127     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4128     _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
4129 }
4130
4131 #ifdef _LIBCPP_MSVC
4132 #pragma warning( push )
4133 #pragma warning( disable: 4231)
4134 #endif // _LIBCPP_MSVC
4135 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
4136 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4137 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4138 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4139 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))
4140 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4141 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&))
4142 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4143 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&))
4144 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4145 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4146 _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>&))
4147 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&))
4148 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&))
4149 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4150
4151 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))
4152 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
4153 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
4154 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
4155 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))
4156 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
4157 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&))
4158 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
4159 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&))
4160 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
4161 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
4162 _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>&))
4163 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&))
4164 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&))
4165 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
4166
4167 _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>&))
4168 #ifdef _LIBCPP_MSVC
4169 #pragma warning( pop )
4170 #endif  // _LIBCPP_MSVC
4171
4172 // lower_bound
4173
4174 template <class _Compare, class _ForwardIterator, class _Tp>
4175 _ForwardIterator
4176 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4177 {
4178     typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4179     difference_type __len = _VSTD::distance(__first, __last);
4180     while (__len != 0)
4181     {
4182         difference_type __l2 = __len / 2;
4183         _ForwardIterator __m = __first;
4184         _VSTD::advance(__m, __l2);
4185         if (__comp(*__m, __value_))
4186         {
4187             __first = ++__m;
4188             __len -= __l2 + 1;
4189         }
4190         else
4191             __len = __l2;
4192     }
4193     return __first;
4194 }
4195
4196 template <class _ForwardIterator, class _Tp, class _Compare>
4197 inline _LIBCPP_INLINE_VISIBILITY
4198 _ForwardIterator
4199 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4200 {
4201 #ifdef _LIBCPP_DEBUG
4202     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4203     __debug_less<_Compare> __c(__comp);
4204     return __lower_bound<_Comp_ref>(__first, __last, __value_, __c);
4205 #else  // _LIBCPP_DEBUG
4206     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4207     return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp);
4208 #endif  // _LIBCPP_DEBUG
4209 }
4210
4211 template <class _ForwardIterator, class _Tp>
4212 inline _LIBCPP_INLINE_VISIBILITY
4213 _ForwardIterator
4214 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4215 {
4216     return _VSTD::lower_bound(__first, __last, __value_,
4217                              __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4218 }
4219
4220 // upper_bound
4221
4222 template <class _Compare, class _ForwardIterator, class _Tp>
4223 _ForwardIterator
4224 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4225 {
4226     typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4227     difference_type __len = _VSTD::distance(__first, __last);
4228     while (__len != 0)
4229     {
4230         difference_type __l2 = __len / 2;
4231         _ForwardIterator __m = __first;
4232         _VSTD::advance(__m, __l2);
4233         if (__comp(__value_, *__m))
4234             __len = __l2;
4235         else
4236         {
4237             __first = ++__m;
4238             __len -= __l2 + 1;
4239         }
4240     }
4241     return __first;
4242 }
4243
4244 template <class _ForwardIterator, class _Tp, class _Compare>
4245 inline _LIBCPP_INLINE_VISIBILITY
4246 _ForwardIterator
4247 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4248 {
4249 #ifdef _LIBCPP_DEBUG
4250     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4251     __debug_less<_Compare> __c(__comp);
4252     return __upper_bound<_Comp_ref>(__first, __last, __value_, __c);
4253 #else  // _LIBCPP_DEBUG
4254     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4255     return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp);
4256 #endif  // _LIBCPP_DEBUG
4257 }
4258
4259 template <class _ForwardIterator, class _Tp>
4260 inline _LIBCPP_INLINE_VISIBILITY
4261 _ForwardIterator
4262 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4263 {
4264     return _VSTD::upper_bound(__first, __last, __value_,
4265                              __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
4266 }
4267
4268 // equal_range
4269
4270 template <class _Compare, class _ForwardIterator, class _Tp>
4271 pair<_ForwardIterator, _ForwardIterator>
4272 __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4273 {
4274     typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
4275     difference_type __len = _VSTD::distance(__first, __last);
4276     while (__len != 0)
4277     {
4278         difference_type __l2 = __len / 2;
4279         _ForwardIterator __m = __first;
4280         _VSTD::advance(__m, __l2);
4281         if (__comp(*__m, __value_))
4282         {
4283             __first = ++__m;
4284             __len -= __l2 + 1;
4285         }
4286         else if (__comp(__value_, *__m))
4287         {
4288             __last = __m;
4289             __len = __l2;
4290         }
4291         else
4292         {
4293             _ForwardIterator __mp1 = __m;
4294             return pair<_ForwardIterator, _ForwardIterator>
4295                    (
4296                       __lower_bound<_Compare>(__first, __m, __value_, __comp),
4297                       __upper_bound<_Compare>(++__mp1, __last, __value_, __comp)
4298                    );
4299         }
4300     }
4301     return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4302 }
4303
4304 template <class _ForwardIterator, class _Tp, class _Compare>
4305 inline _LIBCPP_INLINE_VISIBILITY
4306 pair<_ForwardIterator, _ForwardIterator>
4307 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4308 {
4309 #ifdef _LIBCPP_DEBUG
4310     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4311     __debug_less<_Compare> __c(__comp);
4312     return __equal_range<_Comp_ref>(__first, __last, __value_, __c);
4313 #else  // _LIBCPP_DEBUG
4314     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4315     return __equal_range<_Comp_ref>(__first, __last, __value_, __comp);
4316 #endif  // _LIBCPP_DEBUG
4317 }
4318
4319 template <class _ForwardIterator, class _Tp>
4320 inline _LIBCPP_INLINE_VISIBILITY
4321 pair<_ForwardIterator, _ForwardIterator>
4322 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4323 {
4324     return _VSTD::equal_range(__first, __last, __value_,
4325                              __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4326 }
4327
4328 // binary_search
4329
4330 template <class _Compare, class _ForwardIterator, class _Tp>
4331 inline _LIBCPP_INLINE_VISIBILITY
4332 bool
4333 __binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4334 {
4335     __first = __lower_bound<_Compare>(__first, __last, __value_, __comp);
4336     return __first != __last && !__comp(__value_, *__first);
4337 }
4338
4339 template <class _ForwardIterator, class _Tp, class _Compare>
4340 inline _LIBCPP_INLINE_VISIBILITY
4341 bool
4342 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4343 {
4344 #ifdef _LIBCPP_DEBUG
4345     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4346     __debug_less<_Compare> __c(__comp);
4347     return __binary_search<_Comp_ref>(__first, __last, __value_, __c);
4348 #else  // _LIBCPP_DEBUG
4349     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4350     return __binary_search<_Comp_ref>(__first, __last, __value_, __comp);
4351 #endif  // _LIBCPP_DEBUG
4352 }
4353
4354 template <class _ForwardIterator, class _Tp>
4355 inline _LIBCPP_INLINE_VISIBILITY
4356 bool
4357 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4358 {
4359     return _VSTD::binary_search(__first, __last, __value_,
4360                              __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
4361 }
4362
4363 // merge
4364
4365 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4366 _OutputIterator
4367 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4368         _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4369 {
4370     for (; __first1 != __last1; ++__result)
4371     {
4372         if (__first2 == __last2)
4373             return _VSTD::copy(__first1, __last1, __result);
4374         if (__comp(*__first2, *__first1))
4375         {
4376             *__result = *__first2;
4377             ++__first2;
4378         }
4379         else
4380         {
4381             *__result = *__first1;
4382             ++__first1;
4383         }
4384     }
4385     return _VSTD::copy(__first2, __last2, __result);
4386 }
4387
4388 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
4389 inline _LIBCPP_INLINE_VISIBILITY
4390 _OutputIterator
4391 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4392       _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
4393 {
4394 #ifdef _LIBCPP_DEBUG
4395     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4396     __debug_less<_Compare> __c(__comp);
4397     return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
4398 #else  // _LIBCPP_DEBUG
4399     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4400     return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
4401 #endif  // _LIBCPP_DEBUG
4402 }
4403
4404 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
4405 inline _LIBCPP_INLINE_VISIBILITY
4406 _OutputIterator
4407 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4408       _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
4409 {
4410     typedef typename iterator_traits<_InputIterator1>::value_type __v1;
4411     typedef typename iterator_traits<_InputIterator2>::value_type __v2;
4412     return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
4413 }
4414
4415 // inplace_merge
4416
4417 template <class _Compare, class _InputIterator1, class _InputIterator2,
4418           class _OutputIterator>
4419 void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
4420                           _InputIterator2 __first2, _InputIterator2 __last2,
4421                           _OutputIterator __result, _Compare __comp)
4422 {
4423     for (; __first1 != __last1; ++__result)
4424     {
4425         if (__first2 == __last2)
4426         {
4427             _VSTD::move(__first1, __last1, __result);
4428             return;
4429         }
4430
4431         if (__comp(*__first2, *__first1))
4432         {
4433             *__result = _VSTD::move(*__first2);
4434             ++__first2;
4435         }
4436         else
4437         {
4438             *__result = _VSTD::move(*__first1);
4439             ++__first1;
4440         }
4441     }
4442     // __first2 through __last2 are already in the right spot.
4443 }
4444
4445 template <class _Compare, class _BidirectionalIterator>
4446 void
4447 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4448                 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4449                                  typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4450                 typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
4451 {
4452     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4453     __destruct_n __d(0);
4454     unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4455     if (__len1 <= __len2)
4456     {
4457         value_type* __p = __buff;
4458         for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4459             ::new(__p) value_type(_VSTD::move(*__i));
4460         __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);
4461     }
4462     else
4463     {
4464         value_type* __p = __buff;
4465         for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, ++__p)
4466             ::new(__p) value_type(_VSTD::move(*__i));
4467         typedef reverse_iterator<_BidirectionalIterator> _RBi;
4468         typedef reverse_iterator<value_type*> _Rv;
4469         __half_inplace_merge(_Rv(__p), _Rv(__buff),
4470                              _RBi(__middle), _RBi(__first),
4471                              _RBi(__last), __negate<_Compare>(__comp));
4472     }
4473 }
4474
4475 template <class _Compare, class _BidirectionalIterator>
4476 void
4477 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4478                 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
4479                                  typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
4480                 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
4481 {
4482     typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4483     while (true)
4484     {
4485         // if __middle == __last, we're done
4486         if (__len2 == 0)
4487             return;
4488         if (__len1 <= __buff_size || __len2 <= __buff_size)
4489             return __buffered_inplace_merge<_Compare>
4490                    (__first, __middle, __last, __comp, __len1, __len2, __buff);
4491         // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
4492         for (; true; ++__first, (void) --__len1)
4493         {
4494             if (__len1 == 0)
4495                 return;
4496             if (__comp(*__middle, *__first))
4497                 break;
4498         }
4499         // __first < __middle < __last
4500         // *__first > *__middle
4501         // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4502         //     all elements in:
4503         //         [__first, __m1)  <= [__middle, __m2)
4504         //         [__middle, __m2) <  [__m1, __middle)
4505         //         [__m1, __middle) <= [__m2, __last)
4506         //     and __m1 or __m2 is in the middle of its range
4507         _BidirectionalIterator __m1;  // "median" of [__first, __middle)
4508         _BidirectionalIterator __m2;  // "median" of [__middle, __last)
4509         difference_type __len11;      // distance(__first, __m1)
4510         difference_type __len21;      // distance(__middle, __m2)
4511         // binary search smaller range
4512         if (__len1 < __len2)
4513         {   // __len >= 1, __len2 >= 2
4514             __len21 = __len2 / 2;
4515             __m2 = __middle;
4516             _VSTD::advance(__m2, __len21);
4517             __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4518             __len11 = _VSTD::distance(__first, __m1);
4519         }
4520         else
4521         {
4522             if (__len1 == 1)
4523             {   // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
4524                 // It is known *__first > *__middle
4525                 swap(*__first, *__middle);
4526                 return;
4527             }
4528             // __len1 >= 2, __len2 >= 1
4529             __len11 = __len1 / 2;
4530             __m1 = __first;
4531             _VSTD::advance(__m1, __len11);
4532             __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp);
4533             __len21 = _VSTD::distance(__middle, __m2);
4534         }
4535         difference_type __len12 = __len1 - __len11;  // distance(__m1, __middle)
4536         difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)
4537         // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4538         // swap middle two partitions
4539         __middle = _VSTD::rotate(__m1, __middle, __m2);
4540         // __len12 and __len21 now have swapped meanings
4541         // merge smaller range with recurisve call and larger with tail recursion elimination
4542         if (__len11 + __len21 < __len12 + __len22)
4543         {
4544             __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4545 //          __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4546             __first = __middle;
4547             __middle = __m2;
4548             __len1 = __len12;
4549             __len2 = __len22;
4550         }
4551         else
4552         {
4553             __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
4554 //          __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4555             __last = __middle;
4556             __middle = __m1;
4557             __len1 = __len11;
4558             __len2 = __len21;
4559         }
4560     }
4561 }
4562
4563 template <class _BidirectionalIterator, class _Compare>
4564 inline _LIBCPP_INLINE_VISIBILITY
4565 void
4566 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
4567               _Compare __comp)
4568 {
4569     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
4570     typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
4571     difference_type __len1 = _VSTD::distance(__first, __middle);
4572     difference_type __len2 = _VSTD::distance(__middle, __last);
4573     difference_type __buf_size = _VSTD::min(__len1, __len2);
4574     pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
4575     unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
4576
4577 #ifdef _LIBCPP_DEBUG
4578     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4579     __debug_less<_Compare> __c(__comp);
4580     return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2,
4581                                             __buf.first, __buf.second);
4582 #else  // _LIBCPP_DEBUG
4583     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4584     return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4585                                             __buf.first, __buf.second);
4586 #endif  // _LIBCPP_DEBUG
4587 }
4588
4589 template <class _BidirectionalIterator>
4590 inline _LIBCPP_INLINE_VISIBILITY
4591 void
4592 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
4593 {
4594     _VSTD::inplace_merge(__first, __middle, __last,
4595                         __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
4596 }
4597
4598 // stable_sort
4599
4600 template <class _Compare, class _InputIterator1, class _InputIterator2>
4601 void
4602 __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
4603         _InputIterator2 __first2, _InputIterator2 __last2,
4604         typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
4605 {
4606     typedef typename iterator_traits<_InputIterator1>::value_type value_type;
4607     __destruct_n __d(0);
4608     unique_ptr<value_type, __destruct_n&> __h(__result, __d);
4609     for (; true; ++__result)
4610     {
4611         if (__first1 == __last1)
4612         {
4613             for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0))
4614                 ::new (__result) value_type(_VSTD::move(*__first2));
4615             __h.release();
4616             return;
4617         }
4618         if (__first2 == __last2)
4619         {
4620             for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0))
4621                 ::new (__result) value_type(_VSTD::move(*__first1));
4622             __h.release();
4623             return;
4624         }
4625         if (__comp(*__first2, *__first1))
4626         {
4627             ::new (__result) value_type(_VSTD::move(*__first2));
4628             __d.__incr((value_type*)0);
4629             ++__first2;
4630         }
4631         else
4632         {
4633             ::new (__result) value_type(_VSTD::move(*__first1));
4634             __d.__incr((value_type*)0);
4635             ++__first1;
4636         }
4637     }
4638 }
4639
4640 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
4641 void
4642 __merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
4643         _InputIterator2 __first2, _InputIterator2 __last2,
4644         _OutputIterator __result, _Compare __comp)
4645 {
4646     for (; __first1 != __last1; ++__result)
4647     {
4648         if (__first2 == __last2)
4649         {
4650             for (; __first1 != __last1; ++__first1, ++__result)
4651                 *__result = _VSTD::move(*__first1);
4652             return;
4653         }
4654         if (__comp(*__first2, *__first1))
4655         {
4656             *__result = _VSTD::move(*__first2);
4657             ++__first2;
4658         }
4659         else
4660         {
4661             *__result = _VSTD::move(*__first1);
4662             ++__first1;
4663         }
4664     }
4665     for (; __first2 != __last2; ++__first2, ++__result)
4666         *__result = _VSTD::move(*__first2);
4667 }
4668
4669 template <class _Compare, class _RandomAccessIterator>
4670 void
4671 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4672               typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4673               typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
4674
4675 template <class _Compare, class _RandomAccessIterator>
4676 void
4677 __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
4678                    typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4679                    typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
4680 {
4681     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4682     switch (__len)
4683     {
4684     case 0:
4685         return;
4686     case 1:
4687         ::new(__first2) value_type(_VSTD::move(*__first1));
4688         return;
4689     case 2:
4690        __destruct_n __d(0);
4691         unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
4692          if (__comp(*--__last1, *__first1))
4693         {
4694             ::new(__first2) value_type(_VSTD::move(*__last1));
4695             __d.__incr((value_type*)0);
4696             ++__first2;
4697             ::new(__first2) value_type(_VSTD::move(*__first1));
4698         }
4699         else
4700         {
4701             ::new(__first2) value_type(_VSTD::move(*__first1));
4702             __d.__incr((value_type*)0);
4703             ++__first2;
4704             ::new(__first2) value_type(_VSTD::move(*__last1));
4705         }
4706         __h2.release();
4707         return;
4708     }
4709     if (__len <= 8)
4710     {
4711         __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
4712         return;
4713     }
4714     typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4715     _RandomAccessIterator __m = __first1 + __l2;
4716     __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
4717     __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
4718     __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
4719 }
4720
4721 template <class _Tp>
4722 struct __stable_sort_switch
4723 {
4724     static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
4725 };
4726
4727 template <class _Compare, class _RandomAccessIterator>
4728 void
4729 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4730               typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4731               typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
4732 {
4733     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4734     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4735     switch (__len)
4736     {
4737     case 0:
4738     case 1:
4739         return;
4740     case 2:
4741         if (__comp(*--__last, *__first))
4742             swap(*__first, *__last);
4743         return;
4744     }
4745     if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4746     {
4747         __insertion_sort<_Compare>(__first, __last, __comp);
4748         return;
4749     }
4750     typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
4751     _RandomAccessIterator __m = __first + __l2;
4752     if (__len <= __buff_size)
4753     {
4754         __destruct_n __d(0);
4755         unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
4756         __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4757         __d.__set(__l2, (value_type*)0);
4758         __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
4759         __d.__set(__len, (value_type*)0);
4760         __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4761 //         __merge<_Compare>(move_iterator<value_type*>(__buff),
4762 //                           move_iterator<value_type*>(__buff + __l2),
4763 //                           move_iterator<_RandomAccessIterator>(__buff + __l2),
4764 //                           move_iterator<_RandomAccessIterator>(__buff + __len),
4765 //                           __first, __comp);
4766         return;
4767     }
4768     __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4769     __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
4770     __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4771 }
4772
4773 template <class _RandomAccessIterator, class _Compare>
4774 inline _LIBCPP_INLINE_VISIBILITY
4775 void
4776 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4777 {
4778     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4779     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4780     difference_type __len = __last - __first;
4781     pair<value_type*, ptrdiff_t> __buf(0, 0);
4782     unique_ptr<value_type, __return_temporary_buffer> __h;
4783     if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
4784     {
4785         __buf = _VSTD::get_temporary_buffer<value_type>(__len);
4786         __h.reset(__buf.first);
4787     }
4788 #ifdef _LIBCPP_DEBUG
4789     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4790     __debug_less<_Compare> __c(__comp);
4791     __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);
4792 #else  // _LIBCPP_DEBUG
4793     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4794     __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4795 #endif  // _LIBCPP_DEBUG
4796 }
4797
4798 template <class _RandomAccessIterator>
4799 inline _LIBCPP_INLINE_VISIBILITY
4800 void
4801 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4802 {
4803     _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4804 }
4805
4806 // is_heap_until
4807
4808 template <class _RandomAccessIterator, class _Compare>
4809 _RandomAccessIterator
4810 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4811 {
4812     typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4813     difference_type __len = __last - __first;
4814     difference_type __p = 0;
4815     difference_type __c = 1;
4816     _RandomAccessIterator __pp = __first;
4817     while (__c < __len)
4818     {
4819         _RandomAccessIterator __cp = __first + __c;
4820         if (__comp(*__pp, *__cp))
4821             return __cp;
4822         ++__c;
4823         ++__cp;
4824         if (__c == __len)
4825             return __last;
4826         if (__comp(*__pp, *__cp))
4827             return __cp;
4828         ++__p;
4829         ++__pp;
4830         __c = 2 * __p + 1;
4831     }
4832     return __last;
4833 }
4834
4835 template<class _RandomAccessIterator>
4836 inline _LIBCPP_INLINE_VISIBILITY
4837 _RandomAccessIterator
4838 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4839 {
4840     return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4841 }
4842
4843 // is_heap
4844
4845 template <class _RandomAccessIterator, class _Compare>
4846 inline _LIBCPP_INLINE_VISIBILITY
4847 bool
4848 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4849 {
4850     return _VSTD::is_heap_until(__first, __last, __comp) == __last;
4851 }
4852
4853 template<class _RandomAccessIterator>
4854 inline _LIBCPP_INLINE_VISIBILITY
4855 bool
4856 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4857 {
4858     return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4859 }
4860
4861 // push_heap
4862
4863 template <class _Compare, class _RandomAccessIterator>
4864 void
4865 __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4866           typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4867 {
4868     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4869     if (__len > 1)
4870     {
4871         __len = (__len - 2) / 2;
4872         _RandomAccessIterator __ptr = __first + __len;
4873         if (__comp(*__ptr, *--__last))
4874         {
4875             value_type __t(_VSTD::move(*__last));
4876             do
4877             {
4878                 *__last = _VSTD::move(*__ptr);
4879                 __last = __ptr;
4880                 if (__len == 0)
4881                     break;
4882                 __len = (__len - 1) / 2;
4883                 __ptr = __first + __len;
4884             } while (__comp(*__ptr, __t));
4885             *__last = _VSTD::move(__t);
4886         }
4887     }
4888 }
4889
4890 template <class _RandomAccessIterator, class _Compare>
4891 inline _LIBCPP_INLINE_VISIBILITY
4892 void
4893 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4894 {
4895 #ifdef _LIBCPP_DEBUG
4896     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4897     __debug_less<_Compare> __c(__comp);
4898     __sift_up<_Comp_ref>(__first, __last, __c, __last - __first);
4899 #else  // _LIBCPP_DEBUG
4900     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4901     __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
4902 #endif  // _LIBCPP_DEBUG
4903 }
4904
4905 template <class _RandomAccessIterator>
4906 inline _LIBCPP_INLINE_VISIBILITY
4907 void
4908 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4909 {
4910     _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
4911 }
4912
4913 // pop_heap
4914
4915 template <class _Compare, class _RandomAccessIterator>
4916 void
4917 __sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/,
4918             _Compare __comp,
4919             typename iterator_traits<_RandomAccessIterator>::difference_type __len,
4920             _RandomAccessIterator __start)
4921 {
4922     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
4923     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
4924     // left-child of __start is at 2 * __start + 1
4925     // right-child of __start is at 2 * __start + 2
4926     difference_type __child = __start - __first;
4927
4928     if (__len < 2 || (__len - 2) / 2 < __child)
4929         return;
4930
4931     __child = 2 * __child + 1;
4932     _RandomAccessIterator __child_i = __first + __child;
4933
4934     if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4935         // right-child exists and is greater than left-child
4936         ++__child_i;
4937         ++__child;
4938     }
4939
4940     // check if we are in heap-order
4941     if (__comp(*__child_i, *__start))
4942         // we are, __start is larger than it's largest child
4943         return;
4944
4945     value_type __top(_VSTD::move(*__start));
4946     do
4947     {
4948         // we are not in heap-order, swap the parent with it's largest child
4949         *__start = _VSTD::move(*__child_i);
4950         __start = __child_i;
4951
4952         if ((__len - 2) / 2 < __child)
4953             break;
4954
4955         // recompute the child based off of the updated parent
4956         __child = 2 * __child + 1;
4957         __child_i = __first + __child;
4958
4959         if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
4960             // right-child exists and is greater than left-child
4961             ++__child_i;
4962             ++__child;
4963         }
4964
4965         // check if we are in heap-order
4966     } while (!__comp(*__child_i, __top));
4967     *__start = _VSTD::move(__top);
4968 }
4969
4970 template <class _Compare, class _RandomAccessIterator>
4971 inline _LIBCPP_INLINE_VISIBILITY
4972 void
4973 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4974            typename iterator_traits<_RandomAccessIterator>::difference_type __len)
4975 {
4976     if (__len > 1)
4977     {
4978         swap(*__first, *--__last);
4979         __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);
4980     }
4981 }
4982
4983 template <class _RandomAccessIterator, class _Compare>
4984 inline _LIBCPP_INLINE_VISIBILITY
4985 void
4986 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4987 {
4988 #ifdef _LIBCPP_DEBUG
4989     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
4990     __debug_less<_Compare> __c(__comp);
4991     __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);
4992 #else  // _LIBCPP_DEBUG
4993     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
4994     __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
4995 #endif  // _LIBCPP_DEBUG
4996 }
4997
4998 template <class _RandomAccessIterator>
4999 inline _LIBCPP_INLINE_VISIBILITY
5000 void
5001 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5002 {
5003     _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5004 }
5005
5006 // make_heap
5007
5008 template <class _Compare, class _RandomAccessIterator>
5009 void
5010 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5011 {
5012     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5013     difference_type __n = __last - __first;
5014     if (__n > 1)
5015     {
5016         // start from the first parent, there is no need to consider children
5017         for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start)
5018         {
5019             __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start);
5020         }
5021     }
5022 }
5023
5024 template <class _RandomAccessIterator, class _Compare>
5025 inline _LIBCPP_INLINE_VISIBILITY
5026 void
5027 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5028 {
5029 #ifdef _LIBCPP_DEBUG
5030     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5031     __debug_less<_Compare> __c(__comp);
5032     __make_heap<_Comp_ref>(__first, __last, __c);
5033 #else  // _LIBCPP_DEBUG
5034     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5035     __make_heap<_Comp_ref>(__first, __last, __comp);
5036 #endif  // _LIBCPP_DEBUG
5037 }
5038
5039 template <class _RandomAccessIterator>
5040 inline _LIBCPP_INLINE_VISIBILITY
5041 void
5042 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5043 {
5044     _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5045 }
5046
5047 // sort_heap
5048
5049 template <class _Compare, class _RandomAccessIterator>
5050 void
5051 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5052 {
5053     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5054     for (difference_type __n = __last - __first; __n > 1; --__last, --__n)
5055         __pop_heap<_Compare>(__first, __last, __comp, __n);
5056 }
5057
5058 template <class _RandomAccessIterator, class _Compare>
5059 inline _LIBCPP_INLINE_VISIBILITY
5060 void
5061 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5062 {
5063 #ifdef _LIBCPP_DEBUG
5064     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5065     __debug_less<_Compare> __c(__comp);
5066     __sort_heap<_Comp_ref>(__first, __last, __c);
5067 #else  // _LIBCPP_DEBUG
5068     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5069     __sort_heap<_Comp_ref>(__first, __last, __comp);
5070 #endif  // _LIBCPP_DEBUG
5071 }
5072
5073 template <class _RandomAccessIterator>
5074 inline _LIBCPP_INLINE_VISIBILITY
5075 void
5076 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5077 {
5078     _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5079 }
5080
5081 // partial_sort
5082
5083 template <class _Compare, class _RandomAccessIterator>
5084 void
5085 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5086              _Compare __comp)
5087 {
5088     __make_heap<_Compare>(__first, __middle, __comp);
5089     typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
5090     for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
5091     {
5092         if (__comp(*__i, *__first))
5093         {
5094             swap(*__i, *__first);
5095             __sift_down<_Compare>(__first, __middle, __comp, __len, __first);
5096         }
5097     }
5098     __sort_heap<_Compare>(__first, __middle, __comp);
5099 }
5100
5101 template <class _RandomAccessIterator, class _Compare>
5102 inline _LIBCPP_INLINE_VISIBILITY
5103 void
5104 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
5105              _Compare __comp)
5106 {
5107 #ifdef _LIBCPP_DEBUG
5108     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5109     __debug_less<_Compare> __c(__comp);
5110     __partial_sort<_Comp_ref>(__first, __middle, __last, __c);
5111 #else  // _LIBCPP_DEBUG
5112     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5113     __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
5114 #endif  // _LIBCPP_DEBUG
5115 }
5116
5117 template <class _RandomAccessIterator>
5118 inline _LIBCPP_INLINE_VISIBILITY
5119 void
5120 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
5121 {
5122     _VSTD::partial_sort(__first, __middle, __last,
5123                        __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5124 }
5125
5126 // partial_sort_copy
5127
5128 template <class _Compare, class _InputIterator, class _RandomAccessIterator>
5129 _RandomAccessIterator
5130 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
5131                     _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5132 {
5133     _RandomAccessIterator __r = __result_first;
5134     if (__r != __result_last)
5135     {
5136         for (; __first != __last && __r != __result_last; (void) ++__first, ++__r)
5137             *__r = *__first;
5138         __make_heap<_Compare>(__result_first, __r, __comp);
5139         typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
5140         for (; __first != __last; ++__first)
5141             if (__comp(*__first, *__result_first))
5142             {
5143                 *__result_first = *__first;
5144                 __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first);
5145             }
5146         __sort_heap<_Compare>(__result_first, __r, __comp);
5147     }
5148     return __r;
5149 }
5150
5151 template <class _InputIterator, class _RandomAccessIterator, class _Compare>
5152 inline _LIBCPP_INLINE_VISIBILITY
5153 _RandomAccessIterator
5154 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5155                   _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
5156 {
5157 #ifdef _LIBCPP_DEBUG
5158     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5159     __debug_less<_Compare> __c(__comp);
5160     return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);
5161 #else  // _LIBCPP_DEBUG
5162     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5163     return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
5164 #endif  // _LIBCPP_DEBUG
5165 }
5166
5167 template <class _InputIterator, class _RandomAccessIterator>
5168 inline _LIBCPP_INLINE_VISIBILITY
5169 _RandomAccessIterator
5170 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5171                   _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
5172 {
5173     return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
5174                                    __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5175 }
5176
5177 // nth_element
5178
5179 template <class _Compare, class _RandomAccessIterator>
5180 void
5181 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5182 {
5183     // _Compare is known to be a reference type
5184     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
5185     const difference_type __limit = 7;
5186     while (true)
5187     {
5188     __restart:
5189         if (__nth == __last)
5190             return;
5191         difference_type __len = __last - __first;
5192         switch (__len)
5193         {
5194         case 0:
5195         case 1:
5196             return;
5197         case 2:
5198             if (__comp(*--__last, *__first))
5199                 swap(*__first, *__last);
5200             return;
5201         case 3:
5202             {
5203             _RandomAccessIterator __m = __first;
5204             _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
5205             return;
5206             }
5207         }
5208         if (__len <= __limit)
5209         {
5210             __selection_sort<_Compare>(__first, __last, __comp);
5211             return;
5212         }
5213         // __len > __limit >= 3
5214         _RandomAccessIterator __m = __first + __len/2;
5215         _RandomAccessIterator __lm1 = __last;
5216         unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
5217         // *__m is median
5218         // partition [__first, __m) < *__m and *__m <= [__m, __last)
5219         // (this inhibits tossing elements equivalent to __m around unnecessarily)
5220         _RandomAccessIterator __i = __first;
5221         _RandomAccessIterator __j = __lm1;
5222         // j points beyond range to be tested, *__lm1 is known to be <= *__m
5223         // The search going up is known to be guarded but the search coming down isn't.
5224         // Prime the downward search with a guard.
5225         if (!__comp(*__i, *__m))  // if *__first == *__m
5226         {
5227             // *__first == *__m, *__first doesn't go in first part
5228             // manually guard downward moving __j against __i
5229             while (true)
5230             {
5231                 if (__i == --__j)
5232                 {
5233                     // *__first == *__m, *__m <= all other elements
5234                     // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
5235                     ++__i;  // __first + 1
5236                     __j = __last;
5237                     if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
5238                     {
5239                         while (true)
5240                         {
5241                             if (__i == __j)
5242                                 return;  // [__first, __last) all equivalent elements
5243                             if (__comp(*__first, *__i))
5244                             {
5245                                 swap(*__i, *__j);
5246                                 ++__n_swaps;
5247                                 ++__i;
5248                                 break;
5249                             }
5250                             ++__i;
5251                         }
5252                     }
5253                     // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
5254                     if (__i == __j)
5255                         return;
5256                     while (true)
5257                     {
5258                         while (!__comp(*__first, *__i))
5259                             ++__i;
5260                         while (__comp(*__first, *--__j))
5261                             ;
5262                         if (__i >= __j)
5263                             break;
5264                         swap(*__i, *__j);
5265                         ++__n_swaps;
5266                         ++__i;
5267                     }
5268                     // [__first, __i) == *__first and *__first < [__i, __last)
5269                     // The first part is sorted,
5270                     if (__nth < __i)
5271                         return;
5272                     // __nth_element the secod part
5273                     // __nth_element<_Compare>(__i, __nth, __last, __comp);
5274                     __first = __i;
5275                     goto __restart;
5276                 }
5277                 if (__comp(*__j, *__m))
5278                 {
5279                     swap(*__i, *__j);
5280                     ++__n_swaps;
5281                     break;  // found guard for downward moving __j, now use unguarded partition
5282                 }
5283             }
5284         }
5285         ++__i;
5286         // j points beyond range to be tested, *__lm1 is known to be <= *__m
5287         // if not yet partitioned...
5288         if (__i < __j)
5289         {
5290             // known that *(__i - 1) < *__m
5291             while (true)
5292             {
5293                 // __m still guards upward moving __i
5294                 while (__comp(*__i, *__m))
5295                     ++__i;
5296                 // It is now known that a guard exists for downward moving __j
5297                 while (!__comp(*--__j, *__m))
5298                     ;
5299                 if (__i >= __j)
5300                     break;
5301                 swap(*__i, *__j);
5302                 ++__n_swaps;
5303                 // It is known that __m != __j
5304                 // If __m just moved, follow it
5305                 if (__m == __i)
5306                     __m = __j;
5307                 ++__i;
5308             }
5309         }
5310         // [__first, __i) < *__m and *__m <= [__i, __last)
5311         if (__i != __m && __comp(*__m, *__i))
5312         {
5313             swap(*__i, *__m);
5314             ++__n_swaps;
5315         }
5316         // [__first, __i) < *__i and *__i <= [__i+1, __last)
5317         if (__nth == __i)
5318             return;
5319         if (__n_swaps == 0)
5320         {
5321             // We were given a perfectly partitioned sequence.  Coincidence?
5322             if (__nth < __i)
5323             {
5324                 // Check for [__first, __i) already sorted
5325                 __j = __m = __first;
5326                 while (++__j != __i)
5327                 {
5328                     if (__comp(*__j, *__m))
5329                         // not yet sorted, so sort
5330                         goto not_sorted;
5331                     __m = __j;
5332                 }
5333                 // [__first, __i) sorted
5334                 return;
5335             }
5336             else
5337             {
5338                 // Check for [__i, __last) already sorted
5339                 __j = __m = __i;
5340                 while (++__j != __last)
5341                 {
5342                     if (__comp(*__j, *__m))
5343                         // not yet sorted, so sort
5344                         goto not_sorted;
5345                     __m = __j;
5346                 }
5347                 // [__i, __last) sorted
5348                 return;
5349             }
5350         }
5351 not_sorted:
5352         // __nth_element on range containing __nth
5353         if (__nth < __i)
5354         {
5355             // __nth_element<_Compare>(__first, __nth, __i, __comp);
5356             __last = __i;
5357         }
5358         else
5359         {
5360             // __nth_element<_Compare>(__i+1, __nth, __last, __comp);
5361             __first = ++__i;
5362         }
5363     }
5364 }
5365
5366 template <class _RandomAccessIterator, class _Compare>
5367 inline _LIBCPP_INLINE_VISIBILITY
5368 void
5369 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
5370 {
5371 #ifdef _LIBCPP_DEBUG
5372     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5373     __debug_less<_Compare> __c(__comp);
5374     __nth_element<_Comp_ref>(__first, __nth, __last, __c);
5375 #else  // _LIBCPP_DEBUG
5376     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5377     __nth_element<_Comp_ref>(__first, __nth, __last, __comp);
5378 #endif  // _LIBCPP_DEBUG
5379 }
5380
5381 template <class _RandomAccessIterator>
5382 inline _LIBCPP_INLINE_VISIBILITY
5383 void
5384 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
5385 {
5386     _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
5387 }
5388
5389 // includes
5390
5391 template <class _Compare, class _InputIterator1, class _InputIterator2>
5392 bool
5393 __includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5394            _Compare __comp)
5395 {
5396     for (; __first2 != __last2; ++__first1)
5397     {
5398         if (__first1 == __last1 || __comp(*__first2, *__first1))
5399             return false;
5400         if (!__comp(*__first1, *__first2))
5401             ++__first2;
5402     }
5403     return true;
5404 }
5405
5406 template <class _InputIterator1, class _InputIterator2, class _Compare>
5407 inline _LIBCPP_INLINE_VISIBILITY
5408 bool
5409 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
5410          _Compare __comp)
5411 {
5412 #ifdef _LIBCPP_DEBUG
5413     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5414     __debug_less<_Compare> __c(__comp);
5415     return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5416 #else  // _LIBCPP_DEBUG
5417     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5418     return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5419 #endif  // _LIBCPP_DEBUG
5420 }
5421
5422 template <class _InputIterator1, class _InputIterator2>
5423 inline _LIBCPP_INLINE_VISIBILITY
5424 bool
5425 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
5426 {
5427     return _VSTD::includes(__first1, __last1, __first2, __last2,
5428                           __less<typename iterator_traits<_InputIterator1>::value_type,
5429                                  typename iterator_traits<_InputIterator2>::value_type>());
5430 }
5431
5432 // set_union
5433
5434 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5435 _OutputIterator
5436 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5437             _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5438 {
5439     for (; __first1 != __last1; ++__result)
5440     {
5441         if (__first2 == __last2)
5442             return _VSTD::copy(__first1, __last1, __result);
5443         if (__comp(*__first2, *__first1))
5444         {
5445             *__result = *__first2;
5446             ++__first2;
5447         }
5448         else
5449         {
5450             *__result = *__first1;
5451             if (!__comp(*__first1, *__first2))
5452                 ++__first2;
5453             ++__first1;
5454         }
5455     }
5456     return _VSTD::copy(__first2, __last2, __result);
5457 }
5458
5459 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5460 inline _LIBCPP_INLINE_VISIBILITY
5461 _OutputIterator
5462 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5463           _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5464 {
5465 #ifdef _LIBCPP_DEBUG
5466     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5467     __debug_less<_Compare> __c(__comp);
5468     return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5469 #else  // _LIBCPP_DEBUG
5470     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5471     return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5472 #endif  // _LIBCPP_DEBUG
5473 }
5474
5475 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5476 inline _LIBCPP_INLINE_VISIBILITY
5477 _OutputIterator
5478 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5479           _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5480 {
5481     return _VSTD::set_union(__first1, __last1, __first2, __last2, __result,
5482                           __less<typename iterator_traits<_InputIterator1>::value_type,
5483                                  typename iterator_traits<_InputIterator2>::value_type>());
5484 }
5485
5486 // set_intersection
5487
5488 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5489 _OutputIterator
5490 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5491                    _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5492 {
5493     while (__first1 != __last1 && __first2 != __last2)
5494     {
5495         if (__comp(*__first1, *__first2))
5496             ++__first1;
5497         else
5498         {
5499             if (!__comp(*__first2, *__first1))
5500             {
5501                 *__result = *__first1;
5502                 ++__result;
5503                 ++__first1;
5504             }
5505             ++__first2;
5506         }
5507     }
5508     return __result;
5509 }
5510
5511 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5512 inline _LIBCPP_INLINE_VISIBILITY
5513 _OutputIterator
5514 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5515                  _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5516 {
5517 #ifdef _LIBCPP_DEBUG
5518     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5519     __debug_less<_Compare> __c(__comp);
5520     return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5521 #else  // _LIBCPP_DEBUG
5522     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5523     return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5524 #endif  // _LIBCPP_DEBUG
5525 }
5526
5527 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5528 inline _LIBCPP_INLINE_VISIBILITY
5529 _OutputIterator
5530 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5531                  _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5532 {
5533     return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result,
5534                                   __less<typename iterator_traits<_InputIterator1>::value_type,
5535                                          typename iterator_traits<_InputIterator2>::value_type>());
5536 }
5537
5538 // set_difference
5539
5540 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5541 _OutputIterator
5542 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5543                  _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5544 {
5545     while (__first1 != __last1)
5546     {
5547         if (__first2 == __last2)
5548             return _VSTD::copy(__first1, __last1, __result);
5549         if (__comp(*__first1, *__first2))
5550         {
5551             *__result = *__first1;
5552             ++__result;
5553             ++__first1;
5554         }
5555         else
5556         {
5557             if (!__comp(*__first2, *__first1))
5558                 ++__first1;
5559             ++__first2;
5560         }
5561     }
5562     return __result;
5563 }
5564
5565 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5566 inline _LIBCPP_INLINE_VISIBILITY
5567 _OutputIterator
5568 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5569                _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5570 {
5571 #ifdef _LIBCPP_DEBUG
5572     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5573     __debug_less<_Compare> __c(__comp);
5574     return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5575 #else  // _LIBCPP_DEBUG
5576     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5577     return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5578 #endif  // _LIBCPP_DEBUG
5579 }
5580
5581 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5582 inline _LIBCPP_INLINE_VISIBILITY
5583 _OutputIterator
5584 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5585                _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5586 {
5587     return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result,
5588                                 __less<typename iterator_traits<_InputIterator1>::value_type,
5589                                        typename iterator_traits<_InputIterator2>::value_type>());
5590 }
5591
5592 // set_symmetric_difference
5593
5594 template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
5595 _OutputIterator
5596 __set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5597                            _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5598 {
5599     while (__first1 != __last1)
5600     {
5601         if (__first2 == __last2)
5602             return _VSTD::copy(__first1, __last1, __result);
5603         if (__comp(*__first1, *__first2))
5604         {
5605             *__result = *__first1;
5606             ++__result;
5607             ++__first1;
5608         }
5609         else
5610         {
5611             if (__comp(*__first2, *__first1))
5612             {
5613                 *__result = *__first2;
5614                 ++__result;
5615             }
5616             else
5617                 ++__first1;
5618             ++__first2;
5619         }
5620     }
5621     return _VSTD::copy(__first2, __last2, __result);
5622 }
5623
5624 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
5625 inline _LIBCPP_INLINE_VISIBILITY
5626 _OutputIterator
5627 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5628                          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
5629 {
5630 #ifdef _LIBCPP_DEBUG
5631     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5632     __debug_less<_Compare> __c(__comp);
5633     return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);
5634 #else  // _LIBCPP_DEBUG
5635     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5636     return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
5637 #endif  // _LIBCPP_DEBUG
5638 }
5639
5640 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
5641 inline _LIBCPP_INLINE_VISIBILITY
5642 _OutputIterator
5643 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5644                          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
5645 {
5646     return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
5647                                           __less<typename iterator_traits<_InputIterator1>::value_type,
5648                                                  typename iterator_traits<_InputIterator2>::value_type>());
5649 }
5650
5651 // lexicographical_compare
5652
5653 template <class _Compare, class _InputIterator1, class _InputIterator2>
5654 bool
5655 __lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5656                           _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5657 {
5658     for (; __first2 != __last2; ++__first1, (void) ++__first2)
5659     {
5660         if (__first1 == __last1 || __comp(*__first1, *__first2))
5661             return true;
5662         if (__comp(*__first2, *__first1))
5663             return false;
5664     }
5665     return false;
5666 }
5667
5668 template <class _InputIterator1, class _InputIterator2, class _Compare>
5669 inline _LIBCPP_INLINE_VISIBILITY
5670 bool
5671 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5672                         _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
5673 {
5674 #ifdef _LIBCPP_DEBUG
5675     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5676     __debug_less<_Compare> __c(__comp);
5677     return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c);
5678 #else  // _LIBCPP_DEBUG
5679     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5680     return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
5681 #endif  // _LIBCPP_DEBUG
5682 }
5683
5684 template <class _InputIterator1, class _InputIterator2>
5685 inline _LIBCPP_INLINE_VISIBILITY
5686 bool
5687 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
5688                         _InputIterator2 __first2, _InputIterator2 __last2)
5689 {
5690     return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,
5691                                          __less<typename iterator_traits<_InputIterator1>::value_type,
5692                                                 typename iterator_traits<_InputIterator2>::value_type>());
5693 }
5694
5695 // next_permutation
5696
5697 template <class _Compare, class _BidirectionalIterator>
5698 bool
5699 __next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5700 {
5701     _BidirectionalIterator __i = __last;
5702     if (__first == __last || __first == --__i)
5703         return false;
5704     while (true)
5705     {
5706         _BidirectionalIterator __ip1 = __i;
5707         if (__comp(*--__i, *__ip1))
5708         {
5709             _BidirectionalIterator __j = __last;
5710             while (!__comp(*__i, *--__j))
5711                 ;
5712             swap(*__i, *__j);
5713             _VSTD::reverse(__ip1, __last);
5714             return true;
5715         }
5716         if (__i == __first)
5717         {
5718             _VSTD::reverse(__first, __last);
5719             return false;
5720         }
5721     }
5722 }
5723
5724 template <class _BidirectionalIterator, class _Compare>
5725 inline _LIBCPP_INLINE_VISIBILITY
5726 bool
5727 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5728 {
5729 #ifdef _LIBCPP_DEBUG
5730     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5731     __debug_less<_Compare> __c(__comp);
5732     return __next_permutation<_Comp_ref>(__first, __last, __c);
5733 #else  // _LIBCPP_DEBUG
5734     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5735     return __next_permutation<_Comp_ref>(__first, __last, __comp);
5736 #endif  // _LIBCPP_DEBUG
5737 }
5738
5739 template <class _BidirectionalIterator>
5740 inline _LIBCPP_INLINE_VISIBILITY
5741 bool
5742 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5743 {
5744     return _VSTD::next_permutation(__first, __last,
5745                                   __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5746 }
5747
5748 // prev_permutation
5749
5750 template <class _Compare, class _BidirectionalIterator>
5751 bool
5752 __prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5753 {
5754     _BidirectionalIterator __i = __last;
5755     if (__first == __last || __first == --__i)
5756         return false;
5757     while (true)
5758     {
5759         _BidirectionalIterator __ip1 = __i;
5760         if (__comp(*__ip1, *--__i))
5761         {
5762             _BidirectionalIterator __j = __last;
5763             while (!__comp(*--__j, *__i))
5764                 ;
5765             swap(*__i, *__j);
5766             _VSTD::reverse(__ip1, __last);
5767             return true;
5768         }
5769         if (__i == __first)
5770         {
5771             _VSTD::reverse(__first, __last);
5772             return false;
5773         }
5774     }
5775 }
5776
5777 template <class _BidirectionalIterator, class _Compare>
5778 inline _LIBCPP_INLINE_VISIBILITY
5779 bool
5780 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5781 {
5782 #ifdef _LIBCPP_DEBUG
5783     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
5784     __debug_less<_Compare> __c(__comp);
5785     return __prev_permutation<_Comp_ref>(__first, __last, __c);
5786 #else  // _LIBCPP_DEBUG
5787     typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
5788     return __prev_permutation<_Comp_ref>(__first, __last, __comp);
5789 #endif  // _LIBCPP_DEBUG
5790 }
5791
5792 template <class _BidirectionalIterator>
5793 inline _LIBCPP_INLINE_VISIBILITY
5794 bool
5795 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5796 {
5797     return _VSTD::prev_permutation(__first, __last,
5798                                   __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
5799 }
5800
5801 _LIBCPP_END_NAMESPACE_STD
5802
5803 #endif  // _LIBCPP_ALGORITHM