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 18namespace std 19{ 20 21namespace ranges { 22 template <class I1, class I2> 23 struct in_in_result; // since C++20 24 25 template <class I1, class I2, class O> 26 struct in_in_out_result; // since C++20 27} 28 29template <class InputIterator, class Predicate> 30 constexpr bool // constexpr in C++20 31 all_of(InputIterator first, InputIterator last, Predicate pred); 32 33template <class InputIterator, class Predicate> 34 constexpr bool // constexpr in C++20 35 any_of(InputIterator first, InputIterator last, Predicate pred); 36 37template <class InputIterator, class Predicate> 38 constexpr bool // constexpr in C++20 39 none_of(InputIterator first, InputIterator last, Predicate pred); 40 41template <class InputIterator, class Function> 42 constexpr Function // constexpr in C++20 43 for_each(InputIterator first, InputIterator last, Function f); 44 45template<class InputIterator, class Size, class Function> 46 constexpr InputIterator // constexpr in C++20 47 for_each_n(InputIterator first, Size n, Function f); // C++17 48 49template <class InputIterator, class T> 50 constexpr InputIterator // constexpr in C++20 51 find(InputIterator first, InputIterator last, const T& value); 52 53template <class InputIterator, class Predicate> 54 constexpr InputIterator // constexpr in C++20 55 find_if(InputIterator first, InputIterator last, Predicate pred); 56 57template<class InputIterator, class Predicate> 58 constexpr InputIterator // constexpr in C++20 59 find_if_not(InputIterator first, InputIterator last, Predicate pred); 60 61template <class ForwardIterator1, class ForwardIterator2> 62 constexpr ForwardIterator1 // constexpr in C++20 63 find_end(ForwardIterator1 first1, ForwardIterator1 last1, 64 ForwardIterator2 first2, ForwardIterator2 last2); 65 66template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 67 constexpr ForwardIterator1 // constexpr in C++20 68 find_end(ForwardIterator1 first1, ForwardIterator1 last1, 69 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); 70 71template <class ForwardIterator1, class ForwardIterator2> 72 constexpr ForwardIterator1 // constexpr in C++20 73 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, 74 ForwardIterator2 first2, ForwardIterator2 last2); 75 76template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 77 constexpr ForwardIterator1 // constexpr in C++20 78 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, 79 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); 80 81template <class ForwardIterator> 82 constexpr ForwardIterator // constexpr in C++20 83 adjacent_find(ForwardIterator first, ForwardIterator last); 84 85template <class ForwardIterator, class BinaryPredicate> 86 constexpr ForwardIterator // constexpr in C++20 87 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); 88 89template <class InputIterator, class T> 90 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20 91 count(InputIterator first, InputIterator last, const T& value); 92 93template <class InputIterator, class Predicate> 94 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20 95 count_if(InputIterator first, InputIterator last, Predicate pred); 96 97template <class InputIterator1, class InputIterator2> 98 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 99 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); 100 101template <class InputIterator1, class InputIterator2> 102 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 103 mismatch(InputIterator1 first1, InputIterator1 last1, 104 InputIterator2 first2, InputIterator2 last2); // **C++14** 105 106template <class InputIterator1, class InputIterator2, class BinaryPredicate> 107 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 108 mismatch(InputIterator1 first1, InputIterator1 last1, 109 InputIterator2 first2, BinaryPredicate pred); 110 111template <class InputIterator1, class InputIterator2, class BinaryPredicate> 112 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 113 mismatch(InputIterator1 first1, InputIterator1 last1, 114 InputIterator2 first2, InputIterator2 last2, 115 BinaryPredicate pred); // **C++14** 116 117template <class InputIterator1, class InputIterator2> 118 constexpr bool // constexpr in C++20 119 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); 120 121template <class InputIterator1, class InputIterator2> 122 constexpr bool // constexpr in C++20 123 equal(InputIterator1 first1, InputIterator1 last1, 124 InputIterator2 first2, InputIterator2 last2); // **C++14** 125 126template <class InputIterator1, class InputIterator2, class BinaryPredicate> 127 constexpr bool // constexpr in C++20 128 equal(InputIterator1 first1, InputIterator1 last1, 129 InputIterator2 first2, BinaryPredicate pred); 130 131template <class InputIterator1, class InputIterator2, class BinaryPredicate> 132 constexpr bool // constexpr in C++20 133 equal(InputIterator1 first1, InputIterator1 last1, 134 InputIterator2 first2, InputIterator2 last2, 135 BinaryPredicate pred); // **C++14** 136 137template<class ForwardIterator1, class ForwardIterator2> 138 constexpr bool // constexpr in C++20 139 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 140 ForwardIterator2 first2); 141 142template<class ForwardIterator1, class ForwardIterator2> 143 constexpr bool // constexpr in C++20 144 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 145 ForwardIterator2 first2, ForwardIterator2 last2); // **C++14** 146 147template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 148 constexpr bool // constexpr in C++20 149 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 150 ForwardIterator2 first2, BinaryPredicate pred); 151 152template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 153 constexpr bool // constexpr in C++20 154 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 155 ForwardIterator2 first2, ForwardIterator2 last2, 156 BinaryPredicate pred); // **C++14** 157 158template <class ForwardIterator1, class ForwardIterator2> 159 constexpr ForwardIterator1 // constexpr in C++20 160 search(ForwardIterator1 first1, ForwardIterator1 last1, 161 ForwardIterator2 first2, ForwardIterator2 last2); 162 163template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 164 constexpr ForwardIterator1 // constexpr in C++20 165 search(ForwardIterator1 first1, ForwardIterator1 last1, 166 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); 167 168template <class ForwardIterator, class Size, class T> 169 constexpr ForwardIterator // constexpr in C++20 170 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value); 171 172template <class ForwardIterator, class Size, class T, class BinaryPredicate> 173 constexpr ForwardIterator // constexpr in C++20 174 search_n(ForwardIterator first, ForwardIterator last, 175 Size count, const T& value, BinaryPredicate pred); 176 177template <class InputIterator, class OutputIterator> 178 constexpr OutputIterator // constexpr in C++20 179 copy(InputIterator first, InputIterator last, OutputIterator result); 180 181template<class InputIterator, class OutputIterator, class Predicate> 182 constexpr OutputIterator // constexpr in C++20 183 copy_if(InputIterator first, InputIterator last, 184 OutputIterator result, Predicate pred); 185 186template<class InputIterator, class Size, class OutputIterator> 187 constexpr OutputIterator // constexpr in C++20 188 copy_n(InputIterator first, Size n, OutputIterator result); 189 190template <class BidirectionalIterator1, class BidirectionalIterator2> 191 constexpr BidirectionalIterator2 // constexpr in C++20 192 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, 193 BidirectionalIterator2 result); 194 195template <class ForwardIterator1, class ForwardIterator2> 196 constexpr ForwardIterator2 // constexpr in C++20 197 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); 198 199template <class ForwardIterator1, class ForwardIterator2> 200 constexpr void // constexpr in C++20 201 iter_swap(ForwardIterator1 a, ForwardIterator2 b); 202 203template <class InputIterator, class OutputIterator, class UnaryOperation> 204 constexpr OutputIterator // constexpr in C++20 205 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op); 206 207template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> 208 constexpr OutputIterator // constexpr in C++20 209 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, 210 OutputIterator result, BinaryOperation binary_op); 211 212template <class ForwardIterator, class T> 213 constexpr void // constexpr in C++20 214 replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value); 215 216template <class ForwardIterator, class Predicate, class T> 217 constexpr void // constexpr in C++20 218 replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value); 219 220template <class InputIterator, class OutputIterator, class T> 221 constexpr OutputIterator // constexpr in C++20 222 replace_copy(InputIterator first, InputIterator last, OutputIterator result, 223 const T& old_value, const T& new_value); 224 225template <class InputIterator, class OutputIterator, class Predicate, class T> 226 constexpr OutputIterator // constexpr in C++20 227 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value); 228 229template <class ForwardIterator, class T> 230 constexpr void // constexpr in C++20 231 fill(ForwardIterator first, ForwardIterator last, const T& value); 232 233template <class OutputIterator, class Size, class T> 234 constexpr OutputIterator // constexpr in C++20 235 fill_n(OutputIterator first, Size n, const T& value); 236 237template <class ForwardIterator, class Generator> 238 constexpr void // constexpr in C++20 239 generate(ForwardIterator first, ForwardIterator last, Generator gen); 240 241template <class OutputIterator, class Size, class Generator> 242 constexpr OutputIterator // constexpr in C++20 243 generate_n(OutputIterator first, Size n, Generator gen); 244 245template <class ForwardIterator, class T> 246 constexpr ForwardIterator // constexpr in C++20 247 remove(ForwardIterator first, ForwardIterator last, const T& value); 248 249template <class ForwardIterator, class Predicate> 250 constexpr ForwardIterator // constexpr in C++20 251 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred); 252 253template <class InputIterator, class OutputIterator, class T> 254 constexpr OutputIterator // constexpr in C++20 255 remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value); 256 257template <class InputIterator, class OutputIterator, class Predicate> 258 constexpr OutputIterator // constexpr in C++20 259 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred); 260 261template <class ForwardIterator> 262 constexpr ForwardIterator // constexpr in C++20 263 unique(ForwardIterator first, ForwardIterator last); 264 265template <class ForwardIterator, class BinaryPredicate> 266 constexpr ForwardIterator // constexpr in C++20 267 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); 268 269template <class InputIterator, class OutputIterator> 270 constexpr OutputIterator // constexpr in C++20 271 unique_copy(InputIterator first, InputIterator last, OutputIterator result); 272 273template <class InputIterator, class OutputIterator, class BinaryPredicate> 274 constexpr OutputIterator // constexpr in C++20 275 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred); 276 277template <class BidirectionalIterator> 278 constexpr void // constexpr in C++20 279 reverse(BidirectionalIterator first, BidirectionalIterator last); 280 281template <class BidirectionalIterator, class OutputIterator> 282 constexpr OutputIterator // constexpr in C++20 283 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result); 284 285template <class ForwardIterator> 286 constexpr ForwardIterator // constexpr in C++20 287 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); 288 289template <class ForwardIterator, class OutputIterator> 290 constexpr OutputIterator // constexpr in C++20 291 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result); 292 293template <class RandomAccessIterator> 294 void 295 random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17 296 297template <class RandomAccessIterator, class RandomNumberGenerator> 298 void 299 random_shuffle(RandomAccessIterator first, RandomAccessIterator last, 300 RandomNumberGenerator& rand); // deprecated in C++14, removed in C++17 301 302template<class PopulationIterator, class SampleIterator, 303 class Distance, class UniformRandomBitGenerator> 304 SampleIterator sample(PopulationIterator first, PopulationIterator last, 305 SampleIterator out, Distance n, 306 UniformRandomBitGenerator&& g); // C++17 307 308template<class RandomAccessIterator, class UniformRandomNumberGenerator> 309 void shuffle(RandomAccessIterator first, RandomAccessIterator last, 310 UniformRandomNumberGenerator&& g); 311 312template<class ForwardIterator> 313 constexpr ForwardIterator 314 shift_left(ForwardIterator first, ForwardIterator last, 315 typename iterator_traits<ForwardIterator>::difference_type n); // C++20 316 317template<class ForwardIterator> 318 constexpr ForwardIterator 319 shift_right(ForwardIterator first, ForwardIterator last, 320 typename iterator_traits<ForwardIterator>::difference_type n); // C++20 321 322template <class InputIterator, class Predicate> 323 constexpr bool // constexpr in C++20 324 is_partitioned(InputIterator first, InputIterator last, Predicate pred); 325 326template <class ForwardIterator, class Predicate> 327 constexpr ForwardIterator // constexpr in C++20 328 partition(ForwardIterator first, ForwardIterator last, Predicate pred); 329 330template <class InputIterator, class OutputIterator1, 331 class OutputIterator2, class Predicate> 332 constexpr pair<OutputIterator1, OutputIterator2> // constexpr in C++20 333 partition_copy(InputIterator first, InputIterator last, 334 OutputIterator1 out_true, OutputIterator2 out_false, 335 Predicate pred); 336 337template <class ForwardIterator, class Predicate> 338 ForwardIterator 339 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred); 340 341template<class ForwardIterator, class Predicate> 342 constexpr ForwardIterator // constexpr in C++20 343 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred); 344 345template <class ForwardIterator> 346 constexpr bool // constexpr in C++20 347 is_sorted(ForwardIterator first, ForwardIterator last); 348 349template <class ForwardIterator, class Compare> 350 constexpr bool // constexpr in C++20 351 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp); 352 353template<class ForwardIterator> 354 constexpr ForwardIterator // constexpr in C++20 355 is_sorted_until(ForwardIterator first, ForwardIterator last); 356 357template <class ForwardIterator, class Compare> 358 constexpr ForwardIterator // constexpr in C++20 359 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp); 360 361template <class RandomAccessIterator> 362 constexpr void // constexpr in C++20 363 sort(RandomAccessIterator first, RandomAccessIterator last); 364 365template <class RandomAccessIterator, class Compare> 366 constexpr void // constexpr in C++20 367 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 368 369template <class RandomAccessIterator> 370 void 371 stable_sort(RandomAccessIterator first, RandomAccessIterator last); 372 373template <class RandomAccessIterator, class Compare> 374 void 375 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 376 377template <class RandomAccessIterator> 378 constexpr void // constexpr in C++20 379 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); 380 381template <class RandomAccessIterator, class Compare> 382 constexpr void // constexpr in C++20 383 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); 384 385template <class InputIterator, class RandomAccessIterator> 386 constexpr RandomAccessIterator // constexpr in C++20 387 partial_sort_copy(InputIterator first, InputIterator last, 388 RandomAccessIterator result_first, RandomAccessIterator result_last); 389 390template <class InputIterator, class RandomAccessIterator, class Compare> 391 constexpr RandomAccessIterator // constexpr in C++20 392 partial_sort_copy(InputIterator first, InputIterator last, 393 RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp); 394 395template <class RandomAccessIterator> 396 constexpr void // constexpr in C++20 397 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); 398 399template <class RandomAccessIterator, class Compare> 400 constexpr void // constexpr in C++20 401 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); 402 403template <class ForwardIterator, class T> 404 constexpr ForwardIterator // constexpr in C++20 405 lower_bound(ForwardIterator first, ForwardIterator last, const T& value); 406 407template <class ForwardIterator, class T, class Compare> 408 constexpr ForwardIterator // constexpr in C++20 409 lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); 410 411template <class ForwardIterator, class T> 412 constexpr ForwardIterator // constexpr in C++20 413 upper_bound(ForwardIterator first, ForwardIterator last, const T& value); 414 415template <class ForwardIterator, class T, class Compare> 416 constexpr ForwardIterator // constexpr in C++20 417 upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); 418 419template <class ForwardIterator, class T> 420 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20 421 equal_range(ForwardIterator first, ForwardIterator last, const T& value); 422 423template <class ForwardIterator, class T, class Compare> 424 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20 425 equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); 426 427template <class ForwardIterator, class T> 428 constexpr bool // constexpr in C++20 429 binary_search(ForwardIterator first, ForwardIterator last, const T& value); 430 431template <class ForwardIterator, class T, class Compare> 432 constexpr bool // constexpr in C++20 433 binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); 434 435template <class InputIterator1, class InputIterator2, class OutputIterator> 436 constexpr OutputIterator // constexpr in C++20 437 merge(InputIterator1 first1, InputIterator1 last1, 438 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 439 440template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 441 constexpr OutputIterator // constexpr in C++20 442 merge(InputIterator1 first1, InputIterator1 last1, 443 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); 444 445template <class BidirectionalIterator> 446 void 447 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); 448 449template <class BidirectionalIterator, class Compare> 450 void 451 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); 452 453template <class InputIterator1, class InputIterator2> 454 constexpr bool // constexpr in C++20 455 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); 456 457template <class InputIterator1, class InputIterator2, class Compare> 458 constexpr bool // constexpr in C++20 459 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); 460 461template <class InputIterator1, class InputIterator2, class OutputIterator> 462 constexpr OutputIterator // constexpr in C++20 463 set_union(InputIterator1 first1, InputIterator1 last1, 464 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 465 466template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 467 constexpr OutputIterator // constexpr in C++20 468 set_union(InputIterator1 first1, InputIterator1 last1, 469 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); 470 471template <class InputIterator1, class InputIterator2, class OutputIterator> 472 constexpr OutputIterator // constexpr in C++20 473 set_intersection(InputIterator1 first1, InputIterator1 last1, 474 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 475 476template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 477 constexpr OutputIterator // constexpr in C++20 478 set_intersection(InputIterator1 first1, InputIterator1 last1, 479 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); 480 481template <class InputIterator1, class InputIterator2, class OutputIterator> 482 constexpr OutputIterator // constexpr in C++20 483 set_difference(InputIterator1 first1, InputIterator1 last1, 484 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 485 486template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 487 constexpr OutputIterator // constexpr in C++20 488 set_difference(InputIterator1 first1, InputIterator1 last1, 489 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); 490 491template <class InputIterator1, class InputIterator2, class OutputIterator> 492 constexpr OutputIterator // constexpr in C++20 493 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, 494 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 495 496template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 497 constexpr OutputIterator // constexpr in C++20 498 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, 499 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); 500 501template <class RandomAccessIterator> 502 constexpr void // constexpr in C++20 503 push_heap(RandomAccessIterator first, RandomAccessIterator last); 504 505template <class RandomAccessIterator, class Compare> 506 constexpr void // constexpr in C++20 507 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 508 509template <class RandomAccessIterator> 510 constexpr void // constexpr in C++20 511 pop_heap(RandomAccessIterator first, RandomAccessIterator last); 512 513template <class RandomAccessIterator, class Compare> 514 constexpr void // constexpr in C++20 515 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 516 517template <class RandomAccessIterator> 518 constexpr void // constexpr in C++20 519 make_heap(RandomAccessIterator first, RandomAccessIterator last); 520 521template <class RandomAccessIterator, class Compare> 522 constexpr void // constexpr in C++20 523 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 524 525template <class RandomAccessIterator> 526 constexpr void // constexpr in C++20 527 sort_heap(RandomAccessIterator first, RandomAccessIterator last); 528 529template <class RandomAccessIterator, class Compare> 530 constexpr void // constexpr in C++20 531 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 532 533template <class RandomAccessIterator> 534 constexpr bool // constexpr in C++20 535 is_heap(RandomAccessIterator first, RandomAccessiterator last); 536 537template <class RandomAccessIterator, class Compare> 538 constexpr bool // constexpr in C++20 539 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp); 540 541template <class RandomAccessIterator> 542 constexpr RandomAccessIterator // constexpr in C++20 543 is_heap_until(RandomAccessIterator first, RandomAccessiterator last); 544 545template <class RandomAccessIterator, class Compare> 546 constexpr RandomAccessIterator // constexpr in C++20 547 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp); 548 549template <class ForwardIterator> 550 constexpr ForwardIterator // constexpr in C++14 551 min_element(ForwardIterator first, ForwardIterator last); 552 553template <class ForwardIterator, class Compare> 554 constexpr ForwardIterator // constexpr in C++14 555 min_element(ForwardIterator first, ForwardIterator last, Compare comp); 556 557template <class T> 558 constexpr const T& // constexpr in C++14 559 min(const T& a, const T& b); 560 561template <class T, class Compare> 562 constexpr const T& // constexpr in C++14 563 min(const T& a, const T& b, Compare comp); 564 565template<class T> 566 constexpr T // constexpr in C++14 567 min(initializer_list<T> t); 568 569template<class T, class Compare> 570 constexpr T // constexpr in C++14 571 min(initializer_list<T> t, Compare comp); 572 573template<class T> 574 constexpr const T& clamp(const T& v, const T& lo, const T& hi); // C++17 575 576template<class T, class Compare> 577 constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp); // C++17 578 579template <class ForwardIterator> 580 constexpr ForwardIterator // constexpr in C++14 581 max_element(ForwardIterator first, ForwardIterator last); 582 583template <class ForwardIterator, class Compare> 584 constexpr ForwardIterator // constexpr in C++14 585 max_element(ForwardIterator first, ForwardIterator last, Compare comp); 586 587template <class T> 588 constexpr const T& // constexpr in C++14 589 max(const T& a, const T& b); 590 591template <class T, class Compare> 592 constexpr const T& // constexpr in C++14 593 max(const T& a, const T& b, Compare comp); 594 595template<class T> 596 constexpr T // constexpr in C++14 597 max(initializer_list<T> t); 598 599template<class T, class Compare> 600 constexpr T // constexpr in C++14 601 max(initializer_list<T> t, Compare comp); 602 603template<class ForwardIterator> 604 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14 605 minmax_element(ForwardIterator first, ForwardIterator last); 606 607template<class ForwardIterator, class Compare> 608 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14 609 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); 610 611template<class T> 612 constexpr pair<const T&, const T&> // constexpr in C++14 613 minmax(const T& a, const T& b); 614 615template<class T, class Compare> 616 constexpr pair<const T&, const T&> // constexpr in C++14 617 minmax(const T& a, const T& b, Compare comp); 618 619template<class T> 620 constexpr pair<T, T> // constexpr in C++14 621 minmax(initializer_list<T> t); 622 623template<class T, class Compare> 624 constexpr pair<T, T> // constexpr in C++14 625 minmax(initializer_list<T> t, Compare comp); 626 627template <class InputIterator1, class InputIterator2> 628 constexpr bool // constexpr in C++20 629 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); 630 631template <class InputIterator1, class InputIterator2, class Compare> 632 constexpr bool // constexpr in C++20 633 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, 634 InputIterator2 first2, InputIterator2 last2, Compare comp); 635 636template <class BidirectionalIterator> 637 constexpr bool // constexpr in C++20 638 next_permutation(BidirectionalIterator first, BidirectionalIterator last); 639 640template <class BidirectionalIterator, class Compare> 641 constexpr bool // constexpr in C++20 642 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); 643 644template <class BidirectionalIterator> 645 constexpr bool // constexpr in C++20 646 prev_permutation(BidirectionalIterator first, BidirectionalIterator last); 647 648template <class BidirectionalIterator, class Compare> 649 constexpr bool // constexpr in C++20 650 prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); 651 652namespace ranges { 653// [algorithms.results], algorithm result types 654template<class InputIterator, class OutputIterator> 655 struct in_out_result; 656} 657 658} // std 659 660*/ 661 662#include <__bits> // __libcpp_clz 663#include <__config> 664#include <__debug> 665#include <cstddef> 666#include <cstring> 667#include <functional> 668#include <initializer_list> 669#include <iterator> 670#include <memory> 671#include <type_traits> 672#include <utility> // swap_ranges 673#include <version> 674 675#include <__algorithm/adjacent_find.h> 676#include <__algorithm/all_of.h> 677#include <__algorithm/any_of.h> 678#include <__algorithm/binary_search.h> 679#include <__algorithm/clamp.h> 680#include <__algorithm/comp.h> 681#include <__algorithm/comp_ref_type.h> 682#include <__algorithm/copy.h> 683#include <__algorithm/copy_backward.h> 684#include <__algorithm/copy_if.h> 685#include <__algorithm/copy_n.h> 686#include <__algorithm/count.h> 687#include <__algorithm/count_if.h> 688#include <__algorithm/equal.h> 689#include <__algorithm/equal_range.h> 690#include <__algorithm/fill.h> 691#include <__algorithm/fill_n.h> 692#include <__algorithm/find.h> 693#include <__algorithm/find_end.h> 694#include <__algorithm/find_first_of.h> 695#include <__algorithm/find_if.h> 696#include <__algorithm/find_if_not.h> 697#include <__algorithm/for_each.h> 698#include <__algorithm/for_each_n.h> 699#include <__algorithm/generate.h> 700#include <__algorithm/generate_n.h> 701#include <__algorithm/half_positive.h> 702#include <__algorithm/in_in_out_result.h> 703#include <__algorithm/in_in_result.h> 704#include <__algorithm/in_out_result.h> 705#include <__algorithm/includes.h> 706#include <__algorithm/inplace_merge.h> 707#include <__algorithm/is_heap.h> 708#include <__algorithm/is_heap_until.h> 709#include <__algorithm/is_partitioned.h> 710#include <__algorithm/is_permutation.h> 711#include <__algorithm/is_sorted.h> 712#include <__algorithm/is_sorted_until.h> 713#include <__algorithm/iter_swap.h> 714#include <__algorithm/lexicographical_compare.h> 715#include <__algorithm/lower_bound.h> 716#include <__algorithm/make_heap.h> 717#include <__algorithm/max.h> 718#include <__algorithm/max_element.h> 719#include <__algorithm/merge.h> 720#include <__algorithm/min.h> 721#include <__algorithm/min_element.h> 722#include <__algorithm/minmax.h> 723#include <__algorithm/minmax_element.h> 724#include <__algorithm/mismatch.h> 725#include <__algorithm/move.h> 726#include <__algorithm/move_backward.h> 727#include <__algorithm/next_permutation.h> 728#include <__algorithm/none_of.h> 729#include <__algorithm/nth_element.h> 730#include <__algorithm/partial_sort.h> 731#include <__algorithm/partial_sort_copy.h> 732#include <__algorithm/partition.h> 733#include <__algorithm/partition_copy.h> 734#include <__algorithm/partition_point.h> 735#include <__algorithm/pop_heap.h> 736#include <__algorithm/prev_permutation.h> 737#include <__algorithm/push_heap.h> 738#include <__algorithm/remove.h> 739#include <__algorithm/remove_copy.h> 740#include <__algorithm/remove_copy_if.h> 741#include <__algorithm/remove_if.h> 742#include <__algorithm/replace.h> 743#include <__algorithm/replace_copy.h> 744#include <__algorithm/replace_copy_if.h> 745#include <__algorithm/replace_if.h> 746#include <__algorithm/reverse.h> 747#include <__algorithm/reverse_copy.h> 748#include <__algorithm/rotate.h> 749#include <__algorithm/rotate_copy.h> 750#include <__algorithm/sample.h> 751#include <__algorithm/search.h> 752#include <__algorithm/search_n.h> 753#include <__algorithm/set_difference.h> 754#include <__algorithm/set_intersection.h> 755#include <__algorithm/set_symmetric_difference.h> 756#include <__algorithm/set_union.h> 757#include <__algorithm/shift_left.h> 758#include <__algorithm/shift_right.h> 759#include <__algorithm/shuffle.h> 760#include <__algorithm/sift_down.h> 761#include <__algorithm/sort.h> 762#include <__algorithm/sort_heap.h> 763#include <__algorithm/stable_partition.h> 764#include <__algorithm/stable_sort.h> 765#include <__algorithm/swap_ranges.h> 766#include <__algorithm/transform.h> 767#include <__algorithm/unique.h> 768#include <__algorithm/unique_copy.h> 769#include <__algorithm/unwrap_iter.h> 770#include <__algorithm/upper_bound.h> 771 772#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 773#pragma GCC system_header 774#endif 775 776#if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17 777# include <__pstl_algorithm> 778#endif 779 780#endif // _LIBCPP_ALGORITHM 781