contrib/libc++/include/algorithm

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