contrib/llvm-project/libcxx/include/algorithm

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