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