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