blob: 785c3ef956c1c79e4763c4617a82635e63c589c4 [file] [log] [blame]
Howard Hinnantc51e1022010-05-11 19:42:16 +00001// -*- C++ -*-
Louis Dionne9bd93882021-11-17 16:25:01 -05002//===----------------------------------------------------------------------===//
Howard Hinnantc51e1022010-05-11 19:42:16 +00003//
Chandler Carruthd2012102019-01-19 10:56:40 +00004// 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
Howard Hinnantc51e1022010-05-11 19:42:16 +00007//
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
Nikolas Klauserf74be4e2022-01-14 02:55:51 +010021namespace ranges {
Konstantin Varlamov89a23f32022-06-28 11:59:59 -070022
23 // [algorithms.results], algorithm result types
Nikolas Klauser671b4752022-02-11 17:01:58 +010024 template <class I, class F>
Nikolas Klauser2e263162022-02-21 22:48:36 +010025 struct in_fun_result; // since C++20
Nikolas Klauser671b4752022-02-11 17:01:58 +010026
Nikolas Klauserf74be4e2022-01-14 02:55:51 +010027 template <class I1, class I2>
Nikolas Klauser2e263162022-02-21 22:48:36 +010028 struct in_in_result; // since C++20
Nikolas Klauser05e2cd82022-01-25 11:21:47 +010029
Konstantin Varlamov89a23f32022-06-28 11:59:59 -070030 template <class I, class O>
31 struct in_out_result; // since C++20
32
Nikolas Klauser05e2cd82022-01-25 11:21:47 +010033 template <class I1, class I2, class O>
Nikolas Klauser2e263162022-02-21 22:48:36 +010034 struct in_in_out_result; // since C++20
Nikolas Klauser61ce8162022-02-03 02:17:03 +010035
36 template <class I, class O1, class O2>
37 struct in_out_out_result; // since C++20
Nikolas Klauser671b4752022-02-11 17:01:58 +010038
Nikolas Klauser2e263162022-02-21 22:48:36 +010039 template <class I1, class I2>
40 struct min_max_result; // since C++20
41
Nikolas Klauserdd5ad212022-02-21 23:07:02 +010042 template <class I>
43 struct in_found_result; // since C++20
44
Nikolas Klauser0a62a172022-02-11 13:11:57 +010045 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 = {});
Nikolas Klauser12fc9bf2022-03-08 23:12:35 +010052
Nikolas Klauser10c612d2022-05-22 13:43:37 +020053 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
Konstantin Varlamov89a23f32022-06-28 11:59:59 -070061 template<class I1, class I2>
62 using mismatch_result = in_in_result<I1, I2>;
63
Nikolas Klauser12fc9bf2022-03-08 23:12:35 +010064 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
Nikolas Klauser37d076e2022-03-12 01:45:35 +010075
Nikolas Klauser37d076e2022-03-12 01:45:35 +010076 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
Nikolas Klauser3559e452022-03-18 02:57:08 +0100101
Nikolas Klauser573cd6f2022-04-03 09:17:01 +0200102 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
Nikolas Klauser3559e452022-03-18 02:57:08 +0100105
Nikolas Klauser573cd6f2022-04-03 09:17:01 +0200106 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
Nikolas Klauser3559e452022-03-18 02:57:08 +0100109
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
Nikolas Klauser573cd6f2022-04-03 09:17:01 +0200115
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
Nikolas Klauser559a1772022-04-05 11:05:36 +0200129
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
Nikolas Klauserf1373d02022-04-07 13:02:02 +0200164
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
Nikolas Klauser0a2f44f2022-04-13 22:59:09 +0200184
Konstantin Varlamov89a23f32022-06-28 11:59:59 -0700185 template<class T>
186 using minmax_result = min_max_result<T>;
187
Nikolas Klauser0a2f44f2022-04-13 22:59:09 +0200188 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
Konstantin Varlamov89a23f32022-06-28 11:59:59 -0700204 template<class I>
205 using minmax_element_result = min_max_result<I>;
206
Nikolas Klauser0a2f44f2022-04-13 22:59:09 +0200207 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
Nikolas Klauserd959d842022-04-15 13:43:40 +0200216
217 template<class I, class O>
Konstantin Varlamov89a23f32022-06-28 11:59:59 -0700218 using copy_result = in_out_result<I, O>; // since C++20
Nikolas Klauserd959d842022-04-15 13:43:40 +0200219
Konstantin Varlamov89a23f32022-06-28 11:59:59 -0700220 template<class I, class O>
221 using copy_n_result = in_out_result<I, O>; // since C++20
Nikolas Klauserd959d842022-04-15 13:43:40 +0200222
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
Nikolas Klauser58de98c2022-05-04 20:27:07 +0200263
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
Nikolas Klauserbb9049d2022-05-04 14:19:09 +0200281
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
Konstantin Varlamov389487d2022-07-08 13:46:27 -0700290 template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
291 class Proj = identity>
292 requires sortable<I, Comp, Proj>
293 constexpr I
294 ranges::push_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
295
296 template<random_access_range R, class Comp = ranges::less, class Proj = identity>
297 requires sortable<iterator_t<R>, Comp, Proj>
298 constexpr borrowed_iterator_t<R>
299 ranges::push_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
300
301 template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
302 class Proj = identity>
303 requires sortable<I, Comp, Proj>
304 constexpr I
305 ranges::pop_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
306
307 template<random_access_range R, class Comp = ranges::less, class Proj = identity>
308 requires sortable<iterator_t<R>, Comp, Proj>
309 constexpr borrowed_iterator_t<R>
310 ranges::pop_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
311
312 template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
313 class Proj = identity>
314 requires sortable<I, Comp, Proj>
315 constexpr I
316 ranges::make_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
317
318 template<random_access_range R, class Comp = ranges::less, class Proj = identity>
319 requires sortable<iterator_t<R>, Comp, Proj>
320 constexpr borrowed_iterator_t<R>
321 ranges::make_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
322
323 template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
324 class Proj = identity>
325 requires sortable<I, Comp, Proj>
326 constexpr I
327 ranges::sort_heap(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
328
329 template<random_access_range R, class Comp = ranges::less, class Proj = identity>
330 requires sortable<iterator_t<R>, Comp, Proj>
331 constexpr borrowed_iterator_t<R>
332 ranges::sort_heap(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
333
Nikolas Klauser52f20072022-05-24 10:32:50 +0200334 template<bidirectional_iterator I, sentinel_for<I> S>
335 requires permutable<I>
336 constexpr I ranges::reverse(I first, S last); // since C++20
337
338 template<bidirectional_range R>
339 requires permutable<iterator_t<R>>
340 constexpr borrowed_iterator_t<R> ranges::reverse(R&& r); // since C++20
341
Konstantin Varlamov55e39a82022-06-16 15:20:53 -0700342 template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
343 class Proj = identity>
344 requires sortable<I, Comp, Proj>
345 constexpr I
Konstantin Varlamovdc3e7822022-07-01 16:34:08 -0700346 ranges::sort(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
Konstantin Varlamov55e39a82022-06-16 15:20:53 -0700347
348 template<random_access_range R, class Comp = ranges::less, class Proj = identity>
349 requires sortable<iterator_t<R>, Comp, Proj>
350 constexpr borrowed_iterator_t<R>
Konstantin Varlamovdc3e7822022-07-01 16:34:08 -0700351 ranges::sort(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
352
353 template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
354 class Proj = identity>
355 requires sortable<I, Comp, Proj>
356 I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
357
358 template<random_access_range R, class Comp = ranges::less, class Proj = identity>
359 requires sortable<iterator_t<R>, Comp, Proj>
360 borrowed_iterator_t<R>
361 ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
Konstantin Varlamov55e39a82022-06-16 15:20:53 -0700362
Nikolas Klausereb49c2a2022-05-21 18:26:29 +0200363 template<class T, output_iterator<const T&> O, sentinel_for<O> S>
364 constexpr O ranges::fill(O first, S last, const T& value); // since C++20
365
366 template<class T, output_range<const T&> R>
367 constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value); // since C++20
368
369 template<class T, output_iterator<const T&> O>
370 constexpr O ranges::fill_n(O first, iter_difference_t<O> n, const T& value); // since C++20
Nikolas Klauser353f1dd2022-05-25 11:09:43 +0200371
372 template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
373 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
374 requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
375 constexpr bool ranges::equal(I1 first1, S1 last1, I2 first2, S2 last2,
376 Pred pred = {},
377 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
378
379 template<input_range R1, input_range R2, class Pred = ranges::equal_to,
380 class Proj1 = identity, class Proj2 = identity>
381 requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
382 constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {},
383 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
384
Nikolas Klausered3f0e82022-05-26 16:42:46 +0200385 template<input_iterator I, sentinel_for<I> S, class Proj = identity,
386 indirect_unary_predicate<projected<I, Proj>> Pred>
387 constexpr bool ranges::all_of(I first, S last, Pred pred, Proj proj = {}); // since C++20
388
389 template<input_range R, class Proj = identity,
390 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
391 constexpr bool ranges::all_of(R&& r, Pred pred, Proj proj = {}); // since C++20
392
393 template<input_iterator I, sentinel_for<I> S, class Proj = identity,
394 indirect_unary_predicate<projected<I, Proj>> Pred>
395 constexpr bool ranges::any_of(I first, S last, Pred pred, Proj proj = {}); // since C++20
396
397 template<input_range R, class Proj = identity,
398 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
399 constexpr bool ranges::any_of(R&& r, Pred pred, Proj proj = {}); // since C++20
400
401 template<input_iterator I, sentinel_for<I> S, class Proj = identity,
402 indirect_unary_predicate<projected<I, Proj>> Pred>
403 constexpr bool ranges::none_of(I first, S last, Pred pred, Proj proj = {}); // since C++20
404
405 template<input_range R, class Proj = identity,
406 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
407 constexpr bool ranges::none_of(R&& r, Pred pred, Proj proj = {}); // since C++20
408
Nikolas Klauserab0b7af2022-05-26 16:08:55 +0200409 template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
410 indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
411 constexpr bool ranges::is_sorted(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
412
413 template<forward_range R, class Proj = identity,
414 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
415 constexpr bool ranges::is_sorted(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
416
417 template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
418 indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
419 constexpr I ranges::is_sorted_until(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
420
421 template<forward_range R, class Proj = identity,
422 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
423 constexpr borrowed_iterator_t<R>
424 ranges::is_sorted_until(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
Nikolas Klauser8b381972022-06-05 21:15:16 +0200425
Konstantin Varlamovf18a9de2022-07-07 20:35:51 -0700426 template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
427 class Proj = identity>
428 requires sortable<I, Comp, Proj>
429 constexpr I
430 ranges::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {}); // since C++20
431
432 template<random_access_range R, class Comp = ranges::less, class Proj = identity>
433 requires sortable<iterator_t<R>, Comp, Proj>
434 constexpr borrowed_iterator_t<R>
435 ranges::nth_element(R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {}); // since C++20
436
Nikolas Klauser8b381972022-06-05 21:15:16 +0200437 template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
438 indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
439 constexpr I upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
440
441 template<forward_range R, class T, class Proj = identity,
442 indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
443 ranges::less>
444 constexpr borrowed_iterator_t<R>
445 upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
446
447 template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
448 indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
449 constexpr I lower_bound(I first, S last, const T& value, Comp comp = {},
450 Proj proj = {}); // since C++20
451 template<forward_range R, class T, class Proj = identity,
452 indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
453 ranges::less>
454 constexpr borrowed_iterator_t<R>
455 lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
456
457 template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
458 indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
459 constexpr bool binary_search(I first, S last, const T& value, Comp comp = {},
460 Proj proj = {}); // since C++20
Nikolas Klauser0a7e46d2022-06-06 13:57:34 +0200461
Nikolas Klauser8b381972022-06-05 21:15:16 +0200462 template<forward_range R, class T, class Proj = identity,
463 indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
464 ranges::less>
465 constexpr bool binary_search(R&& r, const T& value, Comp comp = {},
466 Proj proj = {}); // since C++20
Nikolas Klauser0a7e46d2022-06-06 13:57:34 +0200467 template<input_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
468 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
469 requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
470 constexpr I1 ranges::find_first_of(I1 first1, S1 last1, I2 first2, S2 last2,
471 Pred pred = {},
472 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
473
474 template<input_range R1, forward_range R2,
475 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
476 requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
477 constexpr borrowed_iterator_t<R1>
478 ranges::find_first_of(R1&& r1, R2&& r2,
479 Pred pred = {},
480 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
Nikolas Klauser8b381972022-06-05 21:15:16 +0200481
Nikolas Klauser5ae708f2022-06-08 12:14:12 +0200482 template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
483 indirect_binary_predicate<projected<I, Proj>,
484 projected<I, Proj>> Pred = ranges::equal_to>
485 constexpr I ranges::adjacent_find(I first, S last, Pred pred = {}, Proj proj = {}); // since C+20
486
487 template<forward_range R, class Proj = identity,
488 indirect_binary_predicate<projected<iterator_t<R>, Proj>,
489 projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>
490 constexpr borrowed_iterator_t<R> ranges::adjacent_find(R&& r, Pred pred = {}, Proj proj = {}); // since C++20
491
Nikolas Klauserfadea392022-06-07 09:42:10 +0200492 template<input_iterator I, sentinel_for<I> S, class T1, class T2, class Proj = identity>
493 requires indirectly_writable<I, const T2&> &&
494 indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*>
495 constexpr I
496 ranges::replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = {}); // since C++20
497
498 template<input_range R, class T1, class T2, class Proj = identity>
499 requires indirectly_writable<iterator_t<R>, const T2&> &&
500 indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
501 constexpr borrowed_iterator_t<R>
502 ranges::replace(R&& r, const T1& old_value, const T2& new_value, Proj proj = {}); // since C++20
503
504 template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity,
505 indirect_unary_predicate<projected<I, Proj>> Pred>
506 requires indirectly_writable<I, const T&>
507 constexpr I ranges::replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = {}); // since C++20
508
509 template<input_range R, class T, class Proj = identity,
510 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
511 requires indirectly_writable<iterator_t<R>, const T&>
512 constexpr borrowed_iterator_t<R>
513 ranges::replace_if(R&& r, Pred pred, const T& new_value, Proj proj = {}); // since C++20
514
Nikolas Klauser2fd677c2022-06-15 16:24:43 +0200515 template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
516 class Proj1 = identity, class Proj2 = identity,
517 indirect_strict_weak_order<projected<I1, Proj1>,
518 projected<I2, Proj2>> Comp = ranges::less>
519 constexpr bool
520 ranges::lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2,
521 Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
522
523 template<input_range R1, input_range R2, class Proj1 = identity,
524 class Proj2 = identity,
525 indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
526 projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
527 constexpr bool
528 ranges::lexicographical_compare(R1&& r1, R2&& r2, Comp comp = {},
529 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
530
Nikolas Klauser16661d82022-06-23 12:23:41 +0200531 template<bidirectional_iterator I1, sentinel_for<I1> S1, bidirectional_iterator I2>
532 requires indirectly_movable<I1, I2>
533 constexpr ranges::move_backward_result<I1, I2>
534 ranges::move_backward(I1 first, S1 last, I2 result); // since C++20
535
536 template<bidirectional_range R, bidirectional_iterator I>
537 requires indirectly_movable<iterator_t<R>, I>
538 constexpr ranges::move_backward_result<borrowed_iterator_t<R>, I>
539 ranges::move_backward(R&& r, I result); // since C++20
540
541 template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>
542 requires indirectly_movable<I, O>
543 constexpr ranges::move_result<I, O>
544 ranges::move(I first, S last, O result); // since C++20
545
546 template<input_range R, weakly_incrementable O>
547 requires indirectly_movable<iterator_t<R>, O>
548 constexpr ranges::move_result<borrowed_iterator_t<R>, O>
549 ranges::move(R&& r, O result); // since C++20
550
Hui Xie42bdbb72022-06-26 16:13:43 +0100551 template<class I1, class I2, class O>
552 using merge_result = in_in_out_result<I1, I2, O>; // since C++20
553
554 template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
555 weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity,
556 class Proj2 = identity>
557 requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
558 constexpr merge_result<I1, I2, O>
559 merge(I1 first1, S1 last1, I2 first2, S2 last2, O result,
560 Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
561
562 template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ranges::less,
563 class Proj1 = identity, class Proj2 = identity>
564 requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
565 constexpr merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
566 merge(R1&& r1, R2&& r2, O result,
567 Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
Nikolas Klauser16661d82022-06-23 12:23:41 +0200568
Nikolas Klauser7f52f282022-07-06 14:03:00 +0200569 template<permutable I, sentinel_for<I> S, class T, class Proj = identity>
570 requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
571 constexpr subrange<I> ranges::remove(I first, S last, const T& value, Proj proj = {}); // since C++20
572
573 template<forward_range R, class T, class Proj = identity>
574 requires permutable<iterator_t<R>> &&
575 indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
576 constexpr borrowed_subrange_t<R>
577 ranges::remove(R&& r, const T& value, Proj proj = {}); // since C++20
578
579 template<permutable I, sentinel_for<I> S, class Proj = identity,
580 indirect_unary_predicate<projected<I, Proj>> Pred>
581 constexpr subrange<I> ranges::remove_if(I first, S last, Pred pred, Proj proj = {}); // since C++20
582
583 template<forward_range R, class Proj = identity,
584 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
585 requires permutable<iterator_t<R>>
586 constexpr borrowed_subrange_t<R>
587 ranges::remove_if(R&& r, Pred pred, Proj proj = {}); // since C++20
Hui Xie0ae2eef2022-06-26 16:13:43 +0100588
589 template<class I, class O>
590 using set_difference_result = in_out_result<I, O>; // since C++20
591
592 template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
593 weakly_incrementable O, class Comp = ranges::less,
594 class Proj1 = identity, class Proj2 = identity>
595 requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
596 constexpr set_difference_result<I1, O>
597 set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
598 Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
599
600 template<input_range R1, input_range R2, weakly_incrementable O,
601 class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
602 requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
603 constexpr set_difference_result<borrowed_iterator_t<R1>, O>
604 set_difference(R1&& r1, R2&& r2, O result,
605 Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
Nikolas Klauser7f52f282022-07-06 14:03:00 +0200606
Nikolas Klauserf74be4e2022-01-14 02:55:51 +0100607}
608
Marshall Clowd607fdb2018-01-15 17:20:36 +0000609 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000610 all_of(InputIterator first, InputIterator last, Predicate pred);
611
612template <class InputIterator, class Predicate>
Marshall Clowd607fdb2018-01-15 17:20:36 +0000613 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000614 any_of(InputIterator first, InputIterator last, Predicate pred);
615
616template <class InputIterator, class Predicate>
Marshall Clowd607fdb2018-01-15 17:20:36 +0000617 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000618 none_of(InputIterator first, InputIterator last, Predicate pred);
619
620template <class InputIterator, class Function>
Marshall Clow5492c8a2018-01-22 20:44:33 +0000621 constexpr Function // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000622 for_each(InputIterator first, InputIterator last, Function f);
623
Marshall Clowde0169c2017-05-25 02:29:54 +0000624template<class InputIterator, class Size, class Function>
Marshall Clow5492c8a2018-01-22 20:44:33 +0000625 constexpr InputIterator // constexpr in C++20
626 for_each_n(InputIterator first, Size n, Function f); // C++17
Marshall Clowde0169c2017-05-25 02:29:54 +0000627
Howard Hinnantc51e1022010-05-11 19:42:16 +0000628template <class InputIterator, class T>
Marshall Clowee0161e2018-01-15 19:26:05 +0000629 constexpr InputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000630 find(InputIterator first, InputIterator last, const T& value);
631
632template <class InputIterator, class Predicate>
Marshall Clowee0161e2018-01-15 19:26:05 +0000633 constexpr InputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000634 find_if(InputIterator first, InputIterator last, Predicate pred);
635
636template<class InputIterator, class Predicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500637 constexpr InputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000638 find_if_not(InputIterator first, InputIterator last, Predicate pred);
639
640template <class ForwardIterator1, class ForwardIterator2>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500641 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000642 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
643 ForwardIterator2 first2, ForwardIterator2 last2);
644
645template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500646 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000647 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
648 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
649
650template <class ForwardIterator1, class ForwardIterator2>
Marshall Clowee0161e2018-01-15 19:26:05 +0000651 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000652 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
653 ForwardIterator2 first2, ForwardIterator2 last2);
654
655template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clowee0161e2018-01-15 19:26:05 +0000656 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000657 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
658 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
659
660template <class ForwardIterator>
Marshall Clowee0161e2018-01-15 19:26:05 +0000661 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000662 adjacent_find(ForwardIterator first, ForwardIterator last);
663
664template <class ForwardIterator, class BinaryPredicate>
Marshall Clowee0161e2018-01-15 19:26:05 +0000665 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000666 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
667
668template <class InputIterator, class T>
Marshall Clow3c0558f2018-01-15 19:40:34 +0000669 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000670 count(InputIterator first, InputIterator last, const T& value);
671
672template <class InputIterator, class Predicate>
Marshall Clow3c0558f2018-01-15 19:40:34 +0000673 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000674 count_if(InputIterator first, InputIterator last, Predicate pred);
675
676template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000677 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000678 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
679
Marshall Clow96b42b22013-05-09 21:14:23 +0000680template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000681 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Aditya Kumar3a0179a2016-08-25 11:52:38 +0000682 mismatch(InputIterator1 first1, InputIterator1 last1,
Marshall Clow96b42b22013-05-09 21:14:23 +0000683 InputIterator2 first2, InputIterator2 last2); // **C++14**
684
Howard Hinnantc51e1022010-05-11 19:42:16 +0000685template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000686 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000687 mismatch(InputIterator1 first1, InputIterator1 last1,
688 InputIterator2 first2, BinaryPredicate pred);
689
Marshall Clow96b42b22013-05-09 21:14:23 +0000690template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000691 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000692 mismatch(InputIterator1 first1, InputIterator1 last1,
693 InputIterator2 first2, InputIterator2 last2,
694 BinaryPredicate pred); // **C++14**
695
Howard Hinnantc51e1022010-05-11 19:42:16 +0000696template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000697 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000698 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
699
Marshall Clow96b42b22013-05-09 21:14:23 +0000700template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000701 constexpr bool // constexpr in C++20
Aditya Kumar3a0179a2016-08-25 11:52:38 +0000702 equal(InputIterator1 first1, InputIterator1 last1,
Marshall Clow96b42b22013-05-09 21:14:23 +0000703 InputIterator2 first2, InputIterator2 last2); // **C++14**
704
Howard Hinnantc51e1022010-05-11 19:42:16 +0000705template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000706 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000707 equal(InputIterator1 first1, InputIterator1 last1,
708 InputIterator2 first2, BinaryPredicate pred);
709
Marshall Clow96b42b22013-05-09 21:14:23 +0000710template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000711 constexpr bool // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000712 equal(InputIterator1 first1, InputIterator1 last1,
713 InputIterator2 first2, InputIterator2 last2,
714 BinaryPredicate pred); // **C++14**
715
Howard Hinnantc51e1022010-05-11 19:42:16 +0000716template<class ForwardIterator1, class ForwardIterator2>
Marshall Clow96d050a2018-01-15 16:16:32 +0000717 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000718 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
719 ForwardIterator2 first2);
720
Marshall Clow96b42b22013-05-09 21:14:23 +0000721template<class ForwardIterator1, class ForwardIterator2>
Marshall Clow96d050a2018-01-15 16:16:32 +0000722 constexpr bool // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000723 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
724 ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**
725
Howard Hinnantc51e1022010-05-11 19:42:16 +0000726template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clow96d050a2018-01-15 16:16:32 +0000727 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000728 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
729 ForwardIterator2 first2, BinaryPredicate pred);
730
Marshall Clow96b42b22013-05-09 21:14:23 +0000731template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clow96d050a2018-01-15 16:16:32 +0000732 constexpr bool // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000733 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
734 ForwardIterator2 first2, ForwardIterator2 last2,
735 BinaryPredicate pred); // **C++14**
736
Howard Hinnantc51e1022010-05-11 19:42:16 +0000737template <class ForwardIterator1, class ForwardIterator2>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000738 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000739 search(ForwardIterator1 first1, ForwardIterator1 last1,
740 ForwardIterator2 first2, ForwardIterator2 last2);
741
742template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000743 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000744 search(ForwardIterator1 first1, ForwardIterator1 last1,
745 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
746
747template <class ForwardIterator, class Size, class T>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000748 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000749 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
750
751template <class ForwardIterator, class Size, class T, class BinaryPredicate>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000752 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000753 search_n(ForwardIterator first, ForwardIterator last,
754 Size count, const T& value, BinaryPredicate pred);
755
756template <class InputIterator, class OutputIterator>
Louis Dionne65b433b2019-11-06 12:02:41 +0000757 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000758 copy(InputIterator first, InputIterator last, OutputIterator result);
759
760template<class InputIterator, class OutputIterator, class Predicate>
Louis Dionne65b433b2019-11-06 12:02:41 +0000761 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000762 copy_if(InputIterator first, InputIterator last,
763 OutputIterator result, Predicate pred);
764
765template<class InputIterator, class Size, class OutputIterator>
Louis Dionne65b433b2019-11-06 12:02:41 +0000766 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000767 copy_n(InputIterator first, Size n, OutputIterator result);
768
769template <class BidirectionalIterator1, class BidirectionalIterator2>
Louis Dionne65b433b2019-11-06 12:02:41 +0000770 constexpr BidirectionalIterator2 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000771 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
772 BidirectionalIterator2 result);
773
Konstantin Varlamov89a23f32022-06-28 11:59:59 -0700774// [alg.move], move
775template<class InputIterator, class OutputIterator>
776 constexpr OutputIterator move(InputIterator first, InputIterator last,
777 OutputIterator result);
778
779template<class BidirectionalIterator1, class BidirectionalIterator2>
780 constexpr BidirectionalIterator2
781 move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
782 BidirectionalIterator2 result);
783
Howard Hinnantc51e1022010-05-11 19:42:16 +0000784template <class ForwardIterator1, class ForwardIterator2>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500785 constexpr ForwardIterator2 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000786 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
787
Konstantin Varlamov89a23f32022-06-28 11:59:59 -0700788namespace ranges {
789 template<class I1, class I2>
790 using swap_ranges_result = in_in_result<I1, I2>;
791
Nikolas Klauser4ceab5f2022-02-10 13:33:03 +0100792template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2>
793 requires indirectly_swappable<I1, I2>
794 constexpr ranges::swap_ranges_result<I1, I2>
Konstantin Varlamov89a23f32022-06-28 11:59:59 -0700795 swap_ranges(I1 first1, S1 last1, I2 first2, S2 last2);
Nikolas Klauser4ceab5f2022-02-10 13:33:03 +0100796
797template<input_range R1, input_range R2>
798 requires indirectly_swappable<iterator_t<R1>, iterator_t<R2>>
799 constexpr ranges::swap_ranges_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
Konstantin Varlamov89a23f32022-06-28 11:59:59 -0700800 swap_ranges(R1&& r1, R2&& r2);
801}
Nikolas Klauser4ceab5f2022-02-10 13:33:03 +0100802
Howard Hinnantc51e1022010-05-11 19:42:16 +0000803template <class ForwardIterator1, class ForwardIterator2>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500804 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000805 iter_swap(ForwardIterator1 a, ForwardIterator2 b);
806
807template <class InputIterator, class OutputIterator, class UnaryOperation>
Marshall Clow31427c62018-01-19 17:45:39 +0000808 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000809 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
810
811template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
Marshall Clow31427c62018-01-19 17:45:39 +0000812 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000813 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
814 OutputIterator result, BinaryOperation binary_op);
815
816template <class ForwardIterator, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000817 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000818 replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
819
820template <class ForwardIterator, class Predicate, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000821 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000822 replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
823
824template <class InputIterator, class OutputIterator, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000825 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000826 replace_copy(InputIterator first, InputIterator last, OutputIterator result,
827 const T& old_value, const T& new_value);
828
829template <class InputIterator, class OutputIterator, class Predicate, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000830 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000831 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
832
833template <class ForwardIterator, class T>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000834 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000835 fill(ForwardIterator first, ForwardIterator last, const T& value);
836
837template <class OutputIterator, class Size, class T>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000838 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000839 fill_n(OutputIterator first, Size n, const T& value);
840
841template <class ForwardIterator, class Generator>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000842 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000843 generate(ForwardIterator first, ForwardIterator last, Generator gen);
844
845template <class OutputIterator, class Size, class Generator>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000846 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000847 generate_n(OutputIterator first, Size n, Generator gen);
848
849template <class ForwardIterator, class T>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000850 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000851 remove(ForwardIterator first, ForwardIterator last, const T& value);
852
853template <class ForwardIterator, class Predicate>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000854 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000855 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
856
857template <class InputIterator, class OutputIterator, class T>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000858 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000859 remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
860
861template <class InputIterator, class OutputIterator, class Predicate>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000862 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000863 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
864
865template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500866 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000867 unique(ForwardIterator first, ForwardIterator last);
868
869template <class ForwardIterator, class BinaryPredicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500870 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000871 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
872
873template <class InputIterator, class OutputIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500874 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000875 unique_copy(InputIterator first, InputIterator last, OutputIterator result);
876
877template <class InputIterator, class OutputIterator, class BinaryPredicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500878 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000879 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
880
881template <class BidirectionalIterator>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -0500882 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000883 reverse(BidirectionalIterator first, BidirectionalIterator last);
884
885template <class BidirectionalIterator, class OutputIterator>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000886 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000887 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
888
889template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500890 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000891 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
892
893template <class ForwardIterator, class OutputIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500894 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000895 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
896
897template <class RandomAccessIterator>
898 void
Marshall Clowfac06e52017-03-23 13:43:37 +0000899 random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000900
901template <class RandomAccessIterator, class RandomNumberGenerator>
902 void
Marshall Clow83f35392014-03-03 06:14:19 +0000903 random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
Marshall Clowfac06e52017-03-23 13:43:37 +0000904 RandomNumberGenerator& rand); // deprecated in C++14, removed in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000905
Eric Fiselier1208fcd2016-08-28 22:14:37 +0000906template<class PopulationIterator, class SampleIterator,
907 class Distance, class UniformRandomBitGenerator>
908 SampleIterator sample(PopulationIterator first, PopulationIterator last,
909 SampleIterator out, Distance n,
910 UniformRandomBitGenerator&& g); // C++17
911
Howard Hinnant578ac0f2010-05-26 17:49:34 +0000912template<class RandomAccessIterator, class UniformRandomNumberGenerator>
913 void shuffle(RandomAccessIterator first, RandomAccessIterator last,
Howard Hinnanta5e71782010-11-18 01:47:02 +0000914 UniformRandomNumberGenerator&& g);
Howard Hinnant578ac0f2010-05-26 17:49:34 +0000915
Arthur O'Dwyercea050d2020-12-26 01:39:03 -0500916template<class ForwardIterator>
917 constexpr ForwardIterator
918 shift_left(ForwardIterator first, ForwardIterator last,
919 typename iterator_traits<ForwardIterator>::difference_type n); // C++20
920
921template<class ForwardIterator>
922 constexpr ForwardIterator
923 shift_right(ForwardIterator first, ForwardIterator last,
924 typename iterator_traits<ForwardIterator>::difference_type n); // C++20
925
Howard Hinnantc51e1022010-05-11 19:42:16 +0000926template <class InputIterator, class Predicate>
Marshall Clow96d050a2018-01-15 16:16:32 +0000927 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000928 is_partitioned(InputIterator first, InputIterator last, Predicate pred);
929
930template <class ForwardIterator, class Predicate>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -0500931 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000932 partition(ForwardIterator first, ForwardIterator last, Predicate pred);
933
934template <class InputIterator, class OutputIterator1,
935 class OutputIterator2, class Predicate>
Marshall Clow5492c8a2018-01-22 20:44:33 +0000936 constexpr pair<OutputIterator1, OutputIterator2> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000937 partition_copy(InputIterator first, InputIterator last,
938 OutputIterator1 out_true, OutputIterator2 out_false,
939 Predicate pred);
940
941template <class ForwardIterator, class Predicate>
942 ForwardIterator
943 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
944
945template<class ForwardIterator, class Predicate>
Marshall Clowe00916c2018-01-16 02:34:41 +0000946 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000947 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
948
949template <class ForwardIterator>
Marshall Clow96d050a2018-01-15 16:16:32 +0000950 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000951 is_sorted(ForwardIterator first, ForwardIterator last);
952
953template <class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500954 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000955 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
956
957template<class ForwardIterator>
Marshall Clow3c0558f2018-01-15 19:40:34 +0000958 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000959 is_sorted_until(ForwardIterator first, ForwardIterator last);
960
961template <class ForwardIterator, class Compare>
Marshall Clow3c0558f2018-01-15 19:40:34 +0000962 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000963 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
964
965template <class RandomAccessIterator>
Arthur O'Dwyer1bb0f672020-12-20 15:21:42 -0500966 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000967 sort(RandomAccessIterator first, RandomAccessIterator last);
968
969template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer1bb0f672020-12-20 15:21:42 -0500970 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000971 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
972
973template <class RandomAccessIterator>
974 void
975 stable_sort(RandomAccessIterator first, RandomAccessIterator last);
976
977template <class RandomAccessIterator, class Compare>
978 void
979 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
980
981template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500982 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000983 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
984
985template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500986 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000987 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
988
989template <class InputIterator, class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500990 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000991 partial_sort_copy(InputIterator first, InputIterator last,
992 RandomAccessIterator result_first, RandomAccessIterator result_last);
993
994template <class InputIterator, class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500995 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000996 partial_sort_copy(InputIterator first, InputIterator last,
997 RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
998
999template <class RandomAccessIterator>
Arthur O'Dwyer4f5717b2021-02-04 18:12:52 -05001000 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001001 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
1002
1003template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer4f5717b2021-02-04 18:12:52 -05001004 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001005 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
1006
1007template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +00001008 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001009 lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
1010
1011template <class ForwardIterator, class T, class Compare>
Marshall Clowe00916c2018-01-16 02:34:41 +00001012 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001013 lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
1014
1015template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +00001016 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001017 upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
1018
1019template <class ForwardIterator, class T, class Compare>
Marshall Clowe00916c2018-01-16 02:34:41 +00001020 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001021 upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
1022
1023template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +00001024 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001025 equal_range(ForwardIterator first, ForwardIterator last, const T& value);
1026
1027template <class ForwardIterator, class T, class Compare>
Marshall Clowe00916c2018-01-16 02:34:41 +00001028 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001029 equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
1030
1031template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +00001032 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001033 binary_search(ForwardIterator first, ForwardIterator last, const T& value);
1034
1035template <class ForwardIterator, class T, class Compare>
Marshall Clowc0b7f972018-01-22 23:10:40 +00001036 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001037 binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
1038
1039template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001040 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001041 merge(InputIterator1 first1, InputIterator1 last1,
1042 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
1043
1044template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001045 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001046 merge(InputIterator1 first1, InputIterator1 last1,
1047 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
1048
1049template <class BidirectionalIterator>
1050 void
1051 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
1052
1053template <class BidirectionalIterator, class Compare>
1054 void
1055 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
1056
1057template <class InputIterator1, class InputIterator2>
Marshall Clowc0b7f972018-01-22 23:10:40 +00001058 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001059 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
1060
1061template <class InputIterator1, class InputIterator2, class Compare>
Marshall Clowc0b7f972018-01-22 23:10:40 +00001062 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001063 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
1064
1065template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001066 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001067 set_union(InputIterator1 first1, InputIterator1 last1,
1068 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
1069
1070template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001071 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001072 set_union(InputIterator1 first1, InputIterator1 last1,
1073 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
1074
1075template <class InputIterator1, class InputIterator2, class OutputIterator>
Marshall Clowc0b7f972018-01-22 23:10:40 +00001076 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001077 set_intersection(InputIterator1 first1, InputIterator1 last1,
1078 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
1079
1080template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Marshall Clowc0b7f972018-01-22 23:10:40 +00001081 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001082 set_intersection(InputIterator1 first1, InputIterator1 last1,
1083 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
1084
1085template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001086 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001087 set_difference(InputIterator1 first1, InputIterator1 last1,
1088 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
1089
1090template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001091 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001092 set_difference(InputIterator1 first1, InputIterator1 last1,
1093 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
1094
1095template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001096 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001097 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
1098 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
1099
1100template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001101 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001102 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
1103 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
1104
1105template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001106 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001107 push_heap(RandomAccessIterator first, RandomAccessIterator last);
1108
1109template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001110 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001111 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1112
1113template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001114 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001115 pop_heap(RandomAccessIterator first, RandomAccessIterator last);
1116
1117template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001118 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001119 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1120
1121template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001122 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001123 make_heap(RandomAccessIterator first, RandomAccessIterator last);
1124
1125template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001126 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001127 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1128
1129template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001130 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001131 sort_heap(RandomAccessIterator first, RandomAccessIterator last);
1132
1133template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001134 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001135 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1136
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001137template <class RandomAccessIterator>
Marshall Clow96d050a2018-01-15 16:16:32 +00001138 constexpr bool // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001139 is_heap(RandomAccessIterator first, RandomAccessiterator last);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001140
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001141template <class RandomAccessIterator, class Compare>
Marshall Clow96d050a2018-01-15 16:16:32 +00001142 constexpr bool // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001143 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001144
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001145template <class RandomAccessIterator>
Marshall Clow96d050a2018-01-15 16:16:32 +00001146 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001147 is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001148
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001149template <class RandomAccessIterator, class Compare>
Marshall Clow96d050a2018-01-15 16:16:32 +00001150 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001151 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001152
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001153template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001154 constexpr ForwardIterator // constexpr in C++14
1155 min_element(ForwardIterator first, ForwardIterator last);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001156
1157template <class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001158 constexpr ForwardIterator // constexpr in C++14
1159 min_element(ForwardIterator first, ForwardIterator last, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001160
Howard Hinnantc51e1022010-05-11 19:42:16 +00001161template <class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001162 constexpr const T& // constexpr in C++14
1163 min(const T& a, const T& b);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001164
1165template <class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001166 constexpr const T& // constexpr in C++14
1167 min(const T& a, const T& b, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001168
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001169template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001170 constexpr T // constexpr in C++14
1171 min(initializer_list<T> t);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001172
1173template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001174 constexpr T // constexpr in C++14
1175 min(initializer_list<T> t, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001176
Marshall Clow3e18d0e2016-03-07 22:43:49 +00001177template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001178 constexpr const T& clamp(const T& v, const T& lo, const T& hi); // C++17
Marshall Clow3e18d0e2016-03-07 22:43:49 +00001179
1180template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001181 constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp); // C++17
Marshall Clow3e18d0e2016-03-07 22:43:49 +00001182
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001183template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001184 constexpr ForwardIterator // constexpr in C++14
1185 max_element(ForwardIterator first, ForwardIterator last);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001186
1187template <class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001188 constexpr ForwardIterator // constexpr in C++14
1189 max_element(ForwardIterator first, ForwardIterator last, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001190
Howard Hinnantc51e1022010-05-11 19:42:16 +00001191template <class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001192 constexpr const T& // constexpr in C++14
1193 max(const T& a, const T& b);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001194
1195template <class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001196 constexpr const T& // constexpr in C++14
1197 max(const T& a, const T& b, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001198
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001199template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001200 constexpr T // constexpr in C++14
1201 max(initializer_list<T> t);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001202
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001203template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001204 constexpr T // constexpr in C++14
1205 max(initializer_list<T> t, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001206
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001207template<class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001208 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14
1209 minmax_element(ForwardIterator first, ForwardIterator last);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001210
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001211template<class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001212 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14
1213 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001214
1215template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001216 constexpr pair<const T&, const T&> // constexpr in C++14
1217 minmax(const T& a, const T& b);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001218
1219template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001220 constexpr pair<const T&, const T&> // constexpr in C++14
1221 minmax(const T& a, const T& b, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001222
1223template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001224 constexpr pair<T, T> // constexpr in C++14
1225 minmax(initializer_list<T> t);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001226
1227template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001228 constexpr pair<T, T> // constexpr in C++14
1229 minmax(initializer_list<T> t, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001230
1231template <class InputIterator1, class InputIterator2>
Marshall Clow5492c8a2018-01-22 20:44:33 +00001232 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001233 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
1234
1235template <class InputIterator1, class InputIterator2, class Compare>
Marshall Clow5492c8a2018-01-22 20:44:33 +00001236 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001237 lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
1238 InputIterator2 first2, InputIterator2 last2, Compare comp);
1239
1240template <class BidirectionalIterator>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -05001241 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001242 next_permutation(BidirectionalIterator first, BidirectionalIterator last);
1243
1244template <class BidirectionalIterator, class Compare>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -05001245 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001246 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
1247
1248template <class BidirectionalIterator>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -05001249 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001250 prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
1251
1252template <class BidirectionalIterator, class Compare>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -05001253 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001254 prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001255} // std
1256
1257*/
1258
Louis Dionneb4fce352022-03-25 12:55:36 -04001259#include <__assert> // all public C++ headers provide the assertion handler
Arthur O'Dwyer3693d7a2022-02-04 13:09:30 -05001260#include <__bits>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001261#include <__config>
Louis Dionnea60dd872021-06-17 11:30:11 -04001262#include <__debug>
Howard Hinnant60e5cf42012-07-26 17:09:09 +00001263#include <cstddef>
Arthur O'Dwyeref181602021-05-19 11:57:04 -04001264#include <cstring>
Arthur O'Dwyeref181602021-05-19 11:57:04 -04001265#include <memory>
1266#include <type_traits>
Marshall Clow0a1e7502018-09-12 19:41:40 +00001267#include <version>
Howard Hinnantea382952013-08-14 18:00:20 +00001268
Louis Dionnea60dd872021-06-17 11:30:11 -04001269#include <__algorithm/adjacent_find.h>
1270#include <__algorithm/all_of.h>
1271#include <__algorithm/any_of.h>
1272#include <__algorithm/binary_search.h>
1273#include <__algorithm/clamp.h>
1274#include <__algorithm/comp.h>
1275#include <__algorithm/comp_ref_type.h>
1276#include <__algorithm/copy.h>
1277#include <__algorithm/copy_backward.h>
1278#include <__algorithm/copy_if.h>
1279#include <__algorithm/copy_n.h>
1280#include <__algorithm/count.h>
1281#include <__algorithm/count_if.h>
1282#include <__algorithm/equal.h>
1283#include <__algorithm/equal_range.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001284#include <__algorithm/fill.h>
Arthur O'Dwyer65077c02022-01-07 09:45:05 -05001285#include <__algorithm/fill_n.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001286#include <__algorithm/find.h>
1287#include <__algorithm/find_end.h>
1288#include <__algorithm/find_first_of.h>
1289#include <__algorithm/find_if.h>
1290#include <__algorithm/find_if_not.h>
1291#include <__algorithm/for_each.h>
1292#include <__algorithm/for_each_n.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001293#include <__algorithm/generate.h>
Arthur O'Dwyer65077c02022-01-07 09:45:05 -05001294#include <__algorithm/generate_n.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001295#include <__algorithm/half_positive.h>
Nikolas Klauserdd5ad212022-02-21 23:07:02 +01001296#include <__algorithm/in_found_result.h>
Nikolas Klauser671b4752022-02-11 17:01:58 +01001297#include <__algorithm/in_fun_result.h>
Nikolas Klauser05e2cd82022-01-25 11:21:47 +01001298#include <__algorithm/in_in_out_result.h>
Nikolas Klauserf74be4e2022-01-14 02:55:51 +01001299#include <__algorithm/in_in_result.h>
Nikolas Klauser61ce8162022-02-03 02:17:03 +01001300#include <__algorithm/in_out_out_result.h>
Konstantin Varlamov74736812022-01-10 22:49:37 -08001301#include <__algorithm/in_out_result.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001302#include <__algorithm/includes.h>
1303#include <__algorithm/inplace_merge.h>
1304#include <__algorithm/is_heap.h>
1305#include <__algorithm/is_heap_until.h>
1306#include <__algorithm/is_partitioned.h>
1307#include <__algorithm/is_permutation.h>
1308#include <__algorithm/is_sorted.h>
1309#include <__algorithm/is_sorted_until.h>
Christopher Di Bella41f26e82021-06-05 02:47:47 +00001310#include <__algorithm/iter_swap.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001311#include <__algorithm/lexicographical_compare.h>
1312#include <__algorithm/lower_bound.h>
1313#include <__algorithm/make_heap.h>
1314#include <__algorithm/max.h>
1315#include <__algorithm/max_element.h>
1316#include <__algorithm/merge.h>
1317#include <__algorithm/min.h>
1318#include <__algorithm/min_element.h>
Nikolas Klauser2e263162022-02-21 22:48:36 +01001319#include <__algorithm/min_max_result.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001320#include <__algorithm/minmax.h>
1321#include <__algorithm/minmax_element.h>
1322#include <__algorithm/mismatch.h>
1323#include <__algorithm/move.h>
1324#include <__algorithm/move_backward.h>
1325#include <__algorithm/next_permutation.h>
1326#include <__algorithm/none_of.h>
1327#include <__algorithm/nth_element.h>
1328#include <__algorithm/partial_sort.h>
1329#include <__algorithm/partial_sort_copy.h>
1330#include <__algorithm/partition.h>
1331#include <__algorithm/partition_copy.h>
1332#include <__algorithm/partition_point.h>
1333#include <__algorithm/pop_heap.h>
1334#include <__algorithm/prev_permutation.h>
1335#include <__algorithm/push_heap.h>
Nikolas Klauser5ae708f2022-06-08 12:14:12 +02001336#include <__algorithm/ranges_adjacent_find.h>
Nikolas Klausered3f0e82022-05-26 16:42:46 +02001337#include <__algorithm/ranges_all_of.h>
1338#include <__algorithm/ranges_any_of.h>
Nikolas Klauser8b381972022-06-05 21:15:16 +02001339#include <__algorithm/ranges_binary_search.h>
Nikolas Klauserd959d842022-04-15 13:43:40 +02001340#include <__algorithm/ranges_copy.h>
1341#include <__algorithm/ranges_copy_backward.h>
1342#include <__algorithm/ranges_copy_if.h>
1343#include <__algorithm/ranges_copy_n.h>
Nikolas Klauserf1373d02022-04-07 13:02:02 +02001344#include <__algorithm/ranges_count.h>
1345#include <__algorithm/ranges_count_if.h>
Nikolas Klauser353f1dd2022-05-25 11:09:43 +02001346#include <__algorithm/ranges_equal.h>
Nikolas Klausereb49c2a2022-05-21 18:26:29 +02001347#include <__algorithm/ranges_fill.h>
1348#include <__algorithm/ranges_fill_n.h>
Nikolas Klauser37d076e2022-03-12 01:45:35 +01001349#include <__algorithm/ranges_find.h>
Nikolas Klauser0a7e46d2022-06-06 13:57:34 +02001350#include <__algorithm/ranges_find_first_of.h>
Nikolas Klauser37d076e2022-03-12 01:45:35 +01001351#include <__algorithm/ranges_find_if.h>
1352#include <__algorithm/ranges_find_if_not.h>
Nikolas Klauser58de98c2022-05-04 20:27:07 +02001353#include <__algorithm/ranges_for_each.h>
1354#include <__algorithm/ranges_for_each_n.h>
Nikolas Klauserbb9049d2022-05-04 14:19:09 +02001355#include <__algorithm/ranges_is_partitioned.h>
Nikolas Klauserab0b7af2022-05-26 16:08:55 +02001356#include <__algorithm/ranges_is_sorted.h>
1357#include <__algorithm/ranges_is_sorted_until.h>
Nikolas Klauser2fd677c2022-06-15 16:24:43 +02001358#include <__algorithm/ranges_lexicographical_compare.h>
Nikolas Klauser8b381972022-06-05 21:15:16 +02001359#include <__algorithm/ranges_lower_bound.h>
Konstantin Varlamov389487d2022-07-08 13:46:27 -07001360#include <__algorithm/ranges_make_heap.h>
Nikolas Klauser573cd6f2022-04-03 09:17:01 +02001361#include <__algorithm/ranges_max.h>
Nikolas Klauserf2a69ea2022-03-07 17:01:52 +01001362#include <__algorithm/ranges_max_element.h>
Hui Xie42bdbb72022-06-26 16:13:43 +01001363#include <__algorithm/ranges_merge.h>
Nikolas Klauser3559e452022-03-18 02:57:08 +01001364#include <__algorithm/ranges_min.h>
Nikolas Klauser0a62a172022-02-11 13:11:57 +01001365#include <__algorithm/ranges_min_element.h>
Nikolas Klauser0a2f44f2022-04-13 22:59:09 +02001366#include <__algorithm/ranges_minmax.h>
1367#include <__algorithm/ranges_minmax_element.h>
Nikolas Klauser12fc9bf2022-03-08 23:12:35 +01001368#include <__algorithm/ranges_mismatch.h>
Nikolas Klauser16661d82022-06-23 12:23:41 +02001369#include <__algorithm/ranges_move.h>
1370#include <__algorithm/ranges_move_backward.h>
Nikolas Klausered3f0e82022-05-26 16:42:46 +02001371#include <__algorithm/ranges_none_of.h>
Konstantin Varlamovf18a9de2022-07-07 20:35:51 -07001372#include <__algorithm/ranges_nth_element.h>
Konstantin Varlamov389487d2022-07-08 13:46:27 -07001373#include <__algorithm/ranges_pop_heap.h>
1374#include <__algorithm/ranges_push_heap.h>
Nikolas Klauser7f52f282022-07-06 14:03:00 +02001375#include <__algorithm/ranges_remove.h>
1376#include <__algorithm/ranges_remove_if.h>
Nikolas Klauserfadea392022-06-07 09:42:10 +02001377#include <__algorithm/ranges_replace.h>
1378#include <__algorithm/ranges_replace_if.h>
Nikolas Klauser52f20072022-05-24 10:32:50 +02001379#include <__algorithm/ranges_reverse.h>
Hui Xie0ae2eef2022-06-26 16:13:43 +01001380#include <__algorithm/ranges_set_difference.h>
Konstantin Varlamov55e39a82022-06-16 15:20:53 -07001381#include <__algorithm/ranges_sort.h>
Konstantin Varlamov389487d2022-07-08 13:46:27 -07001382#include <__algorithm/ranges_sort_heap.h>
Konstantin Varlamovdc3e7822022-07-01 16:34:08 -07001383#include <__algorithm/ranges_stable_sort.h>
Nikolas Klauser4ceab5f2022-02-10 13:33:03 +01001384#include <__algorithm/ranges_swap_ranges.h>
Nikolas Klauser559a1772022-04-05 11:05:36 +02001385#include <__algorithm/ranges_transform.h>
Nikolas Klauser8b381972022-06-05 21:15:16 +02001386#include <__algorithm/ranges_upper_bound.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001387#include <__algorithm/remove.h>
1388#include <__algorithm/remove_copy.h>
1389#include <__algorithm/remove_copy_if.h>
1390#include <__algorithm/remove_if.h>
1391#include <__algorithm/replace.h>
1392#include <__algorithm/replace_copy.h>
1393#include <__algorithm/replace_copy_if.h>
1394#include <__algorithm/replace_if.h>
1395#include <__algorithm/reverse.h>
1396#include <__algorithm/reverse_copy.h>
1397#include <__algorithm/rotate.h>
1398#include <__algorithm/rotate_copy.h>
1399#include <__algorithm/sample.h>
1400#include <__algorithm/search.h>
1401#include <__algorithm/search_n.h>
1402#include <__algorithm/set_difference.h>
1403#include <__algorithm/set_intersection.h>
1404#include <__algorithm/set_symmetric_difference.h>
1405#include <__algorithm/set_union.h>
1406#include <__algorithm/shift_left.h>
1407#include <__algorithm/shift_right.h>
1408#include <__algorithm/shuffle.h>
1409#include <__algorithm/sift_down.h>
1410#include <__algorithm/sort.h>
1411#include <__algorithm/sort_heap.h>
1412#include <__algorithm/stable_partition.h>
1413#include <__algorithm/stable_sort.h>
Christopher Di Bella41f26e82021-06-05 02:47:47 +00001414#include <__algorithm/swap_ranges.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001415#include <__algorithm/transform.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001416#include <__algorithm/unique.h>
Arthur O'Dwyer65077c02022-01-07 09:45:05 -05001417#include <__algorithm/unique_copy.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001418#include <__algorithm/unwrap_iter.h>
1419#include <__algorithm/upper_bound.h>
Eric Fiselier14b6de92014-08-10 23:53:08 +00001420
Louis Dionne22355cc2022-06-27 15:53:41 -04001421#ifndef _LIBCPP_REMOVE_TRANSITIVE_INCLUDES
1422# include <chrono>
1423# include <iterator>
1424# include <utility>
1425#endif
1426
Nikolas Klausera0e0edb2022-06-16 22:43:46 +02001427// standard-mandated includes
1428#include <initializer_list>
1429
Howard Hinnantaaaa52b2011-10-17 20:05:10 +00001430#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Arthur O'Dwyer6eeaa002022-02-01 20:16:40 -05001431# pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +00001432#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001433
Louis Dionne59d0b3c2019-08-05 18:29:14 +00001434#if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
Louis Dionned53d8c02019-08-06 21:11:24 +00001435# include <__pstl_algorithm>
Louis Dionne59d0b3c2019-08-05 18:29:14 +00001436#endif
1437
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001438#endif // _LIBCPP_ALGORITHM