contrib/llvm-project/libcxx/include/algorithm

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   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     constexpr void               // constexpr in C++20
 355     sort(RandomAccessIterator first, RandomAccessIterator last);
 356
 357 template <class RandomAccessIterator, class Compare>
 358     constexpr void               // constexpr in C++20
 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     constexpr void                    // constexpr in C++20
 371     partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
 372
 373 template <class RandomAccessIterator, class Compare>
 374     constexpr void                    // constexpr in C++20
 375     partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
 376
 377 template <class InputIterator, class RandomAccessIterator>
 378     constexpr RandomAccessIterator    // constexpr in C++20
 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     constexpr RandomAccessIterator    // constexpr in C++20
 384     partial_sort_copy(InputIterator first, InputIterator last,
 385                       RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
 386
 387 template <class RandomAccessIterator>
 388     constexpr void                    // constexpr in C++20
 389     nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
 390
 391 template <class RandomAccessIterator, class Compare>
 392     constexpr void                    // constexpr in C++20
 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     constexpr void                                   // constexpr in C++20
 495     push_heap(RandomAccessIterator first, RandomAccessIterator last);
 496
 497 template <class RandomAccessIterator, class Compare>
 498     constexpr void                                   // constexpr in C++20
 499     push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 500
 501 template <class RandomAccessIterator>
 502     constexpr void                                   // constexpr in C++20
 503     pop_heap(RandomAccessIterator first, RandomAccessIterator last);
 504
 505 template <class RandomAccessIterator, class Compare>
 506     constexpr void                                   // constexpr in C++20
 507     pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 508
 509 template <class RandomAccessIterator>
 510     constexpr void                                   // constexpr in C++20
 511     make_heap(RandomAccessIterator first, RandomAccessIterator last);
 512
 513 template <class RandomAccessIterator, class Compare>
 514     constexpr void                                   // constexpr in C++20
 515     make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 516
 517 template <class RandomAccessIterator>
 518     constexpr void                                   // constexpr in C++20
 519     sort_heap(RandomAccessIterator first, RandomAccessIterator last);
 520
 521 template <class RandomAccessIterator, class Compare>
 522     constexpr void                                   // constexpr in C++20
 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 <__debug>
 650 #include <__bits> // __libcpp_clz
 651 #include <cstddef>
 652 #include <cstring>
 653 #include <functional>
 654 #include <initializer_list>
 655 #include <utility> // needed to provide swap_ranges.
 656 #include <memory>
 657 #include <iterator>
 658 #include <memory>
 659 #include <type_traits>
 660 #include <utility> // swap_ranges
 661 #include <version>
 662
 663 #include <__algorithm/adjacent_find.h>
 664 #include <__algorithm/all_of.h>
 665 #include <__algorithm/any_of.h>
 666 #include <__algorithm/binary_search.h>
 667 #include <__algorithm/clamp.h>
 668 #include <__algorithm/comp.h>
 669 #include <__algorithm/comp_ref_type.h>
 670 #include <__algorithm/copy.h>
 671 #include <__algorithm/copy_backward.h>
 672 #include <__algorithm/copy_if.h>
 673 #include <__algorithm/copy_n.h>
 674 #include <__algorithm/count.h>
 675 #include <__algorithm/count_if.h>
 676 #include <__algorithm/equal.h>
 677 #include <__algorithm/equal_range.h>
 678 #include <__algorithm/fill_n.h>
 679 #include <__algorithm/fill.h>
 680 #include <__algorithm/find.h>
 681 #include <__algorithm/find_end.h>
 682 #include <__algorithm/find_first_of.h>
 683 #include <__algorithm/find_if.h>
 684 #include <__algorithm/find_if_not.h>
 685 #include <__algorithm/for_each.h>
 686 #include <__algorithm/for_each_n.h>
 687 #include <__algorithm/generate_n.h>
 688 #include <__algorithm/generate.h>
 689 #include <__algorithm/half_positive.h>
 690 #include <__algorithm/includes.h>
 691 #include <__algorithm/inplace_merge.h>
 692 #include <__algorithm/is_heap.h>
 693 #include <__algorithm/is_heap_until.h>
 694 #include <__algorithm/is_partitioned.h>
 695 #include <__algorithm/is_permutation.h>
 696 #include <__algorithm/is_sorted.h>
 697 #include <__algorithm/is_sorted_until.h>
 698 #include <__algorithm/iter_swap.h>
 699 #include <__algorithm/lexicographical_compare.h>
 700 #include <__algorithm/lower_bound.h>
 701 #include <__algorithm/make_heap.h>
 702 #include <__algorithm/max.h>
 703 #include <__algorithm/max_element.h>
 704 #include <__algorithm/merge.h>
 705 #include <__algorithm/min.h>
 706 #include <__algorithm/min_element.h>
 707 #include <__algorithm/minmax.h>
 708 #include <__algorithm/minmax_element.h>
 709 #include <__algorithm/mismatch.h>
 710 #include <__algorithm/move.h>
 711 #include <__algorithm/move_backward.h>
 712 #include <__algorithm/next_permutation.h>
 713 #include <__algorithm/none_of.h>
 714 #include <__algorithm/nth_element.h>
 715 #include <__algorithm/partial_sort.h>
 716 #include <__algorithm/partial_sort_copy.h>
 717 #include <__algorithm/partition.h>
 718 #include <__algorithm/partition_copy.h>
 719 #include <__algorithm/partition_point.h>
 720 #include <__algorithm/pop_heap.h>
 721 #include <__algorithm/prev_permutation.h>
 722 #include <__algorithm/push_heap.h>
 723 #include <__algorithm/remove.h>
 724 #include <__algorithm/remove_copy.h>
 725 #include <__algorithm/remove_copy_if.h>
 726 #include <__algorithm/remove_if.h>
 727 #include <__algorithm/replace.h>
 728 #include <__algorithm/replace_copy.h>
 729 #include <__algorithm/replace_copy_if.h>
 730 #include <__algorithm/replace_if.h>
 731 #include <__algorithm/reverse.h>
 732 #include <__algorithm/reverse_copy.h>
 733 #include <__algorithm/rotate.h>
 734 #include <__algorithm/rotate_copy.h>
 735 #include <__algorithm/sample.h>
 736 #include <__algorithm/search.h>
 737 #include <__algorithm/search_n.h>
 738 #include <__algorithm/set_difference.h>
 739 #include <__algorithm/set_intersection.h>
 740 #include <__algorithm/set_symmetric_difference.h>
 741 #include <__algorithm/set_union.h>
 742 #include <__algorithm/shift_left.h>
 743 #include <__algorithm/shift_right.h>
 744 #include <__algorithm/shuffle.h>
 745 #include <__algorithm/sift_down.h>
 746 #include <__algorithm/sort.h>
 747 #include <__algorithm/sort_heap.h>
 748 #include <__algorithm/stable_partition.h>
 749 #include <__algorithm/stable_sort.h>
 750 #include <__algorithm/swap_ranges.h>
 751 #include <__algorithm/transform.h>
 752 #include <__algorithm/unique_copy.h>
 753 #include <__algorithm/unique.h>
 754 #include <__algorithm/unwrap_iter.h>
 755 #include <__algorithm/upper_bound.h>
 756
 757 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 758 #pragma GCC system_header
 759 #endif
 760
 761 #if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
 762 #   include <__pstl_algorithm>
 763 #endif
 764
 765 #endif // _LIBCPP_ALGORITHM