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