contrib/libc++/include/algorithm

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