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