contrib/libc++/include/algorithm

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