blob: 9ae647181c5f2c6a2eeb966fe42800d733c01bcf [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 {
Nikolas Klauser671b4752022-02-11 17:01:58 +010022 template <class I, class F>
Nikolas Klauser2e263162022-02-21 22:48:36 +010023 struct in_fun_result; // since C++20
Nikolas Klauser671b4752022-02-11 17:01:58 +010024
Nikolas Klauserf74be4e2022-01-14 02:55:51 +010025 template <class I1, class I2>
Nikolas Klauser2e263162022-02-21 22:48:36 +010026 struct in_in_result; // since C++20
Nikolas Klauser05e2cd82022-01-25 11:21:47 +010027
28 template <class I1, class I2, class O>
Nikolas Klauser2e263162022-02-21 22:48:36 +010029 struct in_in_out_result; // since C++20
Nikolas Klauser61ce8162022-02-03 02:17:03 +010030
31 template <class I, class O1, class O2>
32 struct in_out_out_result; // since C++20
Nikolas Klauser671b4752022-02-11 17:01:58 +010033
Nikolas Klauser2e263162022-02-21 22:48:36 +010034 template <class I1, class I2>
35 struct min_max_result; // since C++20
36
Nikolas Klauserdd5ad212022-02-21 23:07:02 +010037 template <class I>
38 struct in_found_result; // since C++20
39
Nikolas Klauser0a62a172022-02-11 13:11:57 +010040 template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
41 indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less> // since C++20
42 constexpr I min_element(I first, S last, Comp comp = {}, Proj proj = {});
43
44 template<forward_range R, class Proj = identity,
45 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> // since C++20
46 constexpr borrowed_iterator_t<R> min_element(R&& r, Comp comp = {}, Proj proj = {});
Nikolas Klauser12fc9bf2022-03-08 23:12:35 +010047
Nikolas Klauser10c612d2022-05-22 13:43:37 +020048 template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
49 indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
50 constexpr I ranges::max_element(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
51
52 template<forward_range R, class Proj = identity,
53 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
54 constexpr borrowed_iterator_t<R> ranges::max_element(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
55
Nikolas Klauser12fc9bf2022-03-08 23:12:35 +010056 template <input_iterator I1, sentinel_for<_I1> S1, input_iterator I2, sentinel_for<_I2> S2,
57 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
58 requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
59 constexpr mismatch_result<_I1, _I2>
60 mismatch()(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) // since C++20
61
62 template <input_range R1, input_range R2,
63 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
64 requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
65 constexpr mismatch_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
66 mismatch(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) // since C++20
Nikolas Klauser37d076e2022-03-12 01:45:35 +010067
Nikolas Klauser37d076e2022-03-12 01:45:35 +010068 requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
69 constexpr I find(I first, S last, const T& value, Proj proj = {}); // since C++20
70
71 template<input_range R, class T, class Proj = identity>
72 requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
73 constexpr borrowed_iterator_t<R>
74 find(R&& r, const T& value, Proj proj = {}); // since C++20
75
76 template<input_iterator I, sentinel_for<I> S, class Proj = identity,
77 indirect_unary_predicate<projected<I, Proj>> Pred>
78 constexpr I find_if(I first, S last, Pred pred, Proj proj = {}); // since C++20
79
80 template<input_range R, class Proj = identity,
81 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
82 constexpr borrowed_iterator_t<R>
83 find_if(R&& r, Pred pred, Proj proj = {}); // since C++20
84
85 template<input_iterator I, sentinel_for<I> S, class Proj = identity,
86 indirect_unary_predicate<projected<I, Proj>> Pred>
87 constexpr I find_if_not(I first, S last, Pred pred, Proj proj = {}); // since C++20
88
89 template<input_range R, class Proj = identity,
90 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
91 constexpr borrowed_iterator_t<R>
92 find_if_not(R&& r, Pred pred, Proj proj = {}); // since C++20
Nikolas Klauser3559e452022-03-18 02:57:08 +010093
Nikolas Klauser573cd6f2022-04-03 09:17:01 +020094 template<class T, class Proj = identity,
95 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
96 constexpr const T& min(const T& a, const T& b, Comp comp = {}, Proj proj = {}); // since C++20
Nikolas Klauser3559e452022-03-18 02:57:08 +010097
Nikolas Klauser573cd6f2022-04-03 09:17:01 +020098 template<copyable T, class Proj = identity,
99 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
100 constexpr T min(initializer_list<T> r, Comp comp = {}, Proj proj = {}); // since C++20
Nikolas Klauser3559e452022-03-18 02:57:08 +0100101
102 template<input_range R, class Proj = identity,
103 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
104 requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
105 constexpr range_value_t<R>
106 min(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
Nikolas Klauser573cd6f2022-04-03 09:17:01 +0200107
108 template<class T, class Proj = identity,
109 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
110 constexpr const T& max(const T& a, const T& b, Comp comp = {}, Proj proj = {}); // since C++20
111
112 template<copyable T, class Proj = identity,
113 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
114 constexpr T max(initializer_list<T> r, Comp comp = {}, Proj proj = {}); // since C++20
115
116 template<input_range R, class Proj = identity,
117 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
118 requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
119 constexpr range_value_t<R>
120 max(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
Nikolas Klauser559a1772022-04-05 11:05:36 +0200121
122 template<class I, class O>
123 using unary_transform_result = in_out_result<I, O>; // since C++20
124
125 template<class I1, class I2, class O>
126 using binary_transform_result = in_in_out_result<I1, I2, O>; // since C++20
127
128 template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
129 copy_constructible F, class Proj = identity>
130 requires indirectly_writable<O, indirect_result_t<F&, projected<I, Proj>>>
131 constexpr ranges::unary_transform_result<I, O>
132 transform(I first1, S last1, O result, F op, Proj proj = {}); // since C++20
133
134 template<input_range R, weakly_incrementable O, copy_constructible F,
135 class Proj = identity>
136 requires indirectly_writable<O, indirect_result_t<F&, projected<iterator_t<R>, Proj>>>
137 constexpr ranges::unary_transform_result<borrowed_iterator_t<R>, O>
138 transform(R&& r, O result, F op, Proj proj = {}); // since C++20
139
140 template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
141 weakly_incrementable O, copy_constructible F, class Proj1 = identity,
142 class Proj2 = identity>
143 requires indirectly_writable<O, indirect_result_t<F&, projected<I1, Proj1>,
144 projected<I2, Proj2>>>
145 constexpr ranges::binary_transform_result<I1, I2, O>
146 transform(I1 first1, S1 last1, I2 first2, S2 last2, O result,
147 F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
148
149 template<input_range R1, input_range R2, weakly_incrementable O,
150 copy_constructible F, class Proj1 = identity, class Proj2 = identity>
151 requires indirectly_writable<O, indirect_result_t<F&, projected<iterator_t<R1>, Proj1>,
152 projected<iterator_t<R2>, Proj2>>>
153 constexpr ranges::binary_transform_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
154 transform(R1&& r1, R2&& r2, O result,
155 F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
Nikolas Klauserf1373d02022-04-07 13:02:02 +0200156
157 template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
158 requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
159 constexpr iter_difference_t<I>
160 count(I first, S last, const T& value, Proj proj = {}); // since C++20
161
162 template<input_range R, class T, class Proj = identity>
163 requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
164 constexpr range_difference_t<R>
165 count(R&& r, const T& value, Proj proj = {}); // since C++20
166
167 template<input_iterator I, sentinel_for<I> S, class Proj = identity,
168 indirect_unary_predicate<projected<I, Proj>> Pred>
169 constexpr iter_difference_t<I>
170 count_if(I first, S last, Pred pred, Proj proj = {}); // since C++20
171
172 template<input_range R, class Proj = identity,
173 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
174 constexpr range_difference_t<R>
175 count_if(R&& r, Pred pred, Proj proj = {}); // since C++20
Nikolas Klauser0a2f44f2022-04-13 22:59:09 +0200176
177 template<class T, class Proj = identity,
178 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
179 constexpr ranges::minmax_result<const T&>
180 minmax(const T& a, const T& b, Comp comp = {}, Proj proj = {}); // since C++20
181
182 template<copyable T, class Proj = identity,
183 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
184 constexpr ranges::minmax_result<T>
185 minmax(initializer_list<T> r, Comp comp = {}, Proj proj = {}); // since C++20
186
187 template<input_range R, class Proj = identity,
188 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
189 requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
190 constexpr ranges::minmax_result<range_value_t<R>>
191 minmax(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
192
193 template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
194 indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
195 constexpr ranges::minmax_element_result<I>
196 minmax_element(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
197
198 template<forward_range R, class Proj = identity,
199 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
200 constexpr ranges::minmax_element_result<borrowed_iterator_t<R>>
201 minmax_element(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
Nikolas Klauserd959d842022-04-15 13:43:40 +0200202
203 template<class I, class O>
204 using copy_result = in_out_result<I, O>; // since C++20
205
206 template<class I, class O>
207 using copy_n_result = in_out_result<I, O>; // since C++20
208
209 template<class I, class O>
210 using copy_if_result = in_out_result<I, O>; // since C++20
211
212 template<class I1, class I2>
213 using copy_backward_result = in_out_result<I1, I2>; // since C++20
214
215 template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>
216 requires indirectly_copyable<I, O>
217 constexpr ranges::copy_result<I, O> ranges::copy(I first, S last, O result); // since C++20
218
219 template<input_range R, weakly_incrementable O>
220 requires indirectly_copyable<iterator_t<R>, O>
221 constexpr ranges::copy_result<borrowed_iterator_t<R>, O> ranges::copy(R&& r, O result); // since C++20
222
223 template<input_iterator I, weakly_incrementable O>
224 requires indirectly_copyable<I, O>
225 constexpr ranges::copy_n_result<I, O>
226 ranges::copy_n(I first, iter_difference_t<I> n, O result); // since C++20
227
228 template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Proj = identity,
229 indirect_unary_predicate<projected<I, Proj>> Pred>
230 requires indirectly_copyable<I, O>
231 constexpr ranges::copy_if_result<I, O>
232 ranges::copy_if(I first, S last, O result, Pred pred, Proj proj = {}); // since C++20
233
234 template<input_range R, weakly_incrementable O, class Proj = identity,
235 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
236 requires indirectly_copyable<iterator_t<R>, O>
237 constexpr ranges::copy_if_result<borrowed_iterator_t<R>, O>
238 ranges::copy_if(R&& r, O result, Pred pred, Proj proj = {}); // since C++20
239
240 template<bidirectional_iterator I1, sentinel_for<I1> S1, bidirectional_iterator I2>
241 requires indirectly_copyable<I1, I2>
242 constexpr ranges::copy_backward_result<I1, I2>
243 ranges::copy_backward(I1 first, S1 last, I2 result); // since C++20
244
245 template<bidirectional_range R, bidirectional_iterator I>
246 requires indirectly_copyable<iterator_t<R>, I>
247 constexpr ranges::copy_backward_result<borrowed_iterator_t<R>, I>
248 ranges::copy_backward(R&& r, I result); // since C++20
Nikolas Klauser58de98c2022-05-04 20:27:07 +0200249
250 template<class I, class F>
251 using for_each_result = in_fun_result<I, F>; // since C++20
252
253 template<input_iterator I, sentinel_for<I> S, class Proj = identity,
254 indirectly_unary_invocable<projected<I, Proj>> Fun>
255 constexpr ranges::for_each_result<I, Fun>
256 ranges::for_each(I first, S last, Fun f, Proj proj = {}); // since C++20
257
258 template<input_range R, class Proj = identity,
259 indirectly_unary_invocable<projected<iterator_t<R>, Proj>> Fun>
260 constexpr ranges::for_each_result<borrowed_iterator_t<R>, Fun>
261 ranges::for_each(R&& r, Fun f, Proj proj = {}); // since C++20
262
263 template<input_iterator I, class Proj = identity,
264 indirectly_unary_invocable<projected<I, Proj>> Fun>
265 constexpr ranges::for_each_n_result<I, Fun>
266 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 +0200267
268 template<input_iterator I, sentinel_for<I> S, class Proj = identity,
269 indirect_unary_predicate<projected<I, Proj>> Pred>
270 constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {}); // since C++20
271
272 template<input_range R, class Proj = identity,
273 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
274 constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {}); // since C++20
275
Nikolas Klauser52f20072022-05-24 10:32:50 +0200276
277 template<bidirectional_iterator I, sentinel_for<I> S>
278 requires permutable<I>
279 constexpr I ranges::reverse(I first, S last); // since C++20
280
281 template<bidirectional_range R>
282 requires permutable<iterator_t<R>>
283 constexpr borrowed_iterator_t<R> ranges::reverse(R&& r); // since C++20
284
Konstantin Varlamov55e39a82022-06-16 15:20:53 -0700285 template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
286 class Proj = identity>
287 requires sortable<I, Comp, Proj>
288 constexpr I
289 sort(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
290
291 template<random_access_range R, class Comp = ranges::less, class Proj = identity>
292 requires sortable<iterator_t<R>, Comp, Proj>
293 constexpr borrowed_iterator_t<R>
294 sort(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
295
Nikolas Klausereb49c2a2022-05-21 18:26:29 +0200296 template<class T, output_iterator<const T&> O, sentinel_for<O> S>
297 constexpr O ranges::fill(O first, S last, const T& value); // since C++20
298
299 template<class T, output_range<const T&> R>
300 constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value); // since C++20
301
302 template<class T, output_iterator<const T&> O>
303 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 +0200304
305 template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
306 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
307 requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
308 constexpr bool ranges::equal(I1 first1, S1 last1, I2 first2, S2 last2,
309 Pred pred = {},
310 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
311
312 template<input_range R1, input_range R2, class Pred = ranges::equal_to,
313 class Proj1 = identity, class Proj2 = identity>
314 requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
315 constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {},
316 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
317
Nikolas Klausered3f0e82022-05-26 16:42:46 +0200318 template<input_iterator I, sentinel_for<I> S, class Proj = identity,
319 indirect_unary_predicate<projected<I, Proj>> Pred>
320 constexpr bool ranges::all_of(I first, S last, Pred pred, Proj proj = {}); // since C++20
321
322 template<input_range R, class Proj = identity,
323 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
324 constexpr bool ranges::all_of(R&& r, Pred pred, Proj proj = {}); // since C++20
325
326 template<input_iterator I, sentinel_for<I> S, class Proj = identity,
327 indirect_unary_predicate<projected<I, Proj>> Pred>
328 constexpr bool ranges::any_of(I first, S last, Pred pred, Proj proj = {}); // since C++20
329
330 template<input_range R, class Proj = identity,
331 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
332 constexpr bool ranges::any_of(R&& r, Pred pred, Proj proj = {}); // since C++20
333
334 template<input_iterator I, sentinel_for<I> S, class Proj = identity,
335 indirect_unary_predicate<projected<I, Proj>> Pred>
336 constexpr bool ranges::none_of(I first, S last, Pred pred, Proj proj = {}); // since C++20
337
338 template<input_range R, class Proj = identity,
339 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
340 constexpr bool ranges::none_of(R&& r, Pred pred, Proj proj = {}); // since C++20
341
Nikolas Klauserab0b7af2022-05-26 16:08:55 +0200342 template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
343 indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
344 constexpr bool ranges::is_sorted(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
345
346 template<forward_range R, class Proj = identity,
347 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
348 constexpr bool ranges::is_sorted(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
349
350 template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
351 indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
352 constexpr I ranges::is_sorted_until(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
353
354 template<forward_range R, class Proj = identity,
355 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
356 constexpr borrowed_iterator_t<R>
357 ranges::is_sorted_until(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
Nikolas Klauser8b381972022-06-05 21:15:16 +0200358
359 template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
360 indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
361 constexpr I upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
362
363 template<forward_range R, class T, class Proj = identity,
364 indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
365 ranges::less>
366 constexpr borrowed_iterator_t<R>
367 upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
368
369 template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
370 indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
371 constexpr I lower_bound(I first, S last, const T& value, Comp comp = {},
372 Proj proj = {}); // since C++20
373 template<forward_range R, class T, class Proj = identity,
374 indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
375 ranges::less>
376 constexpr borrowed_iterator_t<R>
377 lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
378
379 template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
380 indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
381 constexpr bool binary_search(I first, S last, const T& value, Comp comp = {},
382 Proj proj = {}); // since C++20
Nikolas Klauser0a7e46d2022-06-06 13:57:34 +0200383
Nikolas Klauser8b381972022-06-05 21:15:16 +0200384 template<forward_range R, class T, class Proj = identity,
385 indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
386 ranges::less>
387 constexpr bool binary_search(R&& r, const T& value, Comp comp = {},
388 Proj proj = {}); // since C++20
Nikolas Klauser0a7e46d2022-06-06 13:57:34 +0200389 template<input_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
390 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
391 requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
392 constexpr I1 ranges::find_first_of(I1 first1, S1 last1, I2 first2, S2 last2,
393 Pred pred = {},
394 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
395
396 template<input_range R1, forward_range R2,
397 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
398 requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
399 constexpr borrowed_iterator_t<R1>
400 ranges::find_first_of(R1&& r1, R2&& r2,
401 Pred pred = {},
402 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
Nikolas Klauser8b381972022-06-05 21:15:16 +0200403
Nikolas Klauser5ae708f2022-06-08 12:14:12 +0200404 template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
405 indirect_binary_predicate<projected<I, Proj>,
406 projected<I, Proj>> Pred = ranges::equal_to>
407 constexpr I ranges::adjacent_find(I first, S last, Pred pred = {}, Proj proj = {}); // since C+20
408
409 template<forward_range R, class Proj = identity,
410 indirect_binary_predicate<projected<iterator_t<R>, Proj>,
411 projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>
412 constexpr borrowed_iterator_t<R> ranges::adjacent_find(R&& r, Pred pred = {}, Proj proj = {}); // since C++20
413
Nikolas Klauserfadea392022-06-07 09:42:10 +0200414 template<input_iterator I, sentinel_for<I> S, class T1, class T2, class Proj = identity>
415 requires indirectly_writable<I, const T2&> &&
416 indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*>
417 constexpr I
418 ranges::replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = {}); // since C++20
419
420 template<input_range R, class T1, class T2, class Proj = identity>
421 requires indirectly_writable<iterator_t<R>, const T2&> &&
422 indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
423 constexpr borrowed_iterator_t<R>
424 ranges::replace(R&& r, const T1& old_value, const T2& new_value, Proj proj = {}); // since C++20
425
426 template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity,
427 indirect_unary_predicate<projected<I, Proj>> Pred>
428 requires indirectly_writable<I, const T&>
429 constexpr I ranges::replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = {}); // since C++20
430
431 template<input_range R, class T, class Proj = identity,
432 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
433 requires indirectly_writable<iterator_t<R>, const T&>
434 constexpr borrowed_iterator_t<R>
435 ranges::replace_if(R&& r, Pred pred, const T& new_value, Proj proj = {}); // since C++20
436
Nikolas Klauser2fd677c2022-06-15 16:24:43 +0200437 template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
438 class Proj1 = identity, class Proj2 = identity,
439 indirect_strict_weak_order<projected<I1, Proj1>,
440 projected<I2, Proj2>> Comp = ranges::less>
441 constexpr bool
442 ranges::lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2,
443 Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
444
445 template<input_range R1, input_range R2, class Proj1 = identity,
446 class Proj2 = identity,
447 indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
448 projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
449 constexpr bool
450 ranges::lexicographical_compare(R1&& r1, R2&& r2, Comp comp = {},
451 Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
452
Nikolas Klauser16661d82022-06-23 12:23:41 +0200453 template<bidirectional_iterator I1, sentinel_for<I1> S1, bidirectional_iterator I2>
454 requires indirectly_movable<I1, I2>
455 constexpr ranges::move_backward_result<I1, I2>
456 ranges::move_backward(I1 first, S1 last, I2 result); // since C++20
457
458 template<bidirectional_range R, bidirectional_iterator I>
459 requires indirectly_movable<iterator_t<R>, I>
460 constexpr ranges::move_backward_result<borrowed_iterator_t<R>, I>
461 ranges::move_backward(R&& r, I result); // since C++20
462
463 template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>
464 requires indirectly_movable<I, O>
465 constexpr ranges::move_result<I, O>
466 ranges::move(I first, S last, O result); // since C++20
467
468 template<input_range R, weakly_incrementable O>
469 requires indirectly_movable<iterator_t<R>, O>
470 constexpr ranges::move_result<borrowed_iterator_t<R>, O>
471 ranges::move(R&& r, O result); // since C++20
472
473
Nikolas Klauserf74be4e2022-01-14 02:55:51 +0100474}
475
Marshall Clowd607fdb2018-01-15 17:20:36 +0000476 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000477 all_of(InputIterator first, InputIterator last, Predicate pred);
478
479template <class InputIterator, class Predicate>
Marshall Clowd607fdb2018-01-15 17:20:36 +0000480 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000481 any_of(InputIterator first, InputIterator last, Predicate pred);
482
483template <class InputIterator, class Predicate>
Marshall Clowd607fdb2018-01-15 17:20:36 +0000484 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000485 none_of(InputIterator first, InputIterator last, Predicate pred);
486
487template <class InputIterator, class Function>
Marshall Clow5492c8a2018-01-22 20:44:33 +0000488 constexpr Function // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000489 for_each(InputIterator first, InputIterator last, Function f);
490
Marshall Clowde0169c2017-05-25 02:29:54 +0000491template<class InputIterator, class Size, class Function>
Marshall Clow5492c8a2018-01-22 20:44:33 +0000492 constexpr InputIterator // constexpr in C++20
493 for_each_n(InputIterator first, Size n, Function f); // C++17
Marshall Clowde0169c2017-05-25 02:29:54 +0000494
Howard Hinnantc51e1022010-05-11 19:42:16 +0000495template <class InputIterator, class T>
Marshall Clowee0161e2018-01-15 19:26:05 +0000496 constexpr InputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000497 find(InputIterator first, InputIterator last, const T& value);
498
499template <class InputIterator, class Predicate>
Marshall Clowee0161e2018-01-15 19:26:05 +0000500 constexpr InputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000501 find_if(InputIterator first, InputIterator last, Predicate pred);
502
503template<class InputIterator, class Predicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500504 constexpr InputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000505 find_if_not(InputIterator first, InputIterator last, Predicate pred);
506
507template <class ForwardIterator1, class ForwardIterator2>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500508 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000509 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
510 ForwardIterator2 first2, ForwardIterator2 last2);
511
512template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500513 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000514 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
515 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
516
517template <class ForwardIterator1, class ForwardIterator2>
Marshall Clowee0161e2018-01-15 19:26:05 +0000518 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000519 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
520 ForwardIterator2 first2, ForwardIterator2 last2);
521
522template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clowee0161e2018-01-15 19:26:05 +0000523 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000524 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
525 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
526
527template <class ForwardIterator>
Marshall Clowee0161e2018-01-15 19:26:05 +0000528 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000529 adjacent_find(ForwardIterator first, ForwardIterator last);
530
531template <class ForwardIterator, class BinaryPredicate>
Marshall Clowee0161e2018-01-15 19:26:05 +0000532 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000533 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
534
535template <class InputIterator, class T>
Marshall Clow3c0558f2018-01-15 19:40:34 +0000536 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000537 count(InputIterator first, InputIterator last, const T& value);
538
539template <class InputIterator, class Predicate>
Marshall Clow3c0558f2018-01-15 19:40:34 +0000540 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000541 count_if(InputIterator first, InputIterator last, Predicate pred);
542
543template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000544 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000545 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
546
Marshall Clow96b42b22013-05-09 21:14:23 +0000547template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000548 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Aditya Kumar3a0179a2016-08-25 11:52:38 +0000549 mismatch(InputIterator1 first1, InputIterator1 last1,
Marshall Clow96b42b22013-05-09 21:14:23 +0000550 InputIterator2 first2, InputIterator2 last2); // **C++14**
551
Howard Hinnantc51e1022010-05-11 19:42:16 +0000552template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000553 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000554 mismatch(InputIterator1 first1, InputIterator1 last1,
555 InputIterator2 first2, BinaryPredicate pred);
556
Marshall Clow96b42b22013-05-09 21:14:23 +0000557template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000558 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000559 mismatch(InputIterator1 first1, InputIterator1 last1,
560 InputIterator2 first2, InputIterator2 last2,
561 BinaryPredicate pred); // **C++14**
562
Howard Hinnantc51e1022010-05-11 19:42:16 +0000563template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000564 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000565 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
566
Marshall Clow96b42b22013-05-09 21:14:23 +0000567template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000568 constexpr bool // constexpr in C++20
Aditya Kumar3a0179a2016-08-25 11:52:38 +0000569 equal(InputIterator1 first1, InputIterator1 last1,
Marshall Clow96b42b22013-05-09 21:14:23 +0000570 InputIterator2 first2, InputIterator2 last2); // **C++14**
571
Howard Hinnantc51e1022010-05-11 19:42:16 +0000572template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000573 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000574 equal(InputIterator1 first1, InputIterator1 last1,
575 InputIterator2 first2, BinaryPredicate pred);
576
Marshall Clow96b42b22013-05-09 21:14:23 +0000577template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000578 constexpr bool // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000579 equal(InputIterator1 first1, InputIterator1 last1,
580 InputIterator2 first2, InputIterator2 last2,
581 BinaryPredicate pred); // **C++14**
582
Howard Hinnantc51e1022010-05-11 19:42:16 +0000583template<class ForwardIterator1, class ForwardIterator2>
Marshall Clow96d050a2018-01-15 16:16:32 +0000584 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000585 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
586 ForwardIterator2 first2);
587
Marshall Clow96b42b22013-05-09 21:14:23 +0000588template<class ForwardIterator1, class ForwardIterator2>
Marshall Clow96d050a2018-01-15 16:16:32 +0000589 constexpr bool // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000590 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
591 ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**
592
Howard Hinnantc51e1022010-05-11 19:42:16 +0000593template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clow96d050a2018-01-15 16:16:32 +0000594 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000595 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
596 ForwardIterator2 first2, BinaryPredicate pred);
597
Marshall Clow96b42b22013-05-09 21:14:23 +0000598template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clow96d050a2018-01-15 16:16:32 +0000599 constexpr bool // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000600 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
601 ForwardIterator2 first2, ForwardIterator2 last2,
602 BinaryPredicate pred); // **C++14**
603
Howard Hinnantc51e1022010-05-11 19:42:16 +0000604template <class ForwardIterator1, class ForwardIterator2>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000605 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000606 search(ForwardIterator1 first1, ForwardIterator1 last1,
607 ForwardIterator2 first2, ForwardIterator2 last2);
608
609template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000610 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000611 search(ForwardIterator1 first1, ForwardIterator1 last1,
612 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
613
614template <class ForwardIterator, class Size, class T>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000615 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000616 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
617
618template <class ForwardIterator, class Size, class T, class BinaryPredicate>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000619 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000620 search_n(ForwardIterator first, ForwardIterator last,
621 Size count, const T& value, BinaryPredicate pred);
622
623template <class InputIterator, class OutputIterator>
Louis Dionne65b433b2019-11-06 12:02:41 +0000624 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000625 copy(InputIterator first, InputIterator last, OutputIterator result);
626
627template<class InputIterator, class OutputIterator, class Predicate>
Louis Dionne65b433b2019-11-06 12:02:41 +0000628 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000629 copy_if(InputIterator first, InputIterator last,
630 OutputIterator result, Predicate pred);
631
632template<class InputIterator, class Size, class OutputIterator>
Louis Dionne65b433b2019-11-06 12:02:41 +0000633 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000634 copy_n(InputIterator first, Size n, OutputIterator result);
635
636template <class BidirectionalIterator1, class BidirectionalIterator2>
Louis Dionne65b433b2019-11-06 12:02:41 +0000637 constexpr BidirectionalIterator2 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000638 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
639 BidirectionalIterator2 result);
640
641template <class ForwardIterator1, class ForwardIterator2>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500642 constexpr ForwardIterator2 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000643 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
644
Nikolas Klauser4ceab5f2022-02-10 13:33:03 +0100645template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2>
646 requires indirectly_swappable<I1, I2>
647 constexpr ranges::swap_ranges_result<I1, I2>
648 ranges::swap_ranges(I1 first1, S1 last1, I2 first2, S2 last2);
649
650template<input_range R1, input_range R2>
651 requires indirectly_swappable<iterator_t<R1>, iterator_t<R2>>
652 constexpr ranges::swap_ranges_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
653 ranges::swap_ranges(R1&& r1, R2&& r2);
654
Howard Hinnantc51e1022010-05-11 19:42:16 +0000655template <class ForwardIterator1, class ForwardIterator2>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500656 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000657 iter_swap(ForwardIterator1 a, ForwardIterator2 b);
658
659template <class InputIterator, class OutputIterator, class UnaryOperation>
Marshall Clow31427c62018-01-19 17:45:39 +0000660 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000661 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
662
663template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
Marshall Clow31427c62018-01-19 17:45:39 +0000664 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000665 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
666 OutputIterator result, BinaryOperation binary_op);
667
668template <class ForwardIterator, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000669 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000670 replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
671
672template <class ForwardIterator, class Predicate, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000673 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000674 replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
675
676template <class InputIterator, class OutputIterator, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000677 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000678 replace_copy(InputIterator first, InputIterator last, OutputIterator result,
679 const T& old_value, const T& new_value);
680
681template <class InputIterator, class OutputIterator, class Predicate, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000682 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000683 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
684
685template <class ForwardIterator, class T>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000686 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000687 fill(ForwardIterator first, ForwardIterator last, const T& value);
688
689template <class OutputIterator, class Size, class T>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000690 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000691 fill_n(OutputIterator first, Size n, const T& value);
692
693template <class ForwardIterator, class Generator>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000694 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000695 generate(ForwardIterator first, ForwardIterator last, Generator gen);
696
697template <class OutputIterator, class Size, class Generator>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000698 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000699 generate_n(OutputIterator first, Size n, Generator gen);
700
701template <class ForwardIterator, class T>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000702 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000703 remove(ForwardIterator first, ForwardIterator last, const T& value);
704
705template <class ForwardIterator, class Predicate>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000706 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000707 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
708
709template <class InputIterator, class OutputIterator, class T>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000710 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000711 remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
712
713template <class InputIterator, class OutputIterator, class Predicate>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000714 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000715 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
716
717template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500718 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000719 unique(ForwardIterator first, ForwardIterator last);
720
721template <class ForwardIterator, class BinaryPredicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500722 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000723 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
724
725template <class InputIterator, class OutputIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500726 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000727 unique_copy(InputIterator first, InputIterator last, OutputIterator result);
728
729template <class InputIterator, class OutputIterator, class BinaryPredicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500730 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000731 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
732
733template <class BidirectionalIterator>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -0500734 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000735 reverse(BidirectionalIterator first, BidirectionalIterator last);
736
737template <class BidirectionalIterator, class OutputIterator>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000738 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000739 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
740
741template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500742 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000743 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
744
745template <class ForwardIterator, class OutputIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500746 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000747 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
748
749template <class RandomAccessIterator>
750 void
Marshall Clowfac06e52017-03-23 13:43:37 +0000751 random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000752
753template <class RandomAccessIterator, class RandomNumberGenerator>
754 void
Marshall Clow83f35392014-03-03 06:14:19 +0000755 random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
Marshall Clowfac06e52017-03-23 13:43:37 +0000756 RandomNumberGenerator& rand); // deprecated in C++14, removed in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000757
Eric Fiselier1208fcd2016-08-28 22:14:37 +0000758template<class PopulationIterator, class SampleIterator,
759 class Distance, class UniformRandomBitGenerator>
760 SampleIterator sample(PopulationIterator first, PopulationIterator last,
761 SampleIterator out, Distance n,
762 UniformRandomBitGenerator&& g); // C++17
763
Howard Hinnant578ac0f2010-05-26 17:49:34 +0000764template<class RandomAccessIterator, class UniformRandomNumberGenerator>
765 void shuffle(RandomAccessIterator first, RandomAccessIterator last,
Howard Hinnanta5e71782010-11-18 01:47:02 +0000766 UniformRandomNumberGenerator&& g);
Howard Hinnant578ac0f2010-05-26 17:49:34 +0000767
Arthur O'Dwyercea050d2020-12-26 01:39:03 -0500768template<class ForwardIterator>
769 constexpr ForwardIterator
770 shift_left(ForwardIterator first, ForwardIterator last,
771 typename iterator_traits<ForwardIterator>::difference_type n); // C++20
772
773template<class ForwardIterator>
774 constexpr ForwardIterator
775 shift_right(ForwardIterator first, ForwardIterator last,
776 typename iterator_traits<ForwardIterator>::difference_type n); // C++20
777
Howard Hinnantc51e1022010-05-11 19:42:16 +0000778template <class InputIterator, class Predicate>
Marshall Clow96d050a2018-01-15 16:16:32 +0000779 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000780 is_partitioned(InputIterator first, InputIterator last, Predicate pred);
781
782template <class ForwardIterator, class Predicate>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -0500783 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000784 partition(ForwardIterator first, ForwardIterator last, Predicate pred);
785
786template <class InputIterator, class OutputIterator1,
787 class OutputIterator2, class Predicate>
Marshall Clow5492c8a2018-01-22 20:44:33 +0000788 constexpr pair<OutputIterator1, OutputIterator2> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000789 partition_copy(InputIterator first, InputIterator last,
790 OutputIterator1 out_true, OutputIterator2 out_false,
791 Predicate pred);
792
793template <class ForwardIterator, class Predicate>
794 ForwardIterator
795 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
796
797template<class ForwardIterator, class Predicate>
Marshall Clowe00916c2018-01-16 02:34:41 +0000798 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000799 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
800
801template <class ForwardIterator>
Marshall Clow96d050a2018-01-15 16:16:32 +0000802 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000803 is_sorted(ForwardIterator first, ForwardIterator last);
804
805template <class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500806 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000807 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
808
809template<class ForwardIterator>
Marshall Clow3c0558f2018-01-15 19:40:34 +0000810 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000811 is_sorted_until(ForwardIterator first, ForwardIterator last);
812
813template <class ForwardIterator, class Compare>
Marshall Clow3c0558f2018-01-15 19:40:34 +0000814 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000815 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
816
817template <class RandomAccessIterator>
Arthur O'Dwyer1bb0f672020-12-20 15:21:42 -0500818 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000819 sort(RandomAccessIterator first, RandomAccessIterator last);
820
821template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer1bb0f672020-12-20 15:21:42 -0500822 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000823 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
824
825template <class RandomAccessIterator>
826 void
827 stable_sort(RandomAccessIterator first, RandomAccessIterator last);
828
829template <class RandomAccessIterator, class Compare>
830 void
831 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
832
833template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500834 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000835 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
836
837template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500838 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000839 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
840
841template <class InputIterator, class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500842 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000843 partial_sort_copy(InputIterator first, InputIterator last,
844 RandomAccessIterator result_first, RandomAccessIterator result_last);
845
846template <class InputIterator, class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500847 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000848 partial_sort_copy(InputIterator first, InputIterator last,
849 RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
850
851template <class RandomAccessIterator>
Arthur O'Dwyer4f5717b2021-02-04 18:12:52 -0500852 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000853 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
854
855template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer4f5717b2021-02-04 18:12:52 -0500856 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000857 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
858
859template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +0000860 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000861 lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
862
863template <class ForwardIterator, class T, class Compare>
Marshall Clowe00916c2018-01-16 02:34:41 +0000864 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000865 lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
866
867template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +0000868 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000869 upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
870
871template <class ForwardIterator, class T, class Compare>
Marshall Clowe00916c2018-01-16 02:34:41 +0000872 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000873 upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
874
875template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +0000876 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000877 equal_range(ForwardIterator first, ForwardIterator last, const T& value);
878
879template <class ForwardIterator, class T, class Compare>
Marshall Clowe00916c2018-01-16 02:34:41 +0000880 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000881 equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
882
883template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +0000884 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000885 binary_search(ForwardIterator first, ForwardIterator last, const T& value);
886
887template <class ForwardIterator, class T, class Compare>
Marshall Clowc0b7f972018-01-22 23:10:40 +0000888 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000889 binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
890
891template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500892 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000893 merge(InputIterator1 first1, InputIterator1 last1,
894 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
895
896template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500897 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000898 merge(InputIterator1 first1, InputIterator1 last1,
899 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
900
901template <class BidirectionalIterator>
902 void
903 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
904
905template <class BidirectionalIterator, class Compare>
906 void
907 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
908
909template <class InputIterator1, class InputIterator2>
Marshall Clowc0b7f972018-01-22 23:10:40 +0000910 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000911 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
912
913template <class InputIterator1, class InputIterator2, class Compare>
Marshall Clowc0b7f972018-01-22 23:10:40 +0000914 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000915 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
916
917template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500918 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000919 set_union(InputIterator1 first1, InputIterator1 last1,
920 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
921
922template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500923 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000924 set_union(InputIterator1 first1, InputIterator1 last1,
925 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
926
927template <class InputIterator1, class InputIterator2, class OutputIterator>
Marshall Clowc0b7f972018-01-22 23:10:40 +0000928 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000929 set_intersection(InputIterator1 first1, InputIterator1 last1,
930 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
931
932template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Marshall Clowc0b7f972018-01-22 23:10:40 +0000933 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000934 set_intersection(InputIterator1 first1, InputIterator1 last1,
935 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
936
937template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500938 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000939 set_difference(InputIterator1 first1, InputIterator1 last1,
940 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
941
942template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500943 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000944 set_difference(InputIterator1 first1, InputIterator1 last1,
945 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
946
947template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500948 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000949 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
950 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
951
952template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500953 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000954 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
955 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
956
957template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500958 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000959 push_heap(RandomAccessIterator first, RandomAccessIterator last);
960
961template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500962 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000963 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
964
965template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500966 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000967 pop_heap(RandomAccessIterator first, RandomAccessIterator last);
968
969template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500970 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000971 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
972
973template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500974 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000975 make_heap(RandomAccessIterator first, RandomAccessIterator last);
976
977template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500978 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000979 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
980
981template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500982 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000983 sort_heap(RandomAccessIterator first, RandomAccessIterator last);
984
985template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500986 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000987 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
988
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000989template <class RandomAccessIterator>
Marshall Clow96d050a2018-01-15 16:16:32 +0000990 constexpr bool // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000991 is_heap(RandomAccessIterator first, RandomAccessiterator last);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000992
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000993template <class RandomAccessIterator, class Compare>
Marshall Clow96d050a2018-01-15 16:16:32 +0000994 constexpr bool // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000995 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000996
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000997template <class RandomAccessIterator>
Marshall Clow96d050a2018-01-15 16:16:32 +0000998 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000999 is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001000
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001001template <class RandomAccessIterator, class Compare>
Marshall Clow96d050a2018-01-15 16:16:32 +00001002 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001003 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001004
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001005template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001006 constexpr ForwardIterator // constexpr in C++14
1007 min_element(ForwardIterator first, ForwardIterator last);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001008
1009template <class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001010 constexpr ForwardIterator // constexpr in C++14
1011 min_element(ForwardIterator first, ForwardIterator last, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001012
Howard Hinnantc51e1022010-05-11 19:42:16 +00001013template <class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001014 constexpr const T& // constexpr in C++14
1015 min(const T& a, const T& b);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001016
1017template <class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001018 constexpr const T& // constexpr in C++14
1019 min(const T& a, const T& b, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001020
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001021template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001022 constexpr T // constexpr in C++14
1023 min(initializer_list<T> t);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001024
1025template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001026 constexpr T // constexpr in C++14
1027 min(initializer_list<T> t, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001028
Marshall Clow3e18d0e2016-03-07 22:43:49 +00001029template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001030 constexpr const T& clamp(const T& v, const T& lo, const T& hi); // C++17
Marshall Clow3e18d0e2016-03-07 22:43:49 +00001031
1032template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001033 constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp); // C++17
Marshall Clow3e18d0e2016-03-07 22:43:49 +00001034
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001035template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001036 constexpr ForwardIterator // constexpr in C++14
1037 max_element(ForwardIterator first, ForwardIterator last);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001038
1039template <class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001040 constexpr ForwardIterator // constexpr in C++14
1041 max_element(ForwardIterator first, ForwardIterator last, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001042
Howard Hinnantc51e1022010-05-11 19:42:16 +00001043template <class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001044 constexpr const T& // constexpr in C++14
1045 max(const T& a, const T& b);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001046
1047template <class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001048 constexpr const T& // constexpr in C++14
1049 max(const T& a, const T& b, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001050
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001051template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001052 constexpr T // constexpr in C++14
1053 max(initializer_list<T> t);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001054
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001055template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001056 constexpr T // constexpr in C++14
1057 max(initializer_list<T> t, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001058
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001059template<class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001060 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14
1061 minmax_element(ForwardIterator first, ForwardIterator last);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001062
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001063template<class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001064 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14
1065 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001066
1067template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001068 constexpr pair<const T&, const T&> // constexpr in C++14
1069 minmax(const T& a, const T& b);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001070
1071template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001072 constexpr pair<const T&, const T&> // constexpr in C++14
1073 minmax(const T& a, const T& b, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001074
1075template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001076 constexpr pair<T, T> // constexpr in C++14
1077 minmax(initializer_list<T> t);
Howard Hinnantb120e7a2010-08-21 20:10:01 +00001078
1079template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -05001080 constexpr pair<T, T> // constexpr in C++14
1081 minmax(initializer_list<T> t, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001082
1083template <class InputIterator1, class InputIterator2>
Marshall Clow5492c8a2018-01-22 20:44:33 +00001084 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001085 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
1086
1087template <class InputIterator1, class InputIterator2, class Compare>
Marshall Clow5492c8a2018-01-22 20:44:33 +00001088 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001089 lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
1090 InputIterator2 first2, InputIterator2 last2, Compare comp);
1091
1092template <class BidirectionalIterator>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -05001093 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001094 next_permutation(BidirectionalIterator first, BidirectionalIterator last);
1095
1096template <class BidirectionalIterator, class Compare>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -05001097 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001098 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
1099
1100template <class BidirectionalIterator>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -05001101 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001102 prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
1103
1104template <class BidirectionalIterator, class Compare>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -05001105 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +00001106 prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001107} // std
1108
1109*/
1110
Louis Dionneb4fce352022-03-25 12:55:36 -04001111#include <__assert> // all public C++ headers provide the assertion handler
Arthur O'Dwyer3693d7a2022-02-04 13:09:30 -05001112#include <__bits>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001113#include <__config>
Louis Dionnea60dd872021-06-17 11:30:11 -04001114#include <__debug>
Howard Hinnant60e5cf42012-07-26 17:09:09 +00001115#include <cstddef>
Arthur O'Dwyeref181602021-05-19 11:57:04 -04001116#include <cstring>
Arthur O'Dwyeref181602021-05-19 11:57:04 -04001117#include <memory>
1118#include <type_traits>
Marshall Clow0a1e7502018-09-12 19:41:40 +00001119#include <version>
Howard Hinnantea382952013-08-14 18:00:20 +00001120
Louis Dionnea60dd872021-06-17 11:30:11 -04001121#include <__algorithm/adjacent_find.h>
1122#include <__algorithm/all_of.h>
1123#include <__algorithm/any_of.h>
1124#include <__algorithm/binary_search.h>
1125#include <__algorithm/clamp.h>
1126#include <__algorithm/comp.h>
1127#include <__algorithm/comp_ref_type.h>
1128#include <__algorithm/copy.h>
1129#include <__algorithm/copy_backward.h>
1130#include <__algorithm/copy_if.h>
1131#include <__algorithm/copy_n.h>
1132#include <__algorithm/count.h>
1133#include <__algorithm/count_if.h>
1134#include <__algorithm/equal.h>
1135#include <__algorithm/equal_range.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001136#include <__algorithm/fill.h>
Arthur O'Dwyer65077c02022-01-07 09:45:05 -05001137#include <__algorithm/fill_n.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001138#include <__algorithm/find.h>
1139#include <__algorithm/find_end.h>
1140#include <__algorithm/find_first_of.h>
1141#include <__algorithm/find_if.h>
1142#include <__algorithm/find_if_not.h>
1143#include <__algorithm/for_each.h>
1144#include <__algorithm/for_each_n.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001145#include <__algorithm/generate.h>
Arthur O'Dwyer65077c02022-01-07 09:45:05 -05001146#include <__algorithm/generate_n.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001147#include <__algorithm/half_positive.h>
Nikolas Klauserdd5ad212022-02-21 23:07:02 +01001148#include <__algorithm/in_found_result.h>
Nikolas Klauser671b4752022-02-11 17:01:58 +01001149#include <__algorithm/in_fun_result.h>
Nikolas Klauser05e2cd82022-01-25 11:21:47 +01001150#include <__algorithm/in_in_out_result.h>
Nikolas Klauserf74be4e2022-01-14 02:55:51 +01001151#include <__algorithm/in_in_result.h>
Nikolas Klauser61ce8162022-02-03 02:17:03 +01001152#include <__algorithm/in_out_out_result.h>
Konstantin Varlamov74736812022-01-10 22:49:37 -08001153#include <__algorithm/in_out_result.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001154#include <__algorithm/includes.h>
1155#include <__algorithm/inplace_merge.h>
1156#include <__algorithm/is_heap.h>
1157#include <__algorithm/is_heap_until.h>
1158#include <__algorithm/is_partitioned.h>
1159#include <__algorithm/is_permutation.h>
1160#include <__algorithm/is_sorted.h>
1161#include <__algorithm/is_sorted_until.h>
Christopher Di Bella41f26e82021-06-05 02:47:47 +00001162#include <__algorithm/iter_swap.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001163#include <__algorithm/lexicographical_compare.h>
1164#include <__algorithm/lower_bound.h>
1165#include <__algorithm/make_heap.h>
1166#include <__algorithm/max.h>
1167#include <__algorithm/max_element.h>
1168#include <__algorithm/merge.h>
1169#include <__algorithm/min.h>
1170#include <__algorithm/min_element.h>
Nikolas Klauser2e263162022-02-21 22:48:36 +01001171#include <__algorithm/min_max_result.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001172#include <__algorithm/minmax.h>
1173#include <__algorithm/minmax_element.h>
1174#include <__algorithm/mismatch.h>
1175#include <__algorithm/move.h>
1176#include <__algorithm/move_backward.h>
1177#include <__algorithm/next_permutation.h>
1178#include <__algorithm/none_of.h>
1179#include <__algorithm/nth_element.h>
1180#include <__algorithm/partial_sort.h>
1181#include <__algorithm/partial_sort_copy.h>
1182#include <__algorithm/partition.h>
1183#include <__algorithm/partition_copy.h>
1184#include <__algorithm/partition_point.h>
1185#include <__algorithm/pop_heap.h>
1186#include <__algorithm/prev_permutation.h>
1187#include <__algorithm/push_heap.h>
Nikolas Klauser5ae708f2022-06-08 12:14:12 +02001188#include <__algorithm/ranges_adjacent_find.h>
Nikolas Klausered3f0e82022-05-26 16:42:46 +02001189#include <__algorithm/ranges_all_of.h>
1190#include <__algorithm/ranges_any_of.h>
Nikolas Klauser8b381972022-06-05 21:15:16 +02001191#include <__algorithm/ranges_binary_search.h>
Nikolas Klauserd959d842022-04-15 13:43:40 +02001192#include <__algorithm/ranges_copy.h>
1193#include <__algorithm/ranges_copy_backward.h>
1194#include <__algorithm/ranges_copy_if.h>
1195#include <__algorithm/ranges_copy_n.h>
Nikolas Klauserf1373d02022-04-07 13:02:02 +02001196#include <__algorithm/ranges_count.h>
1197#include <__algorithm/ranges_count_if.h>
Nikolas Klauser353f1dd2022-05-25 11:09:43 +02001198#include <__algorithm/ranges_equal.h>
Nikolas Klausereb49c2a2022-05-21 18:26:29 +02001199#include <__algorithm/ranges_fill.h>
1200#include <__algorithm/ranges_fill_n.h>
Nikolas Klauser37d076e2022-03-12 01:45:35 +01001201#include <__algorithm/ranges_find.h>
Nikolas Klauser0a7e46d2022-06-06 13:57:34 +02001202#include <__algorithm/ranges_find_first_of.h>
Nikolas Klauser37d076e2022-03-12 01:45:35 +01001203#include <__algorithm/ranges_find_if.h>
1204#include <__algorithm/ranges_find_if_not.h>
Nikolas Klauser58de98c2022-05-04 20:27:07 +02001205#include <__algorithm/ranges_for_each.h>
1206#include <__algorithm/ranges_for_each_n.h>
Nikolas Klauserbb9049d2022-05-04 14:19:09 +02001207#include <__algorithm/ranges_is_partitioned.h>
Nikolas Klauserab0b7af2022-05-26 16:08:55 +02001208#include <__algorithm/ranges_is_sorted.h>
1209#include <__algorithm/ranges_is_sorted_until.h>
Nikolas Klauser2fd677c2022-06-15 16:24:43 +02001210#include <__algorithm/ranges_lexicographical_compare.h>
Nikolas Klauser8b381972022-06-05 21:15:16 +02001211#include <__algorithm/ranges_lower_bound.h>
Nikolas Klauser573cd6f2022-04-03 09:17:01 +02001212#include <__algorithm/ranges_max.h>
Nikolas Klauserf2a69ea2022-03-07 17:01:52 +01001213#include <__algorithm/ranges_max_element.h>
Nikolas Klauser3559e452022-03-18 02:57:08 +01001214#include <__algorithm/ranges_min.h>
Nikolas Klauser0a62a172022-02-11 13:11:57 +01001215#include <__algorithm/ranges_min_element.h>
Nikolas Klauser0a2f44f2022-04-13 22:59:09 +02001216#include <__algorithm/ranges_minmax.h>
1217#include <__algorithm/ranges_minmax_element.h>
Nikolas Klauser12fc9bf2022-03-08 23:12:35 +01001218#include <__algorithm/ranges_mismatch.h>
Nikolas Klauser16661d82022-06-23 12:23:41 +02001219#include <__algorithm/ranges_move.h>
1220#include <__algorithm/ranges_move_backward.h>
Nikolas Klausered3f0e82022-05-26 16:42:46 +02001221#include <__algorithm/ranges_none_of.h>
Nikolas Klauserfadea392022-06-07 09:42:10 +02001222#include <__algorithm/ranges_replace.h>
1223#include <__algorithm/ranges_replace_if.h>
Nikolas Klauser52f20072022-05-24 10:32:50 +02001224#include <__algorithm/ranges_reverse.h>
Konstantin Varlamov55e39a82022-06-16 15:20:53 -07001225#include <__algorithm/ranges_sort.h>
Nikolas Klauser4ceab5f2022-02-10 13:33:03 +01001226#include <__algorithm/ranges_swap_ranges.h>
Nikolas Klauser559a1772022-04-05 11:05:36 +02001227#include <__algorithm/ranges_transform.h>
Nikolas Klauser8b381972022-06-05 21:15:16 +02001228#include <__algorithm/ranges_upper_bound.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001229#include <__algorithm/remove.h>
1230#include <__algorithm/remove_copy.h>
1231#include <__algorithm/remove_copy_if.h>
1232#include <__algorithm/remove_if.h>
1233#include <__algorithm/replace.h>
1234#include <__algorithm/replace_copy.h>
1235#include <__algorithm/replace_copy_if.h>
1236#include <__algorithm/replace_if.h>
1237#include <__algorithm/reverse.h>
1238#include <__algorithm/reverse_copy.h>
1239#include <__algorithm/rotate.h>
1240#include <__algorithm/rotate_copy.h>
1241#include <__algorithm/sample.h>
1242#include <__algorithm/search.h>
1243#include <__algorithm/search_n.h>
1244#include <__algorithm/set_difference.h>
1245#include <__algorithm/set_intersection.h>
1246#include <__algorithm/set_symmetric_difference.h>
1247#include <__algorithm/set_union.h>
1248#include <__algorithm/shift_left.h>
1249#include <__algorithm/shift_right.h>
1250#include <__algorithm/shuffle.h>
1251#include <__algorithm/sift_down.h>
1252#include <__algorithm/sort.h>
1253#include <__algorithm/sort_heap.h>
1254#include <__algorithm/stable_partition.h>
1255#include <__algorithm/stable_sort.h>
Christopher Di Bella41f26e82021-06-05 02:47:47 +00001256#include <__algorithm/swap_ranges.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001257#include <__algorithm/transform.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001258#include <__algorithm/unique.h>
Arthur O'Dwyer65077c02022-01-07 09:45:05 -05001259#include <__algorithm/unique_copy.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001260#include <__algorithm/unwrap_iter.h>
1261#include <__algorithm/upper_bound.h>
Eric Fiselier14b6de92014-08-10 23:53:08 +00001262
Louis Dionne22355cc2022-06-27 15:53:41 -04001263#ifndef _LIBCPP_REMOVE_TRANSITIVE_INCLUDES
1264# include <chrono>
1265# include <iterator>
1266# include <utility>
1267#endif
1268
Nikolas Klausera0e0edb2022-06-16 22:43:46 +02001269// standard-mandated includes
1270#include <initializer_list>
1271
Howard Hinnantaaaa52b2011-10-17 20:05:10 +00001272#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Arthur O'Dwyer6eeaa002022-02-01 20:16:40 -05001273# pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +00001274#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001275
Louis Dionne59d0b3c2019-08-05 18:29:14 +00001276#if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
Louis Dionned53d8c02019-08-06 21:11:24 +00001277# include <__pstl_algorithm>
Louis Dionne59d0b3c2019-08-05 18:29:14 +00001278#endif
1279
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001280#endif // _LIBCPP_ALGORITHM