contrib/llvm-project/libcxx/include/algorithm

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