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 23 // [algorithms.results], algorithm result types 24 template <class I, class F> 25 struct in_fun_result; // since C++20 26 27 template <class I1, class I2> 28 struct in_in_result; // since C++20 29 30 template <class I, class O> 31 struct in_out_result; // since C++20 32 33 template <class I1, class I2, class O> 34 struct in_in_out_result; // since C++20 35 36 template <class I, class O1, class O2> 37 struct in_out_out_result; // since C++20 38 39 template <class I1, class I2> 40 struct min_max_result; // since C++20 41 42 template <class I> 43 struct in_found_result; // since C++20 44 45 template<forward_iterator I, sentinel_for<I> S, class Proj = identity, 46 indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less> // since C++20 47 constexpr I min_element(I first, S last, Comp comp = {}, Proj proj = {}); 48 49 template<forward_range R, class Proj = identity, 50 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> // since C++20 51 constexpr borrowed_iterator_t<R> min_element(R&& r, Comp comp = {}, Proj proj = {}); 52 53 template<forward_iterator I, sentinel_for<I> S, class Proj = identity, 54 indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less> 55 constexpr I ranges::max_element(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 56 57 template<forward_range R, class Proj = identity, 58 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> 59 constexpr borrowed_iterator_t<R> ranges::max_element(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 60 61 template<class I1, class I2> 62 using mismatch_result = in_in_result<I1, I2>; 63 64 template <input_iterator I1, sentinel_for<_I1> S1, input_iterator I2, sentinel_for<_I2> S2, 65 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> 66 requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2> 67 constexpr mismatch_result<_I1, _I2> 68 mismatch()(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) // since C++20 69 70 template <input_range R1, input_range R2, 71 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> 72 requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> 73 constexpr mismatch_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>> 74 mismatch(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) // since C++20 75 76 requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*> 77 constexpr I find(I first, S last, const T& value, Proj proj = {}); // since C++20 78 79 template<input_range R, class T, class Proj = identity> 80 requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> 81 constexpr borrowed_iterator_t<R> 82 find(R&& r, const T& value, Proj proj = {}); // since C++20 83 84 template<input_iterator I, sentinel_for<I> S, class Proj = identity, 85 indirect_unary_predicate<projected<I, Proj>> Pred> 86 constexpr I find_if(I first, S last, Pred pred, Proj proj = {}); // since C++20 87 88 template<input_range R, class Proj = identity, 89 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> 90 constexpr borrowed_iterator_t<R> 91 find_if(R&& r, Pred pred, Proj proj = {}); // since C++20 92 93 template<input_iterator I, sentinel_for<I> S, class Proj = identity, 94 indirect_unary_predicate<projected<I, Proj>> Pred> 95 constexpr I find_if_not(I first, S last, Pred pred, Proj proj = {}); // since C++20 96 97 template<input_range R, class Proj = identity, 98 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> 99 constexpr borrowed_iterator_t<R> 100 find_if_not(R&& r, Pred pred, Proj proj = {}); // since C++20 101 102 template<class T, class Proj = identity, 103 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less> 104 constexpr const T& min(const T& a, const T& b, Comp comp = {}, Proj proj = {}); // since C++20 105 106 template<copyable T, class Proj = identity, 107 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less> 108 constexpr T min(initializer_list<T> r, Comp comp = {}, Proj proj = {}); // since C++20 109 110 template<input_range R, class Proj = identity, 111 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> 112 requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*> 113 constexpr range_value_t<R> 114 min(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 115 116 template<class T, class Proj = identity, 117 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less> 118 constexpr const T& max(const T& a, const T& b, Comp comp = {}, Proj proj = {}); // since C++20 119 120 template<copyable T, class Proj = identity, 121 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less> 122 constexpr T max(initializer_list<T> r, Comp comp = {}, Proj proj = {}); // since C++20 123 124 template<input_range R, class Proj = identity, 125 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> 126 requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*> 127 constexpr range_value_t<R> 128 max(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 129 130 template<class I, class O> 131 using unary_transform_result = in_out_result<I, O>; // since C++20 132 133 template<class I1, class I2, class O> 134 using binary_transform_result = in_in_out_result<I1, I2, O>; // since C++20 135 136 template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, 137 copy_constructible F, class Proj = identity> 138 requires indirectly_writable<O, indirect_result_t<F&, projected<I, Proj>>> 139 constexpr ranges::unary_transform_result<I, O> 140 transform(I first1, S last1, O result, F op, Proj proj = {}); // since C++20 141 142 template<input_range R, weakly_incrementable O, copy_constructible F, 143 class Proj = identity> 144 requires indirectly_writable<O, indirect_result_t<F&, projected<iterator_t<R>, Proj>>> 145 constexpr ranges::unary_transform_result<borrowed_iterator_t<R>, O> 146 transform(R&& r, O result, F op, Proj proj = {}); // since C++20 147 148 template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2, 149 weakly_incrementable O, copy_constructible F, class Proj1 = identity, 150 class Proj2 = identity> 151 requires indirectly_writable<O, indirect_result_t<F&, projected<I1, Proj1>, 152 projected<I2, Proj2>>> 153 constexpr ranges::binary_transform_result<I1, I2, O> 154 transform(I1 first1, S1 last1, I2 first2, S2 last2, O result, 155 F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 156 157 template<input_range R1, input_range R2, weakly_incrementable O, 158 copy_constructible F, class Proj1 = identity, class Proj2 = identity> 159 requires indirectly_writable<O, indirect_result_t<F&, projected<iterator_t<R1>, Proj1>, 160 projected<iterator_t<R2>, Proj2>>> 161 constexpr ranges::binary_transform_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O> 162 transform(R1&& r1, R2&& r2, O result, 163 F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 164 165 template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity> 166 requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*> 167 constexpr iter_difference_t<I> 168 count(I first, S last, const T& value, Proj proj = {}); // since C++20 169 170 template<input_range R, class T, class Proj = identity> 171 requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> 172 constexpr range_difference_t<R> 173 count(R&& r, const T& value, Proj proj = {}); // since C++20 174 175 template<input_iterator I, sentinel_for<I> S, class Proj = identity, 176 indirect_unary_predicate<projected<I, Proj>> Pred> 177 constexpr iter_difference_t<I> 178 count_if(I first, S last, Pred pred, Proj proj = {}); // since C++20 179 180 template<input_range R, class Proj = identity, 181 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> 182 constexpr range_difference_t<R> 183 count_if(R&& r, Pred pred, Proj proj = {}); // since C++20 184 185 template<class T> 186 using minmax_result = min_max_result<T>; 187 188 template<class T, class Proj = identity, 189 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less> 190 constexpr ranges::minmax_result<const T&> 191 minmax(const T& a, const T& b, Comp comp = {}, Proj proj = {}); // since C++20 192 193 template<copyable T, class Proj = identity, 194 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less> 195 constexpr ranges::minmax_result<T> 196 minmax(initializer_list<T> r, Comp comp = {}, Proj proj = {}); // since C++20 197 198 template<input_range R, class Proj = identity, 199 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> 200 requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*> 201 constexpr ranges::minmax_result<range_value_t<R>> 202 minmax(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 203 204 template<class I> 205 using minmax_element_result = min_max_result<I>; 206 207 template<forward_iterator I, sentinel_for<I> S, class Proj = identity, 208 indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less> 209 constexpr ranges::minmax_element_result<I> 210 minmax_element(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 211 212 template<forward_range R, class Proj = identity, 213 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> 214 constexpr ranges::minmax_element_result<borrowed_iterator_t<R>> 215 minmax_element(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 216 217 template<class I, class O> 218 using copy_result = in_out_result<I, O>; // since C++20 219 220 template<class I, class O> 221 using copy_n_result = in_out_result<I, O>; // since C++20 222 223 template<class I, class O> 224 using copy_if_result = in_out_result<I, O>; // since C++20 225 226 template<class I1, class I2> 227 using copy_backward_result = in_out_result<I1, I2>; // since C++20 228 229 template<input_iterator I, sentinel_for<I> S, weakly_incrementable O> 230 requires indirectly_copyable<I, O> 231 constexpr ranges::copy_result<I, O> ranges::copy(I first, S last, O result); // since C++20 232 233 template<input_range R, weakly_incrementable O> 234 requires indirectly_copyable<iterator_t<R>, O> 235 constexpr ranges::copy_result<borrowed_iterator_t<R>, O> ranges::copy(R&& r, O result); // since C++20 236 237 template<input_iterator I, weakly_incrementable O> 238 requires indirectly_copyable<I, O> 239 constexpr ranges::copy_n_result<I, O> 240 ranges::copy_n(I first, iter_difference_t<I> n, O result); // since C++20 241 242 template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Proj = identity, 243 indirect_unary_predicate<projected<I, Proj>> Pred> 244 requires indirectly_copyable<I, O> 245 constexpr ranges::copy_if_result<I, O> 246 ranges::copy_if(I first, S last, O result, Pred pred, Proj proj = {}); // since C++20 247 248 template<input_range R, weakly_incrementable O, class Proj = identity, 249 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> 250 requires indirectly_copyable<iterator_t<R>, O> 251 constexpr ranges::copy_if_result<borrowed_iterator_t<R>, O> 252 ranges::copy_if(R&& r, O result, Pred pred, Proj proj = {}); // since C++20 253 254 template<bidirectional_iterator I1, sentinel_for<I1> S1, bidirectional_iterator I2> 255 requires indirectly_copyable<I1, I2> 256 constexpr ranges::copy_backward_result<I1, I2> 257 ranges::copy_backward(I1 first, S1 last, I2 result); // since C++20 258 259 template<bidirectional_range R, bidirectional_iterator I> 260 requires indirectly_copyable<iterator_t<R>, I> 261 constexpr ranges::copy_backward_result<borrowed_iterator_t<R>, I> 262 ranges::copy_backward(R&& r, I result); // since C++20 263 264 template<class I, class F> 265 using for_each_result = in_fun_result<I, F>; // since C++20 266 267 template<input_iterator I, sentinel_for<I> S, class Proj = identity, 268 indirectly_unary_invocable<projected<I, Proj>> Fun> 269 constexpr ranges::for_each_result<I, Fun> 270 ranges::for_each(I first, S last, Fun f, Proj proj = {}); // since C++20 271 272 template<input_range R, class Proj = identity, 273 indirectly_unary_invocable<projected<iterator_t<R>, Proj>> Fun> 274 constexpr ranges::for_each_result<borrowed_iterator_t<R>, Fun> 275 ranges::for_each(R&& r, Fun f, Proj proj = {}); // since C++20 276 277 template<input_iterator I, class Proj = identity, 278 indirectly_unary_invocable<projected<I, Proj>> Fun> 279 constexpr ranges::for_each_n_result<I, Fun> 280 ranges::for_each_n(I first, iter_difference_t<I> n, Fun f, Proj proj = {}); // since C++20 281 282 template<input_iterator I, sentinel_for<I> S, class Proj = identity, 283 indirect_unary_predicate<projected<I, Proj>> Pred> 284 constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {}); // since C++20 285 286 template<input_range R, class Proj = identity, 287 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> 288 constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {}); // since C++20 289 290 template<bidirectional_iterator I, sentinel_for<I> S> 291 requires permutable<I> 292 constexpr I ranges::reverse(I first, S last); // since C++20 293 294 template<bidirectional_range R> 295 requires permutable<iterator_t<R>> 296 constexpr borrowed_iterator_t<R> ranges::reverse(R&& r); // since C++20 297 298 template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less, 299 class Proj = identity> 300 requires sortable<I, Comp, Proj> 301 constexpr I 302 ranges::sort(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 303 304 template<random_access_range R, class Comp = ranges::less, class Proj = identity> 305 requires sortable<iterator_t<R>, Comp, Proj> 306 constexpr borrowed_iterator_t<R> 307 ranges::sort(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 308 309 template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less, 310 class Proj = identity> 311 requires sortable<I, Comp, Proj> 312 I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 313 314 template<random_access_range R, class Comp = ranges::less, class Proj = identity> 315 requires sortable<iterator_t<R>, Comp, Proj> 316 borrowed_iterator_t<R> 317 ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 318 319 template<class T, output_iterator<const T&> O, sentinel_for<O> S> 320 constexpr O ranges::fill(O first, S last, const T& value); // since C++20 321 322 template<class T, output_range<const T&> R> 323 constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value); // since C++20 324 325 template<class T, output_iterator<const T&> O> 326 constexpr O ranges::fill_n(O first, iter_difference_t<O> n, const T& value); // since C++20 327 328 template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2, 329 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> 330 requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2> 331 constexpr bool ranges::equal(I1 first1, S1 last1, I2 first2, S2 last2, 332 Pred pred = {}, 333 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 334 335 template<input_range R1, input_range R2, class Pred = ranges::equal_to, 336 class Proj1 = identity, class Proj2 = identity> 337 requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> 338 constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {}, 339 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 340 341 template<input_iterator I, sentinel_for<I> S, class Proj = identity, 342 indirect_unary_predicate<projected<I, Proj>> Pred> 343 constexpr bool ranges::all_of(I first, S last, Pred pred, Proj proj = {}); // since C++20 344 345 template<input_range R, class Proj = identity, 346 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> 347 constexpr bool ranges::all_of(R&& r, Pred pred, Proj proj = {}); // since C++20 348 349 template<input_iterator I, sentinel_for<I> S, class Proj = identity, 350 indirect_unary_predicate<projected<I, Proj>> Pred> 351 constexpr bool ranges::any_of(I first, S last, Pred pred, Proj proj = {}); // since C++20 352 353 template<input_range R, class Proj = identity, 354 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> 355 constexpr bool ranges::any_of(R&& r, Pred pred, Proj proj = {}); // since C++20 356 357 template<input_iterator I, sentinel_for<I> S, class Proj = identity, 358 indirect_unary_predicate<projected<I, Proj>> Pred> 359 constexpr bool ranges::none_of(I first, S last, Pred pred, Proj proj = {}); // since C++20 360 361 template<input_range R, class Proj = identity, 362 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> 363 constexpr bool ranges::none_of(R&& r, Pred pred, Proj proj = {}); // since C++20 364 365 template<forward_iterator I, sentinel_for<I> S, class Proj = identity, 366 indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less> 367 constexpr bool ranges::is_sorted(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 368 369 template<forward_range R, class Proj = identity, 370 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> 371 constexpr bool ranges::is_sorted(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 372 373 template<forward_iterator I, sentinel_for<I> S, class Proj = identity, 374 indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less> 375 constexpr I ranges::is_sorted_until(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 376 377 template<forward_range R, class Proj = identity, 378 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> 379 constexpr borrowed_iterator_t<R> 380 ranges::is_sorted_until(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 381 382 template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity, 383 indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less> 384 constexpr I upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); // since C++20 385 386 template<forward_range R, class T, class Proj = identity, 387 indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp = 388 ranges::less> 389 constexpr borrowed_iterator_t<R> 390 upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20 391 392 template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity, 393 indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less> 394 constexpr I lower_bound(I first, S last, const T& value, Comp comp = {}, 395 Proj proj = {}); // since C++20 396 template<forward_range R, class T, class Proj = identity, 397 indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp = 398 ranges::less> 399 constexpr borrowed_iterator_t<R> 400 lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20 401 402 template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity, 403 indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less> 404 constexpr bool binary_search(I first, S last, const T& value, Comp comp = {}, 405 Proj proj = {}); // since C++20 406 407 template<forward_range R, class T, class Proj = identity, 408 indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp = 409 ranges::less> 410 constexpr bool binary_search(R&& r, const T& value, Comp comp = {}, 411 Proj proj = {}); // since C++20 412 template<input_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2, 413 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> 414 requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2> 415 constexpr I1 ranges::find_first_of(I1 first1, S1 last1, I2 first2, S2 last2, 416 Pred pred = {}, 417 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 418 419 template<input_range R1, forward_range R2, 420 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> 421 requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> 422 constexpr borrowed_iterator_t<R1> 423 ranges::find_first_of(R1&& r1, R2&& r2, 424 Pred pred = {}, 425 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 426 427 template<forward_iterator I, sentinel_for<I> S, class Proj = identity, 428 indirect_binary_predicate<projected<I, Proj>, 429 projected<I, Proj>> Pred = ranges::equal_to> 430 constexpr I ranges::adjacent_find(I first, S last, Pred pred = {}, Proj proj = {}); // since C+20 431 432 template<forward_range R, class Proj = identity, 433 indirect_binary_predicate<projected<iterator_t<R>, Proj>, 434 projected<iterator_t<R>, Proj>> Pred = ranges::equal_to> 435 constexpr borrowed_iterator_t<R> ranges::adjacent_find(R&& r, Pred pred = {}, Proj proj = {}); // since C++20 436 437 template<input_iterator I, sentinel_for<I> S, class T1, class T2, class Proj = identity> 438 requires indirectly_writable<I, const T2&> && 439 indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*> 440 constexpr I 441 ranges::replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = {}); // since C++20 442 443 template<input_range R, class T1, class T2, class Proj = identity> 444 requires indirectly_writable<iterator_t<R>, const T2&> && 445 indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*> 446 constexpr borrowed_iterator_t<R> 447 ranges::replace(R&& r, const T1& old_value, const T2& new_value, Proj proj = {}); // since C++20 448 449 template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity, 450 indirect_unary_predicate<projected<I, Proj>> Pred> 451 requires indirectly_writable<I, const T&> 452 constexpr I ranges::replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = {}); // since C++20 453 454 template<input_range R, class T, class Proj = identity, 455 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> 456 requires indirectly_writable<iterator_t<R>, const T&> 457 constexpr borrowed_iterator_t<R> 458 ranges::replace_if(R&& r, Pred pred, const T& new_value, Proj proj = {}); // since C++20 459 460 template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2, 461 class Proj1 = identity, class Proj2 = identity, 462 indirect_strict_weak_order<projected<I1, Proj1>, 463 projected<I2, Proj2>> Comp = ranges::less> 464 constexpr bool 465 ranges::lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2, 466 Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 467 468 template<input_range R1, input_range R2, class Proj1 = identity, 469 class Proj2 = identity, 470 indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>, 471 projected<iterator_t<R2>, Proj2>> Comp = ranges::less> 472 constexpr bool 473 ranges::lexicographical_compare(R1&& r1, R2&& r2, Comp comp = {}, 474 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 475 476 template<bidirectional_iterator I1, sentinel_for<I1> S1, bidirectional_iterator I2> 477 requires indirectly_movable<I1, I2> 478 constexpr ranges::move_backward_result<I1, I2> 479 ranges::move_backward(I1 first, S1 last, I2 result); // since C++20 480 481 template<bidirectional_range R, bidirectional_iterator I> 482 requires indirectly_movable<iterator_t<R>, I> 483 constexpr ranges::move_backward_result<borrowed_iterator_t<R>, I> 484 ranges::move_backward(R&& r, I result); // since C++20 485 486 template<input_iterator I, sentinel_for<I> S, weakly_incrementable O> 487 requires indirectly_movable<I, O> 488 constexpr ranges::move_result<I, O> 489 ranges::move(I first, S last, O result); // since C++20 490 491 template<input_range R, weakly_incrementable O> 492 requires indirectly_movable<iterator_t<R>, O> 493 constexpr ranges::move_result<borrowed_iterator_t<R>, O> 494 ranges::move(R&& r, O result); // since C++20 495 496 497} 498 499 constexpr bool // constexpr in C++20 500 all_of(InputIterator first, InputIterator last, Predicate pred); 501 502template <class InputIterator, class Predicate> 503 constexpr bool // constexpr in C++20 504 any_of(InputIterator first, InputIterator last, Predicate pred); 505 506template <class InputIterator, class Predicate> 507 constexpr bool // constexpr in C++20 508 none_of(InputIterator first, InputIterator last, Predicate pred); 509 510template <class InputIterator, class Function> 511 constexpr Function // constexpr in C++20 512 for_each(InputIterator first, InputIterator last, Function f); 513 514template<class InputIterator, class Size, class Function> 515 constexpr InputIterator // constexpr in C++20 516 for_each_n(InputIterator first, Size n, Function f); // C++17 517 518template <class InputIterator, class T> 519 constexpr InputIterator // constexpr in C++20 520 find(InputIterator first, InputIterator last, const T& value); 521 522template <class InputIterator, class Predicate> 523 constexpr InputIterator // constexpr in C++20 524 find_if(InputIterator first, InputIterator last, Predicate pred); 525 526template<class InputIterator, class Predicate> 527 constexpr InputIterator // constexpr in C++20 528 find_if_not(InputIterator first, InputIterator last, Predicate pred); 529 530template <class ForwardIterator1, class ForwardIterator2> 531 constexpr ForwardIterator1 // constexpr in C++20 532 find_end(ForwardIterator1 first1, ForwardIterator1 last1, 533 ForwardIterator2 first2, ForwardIterator2 last2); 534 535template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 536 constexpr ForwardIterator1 // constexpr in C++20 537 find_end(ForwardIterator1 first1, ForwardIterator1 last1, 538 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); 539 540template <class ForwardIterator1, class ForwardIterator2> 541 constexpr ForwardIterator1 // constexpr in C++20 542 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, 543 ForwardIterator2 first2, ForwardIterator2 last2); 544 545template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 546 constexpr ForwardIterator1 // constexpr in C++20 547 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, 548 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); 549 550template <class ForwardIterator> 551 constexpr ForwardIterator // constexpr in C++20 552 adjacent_find(ForwardIterator first, ForwardIterator last); 553 554template <class ForwardIterator, class BinaryPredicate> 555 constexpr ForwardIterator // constexpr in C++20 556 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); 557 558template <class InputIterator, class T> 559 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20 560 count(InputIterator first, InputIterator last, const T& value); 561 562template <class InputIterator, class Predicate> 563 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20 564 count_if(InputIterator first, InputIterator last, Predicate pred); 565 566template <class InputIterator1, class InputIterator2> 567 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 568 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); 569 570template <class InputIterator1, class InputIterator2> 571 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 572 mismatch(InputIterator1 first1, InputIterator1 last1, 573 InputIterator2 first2, InputIterator2 last2); // **C++14** 574 575template <class InputIterator1, class InputIterator2, class BinaryPredicate> 576 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 577 mismatch(InputIterator1 first1, InputIterator1 last1, 578 InputIterator2 first2, BinaryPredicate pred); 579 580template <class InputIterator1, class InputIterator2, class BinaryPredicate> 581 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20 582 mismatch(InputIterator1 first1, InputIterator1 last1, 583 InputIterator2 first2, InputIterator2 last2, 584 BinaryPredicate pred); // **C++14** 585 586template <class InputIterator1, class InputIterator2> 587 constexpr bool // constexpr in C++20 588 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); 589 590template <class InputIterator1, class InputIterator2> 591 constexpr bool // constexpr in C++20 592 equal(InputIterator1 first1, InputIterator1 last1, 593 InputIterator2 first2, InputIterator2 last2); // **C++14** 594 595template <class InputIterator1, class InputIterator2, class BinaryPredicate> 596 constexpr bool // constexpr in C++20 597 equal(InputIterator1 first1, InputIterator1 last1, 598 InputIterator2 first2, BinaryPredicate pred); 599 600template <class InputIterator1, class InputIterator2, class BinaryPredicate> 601 constexpr bool // constexpr in C++20 602 equal(InputIterator1 first1, InputIterator1 last1, 603 InputIterator2 first2, InputIterator2 last2, 604 BinaryPredicate pred); // **C++14** 605 606template<class ForwardIterator1, class ForwardIterator2> 607 constexpr bool // constexpr in C++20 608 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 609 ForwardIterator2 first2); 610 611template<class ForwardIterator1, class ForwardIterator2> 612 constexpr bool // constexpr in C++20 613 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 614 ForwardIterator2 first2, ForwardIterator2 last2); // **C++14** 615 616template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 617 constexpr bool // constexpr in C++20 618 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 619 ForwardIterator2 first2, BinaryPredicate pred); 620 621template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 622 constexpr bool // constexpr in C++20 623 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, 624 ForwardIterator2 first2, ForwardIterator2 last2, 625 BinaryPredicate pred); // **C++14** 626 627template <class ForwardIterator1, class ForwardIterator2> 628 constexpr ForwardIterator1 // constexpr in C++20 629 search(ForwardIterator1 first1, ForwardIterator1 last1, 630 ForwardIterator2 first2, ForwardIterator2 last2); 631 632template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 633 constexpr ForwardIterator1 // constexpr in C++20 634 search(ForwardIterator1 first1, ForwardIterator1 last1, 635 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); 636 637template <class ForwardIterator, class Size, class T> 638 constexpr ForwardIterator // constexpr in C++20 639 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value); 640 641template <class ForwardIterator, class Size, class T, class BinaryPredicate> 642 constexpr ForwardIterator // constexpr in C++20 643 search_n(ForwardIterator first, ForwardIterator last, 644 Size count, const T& value, BinaryPredicate pred); 645 646template <class InputIterator, class OutputIterator> 647 constexpr OutputIterator // constexpr in C++20 648 copy(InputIterator first, InputIterator last, OutputIterator result); 649 650template<class InputIterator, class OutputIterator, class Predicate> 651 constexpr OutputIterator // constexpr in C++20 652 copy_if(InputIterator first, InputIterator last, 653 OutputIterator result, Predicate pred); 654 655template<class InputIterator, class Size, class OutputIterator> 656 constexpr OutputIterator // constexpr in C++20 657 copy_n(InputIterator first, Size n, OutputIterator result); 658 659template <class BidirectionalIterator1, class BidirectionalIterator2> 660 constexpr BidirectionalIterator2 // constexpr in C++20 661 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, 662 BidirectionalIterator2 result); 663 664// [alg.move], move 665template<class InputIterator, class OutputIterator> 666 constexpr OutputIterator move(InputIterator first, InputIterator last, 667 OutputIterator result); 668 669template<class BidirectionalIterator1, class BidirectionalIterator2> 670 constexpr BidirectionalIterator2 671 move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, 672 BidirectionalIterator2 result); 673 674template <class ForwardIterator1, class ForwardIterator2> 675 constexpr ForwardIterator2 // constexpr in C++20 676 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); 677 678namespace ranges { 679 template<class I1, class I2> 680 using swap_ranges_result = in_in_result<I1, I2>; 681 682template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2> 683 requires indirectly_swappable<I1, I2> 684 constexpr ranges::swap_ranges_result<I1, I2> 685 swap_ranges(I1 first1, S1 last1, I2 first2, S2 last2); 686 687template<input_range R1, input_range R2> 688 requires indirectly_swappable<iterator_t<R1>, iterator_t<R2>> 689 constexpr ranges::swap_ranges_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>> 690 swap_ranges(R1&& r1, R2&& r2); 691} 692 693template <class ForwardIterator1, class ForwardIterator2> 694 constexpr void // constexpr in C++20 695 iter_swap(ForwardIterator1 a, ForwardIterator2 b); 696 697template <class InputIterator, class OutputIterator, class UnaryOperation> 698 constexpr OutputIterator // constexpr in C++20 699 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op); 700 701template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> 702 constexpr OutputIterator // constexpr in C++20 703 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, 704 OutputIterator result, BinaryOperation binary_op); 705 706template <class ForwardIterator, class T> 707 constexpr void // constexpr in C++20 708 replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value); 709 710template <class ForwardIterator, class Predicate, class T> 711 constexpr void // constexpr in C++20 712 replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value); 713 714template <class InputIterator, class OutputIterator, class T> 715 constexpr OutputIterator // constexpr in C++20 716 replace_copy(InputIterator first, InputIterator last, OutputIterator result, 717 const T& old_value, const T& new_value); 718 719template <class InputIterator, class OutputIterator, class Predicate, class T> 720 constexpr OutputIterator // constexpr in C++20 721 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value); 722 723template <class ForwardIterator, class T> 724 constexpr void // constexpr in C++20 725 fill(ForwardIterator first, ForwardIterator last, const T& value); 726 727template <class OutputIterator, class Size, class T> 728 constexpr OutputIterator // constexpr in C++20 729 fill_n(OutputIterator first, Size n, const T& value); 730 731template <class ForwardIterator, class Generator> 732 constexpr void // constexpr in C++20 733 generate(ForwardIterator first, ForwardIterator last, Generator gen); 734 735template <class OutputIterator, class Size, class Generator> 736 constexpr OutputIterator // constexpr in C++20 737 generate_n(OutputIterator first, Size n, Generator gen); 738 739template <class ForwardIterator, class T> 740 constexpr ForwardIterator // constexpr in C++20 741 remove(ForwardIterator first, ForwardIterator last, const T& value); 742 743template <class ForwardIterator, class Predicate> 744 constexpr ForwardIterator // constexpr in C++20 745 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred); 746 747template <class InputIterator, class OutputIterator, class T> 748 constexpr OutputIterator // constexpr in C++20 749 remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value); 750 751template <class InputIterator, class OutputIterator, class Predicate> 752 constexpr OutputIterator // constexpr in C++20 753 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred); 754 755template <class ForwardIterator> 756 constexpr ForwardIterator // constexpr in C++20 757 unique(ForwardIterator first, ForwardIterator last); 758 759template <class ForwardIterator, class BinaryPredicate> 760 constexpr ForwardIterator // constexpr in C++20 761 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); 762 763template <class InputIterator, class OutputIterator> 764 constexpr OutputIterator // constexpr in C++20 765 unique_copy(InputIterator first, InputIterator last, OutputIterator result); 766 767template <class InputIterator, class OutputIterator, class BinaryPredicate> 768 constexpr OutputIterator // constexpr in C++20 769 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred); 770 771template <class BidirectionalIterator> 772 constexpr void // constexpr in C++20 773 reverse(BidirectionalIterator first, BidirectionalIterator last); 774 775template <class BidirectionalIterator, class OutputIterator> 776 constexpr OutputIterator // constexpr in C++20 777 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result); 778 779template <class ForwardIterator> 780 constexpr ForwardIterator // constexpr in C++20 781 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); 782 783template <class ForwardIterator, class OutputIterator> 784 constexpr OutputIterator // constexpr in C++20 785 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result); 786 787template <class RandomAccessIterator> 788 void 789 random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17 790 791template <class RandomAccessIterator, class RandomNumberGenerator> 792 void 793 random_shuffle(RandomAccessIterator first, RandomAccessIterator last, 794 RandomNumberGenerator& rand); // deprecated in C++14, removed in C++17 795 796template<class PopulationIterator, class SampleIterator, 797 class Distance, class UniformRandomBitGenerator> 798 SampleIterator sample(PopulationIterator first, PopulationIterator last, 799 SampleIterator out, Distance n, 800 UniformRandomBitGenerator&& g); // C++17 801 802template<class RandomAccessIterator, class UniformRandomNumberGenerator> 803 void shuffle(RandomAccessIterator first, RandomAccessIterator last, 804 UniformRandomNumberGenerator&& g); 805 806template<class ForwardIterator> 807 constexpr ForwardIterator 808 shift_left(ForwardIterator first, ForwardIterator last, 809 typename iterator_traits<ForwardIterator>::difference_type n); // C++20 810 811template<class ForwardIterator> 812 constexpr ForwardIterator 813 shift_right(ForwardIterator first, ForwardIterator last, 814 typename iterator_traits<ForwardIterator>::difference_type n); // C++20 815 816template <class InputIterator, class Predicate> 817 constexpr bool // constexpr in C++20 818 is_partitioned(InputIterator first, InputIterator last, Predicate pred); 819 820template <class ForwardIterator, class Predicate> 821 constexpr ForwardIterator // constexpr in C++20 822 partition(ForwardIterator first, ForwardIterator last, Predicate pred); 823 824template <class InputIterator, class OutputIterator1, 825 class OutputIterator2, class Predicate> 826 constexpr pair<OutputIterator1, OutputIterator2> // constexpr in C++20 827 partition_copy(InputIterator first, InputIterator last, 828 OutputIterator1 out_true, OutputIterator2 out_false, 829 Predicate pred); 830 831template <class ForwardIterator, class Predicate> 832 ForwardIterator 833 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred); 834 835template<class ForwardIterator, class Predicate> 836 constexpr ForwardIterator // constexpr in C++20 837 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred); 838 839template <class ForwardIterator> 840 constexpr bool // constexpr in C++20 841 is_sorted(ForwardIterator first, ForwardIterator last); 842 843template <class ForwardIterator, class Compare> 844 constexpr bool // constexpr in C++20 845 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp); 846 847template<class ForwardIterator> 848 constexpr ForwardIterator // constexpr in C++20 849 is_sorted_until(ForwardIterator first, ForwardIterator last); 850 851template <class ForwardIterator, class Compare> 852 constexpr ForwardIterator // constexpr in C++20 853 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp); 854 855template <class RandomAccessIterator> 856 constexpr void // constexpr in C++20 857 sort(RandomAccessIterator first, RandomAccessIterator last); 858 859template <class RandomAccessIterator, class Compare> 860 constexpr void // constexpr in C++20 861 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 862 863template <class RandomAccessIterator> 864 void 865 stable_sort(RandomAccessIterator first, RandomAccessIterator last); 866 867template <class RandomAccessIterator, class Compare> 868 void 869 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 870 871template <class RandomAccessIterator> 872 constexpr void // constexpr in C++20 873 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); 874 875template <class RandomAccessIterator, class Compare> 876 constexpr void // constexpr in C++20 877 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); 878 879template <class InputIterator, class RandomAccessIterator> 880 constexpr RandomAccessIterator // constexpr in C++20 881 partial_sort_copy(InputIterator first, InputIterator last, 882 RandomAccessIterator result_first, RandomAccessIterator result_last); 883 884template <class InputIterator, class RandomAccessIterator, class Compare> 885 constexpr RandomAccessIterator // constexpr in C++20 886 partial_sort_copy(InputIterator first, InputIterator last, 887 RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp); 888 889template <class RandomAccessIterator> 890 constexpr void // constexpr in C++20 891 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); 892 893template <class RandomAccessIterator, class Compare> 894 constexpr void // constexpr in C++20 895 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); 896 897template <class ForwardIterator, class T> 898 constexpr ForwardIterator // constexpr in C++20 899 lower_bound(ForwardIterator first, ForwardIterator last, const T& value); 900 901template <class ForwardIterator, class T, class Compare> 902 constexpr ForwardIterator // constexpr in C++20 903 lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); 904 905template <class ForwardIterator, class T> 906 constexpr ForwardIterator // constexpr in C++20 907 upper_bound(ForwardIterator first, ForwardIterator last, const T& value); 908 909template <class ForwardIterator, class T, class Compare> 910 constexpr ForwardIterator // constexpr in C++20 911 upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); 912 913template <class ForwardIterator, class T> 914 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20 915 equal_range(ForwardIterator first, ForwardIterator last, const T& value); 916 917template <class ForwardIterator, class T, class Compare> 918 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20 919 equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); 920 921template <class ForwardIterator, class T> 922 constexpr bool // constexpr in C++20 923 binary_search(ForwardIterator first, ForwardIterator last, const T& value); 924 925template <class ForwardIterator, class T, class Compare> 926 constexpr bool // constexpr in C++20 927 binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); 928 929template <class InputIterator1, class InputIterator2, class OutputIterator> 930 constexpr OutputIterator // constexpr in C++20 931 merge(InputIterator1 first1, InputIterator1 last1, 932 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 933 934template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 935 constexpr OutputIterator // constexpr in C++20 936 merge(InputIterator1 first1, InputIterator1 last1, 937 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); 938 939template <class BidirectionalIterator> 940 void 941 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); 942 943template <class BidirectionalIterator, class Compare> 944 void 945 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); 946 947template <class InputIterator1, class InputIterator2> 948 constexpr bool // constexpr in C++20 949 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); 950 951template <class InputIterator1, class InputIterator2, class Compare> 952 constexpr bool // constexpr in C++20 953 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); 954 955template <class InputIterator1, class InputIterator2, class OutputIterator> 956 constexpr OutputIterator // constexpr in C++20 957 set_union(InputIterator1 first1, InputIterator1 last1, 958 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 959 960template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 961 constexpr OutputIterator // constexpr in C++20 962 set_union(InputIterator1 first1, InputIterator1 last1, 963 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); 964 965template <class InputIterator1, class InputIterator2, class OutputIterator> 966 constexpr OutputIterator // constexpr in C++20 967 set_intersection(InputIterator1 first1, InputIterator1 last1, 968 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 969 970template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 971 constexpr OutputIterator // constexpr in C++20 972 set_intersection(InputIterator1 first1, InputIterator1 last1, 973 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); 974 975template <class InputIterator1, class InputIterator2, class OutputIterator> 976 constexpr OutputIterator // constexpr in C++20 977 set_difference(InputIterator1 first1, InputIterator1 last1, 978 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 979 980template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 981 constexpr OutputIterator // constexpr in C++20 982 set_difference(InputIterator1 first1, InputIterator1 last1, 983 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); 984 985template <class InputIterator1, class InputIterator2, class OutputIterator> 986 constexpr OutputIterator // constexpr in C++20 987 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, 988 InputIterator2 first2, InputIterator2 last2, OutputIterator result); 989 990template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 991 constexpr OutputIterator // constexpr in C++20 992 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, 993 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); 994 995template <class RandomAccessIterator> 996 constexpr void // constexpr in C++20 997 push_heap(RandomAccessIterator first, RandomAccessIterator last); 998 999template <class RandomAccessIterator, class Compare> 1000 constexpr void // constexpr in C++20 1001 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 1002 1003template <class RandomAccessIterator> 1004 constexpr void // constexpr in C++20 1005 pop_heap(RandomAccessIterator first, RandomAccessIterator last); 1006 1007template <class RandomAccessIterator, class Compare> 1008 constexpr void // constexpr in C++20 1009 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 1010 1011template <class RandomAccessIterator> 1012 constexpr void // constexpr in C++20 1013 make_heap(RandomAccessIterator first, RandomAccessIterator last); 1014 1015template <class RandomAccessIterator, class Compare> 1016 constexpr void // constexpr in C++20 1017 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 1018 1019template <class RandomAccessIterator> 1020 constexpr void // constexpr in C++20 1021 sort_heap(RandomAccessIterator first, RandomAccessIterator last); 1022 1023template <class RandomAccessIterator, class Compare> 1024 constexpr void // constexpr in C++20 1025 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); 1026 1027template <class RandomAccessIterator> 1028 constexpr bool // constexpr in C++20 1029 is_heap(RandomAccessIterator first, RandomAccessiterator last); 1030 1031template <class RandomAccessIterator, class Compare> 1032 constexpr bool // constexpr in C++20 1033 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp); 1034 1035template <class RandomAccessIterator> 1036 constexpr RandomAccessIterator // constexpr in C++20 1037 is_heap_until(RandomAccessIterator first, RandomAccessiterator last); 1038 1039template <class RandomAccessIterator, class Compare> 1040 constexpr RandomAccessIterator // constexpr in C++20 1041 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp); 1042 1043template <class ForwardIterator> 1044 constexpr ForwardIterator // constexpr in C++14 1045 min_element(ForwardIterator first, ForwardIterator last); 1046 1047template <class ForwardIterator, class Compare> 1048 constexpr ForwardIterator // constexpr in C++14 1049 min_element(ForwardIterator first, ForwardIterator last, Compare comp); 1050 1051template <class T> 1052 constexpr const T& // constexpr in C++14 1053 min(const T& a, const T& b); 1054 1055template <class T, class Compare> 1056 constexpr const T& // constexpr in C++14 1057 min(const T& a, const T& b, Compare comp); 1058 1059template<class T> 1060 constexpr T // constexpr in C++14 1061 min(initializer_list<T> t); 1062 1063template<class T, class Compare> 1064 constexpr T // constexpr in C++14 1065 min(initializer_list<T> t, Compare comp); 1066 1067template<class T> 1068 constexpr const T& clamp(const T& v, const T& lo, const T& hi); // C++17 1069 1070template<class T, class Compare> 1071 constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp); // C++17 1072 1073template <class ForwardIterator> 1074 constexpr ForwardIterator // constexpr in C++14 1075 max_element(ForwardIterator first, ForwardIterator last); 1076 1077template <class ForwardIterator, class Compare> 1078 constexpr ForwardIterator // constexpr in C++14 1079 max_element(ForwardIterator first, ForwardIterator last, Compare comp); 1080 1081template <class T> 1082 constexpr const T& // constexpr in C++14 1083 max(const T& a, const T& b); 1084 1085template <class T, class Compare> 1086 constexpr const T& // constexpr in C++14 1087 max(const T& a, const T& b, Compare comp); 1088 1089template<class T> 1090 constexpr T // constexpr in C++14 1091 max(initializer_list<T> t); 1092 1093template<class T, class Compare> 1094 constexpr T // constexpr in C++14 1095 max(initializer_list<T> t, Compare comp); 1096 1097template<class ForwardIterator> 1098 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14 1099 minmax_element(ForwardIterator first, ForwardIterator last); 1100 1101template<class ForwardIterator, class Compare> 1102 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14 1103 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); 1104 1105template<class T> 1106 constexpr pair<const T&, const T&> // constexpr in C++14 1107 minmax(const T& a, const T& b); 1108 1109template<class T, class Compare> 1110 constexpr pair<const T&, const T&> // constexpr in C++14 1111 minmax(const T& a, const T& b, Compare comp); 1112 1113template<class T> 1114 constexpr pair<T, T> // constexpr in C++14 1115 minmax(initializer_list<T> t); 1116 1117template<class T, class Compare> 1118 constexpr pair<T, T> // constexpr in C++14 1119 minmax(initializer_list<T> t, Compare comp); 1120 1121template <class InputIterator1, class InputIterator2> 1122 constexpr bool // constexpr in C++20 1123 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); 1124 1125template <class InputIterator1, class InputIterator2, class Compare> 1126 constexpr bool // constexpr in C++20 1127 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, 1128 InputIterator2 first2, InputIterator2 last2, Compare comp); 1129 1130template <class BidirectionalIterator> 1131 constexpr bool // constexpr in C++20 1132 next_permutation(BidirectionalIterator first, BidirectionalIterator last); 1133 1134template <class BidirectionalIterator, class Compare> 1135 constexpr bool // constexpr in C++20 1136 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); 1137 1138template <class BidirectionalIterator> 1139 constexpr bool // constexpr in C++20 1140 prev_permutation(BidirectionalIterator first, BidirectionalIterator last); 1141 1142template <class BidirectionalIterator, class Compare> 1143 constexpr bool // constexpr in C++20 1144 prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); 1145} // std 1146 1147*/ 1148 1149#include <__assert> // all public C++ headers provide the assertion handler 1150#include <__bits> 1151#include <__config> 1152#include <__debug> 1153#include <cstddef> 1154#include <cstring> 1155#include <memory> 1156#include <type_traits> 1157#include <version> 1158 1159#include <__algorithm/adjacent_find.h> 1160#include <__algorithm/all_of.h> 1161#include <__algorithm/any_of.h> 1162#include <__algorithm/binary_search.h> 1163#include <__algorithm/clamp.h> 1164#include <__algorithm/comp.h> 1165#include <__algorithm/comp_ref_type.h> 1166#include <__algorithm/copy.h> 1167#include <__algorithm/copy_backward.h> 1168#include <__algorithm/copy_if.h> 1169#include <__algorithm/copy_n.h> 1170#include <__algorithm/count.h> 1171#include <__algorithm/count_if.h> 1172#include <__algorithm/equal.h> 1173#include <__algorithm/equal_range.h> 1174#include <__algorithm/fill.h> 1175#include <__algorithm/fill_n.h> 1176#include <__algorithm/find.h> 1177#include <__algorithm/find_end.h> 1178#include <__algorithm/find_first_of.h> 1179#include <__algorithm/find_if.h> 1180#include <__algorithm/find_if_not.h> 1181#include <__algorithm/for_each.h> 1182#include <__algorithm/for_each_n.h> 1183#include <__algorithm/generate.h> 1184#include <__algorithm/generate_n.h> 1185#include <__algorithm/half_positive.h> 1186#include <__algorithm/in_found_result.h> 1187#include <__algorithm/in_fun_result.h> 1188#include <__algorithm/in_in_out_result.h> 1189#include <__algorithm/in_in_result.h> 1190#include <__algorithm/in_out_out_result.h> 1191#include <__algorithm/in_out_result.h> 1192#include <__algorithm/includes.h> 1193#include <__algorithm/inplace_merge.h> 1194#include <__algorithm/is_heap.h> 1195#include <__algorithm/is_heap_until.h> 1196#include <__algorithm/is_partitioned.h> 1197#include <__algorithm/is_permutation.h> 1198#include <__algorithm/is_sorted.h> 1199#include <__algorithm/is_sorted_until.h> 1200#include <__algorithm/iter_swap.h> 1201#include <__algorithm/lexicographical_compare.h> 1202#include <__algorithm/lower_bound.h> 1203#include <__algorithm/make_heap.h> 1204#include <__algorithm/max.h> 1205#include <__algorithm/max_element.h> 1206#include <__algorithm/merge.h> 1207#include <__algorithm/min.h> 1208#include <__algorithm/min_element.h> 1209#include <__algorithm/min_max_result.h> 1210#include <__algorithm/minmax.h> 1211#include <__algorithm/minmax_element.h> 1212#include <__algorithm/mismatch.h> 1213#include <__algorithm/move.h> 1214#include <__algorithm/move_backward.h> 1215#include <__algorithm/next_permutation.h> 1216#include <__algorithm/none_of.h> 1217#include <__algorithm/nth_element.h> 1218#include <__algorithm/partial_sort.h> 1219#include <__algorithm/partial_sort_copy.h> 1220#include <__algorithm/partition.h> 1221#include <__algorithm/partition_copy.h> 1222#include <__algorithm/partition_point.h> 1223#include <__algorithm/pop_heap.h> 1224#include <__algorithm/prev_permutation.h> 1225#include <__algorithm/push_heap.h> 1226#include <__algorithm/ranges_adjacent_find.h> 1227#include <__algorithm/ranges_all_of.h> 1228#include <__algorithm/ranges_any_of.h> 1229#include <__algorithm/ranges_binary_search.h> 1230#include <__algorithm/ranges_copy.h> 1231#include <__algorithm/ranges_copy_backward.h> 1232#include <__algorithm/ranges_copy_if.h> 1233#include <__algorithm/ranges_copy_n.h> 1234#include <__algorithm/ranges_count.h> 1235#include <__algorithm/ranges_count_if.h> 1236#include <__algorithm/ranges_equal.h> 1237#include <__algorithm/ranges_fill.h> 1238#include <__algorithm/ranges_fill_n.h> 1239#include <__algorithm/ranges_find.h> 1240#include <__algorithm/ranges_find_first_of.h> 1241#include <__algorithm/ranges_find_if.h> 1242#include <__algorithm/ranges_find_if_not.h> 1243#include <__algorithm/ranges_for_each.h> 1244#include <__algorithm/ranges_for_each_n.h> 1245#include <__algorithm/ranges_is_partitioned.h> 1246#include <__algorithm/ranges_is_sorted.h> 1247#include <__algorithm/ranges_is_sorted_until.h> 1248#include <__algorithm/ranges_lexicographical_compare.h> 1249#include <__algorithm/ranges_lower_bound.h> 1250#include <__algorithm/ranges_max.h> 1251#include <__algorithm/ranges_max_element.h> 1252#include <__algorithm/ranges_min.h> 1253#include <__algorithm/ranges_min_element.h> 1254#include <__algorithm/ranges_minmax.h> 1255#include <__algorithm/ranges_minmax_element.h> 1256#include <__algorithm/ranges_mismatch.h> 1257#include <__algorithm/ranges_move.h> 1258#include <__algorithm/ranges_move_backward.h> 1259#include <__algorithm/ranges_none_of.h> 1260#include <__algorithm/ranges_replace.h> 1261#include <__algorithm/ranges_replace_if.h> 1262#include <__algorithm/ranges_reverse.h> 1263#include <__algorithm/ranges_sort.h> 1264#include <__algorithm/ranges_stable_sort.h> 1265#include <__algorithm/ranges_swap_ranges.h> 1266#include <__algorithm/ranges_transform.h> 1267#include <__algorithm/ranges_upper_bound.h> 1268#include <__algorithm/remove.h> 1269#include <__algorithm/remove_copy.h> 1270#include <__algorithm/remove_copy_if.h> 1271#include <__algorithm/remove_if.h> 1272#include <__algorithm/replace.h> 1273#include <__algorithm/replace_copy.h> 1274#include <__algorithm/replace_copy_if.h> 1275#include <__algorithm/replace_if.h> 1276#include <__algorithm/reverse.h> 1277#include <__algorithm/reverse_copy.h> 1278#include <__algorithm/rotate.h> 1279#include <__algorithm/rotate_copy.h> 1280#include <__algorithm/sample.h> 1281#include <__algorithm/search.h> 1282#include <__algorithm/search_n.h> 1283#include <__algorithm/set_difference.h> 1284#include <__algorithm/set_intersection.h> 1285#include <__algorithm/set_symmetric_difference.h> 1286#include <__algorithm/set_union.h> 1287#include <__algorithm/shift_left.h> 1288#include <__algorithm/shift_right.h> 1289#include <__algorithm/shuffle.h> 1290#include <__algorithm/sift_down.h> 1291#include <__algorithm/sort.h> 1292#include <__algorithm/sort_heap.h> 1293#include <__algorithm/stable_partition.h> 1294#include <__algorithm/stable_sort.h> 1295#include <__algorithm/swap_ranges.h> 1296#include <__algorithm/transform.h> 1297#include <__algorithm/unique.h> 1298#include <__algorithm/unique_copy.h> 1299#include <__algorithm/unwrap_iter.h> 1300#include <__algorithm/upper_bound.h> 1301 1302#ifndef _LIBCPP_REMOVE_TRANSITIVE_INCLUDES 1303# include <chrono> 1304# include <iterator> 1305# include <utility> 1306#endif 1307 1308// standard-mandated includes 1309#include <initializer_list> 1310 1311#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 1312# pragma GCC system_header 1313#endif 1314 1315#if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17 1316# include <__pstl_algorithm> 1317#endif 1318 1319#endif // _LIBCPP_ALGORITHM 1320