blob: 18d8ef3805e538d3bb015dfade2361dc5720b0b2 [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
Nikolas Klauserf16b94d2022-07-11 17:07:35 +0200588
Hui Xie0ae2eef2022-06-26 16:13:43 +0100589 template<class I, class O>
Nikolas Klauserf16b94d2022-07-11 17:07:35 +0200590 using set_difference_result = in_out_result<I, O>; // since C++20
Hui Xie0ae2eef2022-06-26 16:13:43 +0100591
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
Hui Xief34d0172022-07-08 15:21:40 +0100607 template<class I1, class I2, class O>
608 using set_intersection_result = in_in_out_result<I1, I2, O>; // since C++20
609
610 template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
611 weakly_incrementable O, class Comp = ranges::less,
612 class Proj1 = identity, class Proj2 = identity>
613 requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
614 constexpr set_intersection_result<I1, I2, O>
615 set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result,
616 Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
617
618 template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
619 weakly_incrementable O, class Comp = ranges::less,
620 class Proj1 = identity, class Proj2 = identity>
621 requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
622 constexpr set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
623 set_intersection(R1&& r1, R2&& r2, O result,
624 Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
625
Nikolas Klauserf16b94d2022-07-11 17:07:35 +0200626 template <class _InIter, class _OutIter>
627 using reverse_copy_result = in_out_result<_InIter, _OutIter>; // since C++20
628
629 template<bidirectional_iterator I, sentinel_for<I> S, weakly_incrementable O>
630 requires indirectly_copyable<I, O>
631 constexpr ranges::reverse_copy_result<I, O>
632 ranges::reverse_copy(I first, S last, O result); // since C++20
633
634 template<bidirectional_range R, weakly_incrementable O>
635 requires indirectly_copyable<iterator_t<R>, O>
636 constexpr ranges::reverse_copy_result<borrowed_iterator_t<R>, O>
637 ranges::reverse_copy(R&& r, O result); // since C++20
638
639 template <class _InIter, class _OutIter>
640 using rotate_copy_result = in_out_result<_InIter, _OutIter>; // since C++20
641
642 template<forward_iterator I, sentinel_for<I> S, weakly_incrementable O>
643 requires indirectly_copyable<I, O>
644 constexpr ranges::rotate_copy_result<I, O>
645 ranges::rotate_copy(I first, I middle, S last, O result); // since C++20
646
647 template<forward_range R, weakly_incrementable O>
648 requires indirectly_copyable<iterator_t<R>, O>
649 constexpr ranges::rotate_copy_result<borrowed_iterator_t<R>, O>
650 ranges::rotate_copy(R&& r, iterator_t<R> middle, O result); // since C++20
651
Nikolas Klauser863c4fa2022-07-13 18:07:26 +0200652 template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
653 sentinel_for<I2> S2, class Pred = ranges::equal_to,
654 class Proj1 = identity, class Proj2 = identity>
655 requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
656 constexpr subrange<I1>
657 ranges::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
658 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
659
660 template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
661 class Proj1 = identity, class Proj2 = identity>
662 requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
663 constexpr borrowed_subrange_t<R1>
664 ranges::search(R1&& r1, R2&& r2, Pred pred = {},
665 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
666
667 template<forward_iterator I, sentinel_for<I> S, class T,
668 class Pred = ranges::equal_to, class Proj = identity>
669 requires indirectly_comparable<I, const T*, Pred, Proj>
670 constexpr subrange<I>
671 ranges::search_n(I first, S last, iter_difference_t<I> count,
672 const T& value, Pred pred = {}, Proj proj = {}); // since C++20
673
674 template<forward_range R, class T, class Pred = ranges::equal_to,
675 class Proj = identity>
676 requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
677 constexpr borrowed_subrange_t<R>
678 ranges::search_n(R&& r, range_difference_t<R> count,
679 const T& value, Pred pred = {}, Proj proj = {}); // since C++20
680
681 template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
682 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
683 requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
684 constexpr subrange<I1>
685 ranges::find_end(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
686 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
687
688 template<forward_range R1, forward_range R2,
689 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
690 requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
691 constexpr borrowed_subrange_t<R1>
692 ranges::find_end(R1&& r1, R2&& r2, Pred pred = {},
693 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
694
Nikolas Klauserf74be4e2022-01-14 02:55:51 +0100695}
696
Marshall Clowd607fdb2018-01-15 17:20:36 +0000697 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000698 all_of(InputIterator first, InputIterator last, Predicate pred);
699
700template <class InputIterator, class Predicate>
Marshall Clowd607fdb2018-01-15 17:20:36 +0000701 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000702 any_of(InputIterator first, InputIterator last, Predicate pred);
703
704template <class InputIterator, class Predicate>
Marshall Clowd607fdb2018-01-15 17:20:36 +0000705 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000706 none_of(InputIterator first, InputIterator last, Predicate pred);
707
708template <class InputIterator, class Function>
Marshall Clow5492c8a2018-01-22 20:44:33 +0000709 constexpr Function // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000710 for_each(InputIterator first, InputIterator last, Function f);
711
Marshall Clowde0169c2017-05-25 02:29:54 +0000712template<class InputIterator, class Size, class Function>
Marshall Clow5492c8a2018-01-22 20:44:33 +0000713 constexpr InputIterator // constexpr in C++20
714 for_each_n(InputIterator first, Size n, Function f); // C++17
Marshall Clowde0169c2017-05-25 02:29:54 +0000715
Howard Hinnantc51e1022010-05-11 19:42:16 +0000716template <class InputIterator, class T>
Marshall Clowee0161e2018-01-15 19:26:05 +0000717 constexpr InputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000718 find(InputIterator first, InputIterator last, const T& value);
719
720template <class InputIterator, class Predicate>
Marshall Clowee0161e2018-01-15 19:26:05 +0000721 constexpr InputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000722 find_if(InputIterator first, InputIterator last, Predicate pred);
723
724template<class InputIterator, class Predicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500725 constexpr InputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000726 find_if_not(InputIterator first, InputIterator last, Predicate pred);
727
728template <class ForwardIterator1, class ForwardIterator2>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500729 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000730 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
731 ForwardIterator2 first2, ForwardIterator2 last2);
732
733template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500734 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000735 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
736 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
737
738template <class ForwardIterator1, class ForwardIterator2>
Marshall Clowee0161e2018-01-15 19:26:05 +0000739 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000740 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
741 ForwardIterator2 first2, ForwardIterator2 last2);
742
743template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clowee0161e2018-01-15 19:26:05 +0000744 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000745 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
746 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
747
748template <class ForwardIterator>
Marshall Clowee0161e2018-01-15 19:26:05 +0000749 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000750 adjacent_find(ForwardIterator first, ForwardIterator last);
751
752template <class ForwardIterator, class BinaryPredicate>
Marshall Clowee0161e2018-01-15 19:26:05 +0000753 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000754 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
755
756template <class InputIterator, class T>
Marshall Clow3c0558f2018-01-15 19:40:34 +0000757 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000758 count(InputIterator first, InputIterator last, const T& value);
759
760template <class InputIterator, class Predicate>
Marshall Clow3c0558f2018-01-15 19:40:34 +0000761 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000762 count_if(InputIterator first, InputIterator last, Predicate pred);
763
764template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000765 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000766 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
767
Marshall Clow96b42b22013-05-09 21:14:23 +0000768template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000769 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Aditya Kumar3a0179a2016-08-25 11:52:38 +0000770 mismatch(InputIterator1 first1, InputIterator1 last1,
Marshall Clow96b42b22013-05-09 21:14:23 +0000771 InputIterator2 first2, InputIterator2 last2); // **C++14**
772
Howard Hinnantc51e1022010-05-11 19:42:16 +0000773template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000774 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000775 mismatch(InputIterator1 first1, InputIterator1 last1,
776 InputIterator2 first2, BinaryPredicate pred);
777
Marshall Clow96b42b22013-05-09 21:14:23 +0000778template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000779 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000780 mismatch(InputIterator1 first1, InputIterator1 last1,
781 InputIterator2 first2, InputIterator2 last2,
782 BinaryPredicate pred); // **C++14**
783
Howard Hinnantc51e1022010-05-11 19:42:16 +0000784template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000785 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000786 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
787
Marshall Clow96b42b22013-05-09 21:14:23 +0000788template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000789 constexpr bool // constexpr in C++20
Aditya Kumar3a0179a2016-08-25 11:52:38 +0000790 equal(InputIterator1 first1, InputIterator1 last1,
Marshall Clow96b42b22013-05-09 21:14:23 +0000791 InputIterator2 first2, InputIterator2 last2); // **C++14**
792
Howard Hinnantc51e1022010-05-11 19:42:16 +0000793template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000794 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000795 equal(InputIterator1 first1, InputIterator1 last1,
796 InputIterator2 first2, BinaryPredicate pred);
797
Marshall Clow96b42b22013-05-09 21:14:23 +0000798template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000799 constexpr bool // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000800 equal(InputIterator1 first1, InputIterator1 last1,
801 InputIterator2 first2, InputIterator2 last2,
802 BinaryPredicate pred); // **C++14**
803
Howard Hinnantc51e1022010-05-11 19:42:16 +0000804template<class ForwardIterator1, class ForwardIterator2>
Marshall Clow96d050a2018-01-15 16:16:32 +0000805 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000806 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
807 ForwardIterator2 first2);
808
Marshall Clow96b42b22013-05-09 21:14:23 +0000809template<class ForwardIterator1, class ForwardIterator2>
Marshall Clow96d050a2018-01-15 16:16:32 +0000810 constexpr bool // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000811 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
812 ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**
813
Howard Hinnantc51e1022010-05-11 19:42:16 +0000814template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clow96d050a2018-01-15 16:16:32 +0000815 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000816 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
817 ForwardIterator2 first2, BinaryPredicate pred);
818
Marshall Clow96b42b22013-05-09 21:14:23 +0000819template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clow96d050a2018-01-15 16:16:32 +0000820 constexpr bool // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000821 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
822 ForwardIterator2 first2, ForwardIterator2 last2,
823 BinaryPredicate pred); // **C++14**
824
Howard Hinnantc51e1022010-05-11 19:42:16 +0000825template <class ForwardIterator1, class ForwardIterator2>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000826 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000827 search(ForwardIterator1 first1, ForwardIterator1 last1,
828 ForwardIterator2 first2, ForwardIterator2 last2);
829
830template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000831 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000832 search(ForwardIterator1 first1, ForwardIterator1 last1,
833 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
834
835template <class ForwardIterator, class Size, class T>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000836 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000837 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
838
839template <class ForwardIterator, class Size, class T, class BinaryPredicate>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000840 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000841 search_n(ForwardIterator first, ForwardIterator last,
842 Size count, const T& value, BinaryPredicate pred);
843
844template <class InputIterator, class OutputIterator>
Louis Dionne65b433b2019-11-06 12:02:41 +0000845 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000846 copy(InputIterator first, InputIterator last, OutputIterator result);
847
848template<class InputIterator, class OutputIterator, class Predicate>
Louis Dionne65b433b2019-11-06 12:02:41 +0000849 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000850 copy_if(InputIterator first, InputIterator last,
851 OutputIterator result, Predicate pred);
852
853template<class InputIterator, class Size, class OutputIterator>
Louis Dionne65b433b2019-11-06 12:02:41 +0000854 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000855 copy_n(InputIterator first, Size n, OutputIterator result);
856
857template <class BidirectionalIterator1, class BidirectionalIterator2>
Louis Dionne65b433b2019-11-06 12:02:41 +0000858 constexpr BidirectionalIterator2 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000859 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
860 BidirectionalIterator2 result);
861
Konstantin Varlamov89a23f32022-06-28 11:59:59 -0700862// [alg.move], move
863template<class InputIterator, class OutputIterator>
864 constexpr OutputIterator move(InputIterator first, InputIterator last,
865 OutputIterator result);
866
867template<class BidirectionalIterator1, class BidirectionalIterator2>
868 constexpr BidirectionalIterator2
869 move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
870 BidirectionalIterator2 result);
871
Howard Hinnantc51e1022010-05-11 19:42:16 +0000872template <class ForwardIterator1, class ForwardIterator2>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500873 constexpr ForwardIterator2 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000874 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
875
Konstantin Varlamov89a23f32022-06-28 11:59:59 -0700876namespace ranges {
877 template<class I1, class I2>
878 using swap_ranges_result = in_in_result<I1, I2>;
879
Nikolas Klauser4ceab5f2022-02-10 13:33:03 +0100880template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2>
881 requires indirectly_swappable<I1, I2>
882 constexpr ranges::swap_ranges_result<I1, I2>
Konstantin Varlamov89a23f32022-06-28 11:59:59 -0700883 swap_ranges(I1 first1, S1 last1, I2 first2, S2 last2);
Nikolas Klauser4ceab5f2022-02-10 13:33:03 +0100884
885template<input_range R1, input_range R2>
886 requires indirectly_swappable<iterator_t<R1>, iterator_t<R2>>
887 constexpr ranges::swap_ranges_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
Konstantin Varlamov89a23f32022-06-28 11:59:59 -0700888 swap_ranges(R1&& r1, R2&& r2);
889}
Nikolas Klauser4ceab5f2022-02-10 13:33:03 +0100890
Howard Hinnantc51e1022010-05-11 19:42:16 +0000891template <class ForwardIterator1, class ForwardIterator2>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500892 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000893 iter_swap(ForwardIterator1 a, ForwardIterator2 b);
894
895template <class InputIterator, class OutputIterator, class UnaryOperation>
Marshall Clow31427c62018-01-19 17:45:39 +0000896 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000897 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
898
899template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
Marshall Clow31427c62018-01-19 17:45:39 +0000900 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000901 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
902 OutputIterator result, BinaryOperation binary_op);
903
904template <class ForwardIterator, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000905 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000906 replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
907
908template <class ForwardIterator, class Predicate, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000909 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000910 replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
911
912template <class InputIterator, class OutputIterator, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000913 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000914 replace_copy(InputIterator first, InputIterator last, OutputIterator result,
915 const T& old_value, const T& new_value);
916
917template <class InputIterator, class OutputIterator, class Predicate, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000918 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000919 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
920
921template <class ForwardIterator, class T>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000922 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000923 fill(ForwardIterator first, ForwardIterator last, const T& value);
924
925template <class OutputIterator, class Size, class T>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000926 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000927 fill_n(OutputIterator first, Size n, const T& value);
928
929template <class ForwardIterator, class Generator>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000930 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000931 generate(ForwardIterator first, ForwardIterator last, Generator gen);
932
933template <class OutputIterator, class Size, class Generator>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000934 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000935 generate_n(OutputIterator first, Size n, Generator gen);
936
937template <class ForwardIterator, class T>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000938 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000939 remove(ForwardIterator first, ForwardIterator last, const T& value);
940
941template <class ForwardIterator, class Predicate>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000942 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000943 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
944
945template <class InputIterator, class OutputIterator, class T>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000946 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000947 remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
948
949template <class InputIterator, class OutputIterator, class Predicate>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000950 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000951 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
952
953template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500954 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000955 unique(ForwardIterator first, ForwardIterator last);
956
957template <class ForwardIterator, class BinaryPredicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500958 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000959 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
960
961template <class InputIterator, class OutputIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500962 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000963 unique_copy(InputIterator first, InputIterator last, OutputIterator result);
964
965template <class InputIterator, class OutputIterator, class BinaryPredicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500966 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000967 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
968
969template <class BidirectionalIterator>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -0500970 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000971 reverse(BidirectionalIterator first, BidirectionalIterator last);
972
973template <class BidirectionalIterator, class OutputIterator>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000974 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000975 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
976
977template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500978 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000979 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
980
981template <class ForwardIterator, class OutputIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500982 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000983 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
984
985template <class RandomAccessIterator>
986 void
Marshall Clowfac06e52017-03-23 13:43:37 +0000987 random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000988
989template <class RandomAccessIterator, class RandomNumberGenerator>
990 void
Marshall Clow83f35392014-03-03 06:14:19 +0000991 random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
Marshall Clowfac06e52017-03-23 13:43:37 +0000992 RandomNumberGenerator& rand); // deprecated in C++14, removed in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000993
Eric Fiselier1208fcd2016-08-28 22:14:37 +0000994template<class PopulationIterator, class SampleIterator,
995 class Distance, class UniformRandomBitGenerator>
996 SampleIterator sample(PopulationIterator first, PopulationIterator last,
997 SampleIterator out, Distance n,
998 UniformRandomBitGenerator&& g); // C++17
999
Howard Hinnant578ac0f2010-05-26 17:49:34 +00001000template<class RandomAccessIterator, class UniformRandomNumberGenerator>
1001 void shuffle(RandomAccessIterator first, RandomAccessIterator last,
Howard Hinnanta5e71782010-11-18 01:47:02 +00001002 UniformRandomNumberGenerator&& g);
Howard Hinnant578ac0f2010-05-26 17:49:34 +00001003
Arthur O'Dwyercea050d2020-12-26 01:39:03 -05001004template<class ForwardIterator>
1005 constexpr ForwardIterator
1006 shift_left(ForwardIterator first, ForwardIterator last,
1007 typename iterator_traits<ForwardIterator>::difference_type n); // C++20
1008
1009template<class ForwardIterator>
1010 constexpr ForwardIterator
1011 shift_right(ForwardIterator first, ForwardIterator last,
1012 typename iterator_traits<ForwardIterator>::difference_type n); // C++20
1013
Howard Hinnantc51e1022010-05-11 19:42:16 +00001014template <class InputIterator, class Predicate>
Marshall Clow96d050a2018-01-15 16:16:32 +00001015 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001016 is_partitioned(InputIterator first, InputIterator last, Predicate pred);
1017
1018template <class ForwardIterator, class Predicate>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -05001019 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001020 partition(ForwardIterator first, ForwardIterator last, Predicate pred);
1021
1022template <class InputIterator, class OutputIterator1,
1023 class OutputIterator2, class Predicate>
Marshall Clow5492c8a2018-01-22 20:44:33 +00001024 constexpr pair<OutputIterator1, OutputIterator2> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001025 partition_copy(InputIterator first, InputIterator last,
1026 OutputIterator1 out_true, OutputIterator2 out_false,
1027 Predicate pred);
1028
1029template <class ForwardIterator, class Predicate>
1030 ForwardIterator
1031 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
1032
1033template<class ForwardIterator, class Predicate>
Marshall Clowe00916c2018-01-16 02:34:41 +00001034 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001035 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
1036
1037template <class ForwardIterator>
Marshall Clow96d050a2018-01-15 16:16:32 +00001038 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001039 is_sorted(ForwardIterator first, ForwardIterator last);
1040
1041template <class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001042 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001043 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
1044
1045template<class ForwardIterator>
Marshall Clow3c0558f2018-01-15 19:40:34 +00001046 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001047 is_sorted_until(ForwardIterator first, ForwardIterator last);
1048
1049template <class ForwardIterator, class Compare>
Marshall Clow3c0558f2018-01-15 19:40:34 +00001050 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001051 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
1052
1053template <class RandomAccessIterator>
Arthur O'Dwyer1bb0f672020-12-20 15:21:42 -05001054 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001055 sort(RandomAccessIterator first, RandomAccessIterator last);
1056
1057template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer1bb0f672020-12-20 15:21:42 -05001058 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001059 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1060
1061template <class RandomAccessIterator>
1062 void
1063 stable_sort(RandomAccessIterator first, RandomAccessIterator last);
1064
1065template <class RandomAccessIterator, class Compare>
1066 void
1067 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1068
1069template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001070 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001071 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
1072
1073template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001074 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001075 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
1076
1077template <class InputIterator, class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001078 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001079 partial_sort_copy(InputIterator first, InputIterator last,
1080 RandomAccessIterator result_first, RandomAccessIterator result_last);
1081
1082template <class InputIterator, class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001083 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001084 partial_sort_copy(InputIterator first, InputIterator last,
1085 RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
1086
1087template <class RandomAccessIterator>
Arthur O'Dwyer4f5717b2021-02-04 18:12:52 -05001088 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001089 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
1090
1091template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer4f5717b2021-02-04 18:12:52 -05001092 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001093 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
1094
1095template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +00001096 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001097 lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
1098
1099template <class ForwardIterator, class T, class Compare>
Marshall Clowe00916c2018-01-16 02:34:41 +00001100 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001101 lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
1102
1103template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +00001104 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001105 upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
1106
1107template <class ForwardIterator, class T, class Compare>
Marshall Clowe00916c2018-01-16 02:34:41 +00001108 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001109 upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
1110
1111template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +00001112 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001113 equal_range(ForwardIterator first, ForwardIterator last, const T& value);
1114
1115template <class ForwardIterator, class T, class Compare>
Marshall Clowe00916c2018-01-16 02:34:41 +00001116 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001117 equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
1118
1119template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +00001120 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001121 binary_search(ForwardIterator first, ForwardIterator last, const T& value);
1122
1123template <class ForwardIterator, class T, class Compare>
Marshall Clowc0b7f972018-01-22 23:10:40 +00001124 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001125 binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
1126
1127template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001128 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001129 merge(InputIterator1 first1, InputIterator1 last1,
1130 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
1131
1132template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001133 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001134 merge(InputIterator1 first1, InputIterator1 last1,
1135 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
1136
1137template <class BidirectionalIterator>
1138 void
1139 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
1140
1141template <class BidirectionalIterator, class Compare>
1142 void
1143 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
1144
1145template <class InputIterator1, class InputIterator2>
Marshall Clowc0b7f972018-01-22 23:10:40 +00001146 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001147 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
1148
1149template <class InputIterator1, class InputIterator2, class Compare>
Marshall Clowc0b7f972018-01-22 23:10:40 +00001150 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001151 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
1152
1153template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001154 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001155 set_union(InputIterator1 first1, InputIterator1 last1,
1156 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
1157
1158template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001159 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001160 set_union(InputIterator1 first1, InputIterator1 last1,
1161 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
1162
1163template <class InputIterator1, class InputIterator2, class OutputIterator>
Marshall Clowc0b7f972018-01-22 23:10:40 +00001164 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001165 set_intersection(InputIterator1 first1, InputIterator1 last1,
1166 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
1167
1168template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Marshall Clowc0b7f972018-01-22 23:10:40 +00001169 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001170 set_intersection(InputIterator1 first1, InputIterator1 last1,
1171 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
1172
1173template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001174 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001175 set_difference(InputIterator1 first1, InputIterator1 last1,
1176 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
1177
1178template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001179 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001180 set_difference(InputIterator1 first1, InputIterator1 last1,
1181 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
1182
1183template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001184 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001185 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
1186 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
1187
1188template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -05001189 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001190 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
1191 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
1192
1193template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001194 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001195 push_heap(RandomAccessIterator first, RandomAccessIterator last);
1196
1197template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001198 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001199 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1200
1201template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001202 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001203 pop_heap(RandomAccessIterator first, RandomAccessIterator last);
1204
1205template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001206 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001207 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1208
1209template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001210 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001211 make_heap(RandomAccessIterator first, RandomAccessIterator last);
1212
1213template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001214 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001215 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1216
1217template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001218 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001219 sort_heap(RandomAccessIterator first, RandomAccessIterator last);
1220
1221template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -05001222 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001223 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1224
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001225template <class RandomAccessIterator>
Marshall Clow96d050a2018-01-15 16:16:32 +00001226 constexpr bool // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001227 is_heap(RandomAccessIterator first, RandomAccessiterator last);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001228
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001229template <class RandomAccessIterator, class Compare>
Marshall Clow96d050a2018-01-15 16:16:32 +00001230 constexpr bool // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001231 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001232
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001233template <class RandomAccessIterator>
Marshall Clow96d050a2018-01-15 16:16:32 +00001234 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001235 is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001236
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001237template <class RandomAccessIterator, class Compare>
Marshall Clow96d050a2018-01-15 16:16:32 +00001238 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001239 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001240
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001241template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001242 constexpr ForwardIterator // constexpr in C++14
1243 min_element(ForwardIterator first, ForwardIterator last);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001244
1245template <class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001246 constexpr ForwardIterator // constexpr in C++14
1247 min_element(ForwardIterator first, ForwardIterator last, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001248
Howard Hinnantc51e1022010-05-11 19:42:16 +00001249template <class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001250 constexpr const T& // constexpr in C++14
1251 min(const T& a, const T& b);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001252
1253template <class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001254 constexpr const T& // constexpr in C++14
1255 min(const T& a, const T& b, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001256
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001257template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001258 constexpr T // constexpr in C++14
1259 min(initializer_list<T> t);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001260
1261template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001262 constexpr T // constexpr in C++14
1263 min(initializer_list<T> t, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001264
Marshall Clow3e18d0e2016-03-07 22:43:49 +00001265template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001266 constexpr const T& clamp(const T& v, const T& lo, const T& hi); // C++17
Marshall Clow3e18d0e2016-03-07 22:43:49 +00001267
1268template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001269 constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp); // C++17
Marshall Clow3e18d0e2016-03-07 22:43:49 +00001270
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001271template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001272 constexpr ForwardIterator // constexpr in C++14
1273 max_element(ForwardIterator first, ForwardIterator last);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001274
1275template <class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001276 constexpr ForwardIterator // constexpr in C++14
1277 max_element(ForwardIterator first, ForwardIterator last, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001278
Howard Hinnantc51e1022010-05-11 19:42:16 +00001279template <class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001280 constexpr const T& // constexpr in C++14
1281 max(const T& a, const T& b);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001282
1283template <class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001284 constexpr const T& // constexpr in C++14
1285 max(const T& a, const T& b, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001286
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001287template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001288 constexpr T // constexpr in C++14
1289 max(initializer_list<T> t);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001290
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001291template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001292 constexpr T // constexpr in C++14
1293 max(initializer_list<T> t, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001294
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001295template<class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001296 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14
1297 minmax_element(ForwardIterator first, ForwardIterator last);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001298
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001299template<class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001300 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14
1301 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001302
1303template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001304 constexpr pair<const T&, const T&> // constexpr in C++14
1305 minmax(const T& a, const T& b);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001306
1307template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001308 constexpr pair<const T&, const T&> // constexpr in C++14
1309 minmax(const T& a, const T& b, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001310
1311template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001312 constexpr pair<T, T> // constexpr in C++14
1313 minmax(initializer_list<T> t);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001314
1315template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001316 constexpr pair<T, T> // constexpr in C++14
1317 minmax(initializer_list<T> t, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001318
1319template <class InputIterator1, class InputIterator2>
Marshall Clow5492c8a2018-01-22 20:44:33 +00001320 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001321 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
1322
1323template <class InputIterator1, class InputIterator2, class Compare>
Marshall Clow5492c8a2018-01-22 20:44:33 +00001324 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001325 lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
1326 InputIterator2 first2, InputIterator2 last2, Compare comp);
1327
1328template <class BidirectionalIterator>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -05001329 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001330 next_permutation(BidirectionalIterator first, BidirectionalIterator last);
1331
1332template <class BidirectionalIterator, class Compare>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -05001333 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001334 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
1335
1336template <class BidirectionalIterator>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -05001337 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001338 prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
1339
1340template <class BidirectionalIterator, class Compare>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -05001341 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001342 prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001343} // std
1344
1345*/
1346
Louis Dionneb4fce352022-03-25 12:55:36 -04001347#include <__assert> // all public C++ headers provide the assertion handler
Arthur O'Dwyer3693d7a2022-02-04 13:09:30 -05001348#include <__bits>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001349#include <__config>
Louis Dionnea60dd872021-06-17 11:30:11 -04001350#include <__debug>
Howard Hinnant60e5cf42012-07-26 17:09:09 +00001351#include <cstddef>
Arthur O'Dwyeref181602021-05-19 11:57:04 -04001352#include <cstring>
Arthur O'Dwyeref181602021-05-19 11:57:04 -04001353#include <memory>
1354#include <type_traits>
Marshall Clow0a1e7502018-09-12 19:41:40 +00001355#include <version>
Howard Hinnantea382952013-08-14 18:00:20 +00001356
Louis Dionnea60dd872021-06-17 11:30:11 -04001357#include <__algorithm/adjacent_find.h>
1358#include <__algorithm/all_of.h>
1359#include <__algorithm/any_of.h>
1360#include <__algorithm/binary_search.h>
1361#include <__algorithm/clamp.h>
1362#include <__algorithm/comp.h>
1363#include <__algorithm/comp_ref_type.h>
1364#include <__algorithm/copy.h>
1365#include <__algorithm/copy_backward.h>
1366#include <__algorithm/copy_if.h>
1367#include <__algorithm/copy_n.h>
1368#include <__algorithm/count.h>
1369#include <__algorithm/count_if.h>
1370#include <__algorithm/equal.h>
1371#include <__algorithm/equal_range.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001372#include <__algorithm/fill.h>
Arthur O'Dwyer65077c02022-01-07 09:45:05 -05001373#include <__algorithm/fill_n.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001374#include <__algorithm/find.h>
1375#include <__algorithm/find_end.h>
1376#include <__algorithm/find_first_of.h>
1377#include <__algorithm/find_if.h>
1378#include <__algorithm/find_if_not.h>
1379#include <__algorithm/for_each.h>
1380#include <__algorithm/for_each_n.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001381#include <__algorithm/generate.h>
Arthur O'Dwyer65077c02022-01-07 09:45:05 -05001382#include <__algorithm/generate_n.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001383#include <__algorithm/half_positive.h>
Nikolas Klauserdd5ad212022-02-21 23:07:02 +01001384#include <__algorithm/in_found_result.h>
Nikolas Klauser671b4752022-02-11 17:01:58 +01001385#include <__algorithm/in_fun_result.h>
Nikolas Klauser05e2cd82022-01-25 11:21:47 +01001386#include <__algorithm/in_in_out_result.h>
Nikolas Klauserf74be4e2022-01-14 02:55:51 +01001387#include <__algorithm/in_in_result.h>
Nikolas Klauser61ce8162022-02-03 02:17:03 +01001388#include <__algorithm/in_out_out_result.h>
Konstantin Varlamov74736812022-01-10 22:49:37 -08001389#include <__algorithm/in_out_result.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001390#include <__algorithm/includes.h>
1391#include <__algorithm/inplace_merge.h>
1392#include <__algorithm/is_heap.h>
1393#include <__algorithm/is_heap_until.h>
1394#include <__algorithm/is_partitioned.h>
1395#include <__algorithm/is_permutation.h>
1396#include <__algorithm/is_sorted.h>
1397#include <__algorithm/is_sorted_until.h>
Christopher Di Bella41f26e82021-06-05 02:47:47 +00001398#include <__algorithm/iter_swap.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001399#include <__algorithm/lexicographical_compare.h>
1400#include <__algorithm/lower_bound.h>
1401#include <__algorithm/make_heap.h>
1402#include <__algorithm/max.h>
1403#include <__algorithm/max_element.h>
1404#include <__algorithm/merge.h>
1405#include <__algorithm/min.h>
1406#include <__algorithm/min_element.h>
Nikolas Klauser2e263162022-02-21 22:48:36 +01001407#include <__algorithm/min_max_result.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001408#include <__algorithm/minmax.h>
1409#include <__algorithm/minmax_element.h>
1410#include <__algorithm/mismatch.h>
1411#include <__algorithm/move.h>
1412#include <__algorithm/move_backward.h>
1413#include <__algorithm/next_permutation.h>
1414#include <__algorithm/none_of.h>
1415#include <__algorithm/nth_element.h>
1416#include <__algorithm/partial_sort.h>
1417#include <__algorithm/partial_sort_copy.h>
1418#include <__algorithm/partition.h>
1419#include <__algorithm/partition_copy.h>
1420#include <__algorithm/partition_point.h>
1421#include <__algorithm/pop_heap.h>
1422#include <__algorithm/prev_permutation.h>
1423#include <__algorithm/push_heap.h>
Nikolas Klauser5ae708f2022-06-08 12:14:12 +02001424#include <__algorithm/ranges_adjacent_find.h>
Nikolas Klausered3f0e82022-05-26 16:42:46 +02001425#include <__algorithm/ranges_all_of.h>
1426#include <__algorithm/ranges_any_of.h>
Nikolas Klauser8b381972022-06-05 21:15:16 +02001427#include <__algorithm/ranges_binary_search.h>
Nikolas Klauserd959d842022-04-15 13:43:40 +02001428#include <__algorithm/ranges_copy.h>
1429#include <__algorithm/ranges_copy_backward.h>
1430#include <__algorithm/ranges_copy_if.h>
1431#include <__algorithm/ranges_copy_n.h>
Nikolas Klauserf1373d02022-04-07 13:02:02 +02001432#include <__algorithm/ranges_count.h>
1433#include <__algorithm/ranges_count_if.h>
Nikolas Klauser353f1dd2022-05-25 11:09:43 +02001434#include <__algorithm/ranges_equal.h>
Nikolas Klausereb49c2a2022-05-21 18:26:29 +02001435#include <__algorithm/ranges_fill.h>
1436#include <__algorithm/ranges_fill_n.h>
Nikolas Klauser37d076e2022-03-12 01:45:35 +01001437#include <__algorithm/ranges_find.h>
Nikolas Klauser863c4fa2022-07-13 18:07:26 +02001438#include <__algorithm/ranges_find_end.h>
Nikolas Klauser0a7e46d2022-06-06 13:57:34 +02001439#include <__algorithm/ranges_find_first_of.h>
Nikolas Klauser37d076e2022-03-12 01:45:35 +01001440#include <__algorithm/ranges_find_if.h>
1441#include <__algorithm/ranges_find_if_not.h>
Nikolas Klauser58de98c2022-05-04 20:27:07 +02001442#include <__algorithm/ranges_for_each.h>
1443#include <__algorithm/ranges_for_each_n.h>
Nikolas Klauserbb9049d2022-05-04 14:19:09 +02001444#include <__algorithm/ranges_is_partitioned.h>
Nikolas Klauserab0b7af2022-05-26 16:08:55 +02001445#include <__algorithm/ranges_is_sorted.h>
1446#include <__algorithm/ranges_is_sorted_until.h>
Nikolas Klauser2fd677c2022-06-15 16:24:43 +02001447#include <__algorithm/ranges_lexicographical_compare.h>
Nikolas Klauser8b381972022-06-05 21:15:16 +02001448#include <__algorithm/ranges_lower_bound.h>
Konstantin Varlamov389487d2022-07-08 13:46:27 -07001449#include <__algorithm/ranges_make_heap.h>
Nikolas Klauser573cd6f2022-04-03 09:17:01 +02001450#include <__algorithm/ranges_max.h>
Nikolas Klauserf2a69ea2022-03-07 17:01:52 +01001451#include <__algorithm/ranges_max_element.h>
Hui Xie42bdbb72022-06-26 16:13:43 +01001452#include <__algorithm/ranges_merge.h>
Nikolas Klauser3559e452022-03-18 02:57:08 +01001453#include <__algorithm/ranges_min.h>
Nikolas Klauser0a62a172022-02-11 13:11:57 +01001454#include <__algorithm/ranges_min_element.h>
Nikolas Klauser0a2f44f2022-04-13 22:59:09 +02001455#include <__algorithm/ranges_minmax.h>
1456#include <__algorithm/ranges_minmax_element.h>
Nikolas Klauser12fc9bf2022-03-08 23:12:35 +01001457#include <__algorithm/ranges_mismatch.h>
Nikolas Klauser16661d82022-06-23 12:23:41 +02001458#include <__algorithm/ranges_move.h>
1459#include <__algorithm/ranges_move_backward.h>
Nikolas Klausered3f0e82022-05-26 16:42:46 +02001460#include <__algorithm/ranges_none_of.h>
Konstantin Varlamovf18a9de2022-07-07 20:35:51 -07001461#include <__algorithm/ranges_nth_element.h>
Konstantin Varlamov389487d2022-07-08 13:46:27 -07001462#include <__algorithm/ranges_pop_heap.h>
1463#include <__algorithm/ranges_push_heap.h>
Nikolas Klauser7f52f282022-07-06 14:03:00 +02001464#include <__algorithm/ranges_remove.h>
1465#include <__algorithm/ranges_remove_if.h>
Nikolas Klauserfadea392022-06-07 09:42:10 +02001466#include <__algorithm/ranges_replace.h>
1467#include <__algorithm/ranges_replace_if.h>
Nikolas Klauser52f20072022-05-24 10:32:50 +02001468#include <__algorithm/ranges_reverse.h>
Nikolas Klauserf16b94d2022-07-11 17:07:35 +02001469#include <__algorithm/ranges_reverse_copy.h>
1470#include <__algorithm/ranges_rotate_copy.h>
Nikolas Klauser863c4fa2022-07-13 18:07:26 +02001471#include <__algorithm/ranges_search.h>
1472#include <__algorithm/ranges_search_n.h>
Hui Xie0ae2eef2022-06-26 16:13:43 +01001473#include <__algorithm/ranges_set_difference.h>
Hui Xief34d0172022-07-08 15:21:40 +01001474#include <__algorithm/ranges_set_intersection.h>
Konstantin Varlamov55e39a82022-06-16 15:20:53 -07001475#include <__algorithm/ranges_sort.h>
Konstantin Varlamov389487d2022-07-08 13:46:27 -07001476#include <__algorithm/ranges_sort_heap.h>
Konstantin Varlamovdc3e7822022-07-01 16:34:08 -07001477#include <__algorithm/ranges_stable_sort.h>
Nikolas Klauser4ceab5f2022-02-10 13:33:03 +01001478#include <__algorithm/ranges_swap_ranges.h>
Nikolas Klauser559a1772022-04-05 11:05:36 +02001479#include <__algorithm/ranges_transform.h>
Nikolas Klauser8b381972022-06-05 21:15:16 +02001480#include <__algorithm/ranges_upper_bound.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001481#include <__algorithm/remove.h>
1482#include <__algorithm/remove_copy.h>
1483#include <__algorithm/remove_copy_if.h>
1484#include <__algorithm/remove_if.h>
1485#include <__algorithm/replace.h>
1486#include <__algorithm/replace_copy.h>
1487#include <__algorithm/replace_copy_if.h>
1488#include <__algorithm/replace_if.h>
1489#include <__algorithm/reverse.h>
1490#include <__algorithm/reverse_copy.h>
1491#include <__algorithm/rotate.h>
1492#include <__algorithm/rotate_copy.h>
1493#include <__algorithm/sample.h>
1494#include <__algorithm/search.h>
1495#include <__algorithm/search_n.h>
1496#include <__algorithm/set_difference.h>
1497#include <__algorithm/set_intersection.h>
1498#include <__algorithm/set_symmetric_difference.h>
1499#include <__algorithm/set_union.h>
1500#include <__algorithm/shift_left.h>
1501#include <__algorithm/shift_right.h>
1502#include <__algorithm/shuffle.h>
1503#include <__algorithm/sift_down.h>
1504#include <__algorithm/sort.h>
1505#include <__algorithm/sort_heap.h>
1506#include <__algorithm/stable_partition.h>
1507#include <__algorithm/stable_sort.h>
Christopher Di Bella41f26e82021-06-05 02:47:47 +00001508#include <__algorithm/swap_ranges.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001509#include <__algorithm/transform.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001510#include <__algorithm/unique.h>
Arthur O'Dwyer65077c02022-01-07 09:45:05 -05001511#include <__algorithm/unique_copy.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001512#include <__algorithm/unwrap_iter.h>
1513#include <__algorithm/upper_bound.h>
Eric Fiselier14b6de92014-08-10 23:53:08 +00001514
Louis Dionne22355cc2022-06-27 15:53:41 -04001515#ifndef _LIBCPP_REMOVE_TRANSITIVE_INCLUDES
1516# include <chrono>
1517# include <iterator>
1518# include <utility>
1519#endif
1520
Nikolas Klausera0e0edb2022-06-16 22:43:46 +02001521// standard-mandated includes
1522#include <initializer_list>
1523
Howard Hinnantaaaa52b2011-10-17 20:05:10 +00001524#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Arthur O'Dwyer6eeaa002022-02-01 20:16:40 -05001525# pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +00001526#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001527
Louis Dionne59d0b3c2019-08-05 18:29:14 +00001528#if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
Louis Dionned53d8c02019-08-06 21:11:24 +00001529# include <__pstl_algorithm>
Louis Dionne59d0b3c2019-08-05 18:29:14 +00001530#endif
1531
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001532#endif // _LIBCPP_ALGORITHM