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