blob: 2c1474ed45d72668f9558277a4f5f34d4f37b5c5 [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
48 template <input_iterator I1, sentinel_for<_I1> S1, input_iterator I2, sentinel_for<_I2> S2,
49 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
50 requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
51 constexpr mismatch_result<_I1, _I2>
52 mismatch()(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) // since C++20
53
54 template <input_range R1, input_range R2,
55 class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
56 requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
57 constexpr mismatch_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
58 mismatch(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) // since C++20
Nikolas Klauser37d076e2022-03-12 01:45:35 +010059
Nikolas Klauser37d076e2022-03-12 01:45:35 +010060 requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
61 constexpr I find(I first, S last, const T& value, Proj proj = {}); // since C++20
62
63 template<input_range R, class T, class Proj = identity>
64 requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
65 constexpr borrowed_iterator_t<R>
66 find(R&& r, const T& value, Proj proj = {}); // since C++20
67
68 template<input_iterator I, sentinel_for<I> S, class Proj = identity,
69 indirect_unary_predicate<projected<I, Proj>> Pred>
70 constexpr I find_if(I first, S last, Pred pred, Proj proj = {}); // since C++20
71
72 template<input_range R, class Proj = identity,
73 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
74 constexpr borrowed_iterator_t<R>
75 find_if(R&& r, Pred pred, Proj proj = {}); // since C++20
76
77 template<input_iterator I, sentinel_for<I> S, class Proj = identity,
78 indirect_unary_predicate<projected<I, Proj>> Pred>
79 constexpr I find_if_not(I first, S last, Pred pred, Proj proj = {}); // since C++20
80
81 template<input_range R, class Proj = identity,
82 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
83 constexpr borrowed_iterator_t<R>
84 find_if_not(R&& r, Pred pred, Proj proj = {}); // since C++20
Nikolas Klauser3559e452022-03-18 02:57:08 +010085
Nikolas Klauser573cd6f2022-04-03 09:17:01 +020086 template<class T, class Proj = identity,
87 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
88 constexpr const T& min(const T& a, const T& b, Comp comp = {}, Proj proj = {}); // since C++20
Nikolas Klauser3559e452022-03-18 02:57:08 +010089
Nikolas Klauser573cd6f2022-04-03 09:17:01 +020090 template<copyable T, class Proj = identity,
91 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
92 constexpr T min(initializer_list<T> r, Comp comp = {}, Proj proj = {}); // since C++20
Nikolas Klauser3559e452022-03-18 02:57:08 +010093
94 template<input_range R, class Proj = identity,
95 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
96 requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
97 constexpr range_value_t<R>
98 min(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
Nikolas Klauser573cd6f2022-04-03 09:17:01 +020099
100 template<class T, class Proj = identity,
101 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
102 constexpr const T& max(const T& a, const T& b, Comp comp = {}, Proj proj = {}); // since C++20
103
104 template<copyable T, class Proj = identity,
105 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
106 constexpr T max(initializer_list<T> r, Comp comp = {}, Proj proj = {}); // since C++20
107
108 template<input_range R, class Proj = identity,
109 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
110 requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
111 constexpr range_value_t<R>
112 max(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
Nikolas Klauser559a1772022-04-05 11:05:36 +0200113
114 template<class I, class O>
115 using unary_transform_result = in_out_result<I, O>; // since C++20
116
117 template<class I1, class I2, class O>
118 using binary_transform_result = in_in_out_result<I1, I2, O>; // since C++20
119
120 template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
121 copy_constructible F, class Proj = identity>
122 requires indirectly_writable<O, indirect_result_t<F&, projected<I, Proj>>>
123 constexpr ranges::unary_transform_result<I, O>
124 transform(I first1, S last1, O result, F op, Proj proj = {}); // since C++20
125
126 template<input_range R, weakly_incrementable O, copy_constructible F,
127 class Proj = identity>
128 requires indirectly_writable<O, indirect_result_t<F&, projected<iterator_t<R>, Proj>>>
129 constexpr ranges::unary_transform_result<borrowed_iterator_t<R>, O>
130 transform(R&& r, O result, F op, Proj proj = {}); // since C++20
131
132 template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
133 weakly_incrementable O, copy_constructible F, class Proj1 = identity,
134 class Proj2 = identity>
135 requires indirectly_writable<O, indirect_result_t<F&, projected<I1, Proj1>,
136 projected<I2, Proj2>>>
137 constexpr ranges::binary_transform_result<I1, I2, O>
138 transform(I1 first1, S1 last1, I2 first2, S2 last2, O result,
139 F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
140
141 template<input_range R1, input_range R2, weakly_incrementable O,
142 copy_constructible F, class Proj1 = identity, class Proj2 = identity>
143 requires indirectly_writable<O, indirect_result_t<F&, projected<iterator_t<R1>, Proj1>,
144 projected<iterator_t<R2>, Proj2>>>
145 constexpr ranges::binary_transform_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
146 transform(R1&& r1, R2&& r2, O result,
147 F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
Nikolas Klauserf1373d02022-04-07 13:02:02 +0200148
149 template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
150 requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
151 constexpr iter_difference_t<I>
152 count(I first, S last, const T& value, Proj proj = {}); // since C++20
153
154 template<input_range R, class T, class Proj = identity>
155 requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
156 constexpr range_difference_t<R>
157 count(R&& r, const T& value, Proj proj = {}); // since C++20
158
159 template<input_iterator I, sentinel_for<I> S, class Proj = identity,
160 indirect_unary_predicate<projected<I, Proj>> Pred>
161 constexpr iter_difference_t<I>
162 count_if(I first, S last, Pred pred, Proj proj = {}); // since C++20
163
164 template<input_range R, class Proj = identity,
165 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
166 constexpr range_difference_t<R>
167 count_if(R&& r, Pred pred, Proj proj = {}); // since C++20
Nikolas Klauser0a2f44f2022-04-13 22:59:09 +0200168
169 template<class T, class Proj = identity,
170 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
171 constexpr ranges::minmax_result<const T&>
172 minmax(const T& a, const T& b, Comp comp = {}, Proj proj = {}); // since C++20
173
174 template<copyable T, class Proj = identity,
175 indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
176 constexpr ranges::minmax_result<T>
177 minmax(initializer_list<T> r, Comp comp = {}, Proj proj = {}); // since C++20
178
179 template<input_range R, class Proj = identity,
180 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
181 requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
182 constexpr ranges::minmax_result<range_value_t<R>>
183 minmax(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
184
185 template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
186 indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
187 constexpr ranges::minmax_element_result<I>
188 minmax_element(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20
189
190 template<forward_range R, class Proj = identity,
191 indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
192 constexpr ranges::minmax_element_result<borrowed_iterator_t<R>>
193 minmax_element(R&& r, Comp comp = {}, Proj proj = {}); // since C++20
Nikolas Klauserd959d842022-04-15 13:43:40 +0200194
195 template<class I, class O>
196 using copy_result = in_out_result<I, O>; // since C++20
197
198 template<class I, class O>
199 using copy_n_result = in_out_result<I, O>; // since C++20
200
201 template<class I, class O>
202 using copy_if_result = in_out_result<I, O>; // since C++20
203
204 template<class I1, class I2>
205 using copy_backward_result = in_out_result<I1, I2>; // since C++20
206
207 template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>
208 requires indirectly_copyable<I, O>
209 constexpr ranges::copy_result<I, O> ranges::copy(I first, S last, O result); // since C++20
210
211 template<input_range R, weakly_incrementable O>
212 requires indirectly_copyable<iterator_t<R>, O>
213 constexpr ranges::copy_result<borrowed_iterator_t<R>, O> ranges::copy(R&& r, O result); // since C++20
214
215 template<input_iterator I, weakly_incrementable O>
216 requires indirectly_copyable<I, O>
217 constexpr ranges::copy_n_result<I, O>
218 ranges::copy_n(I first, iter_difference_t<I> n, O result); // since C++20
219
220 template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Proj = identity,
221 indirect_unary_predicate<projected<I, Proj>> Pred>
222 requires indirectly_copyable<I, O>
223 constexpr ranges::copy_if_result<I, O>
224 ranges::copy_if(I first, S last, O result, Pred pred, Proj proj = {}); // since C++20
225
226 template<input_range R, weakly_incrementable O, class Proj = identity,
227 indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
228 requires indirectly_copyable<iterator_t<R>, O>
229 constexpr ranges::copy_if_result<borrowed_iterator_t<R>, O>
230 ranges::copy_if(R&& r, O result, Pred pred, Proj proj = {}); // since C++20
231
232 template<bidirectional_iterator I1, sentinel_for<I1> S1, bidirectional_iterator I2>
233 requires indirectly_copyable<I1, I2>
234 constexpr ranges::copy_backward_result<I1, I2>
235 ranges::copy_backward(I1 first, S1 last, I2 result); // since C++20
236
237 template<bidirectional_range R, bidirectional_iterator I>
238 requires indirectly_copyable<iterator_t<R>, I>
239 constexpr ranges::copy_backward_result<borrowed_iterator_t<R>, I>
240 ranges::copy_backward(R&& r, I result); // since C++20
Nikolas Klauserf74be4e2022-01-14 02:55:51 +0100241}
242
Marshall Clowd607fdb2018-01-15 17:20:36 +0000243 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000244 all_of(InputIterator first, InputIterator last, Predicate pred);
245
246template <class InputIterator, class Predicate>
Marshall Clowd607fdb2018-01-15 17:20:36 +0000247 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000248 any_of(InputIterator first, InputIterator last, Predicate pred);
249
250template <class InputIterator, class Predicate>
Marshall Clowd607fdb2018-01-15 17:20:36 +0000251 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000252 none_of(InputIterator first, InputIterator last, Predicate pred);
253
254template <class InputIterator, class Function>
Marshall Clow5492c8a2018-01-22 20:44:33 +0000255 constexpr Function // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000256 for_each(InputIterator first, InputIterator last, Function f);
257
Marshall Clowde0169c2017-05-25 02:29:54 +0000258template<class InputIterator, class Size, class Function>
Marshall Clow5492c8a2018-01-22 20:44:33 +0000259 constexpr InputIterator // constexpr in C++20
260 for_each_n(InputIterator first, Size n, Function f); // C++17
Marshall Clowde0169c2017-05-25 02:29:54 +0000261
Howard Hinnantc51e1022010-05-11 19:42:16 +0000262template <class InputIterator, class T>
Marshall Clowee0161e2018-01-15 19:26:05 +0000263 constexpr InputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000264 find(InputIterator first, InputIterator last, const T& value);
265
266template <class InputIterator, class Predicate>
Marshall Clowee0161e2018-01-15 19:26:05 +0000267 constexpr InputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000268 find_if(InputIterator first, InputIterator last, Predicate pred);
269
270template<class InputIterator, class Predicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500271 constexpr InputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000272 find_if_not(InputIterator first, InputIterator last, Predicate pred);
273
274template <class ForwardIterator1, class ForwardIterator2>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500275 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000276 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
277 ForwardIterator2 first2, ForwardIterator2 last2);
278
279template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500280 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000281 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
282 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
283
284template <class ForwardIterator1, class ForwardIterator2>
Marshall Clowee0161e2018-01-15 19:26:05 +0000285 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000286 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
287 ForwardIterator2 first2, ForwardIterator2 last2);
288
289template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clowee0161e2018-01-15 19:26:05 +0000290 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000291 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
292 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
293
294template <class ForwardIterator>
Marshall Clowee0161e2018-01-15 19:26:05 +0000295 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000296 adjacent_find(ForwardIterator first, ForwardIterator last);
297
298template <class ForwardIterator, class BinaryPredicate>
Marshall Clowee0161e2018-01-15 19:26:05 +0000299 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000300 adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
301
302template <class InputIterator, class T>
Marshall Clow3c0558f2018-01-15 19:40:34 +0000303 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000304 count(InputIterator first, InputIterator last, const T& value);
305
306template <class InputIterator, class Predicate>
Marshall Clow3c0558f2018-01-15 19:40:34 +0000307 constexpr typename iterator_traits<InputIterator>::difference_type // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000308 count_if(InputIterator first, InputIterator last, Predicate pred);
309
310template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000311 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000312 mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
313
Marshall Clow96b42b22013-05-09 21:14:23 +0000314template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000315 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Aditya Kumar3a0179a2016-08-25 11:52:38 +0000316 mismatch(InputIterator1 first1, InputIterator1 last1,
Marshall Clow96b42b22013-05-09 21:14:23 +0000317 InputIterator2 first2, InputIterator2 last2); // **C++14**
318
Howard Hinnantc51e1022010-05-11 19:42:16 +0000319template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000320 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000321 mismatch(InputIterator1 first1, InputIterator1 last1,
322 InputIterator2 first2, BinaryPredicate pred);
323
Marshall Clow96b42b22013-05-09 21:14:23 +0000324template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000325 constexpr pair<InputIterator1, InputIterator2> // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000326 mismatch(InputIterator1 first1, InputIterator1 last1,
327 InputIterator2 first2, InputIterator2 last2,
328 BinaryPredicate pred); // **C++14**
329
Howard Hinnantc51e1022010-05-11 19:42:16 +0000330template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000331 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000332 equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
333
Marshall Clow96b42b22013-05-09 21:14:23 +0000334template <class InputIterator1, class InputIterator2>
Marshall Clow30bf3022018-01-16 02:04:10 +0000335 constexpr bool // constexpr in C++20
Aditya Kumar3a0179a2016-08-25 11:52:38 +0000336 equal(InputIterator1 first1, InputIterator1 last1,
Marshall Clow96b42b22013-05-09 21:14:23 +0000337 InputIterator2 first2, InputIterator2 last2); // **C++14**
338
Howard Hinnantc51e1022010-05-11 19:42:16 +0000339template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000340 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000341 equal(InputIterator1 first1, InputIterator1 last1,
342 InputIterator2 first2, BinaryPredicate pred);
343
Marshall Clow96b42b22013-05-09 21:14:23 +0000344template <class InputIterator1, class InputIterator2, class BinaryPredicate>
Marshall Clow30bf3022018-01-16 02:04:10 +0000345 constexpr bool // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000346 equal(InputIterator1 first1, InputIterator1 last1,
347 InputIterator2 first2, InputIterator2 last2,
348 BinaryPredicate pred); // **C++14**
349
Howard Hinnantc51e1022010-05-11 19:42:16 +0000350template<class ForwardIterator1, class ForwardIterator2>
Marshall Clow96d050a2018-01-15 16:16:32 +0000351 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000352 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
353 ForwardIterator2 first2);
354
Marshall Clow96b42b22013-05-09 21:14:23 +0000355template<class ForwardIterator1, class ForwardIterator2>
Marshall Clow96d050a2018-01-15 16:16:32 +0000356 constexpr bool // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000357 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
358 ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**
359
Howard Hinnantc51e1022010-05-11 19:42:16 +0000360template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clow96d050a2018-01-15 16:16:32 +0000361 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000362 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
363 ForwardIterator2 first2, BinaryPredicate pred);
364
Marshall Clow96b42b22013-05-09 21:14:23 +0000365template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clow96d050a2018-01-15 16:16:32 +0000366 constexpr bool // constexpr in C++20
Marshall Clow96b42b22013-05-09 21:14:23 +0000367 is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
368 ForwardIterator2 first2, ForwardIterator2 last2,
369 BinaryPredicate pred); // **C++14**
370
Howard Hinnantc51e1022010-05-11 19:42:16 +0000371template <class ForwardIterator1, class ForwardIterator2>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000372 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000373 search(ForwardIterator1 first1, ForwardIterator1 last1,
374 ForwardIterator2 first2, ForwardIterator2 last2);
375
376template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000377 constexpr ForwardIterator1 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000378 search(ForwardIterator1 first1, ForwardIterator1 last1,
379 ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
380
381template <class ForwardIterator, class Size, class T>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000382 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000383 search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);
384
385template <class ForwardIterator, class Size, class T, class BinaryPredicate>
Marshall Clow323fc5b2018-01-16 15:48:27 +0000386 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000387 search_n(ForwardIterator first, ForwardIterator last,
388 Size count, const T& value, BinaryPredicate pred);
389
390template <class InputIterator, class OutputIterator>
Louis Dionne65b433b2019-11-06 12:02:41 +0000391 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000392 copy(InputIterator first, InputIterator last, OutputIterator result);
393
394template<class InputIterator, class OutputIterator, class Predicate>
Louis Dionne65b433b2019-11-06 12:02:41 +0000395 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000396 copy_if(InputIterator first, InputIterator last,
397 OutputIterator result, Predicate pred);
398
399template<class InputIterator, class Size, class OutputIterator>
Louis Dionne65b433b2019-11-06 12:02:41 +0000400 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000401 copy_n(InputIterator first, Size n, OutputIterator result);
402
403template <class BidirectionalIterator1, class BidirectionalIterator2>
Louis Dionne65b433b2019-11-06 12:02:41 +0000404 constexpr BidirectionalIterator2 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000405 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
406 BidirectionalIterator2 result);
407
408template <class ForwardIterator1, class ForwardIterator2>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500409 constexpr ForwardIterator2 // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000410 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
411
Nikolas Klauser4ceab5f2022-02-10 13:33:03 +0100412template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2>
413 requires indirectly_swappable<I1, I2>
414 constexpr ranges::swap_ranges_result<I1, I2>
415 ranges::swap_ranges(I1 first1, S1 last1, I2 first2, S2 last2);
416
417template<input_range R1, input_range R2>
418 requires indirectly_swappable<iterator_t<R1>, iterator_t<R2>>
419 constexpr ranges::swap_ranges_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
420 ranges::swap_ranges(R1&& r1, R2&& r2);
421
Howard Hinnantc51e1022010-05-11 19:42:16 +0000422template <class ForwardIterator1, class ForwardIterator2>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500423 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000424 iter_swap(ForwardIterator1 a, ForwardIterator2 b);
425
426template <class InputIterator, class OutputIterator, class UnaryOperation>
Marshall Clow31427c62018-01-19 17:45:39 +0000427 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000428 transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);
429
430template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
Marshall Clow31427c62018-01-19 17:45:39 +0000431 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000432 transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
433 OutputIterator result, BinaryOperation binary_op);
434
435template <class ForwardIterator, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000436 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000437 replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
438
439template <class ForwardIterator, class Predicate, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000440 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000441 replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);
442
443template <class InputIterator, class OutputIterator, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000444 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000445 replace_copy(InputIterator first, InputIterator last, OutputIterator result,
446 const T& old_value, const T& new_value);
447
448template <class InputIterator, class OutputIterator, class Predicate, class T>
Marshall Clow01bbbd22018-01-19 18:07:29 +0000449 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000450 replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
451
452template <class ForwardIterator, class T>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000453 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000454 fill(ForwardIterator first, ForwardIterator last, const T& value);
455
456template <class OutputIterator, class Size, class T>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000457 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000458 fill_n(OutputIterator first, Size n, const T& value);
459
460template <class ForwardIterator, class Generator>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000461 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000462 generate(ForwardIterator first, ForwardIterator last, Generator gen);
463
464template <class OutputIterator, class Size, class Generator>
Marshall Clowe9cdc5c2018-01-20 20:14:32 +0000465 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000466 generate_n(OutputIterator first, Size n, Generator gen);
467
468template <class ForwardIterator, class T>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000469 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000470 remove(ForwardIterator first, ForwardIterator last, const T& value);
471
472template <class ForwardIterator, class Predicate>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000473 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000474 remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
475
476template <class InputIterator, class OutputIterator, class T>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000477 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000478 remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);
479
480template <class InputIterator, class OutputIterator, class Predicate>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000481 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000482 remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
483
484template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500485 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000486 unique(ForwardIterator first, ForwardIterator last);
487
488template <class ForwardIterator, class BinaryPredicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500489 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000490 unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
491
492template <class InputIterator, class OutputIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500493 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000494 unique_copy(InputIterator first, InputIterator last, OutputIterator result);
495
496template <class InputIterator, class OutputIterator, class BinaryPredicate>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500497 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000498 unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);
499
500template <class BidirectionalIterator>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -0500501 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000502 reverse(BidirectionalIterator first, BidirectionalIterator last);
503
504template <class BidirectionalIterator, class OutputIterator>
Marshall Clow7c0fbd82018-01-22 21:43:04 +0000505 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000506 reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
507
508template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500509 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000510 rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
511
512template <class ForwardIterator, class OutputIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500513 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000514 rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
515
516template <class RandomAccessIterator>
517 void
Marshall Clowfac06e52017-03-23 13:43:37 +0000518 random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000519
520template <class RandomAccessIterator, class RandomNumberGenerator>
521 void
Marshall Clow83f35392014-03-03 06:14:19 +0000522 random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
Marshall Clowfac06e52017-03-23 13:43:37 +0000523 RandomNumberGenerator& rand); // deprecated in C++14, removed in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000524
Eric Fiselier1208fcd2016-08-28 22:14:37 +0000525template<class PopulationIterator, class SampleIterator,
526 class Distance, class UniformRandomBitGenerator>
527 SampleIterator sample(PopulationIterator first, PopulationIterator last,
528 SampleIterator out, Distance n,
529 UniformRandomBitGenerator&& g); // C++17
530
Howard Hinnant578ac0f2010-05-26 17:49:34 +0000531template<class RandomAccessIterator, class UniformRandomNumberGenerator>
532 void shuffle(RandomAccessIterator first, RandomAccessIterator last,
Howard Hinnanta5e71782010-11-18 01:47:02 +0000533 UniformRandomNumberGenerator&& g);
Howard Hinnant578ac0f2010-05-26 17:49:34 +0000534
Arthur O'Dwyercea050d2020-12-26 01:39:03 -0500535template<class ForwardIterator>
536 constexpr ForwardIterator
537 shift_left(ForwardIterator first, ForwardIterator last,
538 typename iterator_traits<ForwardIterator>::difference_type n); // C++20
539
540template<class ForwardIterator>
541 constexpr ForwardIterator
542 shift_right(ForwardIterator first, ForwardIterator last,
543 typename iterator_traits<ForwardIterator>::difference_type n); // C++20
544
Howard Hinnantc51e1022010-05-11 19:42:16 +0000545template <class InputIterator, class Predicate>
Marshall Clow96d050a2018-01-15 16:16:32 +0000546 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000547 is_partitioned(InputIterator first, InputIterator last, Predicate pred);
548
549template <class ForwardIterator, class Predicate>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -0500550 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000551 partition(ForwardIterator first, ForwardIterator last, Predicate pred);
552
553template <class InputIterator, class OutputIterator1,
554 class OutputIterator2, class Predicate>
Marshall Clow5492c8a2018-01-22 20:44:33 +0000555 constexpr pair<OutputIterator1, OutputIterator2> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000556 partition_copy(InputIterator first, InputIterator last,
557 OutputIterator1 out_true, OutputIterator2 out_false,
558 Predicate pred);
559
560template <class ForwardIterator, class Predicate>
561 ForwardIterator
562 stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
563
564template<class ForwardIterator, class Predicate>
Marshall Clowe00916c2018-01-16 02:34:41 +0000565 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000566 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
567
568template <class ForwardIterator>
Marshall Clow96d050a2018-01-15 16:16:32 +0000569 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000570 is_sorted(ForwardIterator first, ForwardIterator last);
571
572template <class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500573 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000574 is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
575
576template<class ForwardIterator>
Marshall Clow3c0558f2018-01-15 19:40:34 +0000577 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000578 is_sorted_until(ForwardIterator first, ForwardIterator last);
579
580template <class ForwardIterator, class Compare>
Marshall Clow3c0558f2018-01-15 19:40:34 +0000581 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000582 is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);
583
584template <class RandomAccessIterator>
Arthur O'Dwyer1bb0f672020-12-20 15:21:42 -0500585 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000586 sort(RandomAccessIterator first, RandomAccessIterator last);
587
588template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer1bb0f672020-12-20 15:21:42 -0500589 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000590 sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
591
592template <class RandomAccessIterator>
593 void
594 stable_sort(RandomAccessIterator first, RandomAccessIterator last);
595
596template <class RandomAccessIterator, class Compare>
597 void
598 stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
599
600template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500601 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000602 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
603
604template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500605 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000606 partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
607
608template <class InputIterator, class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500609 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000610 partial_sort_copy(InputIterator first, InputIterator last,
611 RandomAccessIterator result_first, RandomAccessIterator result_last);
612
613template <class InputIterator, class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500614 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000615 partial_sort_copy(InputIterator first, InputIterator last,
616 RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
617
618template <class RandomAccessIterator>
Arthur O'Dwyer4f5717b2021-02-04 18:12:52 -0500619 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000620 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
621
622template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer4f5717b2021-02-04 18:12:52 -0500623 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000624 nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
625
626template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +0000627 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000628 lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
629
630template <class ForwardIterator, class T, class Compare>
Marshall Clowe00916c2018-01-16 02:34:41 +0000631 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000632 lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
633
634template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +0000635 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000636 upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
637
638template <class ForwardIterator, class T, class Compare>
Marshall Clowe00916c2018-01-16 02:34:41 +0000639 constexpr ForwardIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000640 upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
641
642template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +0000643 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000644 equal_range(ForwardIterator first, ForwardIterator last, const T& value);
645
646template <class ForwardIterator, class T, class Compare>
Marshall Clowe00916c2018-01-16 02:34:41 +0000647 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000648 equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
649
650template <class ForwardIterator, class T>
Marshall Clowe00916c2018-01-16 02:34:41 +0000651 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000652 binary_search(ForwardIterator first, ForwardIterator last, const T& value);
653
654template <class ForwardIterator, class T, class Compare>
Marshall Clowc0b7f972018-01-22 23:10:40 +0000655 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000656 binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
657
658template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500659 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000660 merge(InputIterator1 first1, InputIterator1 last1,
661 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
662
663template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500664 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000665 merge(InputIterator1 first1, InputIterator1 last1,
666 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
667
668template <class BidirectionalIterator>
669 void
670 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
671
672template <class BidirectionalIterator, class Compare>
673 void
674 inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
675
676template <class InputIterator1, class InputIterator2>
Marshall Clowc0b7f972018-01-22 23:10:40 +0000677 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000678 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
679
680template <class InputIterator1, class InputIterator2, class Compare>
Marshall Clowc0b7f972018-01-22 23:10:40 +0000681 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000682 includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
683
684template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500685 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000686 set_union(InputIterator1 first1, InputIterator1 last1,
687 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
688
689template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500690 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000691 set_union(InputIterator1 first1, InputIterator1 last1,
692 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
693
694template <class InputIterator1, class InputIterator2, class OutputIterator>
Marshall Clowc0b7f972018-01-22 23:10:40 +0000695 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000696 set_intersection(InputIterator1 first1, InputIterator1 last1,
697 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
698
699template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Marshall Clowc0b7f972018-01-22 23:10:40 +0000700 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000701 set_intersection(InputIterator1 first1, InputIterator1 last1,
702 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
703
704template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500705 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000706 set_difference(InputIterator1 first1, InputIterator1 last1,
707 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
708
709template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500710 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000711 set_difference(InputIterator1 first1, InputIterator1 last1,
712 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
713
714template <class InputIterator1, class InputIterator2, class OutputIterator>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500715 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000716 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
717 InputIterator2 first2, InputIterator2 last2, OutputIterator result);
718
719template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
Arthur O'Dwyer5afc5692020-12-04 13:47:12 -0500720 constexpr OutputIterator // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000721 set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
722 InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
723
724template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500725 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000726 push_heap(RandomAccessIterator first, RandomAccessIterator last);
727
728template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500729 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000730 push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
731
732template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500733 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000734 pop_heap(RandomAccessIterator first, RandomAccessIterator last);
735
736template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500737 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000738 pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
739
740template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500741 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000742 make_heap(RandomAccessIterator first, RandomAccessIterator last);
743
744template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500745 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000746 make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
747
748template <class RandomAccessIterator>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500749 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000750 sort_heap(RandomAccessIterator first, RandomAccessIterator last);
751
752template <class RandomAccessIterator, class Compare>
Arthur O'Dwyer2dfea5d2020-12-17 00:26:18 -0500753 constexpr void // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000754 sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
755
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000756template <class RandomAccessIterator>
Marshall Clow96d050a2018-01-15 16:16:32 +0000757 constexpr bool // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000758 is_heap(RandomAccessIterator first, RandomAccessiterator last);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000759
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000760template <class RandomAccessIterator, class Compare>
Marshall Clow96d050a2018-01-15 16:16:32 +0000761 constexpr bool // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000762 is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000763
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000764template <class RandomAccessIterator>
Marshall Clow96d050a2018-01-15 16:16:32 +0000765 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000766 is_heap_until(RandomAccessIterator first, RandomAccessiterator last);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000767
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000768template <class RandomAccessIterator, class Compare>
Marshall Clow96d050a2018-01-15 16:16:32 +0000769 constexpr RandomAccessIterator // constexpr in C++20
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000770 is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000771
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000772template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500773 constexpr ForwardIterator // constexpr in C++14
774 min_element(ForwardIterator first, ForwardIterator last);
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000775
776template <class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500777 constexpr ForwardIterator // constexpr in C++14
778 min_element(ForwardIterator first, ForwardIterator last, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000779
Howard Hinnantc51e1022010-05-11 19:42:16 +0000780template <class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500781 constexpr const T& // constexpr in C++14
782 min(const T& a, const T& b);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000783
784template <class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500785 constexpr const T& // constexpr in C++14
786 min(const T& a, const T& b, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000787
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000788template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500789 constexpr T // constexpr in C++14
790 min(initializer_list<T> t);
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000791
792template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500793 constexpr T // constexpr in C++14
794 min(initializer_list<T> t, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000795
Marshall Clow3e18d0e2016-03-07 22:43:49 +0000796template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500797 constexpr const T& clamp(const T& v, const T& lo, const T& hi); // C++17
Marshall Clow3e18d0e2016-03-07 22:43:49 +0000798
799template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500800 constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp); // C++17
Marshall Clow3e18d0e2016-03-07 22:43:49 +0000801
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000802template <class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500803 constexpr ForwardIterator // constexpr in C++14
804 max_element(ForwardIterator first, ForwardIterator last);
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000805
806template <class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500807 constexpr ForwardIterator // constexpr in C++14
808 max_element(ForwardIterator first, ForwardIterator last, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000809
Howard Hinnantc51e1022010-05-11 19:42:16 +0000810template <class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500811 constexpr const T& // constexpr in C++14
812 max(const T& a, const T& b);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000813
814template <class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500815 constexpr const T& // constexpr in C++14
816 max(const T& a, const T& b, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000817
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000818template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500819 constexpr T // constexpr in C++14
820 max(initializer_list<T> t);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000821
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000822template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500823 constexpr T // constexpr in C++14
824 max(initializer_list<T> t, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000825
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000826template<class ForwardIterator>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500827 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14
828 minmax_element(ForwardIterator first, ForwardIterator last);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000829
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000830template<class ForwardIterator, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500831 constexpr pair<ForwardIterator, ForwardIterator> // constexpr in C++14
832 minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000833
834template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500835 constexpr pair<const T&, const T&> // constexpr in C++14
836 minmax(const T& a, const T& b);
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000837
838template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500839 constexpr pair<const T&, const T&> // constexpr in C++14
840 minmax(const T& a, const T& b, Compare comp);
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000841
842template<class T>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500843 constexpr pair<T, T> // constexpr in C++14
844 minmax(initializer_list<T> t);
Howard Hinnantb120e7a2010-08-21 20:10:01 +0000845
846template<class T, class Compare>
Arthur O'Dwyer20353a72020-12-02 20:02:18 -0500847 constexpr pair<T, T> // constexpr in C++14
848 minmax(initializer_list<T> t, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000849
850template <class InputIterator1, class InputIterator2>
Marshall Clow5492c8a2018-01-22 20:44:33 +0000851 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000852 lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
853
854template <class InputIterator1, class InputIterator2, class Compare>
Marshall Clow5492c8a2018-01-22 20:44:33 +0000855 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000856 lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
857 InputIterator2 first2, InputIterator2 last2, Compare comp);
858
859template <class BidirectionalIterator>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -0500860 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000861 next_permutation(BidirectionalIterator first, BidirectionalIterator last);
862
863template <class BidirectionalIterator, class Compare>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -0500864 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000865 next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
866
867template <class BidirectionalIterator>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -0500868 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000869 prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
870
871template <class BidirectionalIterator, class Compare>
Arthur O'Dwyere50e7472020-12-17 00:01:08 -0500872 constexpr bool // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000873 prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000874} // std
875
876*/
877
Louis Dionneb4fce352022-03-25 12:55:36 -0400878#include <__assert> // all public C++ headers provide the assertion handler
Arthur O'Dwyer3693d7a2022-02-04 13:09:30 -0500879#include <__bits>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000880#include <__config>
Louis Dionnea60dd872021-06-17 11:30:11 -0400881#include <__debug>
Howard Hinnant60e5cf42012-07-26 17:09:09 +0000882#include <cstddef>
Arthur O'Dwyeref181602021-05-19 11:57:04 -0400883#include <cstring>
Arthur O'Dwyeref181602021-05-19 11:57:04 -0400884#include <initializer_list>
885#include <iterator>
886#include <memory>
887#include <type_traits>
Marshall Clow0a1e7502018-09-12 19:41:40 +0000888#include <version>
Howard Hinnantea382952013-08-14 18:00:20 +0000889
Louis Dionnea60dd872021-06-17 11:30:11 -0400890#include <__algorithm/adjacent_find.h>
891#include <__algorithm/all_of.h>
892#include <__algorithm/any_of.h>
893#include <__algorithm/binary_search.h>
894#include <__algorithm/clamp.h>
895#include <__algorithm/comp.h>
896#include <__algorithm/comp_ref_type.h>
897#include <__algorithm/copy.h>
898#include <__algorithm/copy_backward.h>
899#include <__algorithm/copy_if.h>
900#include <__algorithm/copy_n.h>
901#include <__algorithm/count.h>
902#include <__algorithm/count_if.h>
903#include <__algorithm/equal.h>
904#include <__algorithm/equal_range.h>
Louis Dionnea60dd872021-06-17 11:30:11 -0400905#include <__algorithm/fill.h>
Arthur O'Dwyer65077c02022-01-07 09:45:05 -0500906#include <__algorithm/fill_n.h>
Louis Dionnea60dd872021-06-17 11:30:11 -0400907#include <__algorithm/find.h>
908#include <__algorithm/find_end.h>
909#include <__algorithm/find_first_of.h>
910#include <__algorithm/find_if.h>
911#include <__algorithm/find_if_not.h>
912#include <__algorithm/for_each.h>
913#include <__algorithm/for_each_n.h>
Louis Dionnea60dd872021-06-17 11:30:11 -0400914#include <__algorithm/generate.h>
Arthur O'Dwyer65077c02022-01-07 09:45:05 -0500915#include <__algorithm/generate_n.h>
Louis Dionnea60dd872021-06-17 11:30:11 -0400916#include <__algorithm/half_positive.h>
Nikolas Klauserdd5ad212022-02-21 23:07:02 +0100917#include <__algorithm/in_found_result.h>
Nikolas Klauser671b4752022-02-11 17:01:58 +0100918#include <__algorithm/in_fun_result.h>
Nikolas Klauser05e2cd82022-01-25 11:21:47 +0100919#include <__algorithm/in_in_out_result.h>
Nikolas Klauserf74be4e2022-01-14 02:55:51 +0100920#include <__algorithm/in_in_result.h>
Nikolas Klauser61ce8162022-02-03 02:17:03 +0100921#include <__algorithm/in_out_out_result.h>
Konstantin Varlamov74736812022-01-10 22:49:37 -0800922#include <__algorithm/in_out_result.h>
Louis Dionnea60dd872021-06-17 11:30:11 -0400923#include <__algorithm/includes.h>
924#include <__algorithm/inplace_merge.h>
925#include <__algorithm/is_heap.h>
926#include <__algorithm/is_heap_until.h>
927#include <__algorithm/is_partitioned.h>
928#include <__algorithm/is_permutation.h>
929#include <__algorithm/is_sorted.h>
930#include <__algorithm/is_sorted_until.h>
Christopher Di Bella41f26e82021-06-05 02:47:47 +0000931#include <__algorithm/iter_swap.h>
Louis Dionnea60dd872021-06-17 11:30:11 -0400932#include <__algorithm/lexicographical_compare.h>
933#include <__algorithm/lower_bound.h>
934#include <__algorithm/make_heap.h>
935#include <__algorithm/max.h>
936#include <__algorithm/max_element.h>
937#include <__algorithm/merge.h>
938#include <__algorithm/min.h>
939#include <__algorithm/min_element.h>
Nikolas Klauser2e263162022-02-21 22:48:36 +0100940#include <__algorithm/min_max_result.h>
Louis Dionnea60dd872021-06-17 11:30:11 -0400941#include <__algorithm/minmax.h>
942#include <__algorithm/minmax_element.h>
943#include <__algorithm/mismatch.h>
944#include <__algorithm/move.h>
945#include <__algorithm/move_backward.h>
946#include <__algorithm/next_permutation.h>
947#include <__algorithm/none_of.h>
948#include <__algorithm/nth_element.h>
949#include <__algorithm/partial_sort.h>
950#include <__algorithm/partial_sort_copy.h>
951#include <__algorithm/partition.h>
952#include <__algorithm/partition_copy.h>
953#include <__algorithm/partition_point.h>
954#include <__algorithm/pop_heap.h>
955#include <__algorithm/prev_permutation.h>
956#include <__algorithm/push_heap.h>
Nikolas Klauserd959d842022-04-15 13:43:40 +0200957#include <__algorithm/ranges_copy.h>
958#include <__algorithm/ranges_copy_backward.h>
959#include <__algorithm/ranges_copy_if.h>
960#include <__algorithm/ranges_copy_n.h>
Nikolas Klauserf1373d02022-04-07 13:02:02 +0200961#include <__algorithm/ranges_count.h>
962#include <__algorithm/ranges_count_if.h>
Nikolas Klauser37d076e2022-03-12 01:45:35 +0100963#include <__algorithm/ranges_find.h>
964#include <__algorithm/ranges_find_if.h>
965#include <__algorithm/ranges_find_if_not.h>
Nikolas Klauser573cd6f2022-04-03 09:17:01 +0200966#include <__algorithm/ranges_max.h>
Nikolas Klauserf2a69ea2022-03-07 17:01:52 +0100967#include <__algorithm/ranges_max_element.h>
Nikolas Klauser3559e452022-03-18 02:57:08 +0100968#include <__algorithm/ranges_min.h>
Nikolas Klauser0a62a172022-02-11 13:11:57 +0100969#include <__algorithm/ranges_min_element.h>
Nikolas Klauser0a2f44f2022-04-13 22:59:09 +0200970#include <__algorithm/ranges_minmax.h>
971#include <__algorithm/ranges_minmax_element.h>
Nikolas Klauser12fc9bf2022-03-08 23:12:35 +0100972#include <__algorithm/ranges_mismatch.h>
Nikolas Klauser4ceab5f2022-02-10 13:33:03 +0100973#include <__algorithm/ranges_swap_ranges.h>
Nikolas Klauser559a1772022-04-05 11:05:36 +0200974#include <__algorithm/ranges_transform.h>
Louis Dionnea60dd872021-06-17 11:30:11 -0400975#include <__algorithm/remove.h>
976#include <__algorithm/remove_copy.h>
977#include <__algorithm/remove_copy_if.h>
978#include <__algorithm/remove_if.h>
979#include <__algorithm/replace.h>
980#include <__algorithm/replace_copy.h>
981#include <__algorithm/replace_copy_if.h>
982#include <__algorithm/replace_if.h>
983#include <__algorithm/reverse.h>
984#include <__algorithm/reverse_copy.h>
985#include <__algorithm/rotate.h>
986#include <__algorithm/rotate_copy.h>
987#include <__algorithm/sample.h>
988#include <__algorithm/search.h>
989#include <__algorithm/search_n.h>
990#include <__algorithm/set_difference.h>
991#include <__algorithm/set_intersection.h>
992#include <__algorithm/set_symmetric_difference.h>
993#include <__algorithm/set_union.h>
994#include <__algorithm/shift_left.h>
995#include <__algorithm/shift_right.h>
996#include <__algorithm/shuffle.h>
997#include <__algorithm/sift_down.h>
998#include <__algorithm/sort.h>
999#include <__algorithm/sort_heap.h>
1000#include <__algorithm/stable_partition.h>
1001#include <__algorithm/stable_sort.h>
Christopher Di Bella41f26e82021-06-05 02:47:47 +00001002#include <__algorithm/swap_ranges.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001003#include <__algorithm/transform.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001004#include <__algorithm/unique.h>
Arthur O'Dwyer65077c02022-01-07 09:45:05 -05001005#include <__algorithm/unique_copy.h>
Louis Dionnea60dd872021-06-17 11:30:11 -04001006#include <__algorithm/unwrap_iter.h>
1007#include <__algorithm/upper_bound.h>
Eric Fiselier14b6de92014-08-10 23:53:08 +00001008
Howard Hinnantaaaa52b2011-10-17 20:05:10 +00001009#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Arthur O'Dwyer6eeaa002022-02-01 20:16:40 -05001010# pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +00001011#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001012
Louis Dionne59d0b3c2019-08-05 18:29:14 +00001013#if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
Louis Dionned53d8c02019-08-06 21:11:24 +00001014# include <__pstl_algorithm>
Louis Dionne59d0b3c2019-08-05 18:29:14 +00001015#endif
1016
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001017#endif // _LIBCPP_ALGORITHM