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