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