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