contrib/libc++/include/algorithm

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