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