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