ranges_algo.h source code [include/c++/16.1.1/bits/ranges_algo.h]

1	// Core algorithmic facilities -- C++ --
2
3	// Copyright (C) 2020-2026 Free Software Foundation, Inc.
4	//
5	// This file is part of the GNU ISO C++ Library. This library is free
6	// software; you can redistribute it and/or modify it under the
7	// terms of the GNU General Public License as published by the
8	// Free Software Foundation; either version 3, or (at your option)
9	// any later version.
10
11	// This library is distributed in the hope that it will be useful,
12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14	// GNU General Public License for more details.
15
16	// Under Section 7 of GPL version 3, you are granted additional
17	// permissions described in the GCC Runtime Library Exception, version
18	// 3.1, as published by the Free Software Foundation.
19
20	// You should have received a copy of the GNU General Public License and
21	// a copy of the GCC Runtime Library Exception along with this program;
22	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23	// <http://www.gnu.org/licenses/>.
24
25	/* @file bits/ranges_algo.h*
26	* This is an internal header file, included by other library headers.
27	* Do not attempt to use it directly. @headername{algorithm}
28	*/
29
30	#ifndef _RANGES_ALGO_H
31	#define _RANGES_ALGO_H 1
32
33	#if __cplusplus > 201703L
34
35	#include <bit> // __bit_width
36	#if __cplusplus > 202002L
37	#include <optional>
38	#endif
39	#include <bits/ranges_algobase.h>
40	#include <bits/ranges_util.h>
41	#include <bits/uniform_int_dist.h> // concept uniform_random_bit_generator
42
43	#if __glibcxx_concepts
44	namespace std _GLIBCXX_VISIBILITY(default)
45	{
46	_GLIBCXX_BEGIN_NAMESPACE_VERSION
47	namespace ranges
48	{
49	namespace __detail
50	{
51	template<typename _Fp>
52	using __by_ref_or_value_fn
53	= __conditional_t<is_scalar_v<_Fp> \|\| is_empty_v<_Fp>, _Fp, _Fp&>;
54
55	template<typename _Comp, typename _Proj>
56	struct _Comp_proj
57	{
58	[[no_unique_address]] __by_ref_or_value_fn<_Comp> _M_comp;
59	[[no_unique_address]] __by_ref_or_value_fn<_Proj> _M_proj;
60
61	constexpr
62	_Comp_proj(_Comp& __comp, _Proj& __proj)
63	: _M_comp(__comp), _M_proj(__proj)
64	{ }
65
66	template<typename _Tp, typename _Up>
67	constexpr bool
68	operator()(_Tp&& __x, _Up&& __y)
69	{
70	return std::__invoke(_M_comp,
71	std::__invoke(_M_proj, std::forward<_Tp>(__x)),
72	std::__invoke(_M_proj, std::forward<_Up>(__y)));
73	}
74	};
75
76	template<typename _Comp, typename _Proj>
77	constexpr _Comp_proj<_Comp, _Proj>
78	__make_comp_proj(_Comp& __comp, _Proj& __proj)
79	{ return {__comp, __proj}; }
80
81	template<typename _Pred, typename _Proj>
82	struct _Pred_proj
83	{
84	[[no_unique_address]] __by_ref_or_value_fn<_Pred> _M_pred;
85	[[no_unique_address]] __by_ref_or_value_fn<_Proj> _M_proj;
86
87	constexpr
88	_Pred_proj(_Pred& __pred, _Proj& __proj)
89	: _M_pred(__pred), _M_proj(__proj)
90	{ }
91
92	template<typename _Tp>
93	constexpr bool
94	operator()(_Tp&& __x)
95	{
96	return std::__invoke(_M_pred,
97	std::__invoke(_M_proj, std::forward<_Tp>(__x)));
98	}
99	};
100
101	template<typename _Pred, typename _Proj>
102	constexpr _Pred_proj<_Pred, _Proj>
103	__make_pred_proj(_Pred& __pred, _Proj& __proj)
104	{ return {__pred, __proj}; }
105	} // namespace __detail
106
107	struct __all_of_fn
108	{
109	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
110	typename _Proj = identity,
111	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
112	[[nodiscard]] constexpr bool
113	operator()(_Iter __first, _Sent __last,
114	_Pred __pred, _Proj __proj = {}) const
115	{
116	for (; __first != __last; ++__first)
117	if (!(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
118	return false;
119	return true;
120	}
121
122	template<input_range _Range, typename _Proj = identity,
123	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
124	_Pred>
125	[[nodiscard]] constexpr bool
126	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
127	{
128	return (*this)(ranges::begin(__r), ranges::end(__r),
129	std::move(__pred), std::move(__proj));
130	}
131	};
132
133	inline constexpr __all_of_fn all_of{};
134
135	struct __any_of_fn
136	{
137	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
138	typename _Proj = identity,
139	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
140	[[nodiscard]] constexpr bool
141	operator()(_Iter __first, _Sent __last,
142	_Pred __pred, _Proj __proj = {}) const
143	{
144	for (; __first != __last; ++__first)
145	if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
146	return true;
147	return false;
148	}
149
150	template<input_range _Range, typename _Proj = identity,
151	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
152	_Pred>
153	[[nodiscard]] constexpr bool
154	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
155	{
156	return (*this)(ranges::begin(__r), ranges::end(__r),
157	std::move(__pred), std::move(__proj));
158	}
159	};
160
161	inline constexpr __any_of_fn any_of{};
162
163	struct __none_of_fn
164	{
165	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
166	typename _Proj = identity,
167	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
168	[[nodiscard]] constexpr bool
169	operator()(_Iter __first, _Sent __last,
170	_Pred __pred, _Proj __proj = {}) const
171	{
172	for (; __first != __last; ++__first)
173	if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
174	return false;
175	return true;
176	}
177
178	template<input_range _Range, typename _Proj = identity,
179	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
180	_Pred>
181	[[nodiscard]] constexpr bool
182	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
183	{
184	return (*this)(ranges::begin(__r), ranges::end(__r),
185	std::move(__pred), std::move(__proj));
186	}
187	};
188
189	inline constexpr __none_of_fn none_of{};
190
191	template<typename _Iter, typename _Fp>
192	struct in_fun_result
193	{
194	[[no_unique_address]] _Iter in;
195	[[no_unique_address]] _Fp fun;
196
197	template<typename _Iter2, typename _F2p>
198	requires convertible_to<const _Iter&, _Iter2>
199	&& convertible_to<const _Fp&, _F2p>
200	constexpr
201	operator in_fun_result<_Iter2, _F2p>() const &
202	{ return {in, fun}; }
203
204	template<typename _Iter2, typename _F2p>
205	requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p>
206	constexpr
207	operator in_fun_result<_Iter2, _F2p>() &&
208	{ return {std::move(in), std::move(fun)}; }
209	};
210
211	template<typename _Iter, typename _Fp>
212	using for_each_result = in_fun_result<_Iter, _Fp>;
213
214	struct __for_each_fn
215	{
216	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
217	typename _Proj = identity,
218	indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
219	constexpr for_each_result<_Iter, _Fun>
220	operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {}) const
221	{
222	for (; __first != __last; ++__first)
223	std::__invoke(__f, std::__invoke(__proj, *__first));
224	return { std::move(__first), std::move(__f) };
225	}
226
227	template<input_range _Range, typename _Proj = identity,
228	indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>>
229	_Fun>
230	constexpr for_each_result<borrowed_iterator_t<_Range>, _Fun>
231	operator()(_Range&& __r, _Fun __f, _Proj __proj = {}) const
232	{
233	return (*this)(ranges::begin(__r), ranges::end(__r),
234	std::move(__f), std::move(__proj));
235	}
236	};
237
238	inline constexpr __for_each_fn for_each{};
239
240	template<typename _Iter, typename _Fp>
241	using for_each_n_result = in_fun_result<_Iter, _Fp>;
242
243	struct __for_each_n_fn
244	{
245	template<input_iterator _Iter, typename _Proj = identity,
246	indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
247	constexpr for_each_n_result<_Iter, _Fun>
248	operator()(_Iter __first, iter_difference_t<_Iter> __n,
249	_Fun __f, _Proj __proj = {}) const
250	{
251	if constexpr (random_access_iterator<_Iter>)
252	{
253	if (__n <= `0`)
254	return {std::move(__first), std::move(__f)};
255	auto __last = __first + __n;
256	return ranges::for_each(std::move(__first), std::move(__last),
257	std::move(__f), std::move(__proj));
258	}
259	else
260	{
261	while (__n-- > `0`)
262	{
263	std::__invoke(__f, std::__invoke(__proj, *__first));
264	++__first;
265	}
266	return {std::move(__first), std::move(__f)};
267	}
268	}
269	};
270
271	inline constexpr __for_each_n_fn for_each_n{};
272
273	// find, find_if and find_if_not are defined in <bits/ranges_util.h>.
274
275	struct __find_first_of_fn
276	{
277	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
278	forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
279	typename _Pred = ranges::equal_to,
280	typename _Proj1 = identity, typename _Proj2 = identity>
281	requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
282	[[nodiscard]] constexpr _Iter1
283	operator()(_Iter1 __first1, _Sent1 __last1,
284	_Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
285	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
286	{
287	for (; __first1 != __last1; ++__first1)
288	for (auto __iter = __first2; __iter != __last2; ++__iter)
289	if (std::__invoke(__pred,
290	std::__invoke(__proj1, *__first1),
291	std::__invoke(__proj2, *__iter)))
292	return __first1;
293	return __first1;
294	}
295
296	template<input_range _Range1, forward_range _Range2,
297	typename _Pred = ranges::equal_to,
298	typename _Proj1 = identity, typename _Proj2 = identity>
299	requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
300	_Pred, _Proj1, _Proj2>
301	[[nodiscard]] constexpr borrowed_iterator_t<_Range1>
302	operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
303	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
304	{
305	return (*this)(ranges::begin(__r1), ranges::end(__r1),
306	ranges::begin(__r2), ranges::end(__r2),
307	std::move(__pred),
308	std::move(__proj1), std::move(__proj2));
309	}
310	};
311
312	inline constexpr __find_first_of_fn find_first_of{};
313
314	struct __count_fn
315	{
316	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
317	typename _Proj = identity,
318	typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
319	requires indirect_binary_predicate<ranges::equal_to,
320	projected<_Iter, _Proj>,
321	const _Tp*>
322	[[nodiscard]] constexpr iter_difference_t<_Iter>
323	operator()(_Iter __first, _Sent __last,
324	const _Tp& __value, _Proj __proj = {}) const
325	{
326	iter_difference_t<_Iter> __n = `0`;
327	for (; __first != __last; ++__first)
328	if (std::__invoke(__proj, *__first) == __value)
329	++__n;
330	return __n;
331	}
332
333	template<input_range _Range, typename _Proj = identity,
334	typename _Tp
335	_GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)>
336	requires indirect_binary_predicate<ranges::equal_to,
337	projected<iterator_t<_Range>, _Proj>,
338	const _Tp*>
339	[[nodiscard]] constexpr range_difference_t<_Range>
340	operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
341	{
342	return (*this)(ranges::begin(__r), ranges::end(__r),
343	__value, std::move(__proj));
344	}
345	};
346
347	inline constexpr __count_fn count{};
348
349	struct __count_if_fn
350	{
351	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
352	typename _Proj = identity,
353	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
354	constexpr iter_difference_t<_Iter>
355	operator()(_Iter __first, _Sent __last,
356	_Pred __pred, _Proj __proj = {}) const
357	{
358	iter_difference_t<_Iter> __n = `0`;
359	for (; __first != __last; ++__first)
360	if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
361	++__n;
362	return __n;
363	}
364
365	template<input_range _Range,
366	typename _Proj = identity,
367	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
368	_Pred>
369	constexpr range_difference_t<_Range>
370	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
371	{
372	return (*this)(ranges::begin(__r), ranges::end(__r),
373	std::move(__pred), std::move(__proj));
374	}
375	};
376
377	inline constexpr __count_if_fn count_if{};
378
379	// in_in_result, mismatch and search are defined in <bits/ranges_util.h>.
380
381	struct __search_n_fn
382	{
383	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
384	typename _Pred = ranges::equal_to, typename _Proj = identity,
385	typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
386	requires indirectly_comparable<_Iter, const _Tp*, _Pred, _Proj>
387	constexpr subrange<_Iter>
388	operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __count,
389	const _Tp& __value, _Pred __pred = {}, _Proj __proj = {}) const
390	{
391	if (__count <= `0`)
392	return {__first, __first};
393
394	auto __value_comp = [&] <typename _Rp> (_Rp&& __arg) -> bool {
395	return std::__invoke(__pred, std::forward<_Rp>(__arg), __value);
396	};
397	if (__count == `1`)
398	{
399	__first = ranges::find_if(std::move(__first), __last,
400	std::move(__value_comp),
401	std::move(__proj));
402	if (__first == __last)
403	return {__first, __first};
404	else
405	{
406	auto __end = __first;
407	return {__first, ++__end};
408	}
409	}
410
411	if constexpr (sized_sentinel_for<_Sent, _Iter>
412	&& random_access_iterator<_Iter>)
413	{
414	auto __tail_size = __last - __first;
415	auto __remainder = __count;
416
417	while (__remainder <= __tail_size)
418	{
419	__first += __remainder;
420	__tail_size -= __remainder;
421	auto __backtrack = __first;
422	while (__value_comp(std::__invoke(__proj, *--__backtrack)))
423	{
424	if (--__remainder == `0`)
425	return {__first - __count, __first};
426	}
427	__remainder = __count + `1` - (__first - __backtrack);
428	}
429	auto __i = __first + __tail_size;
430	return {__i, __i};
431	}
432	else
433	{
434	__first = ranges::find_if(__first, __last, __value_comp, __proj);
435	while (__first != __last)
436	{
437	auto __n = __count;
438	auto __i = __first;
439	++__i;
440	while (__i != __last && __n != `1`
441	&& __value_comp(std::__invoke(__proj, *__i)))
442	{
443	++__i;
444	--__n;
445	}
446	if (__n == `1`)
447	return {__first, __i};
448	if (__i == __last)
449	return {__i, __i};
450	__first = ranges::find_if(++__i, __last, __value_comp, __proj);
451	}
452	return {__first, __first};
453	}
454	}
455
456	template<forward_range _Range,
457	typename _Pred = ranges::equal_to, typename _Proj = identity,
458	typename _Tp
459	_GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)>
460	requires indirectly_comparable<iterator_t<_Range>, const _Tp*,
461	_Pred, _Proj>
462	constexpr borrowed_subrange_t<_Range>
463	operator()(_Range&& __r, range_difference_t<_Range> __count,
464	const _Tp& __value, _Pred __pred = {}, _Proj __proj = {}) const
465	{
466	return (*this)(ranges::begin(__r), ranges::end(__r),
467	std::move(__count), __value,
468	std::move(__pred), std::move(__proj));
469	}
470	};
471
472	inline constexpr __search_n_fn search_n{};
473
474	#if __glibcxx_ranges_starts_ends_with // C++ >= 23
475	struct __starts_with_fn
476	{
477	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
478	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
479	typename _Pred = ranges::equal_to,
480	typename _Proj1 = identity, typename _Proj2 = identity>
481	requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
482	constexpr bool
483	operator()(_Iter1 __first1, _Sent1 __last1,
484	_Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
485	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
486	{
487	iter_difference_t<_Iter1> __n1 = -`1`;
488	iter_difference_t<_Iter2> __n2 = -`1`;
489	if constexpr (sized_sentinel_for<_Sent1, _Iter1>)
490	__n1 = __last1 - __first1;
491	if constexpr (sized_sentinel_for<_Sent2, _Iter2>)
492	__n2 = __last2 - __first2;
493	return _S_impl(std::move(__first1), __last1, __n1,
494	std::move(__first2), __last2, __n2,
495	std::move(__pred),
496	std::move(__proj1), std::move(__proj2));
497	}
498
499	template<input_range _Range1, input_range _Range2,
500	typename _Pred = ranges::equal_to,
501	typename _Proj1 = identity, typename _Proj2 = identity>
502	requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
503	_Pred, _Proj1, _Proj2>
504	constexpr bool
505	operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
506	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
507	{
508	range_difference_t<_Range1> __n1 = -`1`;
509	range_difference_t<_Range2> __n2 = -`1`;
510	if constexpr (sized_range<_Range1>)
511	__n1 = ranges::size(__r1);
512	if constexpr (sized_range<_Range2>)
513	__n2 = ranges::size(__r2);
514	return _S_impl(ranges::begin(__r1), ranges::end(__r1), __n1,
515	ranges::begin(__r2), ranges::end(__r2), __n2,
516	std::move(__pred),
517	std::move(__proj1), std::move(__proj2));
518	}
519
520	private:
521	template<typename _Iter1, typename _Sent1, typename _Iter2, typename _Sent2,
522	typename _Pred,
523	typename _Proj1, typename _Proj2>
524	static constexpr bool
525	_S_impl(_Iter1 __first1, _Sent1 __last1, iter_difference_t<_Iter1> __n1,
526	_Iter2 __first2, _Sent2 __last2, iter_difference_t<_Iter2> __n2,
527	_Pred __pred, _Proj1 __proj1, _Proj2 __proj2)
528	{
529	if (__first2 == __last2) [[unlikely]]
530	return true;
531	else if (__n1 == -`1` \|\| __n2 == -`1`)
532	return ranges::mismatch(std::move(__first1), __last1,
533	std::move(__first2), __last2,
534	std::move(__pred),
535	std::move(__proj1), std::move(__proj2)).in2 == __last2;
536	else if (__n1 < __n2)
537	return false;
538	else if constexpr (random_access_iterator<_Iter1>)
539	return ranges::equal(__first1, __first1 + iter_difference_t<_Iter1>(__n2),
540	std::move(__first2), __last2,
541	std::move(__pred),
542	std::move(__proj1), std::move(__proj2));
543	else
544	return ranges::equal(counted_iterator(std::move(__first1),
545	iter_difference_t<_Iter1>(__n2)),
546	default_sentinel,
547	std::move(__first2), __last2,
548	std::move(__pred),
549	std::move(__proj1), std::move(__proj2));
550	}
551
552	friend struct __ends_with_fn;
553	};
554
555	inline constexpr __starts_with_fn starts_with{};
556
557	struct __ends_with_fn
558	{
559	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
560	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
561	typename _Pred = ranges::equal_to,
562	typename _Proj1 = identity, typename _Proj2 = identity>
563	requires (forward_iterator<_Iter1> \|\| sized_sentinel_for<_Sent1, _Iter1>)
564	&& (forward_iterator<_Iter2> \|\| sized_sentinel_for<_Sent2, _Iter2>)
565	&& indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
566	constexpr bool
567	operator()(_Iter1 __first1, _Sent1 __last1,
568	_Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
569	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
570	{
571	iter_difference_t<_Iter1> __n1 = -`1`;
572	iter_difference_t<_Iter2> __n2 = -`1`;
573	if constexpr (sized_sentinel_for<_Sent1, _Iter1>)
574	__n1 = __last1 - __first1;
575	if constexpr (sized_sentinel_for<_Sent2, _Iter2>)
576	__n2 = __last2 - __first2;
577	return _S_impl(std::move(__first1), __last1, __n1,
578	std::move(__first2), __last2, __n2,
579	std::move(__pred),
580	std::move(__proj1), std::move(__proj2));
581	}
582
583	template<input_range _Range1, input_range _Range2,
584	typename _Pred = ranges::equal_to,
585	typename _Proj1 = identity, typename _Proj2 = identity>
586	requires (forward_range<_Range1> \|\| sized_range<_Range1>)
587	&& (forward_range<_Range2> \|\| sized_range<_Range2>)
588	&& indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
589	_Pred, _Proj1, _Proj2>
590	constexpr bool
591	operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
592	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
593	{
594	range_difference_t<_Range1> __n1 = -`1`;
595	range_difference_t<_Range2> __n2 = -`1`;
596	if constexpr (sized_range<_Range1>)
597	__n1 = ranges::size(__r1);
598	if constexpr (sized_range<_Range2>)
599	__n2 = ranges::size(__r2);
600	return _S_impl(ranges::begin(__r1), ranges::end(__r1), __n1,
601	ranges::begin(__r2), ranges::end(__r2), __n2,
602	std::move(__pred),
603	std::move(__proj1), std::move(__proj2));
604	}
605
606	private:
607	template<typename _Iter1, typename _Sent1,
608	typename _Iter2, typename _Sent2,
609	typename _Pred,
610	typename _Proj1, typename _Proj2>
611	static constexpr bool
612	_S_impl(_Iter1 __first1, _Sent1 __last1, iter_difference_t<_Iter1> __n1,
613	_Iter2 __first2, _Sent2 __last2, iter_difference_t<_Iter2> __n2,
614	_Pred __pred, _Proj1 __proj1, _Proj2 __proj2)
615	{
616	if constexpr (!random_access_iterator<_Iter1>
617	&& bidirectional_iterator<_Iter1> && same_as<_Iter1, _Sent1>
618	&& bidirectional_iterator<_Iter2> && same_as<_Iter2, _Sent2>)
619	return starts_with._S_impl(std::make_reverse_iterator(__last1),
620	std::make_reverse_iterator(__first1),
621	__n1,
622	std::make_reverse_iterator(__last2),
623	std::make_reverse_iterator(__first2),
624	__n2,
625	std::move(__pred),
626	std::move(__proj1), std::move(__proj2));
627
628	if (__first2 == __last2) [[unlikely]]
629	return true;
630
631	if constexpr (forward_iterator<_Iter2>)
632	if (__n2 == -`1`)
633	__n2 = ranges::distance(__first2, __last2);
634
635	// __glibcxx_assert(__n2 != -1);
636
637	if (__n1 != -`1`)
638	{
639	if (__n1 < __n2)
640	return false;
641	auto __shift = __n1 - iter_difference_t<_Iter1>(__n2);
642	if (random_access_iterator<_Iter1>
643	\|\| !bidirectional_iterator<_Iter1>
644	\|\| !same_as<_Iter1, _Sent1>
645	\|\| __shift < __n2)
646	{
647	ranges::advance(__first1, __shift);
648	return ranges::equal(std::move(__first1), __last1,
649	std::move(__first2), __last2,
650	std::move(__pred),
651	std::move(__proj1), std::move(__proj2));
652	}
653	}
654
655	if constexpr (bidirectional_iterator<_Iter1> && same_as<_Iter1, _Sent1>)
656	{
657	_Iter1 __it1 = __last1;
658	if (__n1 != -`1`)
659	ranges::advance(__it1, -iter_difference_t<_Iter1>(__n2));
660	else
661	{
662	// We can't use ranges::advance if the haystack size is
663	// unknown, since we need to detect and return false if
664	// it's smaller than the needle.
665	iter_difference_t<_Iter2> __m = __n2;
666	while (__m != `0` && __it1 != __first1)
667	{
668	--__m;
669	--__it1;
670	}
671	if (__m != `0`)
672	return false;
673	}
674	return ranges::equal(__it1, __last1,
675	std::move(__first2), __last2,
676	std::move(__pred),
677	std::move(__proj1), std::move(__proj2));
678	}
679	else if constexpr (forward_iterator<_Iter1>)
680	{
681	// __glibcxx_assert(__n1 == -1);
682	_Iter1 __prev_first1;
683	__n1 = `0`;
684	while (true)
685	{
686	iter_difference_t<_Iter2> __m = __n2;
687	_Iter1 __it1 = __first1;
688	while (__m != `0` && __it1 != __last1)
689	{
690	++__n1;
691	--__m;
692	++__it1;
693	}
694	if (__m != `0`)
695	{
696	// __glibcxx_assert(__it1 == __last1);
697	if (__n1 < __n2)
698	return false;
699	__first1 = ranges::next(__prev_first1,
700	iter_difference_t<_Iter1>(__n2 - __m));
701	break;
702	}
703	__prev_first1 = __first1;
704	__first1 = __it1;
705	}
706	return ranges::equal(__first1, __last1,
707	std::move(__first2), __last2,
708	std::move(__pred),
709	std::move(__proj1), std::move(__proj2));
710	}
711	else
712	// If the haystack is non-forward then it must be sized, in which case
713	// we already returned via the __n1 != 1 case.
714	__builtin_unreachable();
715	}
716
717	};
718
719	inline constexpr __ends_with_fn ends_with{};
720	#endif // __glibcxx_ranges_starts_ends_with
721
722	struct __find_end_fn
723	{
724	template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
725	forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
726	typename _Pred = ranges::equal_to,
727	typename _Proj1 = identity, typename _Proj2 = identity>
728	requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
729	[[nodiscard]] constexpr subrange<_Iter1>
730	operator()(_Iter1 __first1, _Sent1 __last1,
731	_Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
732	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
733	{
734	if constexpr (bidirectional_iterator<_Iter1>
735	&& bidirectional_iterator<_Iter2>)
736	{
737	auto __i1 = ranges::next(__first1, __last1);
738	auto __i2 = ranges::next(__first2, __last2);
739	auto __rresult
740	= ranges::search(reverse_iterator<_Iter1>{__i1},
741	reverse_iterator<_Iter1>{__first1},
742	reverse_iterator<_Iter2>{__i2},
743	reverse_iterator<_Iter2>{__first2},
744	std::move(__pred),
745	std::move(__proj1), std::move(__proj2));
746	auto __result_first = ranges::end(__rresult).base();
747	auto __result_last = ranges::begin(__rresult).base();
748	if (__result_last == __first1)
749	return {__i1, __i1};
750	else
751	return {__result_first, __result_last};
752	}
753	else
754	{
755	auto __i = ranges::next(__first1, __last1);
756	if (__first2 == __last2)
757	return {__i, __i};
758
759	auto __result_begin = __i;
760	auto __result_end = __i;
761	for (;;)
762	{
763	auto __new_range = ranges::search(__first1, __last1,
764	__first2, __last2,
765	__pred, __proj1, __proj2);
766	auto __new_result_begin = ranges::begin(__new_range);
767	auto __new_result_end = ranges::end(__new_range);
768	if (__new_result_begin == __last1)
769	return {__result_begin, __result_end};
770	else
771	{
772	__result_begin = __new_result_begin;
773	__result_end = __new_result_end;
774	__first1 = __result_begin;
775	++__first1;
776	}
777	}
778	}
779	}
780
781	template<forward_range _Range1, forward_range _Range2,
782	typename _Pred = ranges::equal_to,
783	typename _Proj1 = identity, typename _Proj2 = identity>
784	requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
785	_Pred, _Proj1, _Proj2>
786	[[nodiscard]] constexpr borrowed_subrange_t<_Range1>
787	operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
788	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
789	{
790	return (*this)(ranges::begin(__r1), ranges::end(__r1),
791	ranges::begin(__r2), ranges::end(__r2),
792	std::move(__pred),
793	std::move(__proj1), std::move(__proj2));
794	}
795	};
796
797	inline constexpr __find_end_fn find_end{};
798
799	// adjacent_find is defined in <bits/ranges_util.h>.
800
801	struct __is_permutation_fn
802	{
803	template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
804	forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
805	typename _Proj1 = identity, typename _Proj2 = identity,
806	indirect_equivalence_relation<projected<_Iter1, _Proj1>,
807	projected<_Iter2, _Proj2>> _Pred
808	= ranges::equal_to>
809	[[nodiscard]] constexpr bool
810	operator()(_Iter1 __first1, _Sent1 __last1,
811	_Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
812	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
813	{
814	constexpr bool __sized_iters
815	= (sized_sentinel_for<_Sent1, _Iter1>
816	&& sized_sentinel_for<_Sent2, _Iter2>);
817	if constexpr (__sized_iters)
818	{
819	auto __d1 = ranges::distance(__first1, __last1);
820	auto __d2 = ranges::distance(__first2, __last2);
821	if (__d1 != __d2)
822	return false;
823	}
824
825	// Efficiently compare identical prefixes: O(N) if sequences
826	// have the same elements in the same order.
827	for (; __first1 != __last1 && __first2 != __last2;
828	++__first1, (void)++__first2)
829	if (!(bool)std::__invoke(__pred,
830	std::__invoke(__proj1, *__first1),
831	std::__invoke(__proj2, *__first2)))
832	break;
833
834	if constexpr (__sized_iters)
835	{
836	if (__first1 == __last1)
837	return true;
838	}
839	else
840	{
841	auto __d1 = ranges::distance(__first1, __last1);
842	auto __d2 = ranges::distance(__first2, __last2);
843	if (__d1 == `0` && __d2 == `0`)
844	return true;
845	if (__d1 != __d2)
846	return false;
847	}
848
849	for (auto __scan = __first1; __scan != __last1; ++__scan)
850	{
851	auto&& __scan_deref = *__scan;
852	auto&& __proj_scan =
853	std::__invoke(__proj1, std::forward<decltype(__scan_deref)>(__scan_deref));
854	auto __comp_scan = [&] <typename _Tp> (_Tp&& __arg) -> bool {
855	return std::__invoke(__pred,
856	std::forward<decltype(__proj_scan)>(__proj_scan),
857	std::forward<_Tp>(__arg));
858	};
859	if (__scan != ranges::find_if(__first1, __scan,
860	__comp_scan, __proj1))
861	continue; // We've seen this one before.
862
863	auto __matches = ranges::count_if(__first2, __last2,
864	__comp_scan, __proj2);
865	if (__matches == `0`
866	\|\| ranges::count_if(__scan, __last1,
867	__comp_scan, __proj1) != __matches)
868	return false;
869	}
870	return true;
871	}
872
873	template<forward_range _Range1, forward_range _Range2,
874	typename _Proj1 = identity, typename _Proj2 = identity,
875	indirect_equivalence_relation<
876	projected<iterator_t<_Range1>, _Proj1>,
877	projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to>
878	[[nodiscard]] constexpr bool
879	operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
880	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
881	{
882	// _GLIBCXX_RESOLVE_LIB_DEFECTS
883	// 3560. ranges::is_permutation should short-circuit for sized_ranges
884	if constexpr (sized_range<_Range1>)
885	if constexpr (sized_range<_Range2>)
886	if (ranges::distance(__r1) != ranges::distance(__r2))
887	return false;
888
889	return (*this)(ranges::begin(__r1), ranges::end(__r1),
890	ranges::begin(__r2), ranges::end(__r2),
891	std::move(__pred),
892	std::move(__proj1), std::move(__proj2));
893	}
894	};
895
896	inline constexpr __is_permutation_fn is_permutation{};
897
898	template<typename _Iter, typename _Out>
899	using copy_if_result = in_out_result<_Iter, _Out>;
900
901	struct __copy_if_fn
902	{
903	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
904	weakly_incrementable _Out, typename _Proj = identity,
905	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
906	requires indirectly_copyable<_Iter, _Out>
907	constexpr copy_if_result<_Iter, _Out>
908	operator()(_Iter __first, _Sent __last, _Out __result,
909	_Pred __pred, _Proj __proj = {}) const
910	{
911	for (; __first != __last; ++__first)
912	if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
913	{
914	__result = __first;
915	++__result;
916	}
917	return {std::move(__first), std::move(__result)};
918	}
919
920	template<input_range _Range, weakly_incrementable _Out,
921	typename _Proj = identity,
922	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
923	_Pred>
924	requires indirectly_copyable<iterator_t<_Range>, _Out>
925	constexpr copy_if_result<borrowed_iterator_t<_Range>, _Out>
926	operator()(_Range&& __r, _Out __result,
927	_Pred __pred, _Proj __proj = {}) const
928	{
929	return (*this)(ranges::begin(__r), ranges::end(__r),
930	std::move(__result),
931	std::move(__pred), std::move(__proj));
932	}
933	};
934
935	inline constexpr __copy_if_fn copy_if{};
936
937	template<typename _Iter1, typename _Iter2>
938	using swap_ranges_result = in_in_result<_Iter1, _Iter2>;
939
940	struct __swap_ranges_fn
941	{
942	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
943	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2>
944	requires indirectly_swappable<_Iter1, _Iter2>
945	constexpr swap_ranges_result<_Iter1, _Iter2>
946	operator()(_Iter1 __first1, _Sent1 __last1,
947	_Iter2 __first2, _Sent2 __last2) const
948	{
949	for (; __first1 != __last1 && __first2 != __last2;
950	++__first1, (void)++__first2)
951	ranges::iter_swap(__first1, __first2);
952	return {std::move(__first1), std::move(__first2)};
953	}
954
955	template<input_range _Range1, input_range _Range2>
956	requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>>
957	constexpr swap_ranges_result<borrowed_iterator_t<_Range1>,
958	borrowed_iterator_t<_Range2>>
959	operator()(_Range1&& __r1, _Range2&& __r2) const
960	{
961	return (*this)(ranges::begin(__r1), ranges::end(__r1),
962	ranges::begin(__r2), ranges::end(__r2));
963	}
964	};
965
966	inline constexpr __swap_ranges_fn swap_ranges{};
967
968	template<typename _Iter, typename _Out>
969	using unary_transform_result = in_out_result<_Iter, _Out>;
970
971	template<typename _Iter1, typename _Iter2, typename _Out>
972	struct in_in_out_result
973	{
974	[[no_unique_address]] _Iter1 in1;
975	[[no_unique_address]] _Iter2 in2;
976	[[no_unique_address]] _Out out;
977
978	template<typename _IIter1, typename _IIter2, typename _OOut>
979	requires convertible_to<const _Iter1&, _IIter1>
980	&& convertible_to<const _Iter2&, _IIter2>
981	&& convertible_to<const _Out&, _OOut>
982	constexpr
983	operator in_in_out_result<_IIter1, _IIter2, _OOut>() const &
984	{ return {in1, in2, out}; }
985
986	template<typename _IIter1, typename _IIter2, typename _OOut>
987	requires convertible_to<_Iter1, _IIter1>
988	&& convertible_to<_Iter2, _IIter2>
989	&& convertible_to<_Out, _OOut>
990	constexpr
991	operator in_in_out_result<_IIter1, _IIter2, _OOut>() &&
992	{ return {std::move(in1), std::move(in2), std::move(out)}; }
993	};
994
995	template<typename _Iter1, typename _Iter2, typename _Out>
996	using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>;
997
998	struct __transform_fn
999	{
1000	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1001	weakly_incrementable _Out,
1002	copy_constructible _Fp, typename _Proj = identity>
1003	requires indirectly_writable<_Out,
1004	indirect_result_t<_Fp&,
1005	projected<_Iter, _Proj>>>
1006	constexpr unary_transform_result<_Iter, _Out>
1007	operator()(_Iter __first1, _Sent __last1, _Out __result,
1008	_Fp __op, _Proj __proj = {}) const
1009	{
1010	for (; __first1 != __last1; ++__first1, (void)++__result)
1011	__result = std::__invoke(__op, std::__invoke(__proj, __first1));
1012	return {std::move(__first1), std::move(__result)};
1013	}
1014
1015	template<input_range _Range, weakly_incrementable _Out,
1016	copy_constructible _Fp, typename _Proj = identity>
1017	requires indirectly_writable<_Out,
1018	indirect_result_t<_Fp&,
1019	projected<iterator_t<_Range>, _Proj>>>
1020	constexpr unary_transform_result<borrowed_iterator_t<_Range>, _Out>
1021	operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {}) const
1022	{
1023	return (*this)(ranges::begin(__r), ranges::end(__r),
1024	std::move(__result),
1025	std::move(__op), std::move(__proj));
1026	}
1027
1028	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
1029	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
1030	weakly_incrementable _Out, copy_constructible _Fp,
1031	typename _Proj1 = identity, typename _Proj2 = identity>
1032	requires indirectly_writable<_Out,
1033	indirect_result_t<_Fp&,
1034	projected<_Iter1, _Proj1>,
1035	projected<_Iter2, _Proj2>>>
1036	constexpr binary_transform_result<_Iter1, _Iter2, _Out>
1037	operator()(_Iter1 __first1, _Sent1 __last1,
1038	_Iter2 __first2, _Sent2 __last2,
1039	_Out __result, _Fp __binary_op,
1040	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
1041	{
1042	for (; __first1 != __last1 && __first2 != __last2;
1043	++__first1, (void)++__first2, ++__result)
1044	*__result = std::__invoke(__binary_op,
1045	std::__invoke(__proj1, *__first1),
1046	std::__invoke(__proj2, *__first2));
1047	return {std::move(__first1), std::move(__first2), std::move(__result)};
1048	}
1049
1050	template<input_range _Range1, input_range _Range2,
1051	weakly_incrementable _Out, copy_constructible _Fp,
1052	typename _Proj1 = identity, typename _Proj2 = identity>
1053	requires indirectly_writable<_Out,
1054	indirect_result_t<_Fp&,
1055	projected<iterator_t<_Range1>, _Proj1>,
1056	projected<iterator_t<_Range2>, _Proj2>>>
1057	constexpr binary_transform_result<borrowed_iterator_t<_Range1>,
1058	borrowed_iterator_t<_Range2>, _Out>
1059	operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op,
1060	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
1061	{
1062	return (*this)(ranges::begin(__r1), ranges::end(__r1),
1063	ranges::begin(__r2), ranges::end(__r2),
1064	std::move(__result), std::move(__binary_op),
1065	std::move(__proj1), std::move(__proj2));
1066	}
1067	};
1068
1069	inline constexpr __transform_fn transform{};
1070
1071	struct __replace_fn
1072	{
1073	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1074	typename _Proj = identity,
1075	typename _Tp1 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
1076	typename _Tp2 _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>)>
1077	requires indirectly_writable<_Iter, const _Tp2&>
1078	&& indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
1079	const _Tp1*>
1080	constexpr _Iter
1081	operator()(_Iter __first, _Sent __last,
1082	const _Tp1& __old_value, const _Tp2& __new_value,
1083	_Proj __proj = {}) const
1084	{
1085	for (; __first != __last; ++__first)
1086	if (std::__invoke(__proj, *__first) == __old_value)
1087	*__first = __new_value;
1088	return __first;
1089	}
1090
1091	template<input_range _Range, typename _Proj = identity,
1092	typename _Tp1
1093	_GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj),
1094	typename _Tp2 _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>)>
1095	requires indirectly_writable<iterator_t<_Range>, const _Tp2&>
1096	&& indirect_binary_predicate<ranges::equal_to,
1097	projected<iterator_t<_Range>, _Proj>,
1098	const _Tp1*>
1099	constexpr borrowed_iterator_t<_Range>
1100	operator()(_Range&& __r,
1101	const _Tp1& __old_value, const _Tp2& __new_value,
1102	_Proj __proj = {}) const
1103	{
1104	return (*this)(ranges::begin(__r), ranges::end(__r),
1105	__old_value, __new_value, std::move(__proj));
1106	}
1107	};
1108
1109	inline constexpr __replace_fn replace{};
1110
1111	struct __replace_if_fn
1112	{
1113	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1114	typename _Proj = identity,
1115	typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>),
1116	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1117	requires indirectly_writable<_Iter, const _Tp&>
1118	constexpr _Iter
1119	operator()(_Iter __first, _Sent __last,
1120	_Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
1121	{
1122	for (; __first != __last; ++__first)
1123	if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
1124	*__first = __new_value;
1125	return std::move(__first);
1126	}
1127
1128	template<input_range _Range, typename _Proj = identity,
1129	typename _Tp
1130	_GLIBCXX26_DEF_VAL_T(range_value_t<_Range>),
1131	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1132	_Pred>
1133	requires indirectly_writable<iterator_t<_Range>, const _Tp&>
1134	constexpr borrowed_iterator_t<_Range>
1135	operator()(_Range&& __r,
1136	_Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
1137	{
1138	return (*this)(ranges::begin(__r), ranges::end(__r),
1139	std::move(__pred), __new_value, std::move(__proj));
1140	}
1141	};
1142
1143	inline constexpr __replace_if_fn replace_if{};
1144
1145	template<typename _Iter, typename _Out>
1146	using replace_copy_result = in_out_result<_Iter, _Out>;
1147
1148	struct __replace_copy_fn
1149	{
1150	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1151	typename _Out, typename _Proj = identity,
1152	typename _Tp1 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
1153	typename _Tp2 _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>)>
1154	requires indirectly_copyable<_Iter, _Out>
1155	&& indirect_binary_predicate<ranges::equal_to,
1156	projected<_Iter, _Proj>, const _Tp1*>
1157	&& output_iterator<_Out, const _Tp2&>
1158	constexpr replace_copy_result<_Iter, _Out>
1159	operator()(_Iter __first, _Sent __last, _Out __result,
1160	const _Tp1& __old_value, const _Tp2& __new_value,
1161	_Proj __proj = {}) const
1162	{
1163	for (; __first != __last; ++__first, (void)++__result)
1164	if (std::__invoke(__proj, *__first) == __old_value)
1165	*__result = __new_value;
1166	else
1167	__result = __first;
1168	return {std::move(__first), std::move(__result)};
1169	}
1170
1171	template<input_range _Range, typename _Out,
1172	typename _Proj = identity,
1173	typename _Tp1
1174	_GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj),
1175	typename _Tp2 _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>)>
1176	requires indirectly_copyable<iterator_t<_Range>, _Out>
1177	&& indirect_binary_predicate<ranges::equal_to,
1178	projected<iterator_t<_Range>, _Proj>,
1179	const _Tp1*>
1180	&& output_iterator<_Out, const _Tp2&>
1181	constexpr replace_copy_result<borrowed_iterator_t<_Range>, _Out>
1182	operator()(_Range&& __r, _Out __result,
1183	const _Tp1& __old_value, const _Tp2& __new_value,
1184	_Proj __proj = {}) const
1185	{
1186	return (*this)(ranges::begin(__r), ranges::end(__r),
1187	std::move(__result), __old_value,
1188	__new_value, std::move(__proj));
1189	}
1190	};
1191
1192	inline constexpr __replace_copy_fn replace_copy{};
1193
1194	template<typename _Iter, typename _Out>
1195	using replace_copy_if_result = in_out_result<_Iter, _Out>;
1196
1197	struct __replace_copy_if_fn
1198	{
1199	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1200	typename _Out,
1201	typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>),
1202	typename _Proj = identity,
1203	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1204	requires indirectly_copyable<_Iter, _Out>
1205	&& output_iterator<_Out, const _Tp&>
1206	constexpr replace_copy_if_result<_Iter, _Out>
1207	operator()(_Iter __first, _Sent __last, _Out __result,
1208	_Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
1209	{
1210	for (; __first != __last; ++__first, (void)++__result)
1211	if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
1212	*__result = __new_value;
1213	else
1214	__result = __first;
1215	return {std::move(__first), std::move(__result)};
1216	}
1217
1218	template<input_range _Range,
1219	typename _Out,
1220	typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>),
1221	typename _Proj = identity,
1222	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1223	_Pred>
1224	requires indirectly_copyable<iterator_t<_Range>, _Out>
1225	&& output_iterator<_Out, const _Tp&>
1226	constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _Out>
1227	operator()(_Range&& __r, _Out __result,
1228	_Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
1229	{
1230	return (*this)(ranges::begin(__r), ranges::end(__r),
1231	std::move(__result), std::move(__pred),
1232	__new_value, std::move(__proj));
1233	}
1234	};
1235
1236	inline constexpr __replace_copy_if_fn replace_copy_if{};
1237
1238	struct __generate_n_fn
1239	{
1240	template<input_or_output_iterator _Out, copy_constructible _Fp>
1241	requires invocable<_Fp&>
1242	&& indirectly_writable<_Out, invoke_result_t<_Fp&>>
1243	constexpr _Out
1244	operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen) const
1245	{
1246	for (; __n > `0`; --__n, (void)++__first)
1247	*__first = std::__invoke(__gen);
1248	return __first;
1249	}
1250	};
1251
1252	inline constexpr __generate_n_fn generate_n{};
1253
1254	struct __generate_fn
1255	{
1256	template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent,
1257	copy_constructible _Fp>
1258	requires invocable<_Fp&>
1259	&& indirectly_writable<_Out, invoke_result_t<_Fp&>>
1260	constexpr _Out
1261	operator()(_Out __first, _Sent __last, _Fp __gen) const
1262	{
1263	for (; __first != __last; ++__first)
1264	*__first = std::__invoke(__gen);
1265	return __first;
1266	}
1267
1268	template<typename _Range, copy_constructible _Fp>
1269	requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>>
1270	constexpr borrowed_iterator_t<_Range>
1271	operator()(_Range&& __r, _Fp __gen) const
1272	{
1273	return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__gen));
1274	}
1275	};
1276
1277	inline constexpr __generate_fn generate{};
1278
1279	struct __remove_if_fn
1280	{
1281	template<permutable _Iter, sentinel_for<_Iter> _Sent,
1282	typename _Proj = identity,
1283	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1284	[[nodiscard]] constexpr subrange<_Iter>
1285	operator()(_Iter __first, _Sent __last,
1286	_Pred __pred, _Proj __proj = {}) const
1287	{
1288	__first = ranges::find_if(__first, __last, __pred, __proj);
1289	if (__first == __last)
1290	return {__first, __first};
1291
1292	auto __result = __first;
1293	++__first;
1294	for (; __first != __last; ++__first)
1295	if (!std::__invoke(__pred, std::__invoke(__proj, *__first)))
1296	{
1297	*__result = ranges::iter_move(__first);
1298	++__result;
1299	}
1300
1301	return {__result, __first};
1302	}
1303
1304	template<forward_range _Range, typename _Proj = identity,
1305	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1306	_Pred>
1307	requires permutable<iterator_t<_Range>>
1308	[[nodiscard]] constexpr borrowed_subrange_t<_Range>
1309	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
1310	{
1311	return (*this)(ranges::begin(__r), ranges::end(__r),
1312	std::move(__pred), std::move(__proj));
1313	}
1314	};
1315
1316	inline constexpr __remove_if_fn remove_if{};
1317
1318	struct __remove_fn
1319	{
1320	template<permutable _Iter, sentinel_for<_Iter> _Sent,
1321	typename _Proj = identity,
1322	typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
1323	requires indirect_binary_predicate<ranges::equal_to,
1324	projected<_Iter, _Proj>,
1325	const _Tp*>
1326	[[nodiscard]] constexpr subrange<_Iter>
1327	operator()(_Iter __first, _Sent __last,
1328	const _Tp& __value, _Proj __proj = {}) const
1329	{
1330	auto __pred = [&] (auto&& __arg) -> bool {
1331	return std::forward<decltype(__arg)>(__arg) == __value;
1332	};
1333	return ranges::remove_if(__first, __last,
1334	std::move(__pred), std::move(__proj));
1335	}
1336
1337	template<forward_range _Range, typename _Proj = identity,
1338	typename _Tp
1339	_GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)>
1340	requires permutable<iterator_t<_Range>>
1341	&& indirect_binary_predicate<ranges::equal_to,
1342	projected<iterator_t<_Range>, _Proj>,
1343	const _Tp*>
1344	[[nodiscard]] constexpr borrowed_subrange_t<_Range>
1345	operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
1346	{
1347	return (*this)(ranges::begin(__r), ranges::end(__r),
1348	__value, std::move(__proj));
1349	}
1350	};
1351
1352	inline constexpr __remove_fn remove{};
1353
1354	template<typename _Iter, typename _Out>
1355	using remove_copy_if_result = in_out_result<_Iter, _Out>;
1356
1357	struct __remove_copy_if_fn
1358	{
1359	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1360	weakly_incrementable _Out, typename _Proj = identity,
1361	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1362	requires indirectly_copyable<_Iter, _Out>
1363	constexpr remove_copy_if_result<_Iter, _Out>
1364	operator()(_Iter __first, _Sent __last, _Out __result,
1365	_Pred __pred, _Proj __proj = {}) const
1366	{
1367	for (; __first != __last; ++__first)
1368	if (!std::__invoke(__pred, std::__invoke(__proj, *__first)))
1369	{
1370	__result = __first;
1371	++__result;
1372	}
1373	return {std::move(__first), std::move(__result)};
1374	}
1375
1376	template<input_range _Range, weakly_incrementable _Out,
1377	typename _Proj = identity,
1378	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1379	_Pred>
1380	requires indirectly_copyable<iterator_t<_Range>, _Out>
1381	constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _Out>
1382	operator()(_Range&& __r, _Out __result,
1383	_Pred __pred, _Proj __proj = {}) const
1384	{
1385	return (*this)(ranges::begin(__r), ranges::end(__r),
1386	std::move(__result),
1387	std::move(__pred), std::move(__proj));
1388	}
1389	};
1390
1391	inline constexpr __remove_copy_if_fn remove_copy_if{};
1392
1393	template<typename _Iter, typename _Out>
1394	using remove_copy_result = in_out_result<_Iter, _Out>;
1395
1396	struct __remove_copy_fn
1397	{
1398	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1399	weakly_incrementable _Out, typename _Proj = identity,
1400	typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
1401	requires indirectly_copyable<_Iter, _Out>
1402	&& indirect_binary_predicate<ranges::equal_to,
1403	projected<_Iter, _Proj>,
1404	const _Tp*>
1405	constexpr remove_copy_result<_Iter, _Out>
1406	operator()(_Iter __first, _Sent __last, _Out __result,
1407	const _Tp& __value, _Proj __proj = {}) const
1408	{
1409	for (; __first != __last; ++__first)
1410	if (!(std::__invoke(__proj, *__first) == __value))
1411	{
1412	__result = __first;
1413	++__result;
1414	}
1415	return {std::move(__first), std::move(__result)};
1416	}
1417
1418	template<input_range _Range, weakly_incrementable _Out,
1419	typename _Proj = identity,
1420	typename _Tp
1421	_GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)>
1422	requires indirectly_copyable<iterator_t<_Range>, _Out>
1423	&& indirect_binary_predicate<ranges::equal_to,
1424	projected<iterator_t<_Range>, _Proj>,
1425	const _Tp*>
1426	constexpr remove_copy_result<borrowed_iterator_t<_Range>, _Out>
1427	operator()(_Range&& __r, _Out __result,
1428	const _Tp& __value, _Proj __proj = {}) const
1429	{
1430	return (*this)(ranges::begin(__r), ranges::end(__r),
1431	std::move(__result), __value, std::move(__proj));
1432	}
1433	};
1434
1435	inline constexpr __remove_copy_fn remove_copy{};
1436
1437	struct __unique_fn
1438	{
1439	template<permutable _Iter, sentinel_for<_Iter> _Sent,
1440	typename _Proj = identity,
1441	indirect_equivalence_relation<
1442	projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1443	[[nodiscard]] constexpr subrange<_Iter>
1444	operator()(_Iter __first, _Sent __last,
1445	_Comp __comp = {}, _Proj __proj = {}) const
1446	{
1447	__first = ranges::adjacent_find(__first, __last, __comp, __proj);
1448	if (__first == __last)
1449	return {__first, __first};
1450
1451	auto __dest = __first;
1452	++__first;
1453	while (++__first != __last)
1454	if (!std::__invoke(__comp,
1455	std::__invoke(__proj, *__dest),
1456	std::__invoke(__proj, *__first)))
1457	*++__dest = ranges::iter_move(__first);
1458	return {++__dest, __first};
1459	}
1460
1461	template<forward_range _Range, typename _Proj = identity,
1462	indirect_equivalence_relation<
1463	projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1464	requires permutable<iterator_t<_Range>>
1465	[[nodiscard]] constexpr borrowed_subrange_t<_Range>
1466	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1467	{
1468	return (*this)(ranges::begin(__r), ranges::end(__r),
1469	std::move(__comp), std::move(__proj));
1470	}
1471	};
1472
1473	inline constexpr __unique_fn unique{};
1474
1475	namespace __detail
1476	{
1477	template<typename _Out, typename _Tp>
1478	concept __can_reread_output = input_iterator<_Out>
1479	&& same_as<_Tp, iter_value_t<_Out>>;
1480	}
1481
1482	template<typename _Iter, typename _Out>
1483	using unique_copy_result = in_out_result<_Iter, _Out>;
1484
1485	struct __unique_copy_fn
1486	{
1487	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1488	weakly_incrementable _Out, typename _Proj = identity,
1489	indirect_equivalence_relation<
1490	projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1491	requires indirectly_copyable<_Iter, _Out>
1492	&& (forward_iterator<_Iter>
1493	\|\| __detail::__can_reread_output<_Out, iter_value_t<_Iter>>
1494	\|\| indirectly_copyable_storable<_Iter, _Out>)
1495	constexpr unique_copy_result<_Iter, _Out>
1496	operator()(_Iter __first, _Sent __last, _Out __result,
1497	_Comp __comp = {}, _Proj __proj = {}) const
1498	{
1499	if (__first == __last)
1500	return {std::move(__first), std::move(__result)};
1501
1502	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1503	// 4269. unique_copy passes arguments to its predicate backwards
1504
1505	// TODO: perform a closer comparison with reference implementations
1506	if constexpr (forward_iterator<_Iter>)
1507	{
1508	auto __next = __first;
1509	__result = __next;
1510	while (++__next != __last)
1511	if (!std::__invoke(__comp,
1512	std::__invoke(__proj, *__first),
1513	std::__invoke(__proj, *__next)))
1514	{
1515	__first = __next;
1516	++__result = __first;
1517	}
1518	return {__next, std::move(++__result)};
1519	}
1520	else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>)
1521	{
1522	__result = __first;
1523	while (++__first != __last)
1524	if (!std::__invoke(__comp,
1525	std::__invoke(__proj, *__result),
1526	std::__invoke(__proj, *__first)))
1527	++__result = __first;
1528	return {std::move(__first), std::move(++__result)};
1529	}
1530	else // indirectly_copyable_storable<_Iter, _Out>
1531	{
1532	iter_value_t<_Iter> __value(*__first);
1533	*__result = __value;
1534	while (++__first != __last)
1535	{
1536	if (!(bool)std::__invoke(__comp,
1537	std::__invoke(__proj, __value),
1538	std::__invoke(__proj, *__first)))
1539	{
1540	__value = *__first;
1541	*++__result = __value;
1542	}
1543	}
1544	return {std::move(__first), std::move(++__result)};
1545	}
1546	}
1547
1548	template<input_range _Range,
1549	weakly_incrementable _Out, typename _Proj = identity,
1550	indirect_equivalence_relation<
1551	projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1552	requires indirectly_copyable<iterator_t<_Range>, _Out>
1553	&& (forward_iterator<iterator_t<_Range>>
1554	\|\| __detail::__can_reread_output<_Out, range_value_t<_Range>>
1555	\|\| indirectly_copyable_storable<iterator_t<_Range>, _Out>)
1556	constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out>
1557	operator()(_Range&& __r, _Out __result,
1558	_Comp __comp = {}, _Proj __proj = {}) const
1559	{
1560	return (*this)(ranges::begin(__r), ranges::end(__r),
1561	std::move(__result),
1562	std::move(__comp), std::move(__proj));
1563	}
1564	};
1565
1566	inline constexpr __unique_copy_fn unique_copy{};
1567
1568	struct __reverse_fn
1569	{
1570	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
1571	requires permutable<_Iter>
1572	constexpr _Iter
1573	operator()(_Iter __first, _Sent __last) const
1574	{
1575	auto __i = ranges::next(__first, __last);
1576	auto __tail = __i;
1577
1578	if constexpr (random_access_iterator<_Iter>)
1579	{
1580	if (__first != __last)
1581	{
1582	--__tail;
1583	while (__first < __tail)
1584	{
1585	ranges::iter_swap(__first, __tail);
1586	++__first;
1587	--__tail;
1588	}
1589	}
1590	return __i;
1591	}
1592	else
1593	{
1594	for (;;)
1595	if (__first == __tail \|\| __first == --__tail)
1596	break;
1597	else
1598	{
1599	ranges::iter_swap(__first, __tail);
1600	++__first;
1601	}
1602	return __i;
1603	}
1604	}
1605
1606	template<bidirectional_range _Range>
1607	requires permutable<iterator_t<_Range>>
1608	constexpr borrowed_iterator_t<_Range>
1609	operator()(_Range&& __r) const
1610	{
1611	return (*this)(ranges::begin(__r), ranges::end(__r));
1612	}
1613	};
1614
1615	inline constexpr __reverse_fn reverse{};
1616
1617	template<typename _Iter, typename _Out>
1618	using reverse_copy_result = in_out_result<_Iter, _Out>;
1619
1620	struct __reverse_copy_fn
1621	{
1622	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
1623	weakly_incrementable _Out>
1624	requires indirectly_copyable<_Iter, _Out>
1625	constexpr reverse_copy_result<_Iter, _Out>
1626	operator()(_Iter __first, _Sent __last, _Out __result) const
1627	{
1628	auto __i = ranges::next(__first, __last);
1629	auto __tail = __i;
1630	while (__first != __tail)
1631	{
1632	--__tail;
1633	__result = __tail;
1634	++__result;
1635	}
1636	return {__i, std::move(__result)};
1637	}
1638
1639	template<bidirectional_range _Range, weakly_incrementable _Out>
1640	requires indirectly_copyable<iterator_t<_Range>, _Out>
1641	constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out>
1642	operator()(_Range&& __r, _Out __result) const
1643	{
1644	return (*this)(ranges::begin(__r), ranges::end(__r),
1645	std::move(__result));
1646	}
1647	};
1648
1649	inline constexpr __reverse_copy_fn reverse_copy{};
1650
1651	struct __rotate_fn
1652	{
1653	template<permutable _Iter, sentinel_for<_Iter> _Sent>
1654	constexpr subrange<_Iter>
1655	operator()(_Iter __first, _Iter __middle, _Sent __last) const
1656	{
1657	auto __lasti = ranges::next(__first, __last);
1658	if (__first == __middle)
1659	return {__lasti, __lasti};
1660	if (__last == __middle)
1661	return {std::move(__first), std::move(__lasti)};
1662
1663	if constexpr (random_access_iterator<_Iter>)
1664	{
1665	auto __n = __lasti - __first;
1666	auto __k = __middle - __first;
1667
1668	if (__k == __n - __k)
1669	{
1670	ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
1671	return {std::move(__middle), std::move(__lasti)};
1672	}
1673
1674	auto __p = __first;
1675	auto __ret = __first + (__lasti - __middle);
1676
1677	for (;;)
1678	{
1679	if (__k < __n - __k)
1680	{
1681	// TODO: is_pod is deprecated, but this condition is
1682	// consistent with the STL implementation.
1683	if constexpr (__is_pod(iter_value_t<_Iter>))
1684	if (__k == `1`)
1685	{
1686	auto __mid = ranges::next(__p, __n - `1`);
1687	auto __end = ranges::next(__mid);
1688	iter_value_t<_Iter> __t(ranges::iter_move(__p));
1689	ranges::move(ranges::next(__p), __end, __p);
1690	*__mid = std::move(__t);
1691	return {std::move(__ret), std::move(__lasti)};
1692	}
1693	auto __q = __p + __k;
1694	for (decltype(__n) __i = `0`; __i < __n - __k; ++ __i)
1695	{
1696	ranges::iter_swap(__p, __q);
1697	++__p;
1698	++__q;
1699	}
1700	__n %= __k;
1701	if (__n == `0`)
1702	return {std::move(__ret), std::move(__lasti)};
1703	ranges::swap(__n, __k);
1704	__k = __n - __k;
1705	}
1706	else
1707	{
1708	__k = __n - __k;
1709	// TODO: is_pod is deprecated, but this condition is
1710	// consistent with the STL implementation.
1711	if constexpr (__is_pod(iter_value_t<_Iter>))
1712	if (__k == `1`)
1713	{
1714	auto __mid = ranges::next(__p, __n - `1`);
1715	auto __end = ranges::next(__mid);
1716	iter_value_t<_Iter> __t(ranges::iter_move(__mid));
1717	ranges::move_backward(__p, __mid, __end);
1718	*__p = std::move(__t);
1719	return {std::move(__ret), std::move(__lasti)};
1720	}
1721	auto __q = __p + __n;
1722	__p = __q - __k;
1723	for (decltype(__n) __i = `0`; __i < __n - __k; ++ __i)
1724	{
1725	--__p;
1726	--__q;
1727	ranges::iter_swap(__p, __q);
1728	}
1729	__n %= __k;
1730	if (__n == `0`)
1731	return {std::move(__ret), std::move(__lasti)};
1732	std::swap(__n, __k);
1733	}
1734	}
1735	}
1736	else if constexpr (bidirectional_iterator<_Iter>)
1737	{
1738	auto __tail = __lasti;
1739
1740	ranges::reverse(__first, __middle);
1741	ranges::reverse(__middle, __tail);
1742
1743	while (__first != __middle && __middle != __tail)
1744	{
1745	ranges::iter_swap(__first, --__tail);
1746	++__first;
1747	}
1748
1749	if (__first == __middle)
1750	{
1751	ranges::reverse(__middle, __tail);
1752	return {std::move(__tail), std::move(__lasti)};
1753	}
1754	else
1755	{
1756	ranges::reverse(__first, __middle);
1757	return {std::move(__first), std::move(__lasti)};
1758	}
1759	}
1760	else
1761	{
1762	auto __first2 = __middle;
1763	do
1764	{
1765	ranges::iter_swap(__first, __first2);
1766	++__first;
1767	++__first2;
1768	if (__first == __middle)
1769	__middle = __first2;
1770	} while (__first2 != __last);
1771
1772	auto __ret = __first;
1773
1774	__first2 = __middle;
1775
1776	while (__first2 != __last)
1777	{
1778	ranges::iter_swap(__first, __first2);
1779	++__first;
1780	++__first2;
1781	if (__first == __middle)
1782	__middle = __first2;
1783	else if (__first2 == __last)
1784	__first2 = __middle;
1785	}
1786	return {std::move(__ret), std::move(__lasti)};
1787	}
1788	}
1789
1790	template<forward_range _Range>
1791	requires permutable<iterator_t<_Range>>
1792	constexpr borrowed_subrange_t<_Range>
1793	operator()(_Range&& __r, iterator_t<_Range> __middle) const
1794	{
1795	return (*this)(ranges::begin(__r), std::move(__middle),
1796	ranges::end(__r));
1797	}
1798	};
1799
1800	inline constexpr __rotate_fn rotate{};
1801
1802	template<typename _Iter, typename _Out>
1803	using rotate_copy_result = in_out_result<_Iter, _Out>;
1804
1805	struct __rotate_copy_fn
1806	{
1807	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1808	weakly_incrementable _Out>
1809	requires indirectly_copyable<_Iter, _Out>
1810	constexpr rotate_copy_result<_Iter, _Out>
1811	operator()(_Iter __first, _Iter __middle, _Sent __last,
1812	_Out __result) const
1813	{
1814	auto __copy1 = ranges::copy(__middle,
1815	std::move(__last),
1816	std::move(__result));
1817	auto __copy2 = ranges::copy(std::move(__first),
1818	std::move(__middle),
1819	std::move(__copy1.out));
1820	return { std::move(__copy1.in), std::move(__copy2.out) };
1821	}
1822
1823	template<forward_range _Range, weakly_incrementable _Out>
1824	requires indirectly_copyable<iterator_t<_Range>, _Out>
1825	constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out>
1826	operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result) const
1827	{
1828	return (*this)(ranges::begin(__r), std::move(__middle),
1829	ranges::end(__r), std::move(__result));
1830	}
1831	};
1832
1833	inline constexpr __rotate_copy_fn rotate_copy{};
1834
1835	struct __sample_fn
1836	{
1837	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1838	weakly_incrementable _Out, typename _Gen>
1839	requires (forward_iterator<_Iter> \|\| random_access_iterator<_Out>)
1840	&& indirectly_copyable<_Iter, _Out>
1841	&& uniform_random_bit_generator<remove_reference_t<_Gen>>
1842	_Out
1843	operator()(_Iter __first, _Sent __last, _Out __out,
1844	iter_difference_t<_Iter> __n, _Gen&& __g) const
1845	{
1846	// FIXME: Correctly handle integer-class difference types.
1847	if constexpr (forward_iterator<_Iter>)
1848	{
1849	using _Size = iter_difference_t<_Iter>;
1850	using __distrib_type = uniform_int_distribution<_Size>;
1851	using __param_type = typename __distrib_type::param_type;
1852	using _USize = __detail::__make_unsigned_like_t<_Size>;
1853	using __uc_type
1854	= common_type_t<typename remove_reference_t<_Gen>::result_type, _USize>;
1855
1856	if (__first == __last)
1857	return __out;
1858
1859	__distrib_type __d{};
1860	_Size __unsampled_sz = ranges::distance(__first, __last);
1861	__n = std::min(__n, __unsampled_sz);
1862
1863	// If possible, we use __gen_two_uniform_ints to efficiently produce
1864	// two random numbers using a single distribution invocation:
1865
1866	const __uc_type __urngrange = __g.max() - __g.min();
1867	if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
1868	// I.e. (__urngrange >= __unsampled_sz __unsampled_sz) but without*
1869	// wrapping issues.
1870	{
1871	while (__n != `0` && __unsampled_sz >= `2`)
1872	{
1873	const pair<_Size, _Size> __p =
1874	__gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - `1`, __g);
1875
1876	--__unsampled_sz;
1877	if (__p.first < __n)
1878	{
1879	__out = __first;
1880	++__out;
1881	--__n;
1882	}
1883
1884	++__first;
1885
1886	if (__n == `0`) break;
1887
1888	--__unsampled_sz;
1889	if (__p.second < __n)
1890	{
1891	__out = __first;
1892	++__out;
1893	--__n;
1894	}
1895
1896	++__first;
1897	}
1898	}
1899
1900	// The loop above is otherwise equivalent to this one-at-a-time version:
1901
1902	for (; __n != `0`; ++__first)
1903	if (__d(__g, __param_type{`0`, --__unsampled_sz}) < __n)
1904	{
1905	__out = __first;
1906	++__out;
1907	--__n;
1908	}
1909	return __out;
1910	}
1911	else
1912	{
1913	using __distrib_type
1914	= uniform_int_distribution<iter_difference_t<_Iter>>;
1915	using __param_type = typename __distrib_type::param_type;
1916	__distrib_type __d{};
1917	iter_difference_t<_Iter> __sample_sz = `0`;
1918	while (__first != __last && __sample_sz != __n)
1919	{
1920	__out[__sample_sz++] = *__first;
1921	++__first;
1922	}
1923	for (auto __pop_sz = __sample_sz; __first != __last;
1924	++__first, (void) ++__pop_sz)
1925	{
1926	const auto __k = __d(__g, __param_type{`0`, __pop_sz});
1927	if (__k < __n)
1928	__out[__k] = *__first;
1929	}
1930	return __out + iter_difference_t<_Out>(__sample_sz);
1931	}
1932	}
1933
1934	template<input_range _Range, weakly_incrementable _Out, typename _Gen>
1935	requires (forward_range<_Range> \|\| random_access_iterator<_Out>)
1936	&& indirectly_copyable<iterator_t<_Range>, _Out>
1937	&& uniform_random_bit_generator<remove_reference_t<_Gen>>
1938	_Out
1939	operator()(_Range&& __r, _Out __out,
1940	range_difference_t<_Range> __n, _Gen&& __g) const
1941	{
1942	return (*this)(ranges::begin(__r), ranges::end(__r),
1943	std::move(__out), __n,
1944	std::forward<_Gen>(__g));
1945	}
1946	};
1947
1948	inline constexpr __sample_fn sample{};
1949
1950	struct __shuffle_fn
1951	{
1952	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1953	typename _Gen>
1954	requires permutable<_Iter>
1955	&& uniform_random_bit_generator<remove_reference_t<_Gen>>
1956	_Iter
1957	operator()(_Iter __first, _Sent __last, _Gen&& __g) const
1958	{
1959	// FIXME: Correctly handle integer-class difference types.
1960	if (__first == __last)
1961	return __first;
1962
1963	using _DistanceType = iter_difference_t<_Iter>;
1964	using __ud_type = __detail::__make_unsigned_like_t<_DistanceType>;
1965	using __distr_type = std::uniform_int_distribution<__ud_type>;
1966	using __p_type = typename __distr_type::param_type;
1967
1968	using __uc_type
1969	= common_type_t<typename remove_reference_t<_Gen>::result_type, __ud_type>;
1970
1971	if constexpr (sized_sentinel_for<_Sent, _Iter>)
1972	{
1973	const __uc_type __urngrange = __g.max() - __g.min();
1974	const __uc_type __urange = __uc_type(__last - __first);
1975
1976	if (__urngrange / __urange >= __urange)
1977	// I.e. (__urngrange >= __urange __urange) but without wrap issues.*
1978	{
1979	_Iter __i = ranges::next(__first);
1980
1981	// Since we know the range isn't empty, an even number of elements
1982	// means an uneven number of elements /to swap/, in which case we
1983	// do the first one up front:
1984
1985	if ((__urange % `2`) == `0`)
1986	{
1987	__distr_type __d{`0`, `1`};
1988	ranges::iter_swap(__i++, ranges::next(__first, __d(__g)));
1989	}
1990
1991	// Now we know that __last - __i is even, so we do the rest in pairs,
1992	// using a single distribution invocation to produce swap positions
1993	// for two successive elements at a time:
1994
1995	while (__i != __last)
1996	{
1997	const __uc_type __swap_range = __uc_type(__i - __first) + `1`;
1998
1999	const pair<_DistanceType, _DistanceType> __pospos =
2000	__gen_two_uniform_ints(__swap_range, __swap_range + `1`, __g);
2001
2002	ranges::iter_swap(__i++, ranges::next(__first, __pospos.first));
2003	ranges::iter_swap(__i++, ranges::next(__first, __pospos.second));
2004	}
2005
2006	return __i;
2007	}
2008	}
2009
2010	__distr_type __d;
2011
2012	_Iter __i = ranges::next(__first);
2013	for (; __i != __last; ++__i)
2014	ranges::iter_swap(__i,
2015	ranges::next(__first,
2016	__d(__g, __p_type(`0`, __i - __first))));
2017
2018	return __i;
2019	}
2020
2021	template<random_access_range _Range, typename _Gen>
2022	requires permutable<iterator_t<_Range>>
2023	&& uniform_random_bit_generator<remove_reference_t<_Gen>>
2024	borrowed_iterator_t<_Range>
2025	operator()(_Range&& __r, _Gen&& __g) const
2026	{
2027	if constexpr (sized_range<_Range>
2028	&& !sized_sentinel_for<sentinel_t<_Range>,
2029	iterator_t<_Range>>)
2030	return (*this)(ranges::begin(__r),
2031	ranges::begin(__r) + ranges::distance(__r),
2032	std::forward<_Gen>(__g));
2033	else
2034	return (*this)(ranges::begin(__r), ranges::end(__r),
2035	std::forward<_Gen>(__g));
2036	}
2037	};
2038
2039	inline constexpr __shuffle_fn shuffle{};
2040
2041	namespace __detail
2042	{
2043	template<typename _Iter, typename _Comp>
2044	constexpr void
2045	__push_heap(_Iter __first,
2046	iter_difference_t<_Iter> __holeIndex,
2047	iter_difference_t<_Iter> __topIndex,
2048	iter_value_t<_Iter> __value,
2049	_Comp __comp)
2050	{
2051	auto __parent = (__holeIndex - `1`) / `2`;
2052	while (__holeIndex > __topIndex
2053	&& __comp(*(__first + __parent), __value))
2054	{
2055	*(__first + __holeIndex) = ranges::iter_move(__first + __parent);
2056	__holeIndex = __parent;
2057	__parent = (__holeIndex - `1`) / `2`;
2058	}
2059	*(__first + __holeIndex) = std::move(__value);
2060	}
2061	} // namespace __detail
2062
2063	struct __push_heap_fn
2064	{
2065	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2066	typename _Comp = ranges::less, typename _Proj = identity>
2067	requires sortable<_Iter, _Comp, _Proj>
2068	constexpr _Iter
2069	operator()(_Iter __first, _Sent __last,
2070	_Comp __comp = {}, _Proj __proj = {}) const
2071	{
2072	if constexpr (!same_as<_Iter, _Sent>)
2073	return (*this)(__first, ranges::next(__first, __last),
2074	std::move(__comp), std::move(__proj));
2075	else
2076	{
2077	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
2078	iter_value_t<_Iter> __value(ranges::iter_move(ranges::prev(__last)));
2079	__detail::__push_heap(__first, (__last - __first) - `1`,
2080	`0`, std::move(__value), __comp_proj);
2081	return __last;
2082	}
2083	}
2084
2085	template<random_access_range _Range,
2086	typename _Comp = ranges::less, typename _Proj = identity>
2087	requires sortable<iterator_t<_Range>, _Comp, _Proj>
2088	constexpr borrowed_iterator_t<_Range>
2089	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2090	{
2091	return (*this)(ranges::begin(__r), ranges::end(__r),
2092	std::move(__comp), std::move(__proj));
2093	}
2094	};
2095
2096	inline constexpr __push_heap_fn push_heap{};
2097
2098	namespace __detail
2099	{
2100	template<typename _Iter, typename _Comp>
2101	constexpr void
2102	__adjust_heap(_Iter __first,
2103	iter_difference_t<_Iter> __holeIndex,
2104	iter_difference_t<_Iter> __len,
2105	iter_value_t<_Iter> __value,
2106	_Comp __comp)
2107	{
2108	auto __topIndex = __holeIndex;
2109	auto __secondChild = __holeIndex;
2110	while (__secondChild < (__len - `1`) / `2`)
2111	{
2112	__secondChild = `2` * (__secondChild + `1`);
2113	if (__comp(*(__first + __secondChild),
2114	*(__first + (__secondChild - `1`))))
2115	__secondChild--;
2116	*(__first + __holeIndex) = ranges::iter_move(__first + __secondChild);
2117	__holeIndex = __secondChild;
2118	}
2119	if ((__len & `1`) == `0` && __secondChild == (__len - `2`) / `2`)
2120	{
2121	__secondChild = `2` * (__secondChild + `1`);
2122	*(__first + __holeIndex) = ranges::iter_move(__first + (__secondChild - `1`));
2123	__holeIndex = __secondChild - `1`;
2124	}
2125	__detail::__push_heap(__first, __holeIndex, __topIndex,
2126	std::move(__value), __comp);
2127	}
2128
2129	template<typename _Iter, typename _Comp>
2130	constexpr void
2131	__pop_heap(_Iter __first, _Iter __last, _Iter __result, _Comp __comp)
2132	{
2133	iter_value_t<_Iter> __value = ranges::iter_move(__result);
2134	*__result = ranges::iter_move(__first);
2135	__detail::__adjust_heap(__first, `0`, __last - __first,
2136	std::move(__value), __comp);
2137	}
2138	} // namespace __detail
2139
2140	struct __pop_heap_fn
2141	{
2142	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2143	typename _Comp = ranges::less, typename _Proj = identity>
2144	requires sortable<_Iter, _Comp, _Proj>
2145	constexpr _Iter
2146	operator()(_Iter __first, _Sent __last,
2147	_Comp __comp = {}, _Proj __proj = {}) const
2148	{
2149	if constexpr (!same_as<_Iter, _Sent>)
2150	return (*this)(__first, ranges::next(__first, __last),
2151	std::move(__comp), std::move(__proj));
2152	else
2153	{
2154	if (__last - __first > `1`)
2155	{
2156	auto __back = ranges::prev(__last);
2157	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
2158	__detail::__pop_heap(__first, __back, __back, __comp_proj);
2159	}
2160	return __last;
2161	}
2162	}
2163
2164	template<random_access_range _Range,
2165	typename _Comp = ranges::less, typename _Proj = identity>
2166	requires sortable<iterator_t<_Range>, _Comp, _Proj>
2167	constexpr borrowed_iterator_t<_Range>
2168	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2169	{
2170	return (*this)(ranges::begin(__r), ranges::end(__r),
2171	std::move(__comp), std::move(__proj));
2172	}
2173	};
2174
2175	inline constexpr __pop_heap_fn pop_heap{};
2176
2177	struct __make_heap_fn
2178	{
2179	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2180	typename _Comp = ranges::less, typename _Proj = identity>
2181	requires sortable<_Iter, _Comp, _Proj>
2182	constexpr _Iter
2183	operator()(_Iter __first, _Sent __last,
2184	_Comp __comp = {}, _Proj __proj = {}) const
2185	{
2186	if constexpr (!same_as<_Iter, _Sent>)
2187	return (*this)(__first, ranges::next(__first, __last),
2188	std::move(__comp), std::move(__proj));
2189	else
2190	{
2191	const auto __len = __last - __first;
2192	if (__len < `2`)
2193	return __last;
2194
2195	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
2196	auto __parent = (__len - `2`) / `2`;
2197	while (true)
2198	{
2199	iter_value_t<_Iter> __value = ranges::iter_move(__first + __parent);
2200	__detail::__adjust_heap(__first, __parent, __len,
2201	std::move(__value),
2202	__comp_proj);
2203	if (__parent == `0`)
2204	break;
2205	__parent--;
2206	}
2207	return __last;
2208	}
2209	}
2210
2211	template<random_access_range _Range,
2212	typename _Comp = ranges::less, typename _Proj = identity>
2213	requires sortable<iterator_t<_Range>, _Comp, _Proj>
2214	constexpr borrowed_iterator_t<_Range>
2215	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2216	{
2217	return (*this)(ranges::begin(__r), ranges::end(__r),
2218	std::move(__comp), std::move(__proj));
2219	}
2220	};
2221
2222	inline constexpr __make_heap_fn make_heap{};
2223
2224	struct __sort_heap_fn
2225	{
2226	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2227	typename _Comp = ranges::less, typename _Proj = identity>
2228	requires sortable<_Iter, _Comp, _Proj>
2229	constexpr _Iter
2230	operator()(_Iter __first, _Sent __last,
2231	_Comp __comp = {}, _Proj __proj = {}) const
2232	{
2233	if constexpr (!same_as<_Iter, _Sent>)
2234	return (*this)(__first, ranges::next(__first, __last),
2235	std::move(__comp), std::move(__proj));
2236	else
2237	{
2238	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
2239	_Iter __ret = __last;
2240	while (__last - __first > `1`)
2241	{
2242	--__last;
2243	__detail::__pop_heap(__first, __last, __last, __comp_proj);
2244	}
2245	return __ret;
2246	}
2247	}
2248
2249	template<random_access_range _Range,
2250	typename _Comp = ranges::less, typename _Proj = identity>
2251	requires sortable<iterator_t<_Range>, _Comp, _Proj>
2252	constexpr borrowed_iterator_t<_Range>
2253	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2254	{
2255	return (*this)(ranges::begin(__r), ranges::end(__r),
2256	std::move(__comp), std::move(__proj));
2257	}
2258	};
2259
2260	inline constexpr __sort_heap_fn sort_heap{};
2261
2262	struct __is_heap_until_fn
2263	{
2264	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2265	typename _Proj = identity,
2266	indirect_strict_weak_order<projected<_Iter, _Proj>>
2267	_Comp = ranges::less>
2268	constexpr _Iter
2269	operator()(_Iter __first, _Sent __last,
2270	_Comp __comp = {}, _Proj __proj = {}) const
2271	{
2272	iter_difference_t<_Iter> __n = ranges::distance(__first, __last);
2273	iter_difference_t<_Iter> __parent = `0`, __child = `1`;
2274	for (; __child < __n; ++__child)
2275	if (std::__invoke(__comp,
2276	std::__invoke(__proj, *(__first + __parent)),
2277	std::__invoke(__proj, *(__first + __child))))
2278	return __first + __child;
2279	else if ((__child & `1`) == `0`)
2280	++__parent;
2281
2282	return __first + __n;
2283	}
2284
2285	template<random_access_range _Range,
2286	typename _Proj = identity,
2287	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2288	_Comp = ranges::less>
2289	constexpr borrowed_iterator_t<_Range>
2290	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2291	{
2292	return (*this)(ranges::begin(__r), ranges::end(__r),
2293	std::move(__comp), std::move(__proj));
2294	}
2295	};
2296
2297	inline constexpr __is_heap_until_fn is_heap_until{};
2298
2299	struct __is_heap_fn
2300	{
2301	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2302	typename _Proj = identity,
2303	indirect_strict_weak_order<projected<_Iter, _Proj>>
2304	_Comp = ranges::less>
2305	constexpr bool
2306	operator()(_Iter __first, _Sent __last,
2307	_Comp __comp = {}, _Proj __proj = {}) const
2308	{
2309	return (__last
2310	== ranges::is_heap_until(__first, __last,
2311	std::move(__comp),
2312	std::move(__proj)));
2313	}
2314
2315	template<random_access_range _Range,
2316	typename _Proj = identity,
2317	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2318	_Comp = ranges::less>
2319	constexpr bool
2320	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2321	{
2322	return (*this)(ranges::begin(__r), ranges::end(__r),
2323	std::move(__comp), std::move(__proj));
2324	}
2325	};
2326
2327	inline constexpr __is_heap_fn is_heap{};
2328
2329	namespace __detail
2330	{
2331	template<typename _Iter, typename _Comp>
2332	constexpr void
2333	__move_median_to_first(_Iter __result, _Iter __a, _Iter __b, _Iter __c,
2334	_Comp __comp)
2335	{
2336	if (__comp(__a, __b))
2337	{
2338	if (__comp(__b, __c))
2339	ranges::iter_swap(__result, __b);
2340	else if (__comp(__a, __c))
2341	ranges::iter_swap(__result, __c);
2342	else
2343	ranges::iter_swap(__result, __a);
2344	}
2345	else if (__comp(__a, __c))
2346	ranges::iter_swap(__result, __a);
2347	else if (__comp(__b, __c))
2348	ranges::iter_swap(__result, __c);
2349	else
2350	ranges::iter_swap(__result, __b);
2351	}
2352
2353	template<typename _Iter, typename _Comp>
2354	constexpr void
2355	__unguarded_linear_insert(_Iter __last, _Comp __comp)
2356	{
2357	iter_value_t<_Iter> __val = ranges::iter_move(__last);
2358	_Iter __next = __last;
2359	--__next;
2360	while (__comp(__val, *__next))
2361	{
2362	*__last = ranges::iter_move(__next);
2363	__last = __next;
2364	--__next;
2365	}
2366	*__last = std::move(__val);
2367	}
2368
2369	template<typename _Iter, typename _Comp>
2370	constexpr void
2371	__insertion_sort(_Iter __first, _Iter __last, _Comp __comp)
2372	{
2373	if (__first == __last)
2374	return;
2375
2376	for (_Iter __i = ranges::next(__first); __i != __last; ++__i)
2377	{
2378	if (__comp(__i, __first))
2379	{
2380	iter_value_t<_Iter> __val = ranges::iter_move(__i);
2381	ranges::move_backward(__first, __i, ranges::next(__i));
2382	*__first = std::move(__val);
2383	}
2384	else
2385	__detail::__unguarded_linear_insert(__i, __comp);
2386	}
2387	}
2388
2389	template<typename _Iter, typename _Comp>
2390	constexpr void
2391	__unguarded_insertion_sort(_Iter __first, _Iter __last, _Comp __comp)
2392	{
2393	for (_Iter __i = __first; __i != __last; ++__i)
2394	__detail::__unguarded_linear_insert(__i, __comp);
2395	}
2396
2397	inline constexpr int __sort_threshold = `16`;
2398
2399	template<typename _Iter, typename _Comp>
2400	constexpr void
2401	__final_insertion_sort(_Iter __first, _Iter __last, _Comp __comp)
2402	{
2403	constexpr iter_difference_t<_Iter> __threshold = __sort_threshold;
2404	if (__last - __first > __threshold)
2405	{
2406	__detail::__insertion_sort(__first, __first + __threshold, __comp);
2407	__detail::__unguarded_insertion_sort(__first + __threshold, __last,
2408	__comp);
2409	}
2410	else
2411	__detail::__insertion_sort(__first, __last, __comp);
2412	}
2413
2414	template<typename _Iter, typename _Comp>
2415	constexpr _Iter
2416	__unguarded_partition(_Iter __first, _Iter __last, _Iter __pivot, _Comp __comp)
2417	{
2418	while (true)
2419	{
2420	while (__comp(__first, __pivot))
2421	++__first;
2422	--__last;
2423	while (__comp(__pivot, __last))
2424	--__last;
2425	if (!(__first < __last))
2426	return __first;
2427	ranges::iter_swap(__first, __last);
2428	++__first;
2429	}
2430	}
2431
2432	template<typename _Iter, typename _Comp>
2433	constexpr _Iter
2434	__unguarded_partition_pivot(_Iter __first, _Iter __last, _Comp __comp)
2435	{
2436	_Iter __mid = __first + (__last - __first) / `2`;
2437	__detail::__move_median_to_first(__first, ranges::next(__first), __mid,
2438	ranges::prev(__last), __comp);
2439	return __detail::__unguarded_partition(ranges::next(__first), __last,
2440	__first, __comp);
2441	}
2442
2443	template<typename _Iter, typename _Comp>
2444	constexpr void
2445	__heap_select(_Iter __first, _Iter __middle, _Iter __last, _Comp __comp)
2446	{
2447	ranges::make_heap(__first, __middle, __comp);
2448	for (_Iter __i = __middle; __i < __last; ++__i)
2449	if (__comp(__i, __first))
2450	__detail::__pop_heap(__first, __middle, __i, __comp);
2451	}
2452
2453	template<typename _Iter, typename _Comp>
2454	constexpr void
2455	__partial_sort(_Iter __first, _Iter __middle, _Iter __last, _Comp __comp)
2456	{
2457	__detail::__heap_select(__first, __middle, __last, __comp);
2458	ranges::sort_heap(__first, __middle, __comp);
2459	}
2460
2461	template<typename _Iter, typename _Comp>
2462	constexpr void
2463	__introsort_loop(_Iter __first, _Iter __last, unsigned __depth_limit, _Comp __comp)
2464	{
2465	while (__last - __first > __sort_threshold)
2466	{
2467	if (__depth_limit == `0`)
2468	{
2469	__detail::__partial_sort(__first, __last, __last, __comp);
2470	return;
2471	}
2472	--__depth_limit;
2473	_Iter __cut = __detail::__unguarded_partition_pivot(__first, __last, __comp);
2474	__detail::__introsort_loop(__cut, __last, __depth_limit, __comp);
2475	__last = __cut;
2476	}
2477	}
2478	} // namespace __detail
2479
2480	struct __sort_fn
2481	{
2482	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2483	typename _Comp = ranges::less, typename _Proj = identity>
2484	requires sortable<_Iter, _Comp, _Proj>
2485	constexpr _Iter
2486	operator()(_Iter __first, _Sent __last,
2487	_Comp __comp = {}, _Proj __proj = {}) const
2488	{
2489	if constexpr (!same_as<_Iter, _Sent>)
2490	return (*this)(__first, ranges::next(__first, __last),
2491	std::move(__comp), std::move(__proj));
2492	else
2493	{
2494	if (__first != __last)
2495	{
2496	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
2497	auto __n = __detail::__to_unsigned_like(__last - __first);
2498	unsigned __depth_limit = (std::__bit_width(__n) - `1`) * `2`;
2499	__detail::__introsort_loop(__first, __last, __depth_limit, __comp_proj);
2500	__detail::__final_insertion_sort(__first, __last, __comp_proj);
2501	}
2502	return __last;
2503	}
2504	}
2505
2506	template<random_access_range _Range,
2507	typename _Comp = ranges::less, typename _Proj = identity>
2508	requires sortable<iterator_t<_Range>, _Comp, _Proj>
2509	constexpr borrowed_iterator_t<_Range>
2510	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2511	{
2512	return (*this)(ranges::begin(__r), ranges::end(__r),
2513	std::move(__comp), std::move(__proj));
2514	}
2515	};
2516
2517	inline constexpr __sort_fn sort{};
2518
2519	namespace __detail
2520	{
2521	// This is a helper function for the __merge_sort_loop routines.
2522	template<typename _Iter, typename _Out, typename _Comp>
2523	_Out
2524	__move_merge(_Iter __first1, _Iter __last1,
2525	_Iter __first2, _Iter __last2,
2526	_Out __result, _Comp __comp)
2527	{
2528	while (__first1 != __last1 && __first2 != __last2)
2529	{
2530	if (__comp(__first2, __first1))
2531	{
2532	*__result = ranges::iter_move(__first2);
2533	++__first2;
2534	}
2535	else
2536	{
2537	*__result = ranges::iter_move(__first1);
2538	++__first1;
2539	}
2540	++__result;
2541	}
2542	return ranges::move(__first2, __last2,
2543	ranges::move(__first1, __last1, __result).out).out;
2544	}
2545
2546	template<typename _Iter, typename _Out, typename _Distance, typename _Comp>
2547	void
2548	__merge_sort_loop(_Iter __first, _Iter __last, _Out __result,
2549	_Distance __step_size, _Comp __comp)
2550	{
2551	const _Distance __two_step = `2` * __step_size;
2552
2553	while (__last - __first >= __two_step)
2554	{
2555	__result = __detail::__move_merge(__first, __first + __step_size,
2556	__first + __step_size,
2557	__first + __two_step,
2558	__result, __comp);
2559	__first += __two_step;
2560	}
2561	__step_size = ranges::min(_Distance(__last - __first), __step_size);
2562
2563	__detail::__move_merge(__first, __first + __step_size,
2564	__first + __step_size, __last, __result, __comp);
2565	}
2566
2567	template<typename _Iter, typename _Distance, typename _Compare>
2568	constexpr void
2569	__chunk_insertion_sort(_Iter __first, _Iter __last,
2570	_Distance __chunk_size, _Compare __comp)
2571	{
2572	while (__last - __first >= __chunk_size)
2573	{
2574	__detail::__insertion_sort(__first, __first + __chunk_size, __comp);
2575	__first += __chunk_size;
2576	}
2577	__detail::__insertion_sort(__first, __last, __comp);
2578	}
2579
2580	template<typename _Iter, typename _Pointer, typename _Comp>
2581	void
2582	__merge_sort_with_buffer(_Iter __first, _Iter __last,
2583	_Pointer __buffer, _Comp __comp)
2584	{
2585	using _Distance = iter_difference_t<_Iter>;
2586
2587	const _Distance __len = __last - __first;
2588	const _Pointer __buffer_last = __buffer + ptrdiff_t(__len);
2589
2590	constexpr int __chunk_size = `7`;
2591	_Distance __step_size = __chunk_size;
2592	__detail::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2593
2594	while (__step_size < __len)
2595	{
2596	__detail::__merge_sort_loop(__first, __last, __buffer,
2597	__step_size, __comp);
2598	__step_size *= `2`;
2599	__detail::__merge_sort_loop(__buffer, __buffer_last, __first,
2600	ptrdiff_t(__step_size), __comp);
2601	__step_size *= `2`;
2602	}
2603	}
2604
2605	template<typename _Iter, typename _Pointer, typename _Comp>
2606	void
2607	__merge_adaptive(_Iter __first, _Iter __middle, _Iter __last,
2608	iter_difference_t<_Iter> __len1,
2609	iter_difference_t<_Iter> __len2,
2610	_Pointer __buffer, _Comp __comp); // defined near inplace_merge
2611
2612	template<typename _Iter, typename _Distance, typename _Pointer, typename _Comp>
2613	void
2614	__merge_adaptive_resize(_Iter __first, _Iter __middle, _Iter __last,
2615	_Distance __len1, _Distance __len2,
2616	_Pointer __buffer, _Distance __buffer_size,
2617	_Comp __comp); // defined near inplace_merge
2618
2619	template<typename _Iter, typename _Distance, typename _Comp>
2620	constexpr void
2621	__merge_without_buffer(_Iter __first, _Iter __middle, _Iter __last,
2622	_Distance __len1, _Distance __len2,
2623	_Comp __comp); // defined near inplace_merge
2624
2625	template<typename _Iter, typename _Pointer, typename _Comp>
2626	void
2627	__stable_sort_adaptive(_Iter __first, _Iter __middle, _Iter __last,
2628	_Pointer __buffer, _Comp __comp)
2629	{
2630	__detail::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2631	__detail::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2632
2633	__detail::__merge_adaptive(__first, __middle, __last,
2634	__middle - __first, __last - __middle,
2635	__buffer, __comp);
2636	}
2637
2638	template<typename _Iter, typename _Pointer, typename _Distance, typename _Comp>
2639	void
2640	__stable_sort_adaptive_resize(_Iter __first, _Iter __last,
2641	_Pointer __buffer, _Distance __buffer_size,
2642	_Comp __comp)
2643	{
2644	const _Distance __len = (__last - __first + `1`) / `2`;
2645	const _Iter __middle = __first + __len;
2646	if (__len > __buffer_size)
2647	{
2648	__detail::__stable_sort_adaptive_resize(__first, __middle, __buffer,
2649	__buffer_size, __comp);
2650	__detail::__stable_sort_adaptive_resize(__middle, __last, __buffer,
2651	__buffer_size, __comp);
2652	__detail::__merge_adaptive_resize(__first, __middle, __last,
2653	_Distance(__middle - __first),
2654	_Distance(__last - __middle),
2655	__buffer, __buffer_size,
2656	__comp);
2657	}
2658	else
2659	__detail::__stable_sort_adaptive(__first, __middle, __last,
2660	__buffer, __comp);
2661	}
2662
2663	template<typename _Iter, typename _Comp>
2664	constexpr void
2665	__inplace_stable_sort(_Iter __first, _Iter __last, _Comp __comp)
2666	{
2667	if (__last - __first < `15`)
2668	{
2669	__detail::__insertion_sort(__first, __last, __comp);
2670	return;
2671	}
2672	_Iter __middle = __first + (__last - __first) / `2`;
2673	__detail::__inplace_stable_sort(__first, __middle, __comp);
2674	__detail::__inplace_stable_sort(__middle, __last, __comp);
2675	__detail::__merge_without_buffer(__first, __middle, __last,
2676	__middle - __first,
2677	__last - __middle,
2678	__comp);
2679	}
2680	} // namespace __detail
2681
2682	struct __stable_sort_fn
2683	{
2684	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2685	typename _Comp = ranges::less, typename _Proj = identity>
2686	requires sortable<_Iter, _Comp, _Proj>
2687	_GLIBCXX26_CONSTEXPR
2688	_Iter
2689	operator()(_Iter __first, _Sent __last,
2690	_Comp __comp = {}, _Proj __proj = {}) const
2691	{
2692	if constexpr (!same_as<_Iter, _Sent>)
2693	return (*this)(__first, ranges::next(__first, __last),
2694	std::move(__comp), std::move(__proj));
2695	else
2696	{
2697	using _DistanceType = iter_difference_t<_Iter>;
2698
2699	if (__first == __last)
2700	return __last;
2701
2702	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
2703
2704	#if _GLIBCXX_HOSTED
2705	# if __glibcxx_constexpr_algorithms >= 202306L // >= C++26
2706	if consteval {
2707	__detail::__inplace_stable_sort(__first, __last, __comp_proj);
2708	return __last;
2709	}
2710	# endif
2711
2712	using _TmpBuf = _Temporary_buffer<_Iter, iter_value_t<_Iter>>;
2713	// __stable_sort_adaptive sorts the range in two halves,
2714	// so the buffer only needs to fit half the range at once.
2715	_TmpBuf __buf(__first, ptrdiff_t((__last - __first + `1`) / `2`));
2716
2717	if (__buf._M_requested_size() == __buf.size()) [[likely]]
2718	__detail::__stable_sort_adaptive(__first,
2719	__first + _DistanceType(__buf.size()),
2720	__last, __buf.begin(), __comp_proj);
2721	else if (__buf.begin() == nullptr) [[unlikely]]
2722	__detail::__inplace_stable_sort(__first, __last, __comp_proj);
2723	else
2724	__detail::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
2725	_DistanceType(__buf.size()),
2726	__comp_proj);
2727	#else
2728	__detail::__inplace_stable_sort(__first, __last, __comp_proj);
2729	#endif
2730	return __last;
2731	}
2732	}
2733
2734	template<random_access_range _Range,
2735	typename _Comp = ranges::less, typename _Proj = identity>
2736	requires sortable<iterator_t<_Range>, _Comp, _Proj>
2737	_GLIBCXX26_CONSTEXPR
2738	borrowed_iterator_t<_Range>
2739	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2740	{
2741	return (*this)(ranges::begin(__r), ranges::end(__r),
2742	std::move(__comp), std::move(__proj));
2743	}
2744	};
2745
2746	inline constexpr __stable_sort_fn stable_sort{};
2747
2748	struct __partial_sort_fn
2749	{
2750	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2751	typename _Comp = ranges::less, typename _Proj = identity>
2752	requires sortable<_Iter, _Comp, _Proj>
2753	constexpr _Iter
2754	operator()(_Iter __first, _Iter __middle, _Sent __last,
2755	_Comp __comp = {}, _Proj __proj = {}) const
2756	{
2757	if (__first == __middle)
2758	return ranges::next(__first, __last);
2759
2760	ranges::make_heap(__first, __middle, __comp, __proj);
2761	auto __i = __middle;
2762	for (; __i != __last; ++__i)
2763	if (std::__invoke(__comp,
2764	std::__invoke(__proj, *__i),
2765	std::__invoke(__proj, *__first)))
2766	{
2767	ranges::pop_heap(__first, __middle, __comp, __proj);
2768	ranges::iter_swap(std::prev(__middle), __i);
2769	ranges::push_heap(__first, __middle, __comp, __proj);
2770	}
2771	ranges::sort_heap(__first, __middle, __comp, __proj);
2772
2773	return __i;
2774	}
2775
2776	template<random_access_range _Range,
2777	typename _Comp = ranges::less, typename _Proj = identity>
2778	requires sortable<iterator_t<_Range>, _Comp, _Proj>
2779	constexpr borrowed_iterator_t<_Range>
2780	operator()(_Range&& __r, iterator_t<_Range> __middle,
2781	_Comp __comp = {}, _Proj __proj = {}) const
2782	{
2783	return (*this)(ranges::begin(__r), std::move(__middle),
2784	ranges::end(__r),
2785	std::move(__comp), std::move(__proj));
2786	}
2787	};
2788
2789	inline constexpr __partial_sort_fn partial_sort{};
2790
2791	template<typename _Iter, typename _Out>
2792	using partial_sort_copy_result = in_out_result<_Iter, _Out>;
2793
2794	struct __partial_sort_copy_fn
2795	{
2796	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2797	random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2798	typename _Comp = ranges::less,
2799	typename _Proj1 = identity, typename _Proj2 = identity>
2800	requires indirectly_copyable<_Iter1, _Iter2>
2801	&& sortable<_Iter2, _Comp, _Proj2>
2802	&& indirect_strict_weak_order<_Comp,
2803	projected<_Iter1, _Proj1>,
2804	projected<_Iter2, _Proj2>>
2805	constexpr partial_sort_copy_result<_Iter1, _Iter2>
2806	operator()(_Iter1 __first, _Sent1 __last,
2807	_Iter2 __result_first, _Sent2 __result_last,
2808	_Comp __comp = {},
2809	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2810	{
2811	if (__result_first == __result_last)
2812	{
2813	// TODO: Eliminating the variable __lasti triggers an ICE.
2814	auto __lasti = ranges::next(std::move(__first),
2815	std::move(__last));
2816	return {std::move(__lasti), std::move(__result_first)};
2817	}
2818
2819	auto __result_real_last = __result_first;
2820	while (__first != __last && __result_real_last != __result_last)
2821	{
2822	__result_real_last = __first;
2823	++__result_real_last;
2824	++__first;
2825	}
2826
2827	ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
2828	for (; __first != __last; ++__first)
2829	if (std::__invoke(__comp,
2830	std::__invoke(__proj1, *__first),
2831	std::__invoke(__proj2, *__result_first)))
2832	{
2833	ranges::pop_heap(__result_first, __result_real_last,
2834	__comp, __proj2);
2835	ranges::prev(__result_real_last) = __first;
2836	ranges::push_heap(__result_first, __result_real_last,
2837	__comp, __proj2);
2838	}
2839	ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
2840
2841	return {std::move(__first), std::move(__result_real_last)};
2842	}
2843
2844	template<input_range _Range1, random_access_range _Range2,
2845	typename _Comp = ranges::less,
2846	typename _Proj1 = identity, typename _Proj2 = identity>
2847	requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
2848	&& sortable<iterator_t<_Range2>, _Comp, _Proj2>
2849	&& indirect_strict_weak_order<_Comp,
2850	projected<iterator_t<_Range1>, _Proj1>,
2851	projected<iterator_t<_Range2>, _Proj2>>
2852	constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>,
2853	borrowed_iterator_t<_Range2>>
2854	operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
2855	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2856	{
2857	return (*this)(ranges::begin(__r), ranges::end(__r),
2858	ranges::begin(__out), ranges::end(__out),
2859	std::move(__comp),
2860	std::move(__proj1), std::move(__proj2));
2861	}
2862	};
2863
2864	inline constexpr __partial_sort_copy_fn partial_sort_copy{};
2865
2866	struct __is_sorted_until_fn
2867	{
2868	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2869	typename _Proj = identity,
2870	indirect_strict_weak_order<projected<_Iter, _Proj>>
2871	_Comp = ranges::less>
2872	[[nodiscard]] constexpr _Iter
2873	operator()(_Iter __first, _Sent __last,
2874	_Comp __comp = {}, _Proj __proj = {}) const
2875	{
2876	if (__first == __last)
2877	return __first;
2878
2879	auto __next = __first;
2880	for (++__next; __next != __last; __first = __next, (void)++__next)
2881	if (std::__invoke(__comp,
2882	std::__invoke(__proj, *__next),
2883	std::__invoke(__proj, *__first)))
2884	return __next;
2885	return __next;
2886	}
2887
2888	template<forward_range _Range, typename _Proj = identity,
2889	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2890	_Comp = ranges::less>
2891	[[nodiscard]] constexpr borrowed_iterator_t<_Range>
2892	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2893	{
2894	return (*this)(ranges::begin(__r), ranges::end(__r),
2895	std::move(__comp), std::move(__proj));
2896	}
2897	};
2898
2899	inline constexpr __is_sorted_until_fn is_sorted_until{};
2900
2901	struct __is_sorted_fn
2902	{
2903	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2904	typename _Proj = identity,
2905	indirect_strict_weak_order<projected<_Iter, _Proj>>
2906	_Comp = ranges::less>
2907	[[nodiscard]] constexpr bool
2908	operator()(_Iter __first, _Sent __last,
2909	_Comp __comp = {}, _Proj __proj = {}) const
2910	{
2911	if (__first == __last)
2912	return true;
2913
2914	auto __next = __first;
2915	for (++__next; __next != __last; __first = __next, (void)++__next)
2916	if (std::__invoke(__comp,
2917	std::__invoke(__proj, *__next),
2918	std::__invoke(__proj, *__first)))
2919	return false;
2920	return true;
2921	}
2922
2923	template<forward_range _Range, typename _Proj = identity,
2924	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2925	_Comp = ranges::less>
2926	[[nodiscard]] constexpr bool
2927	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2928	{
2929	return (*this)(ranges::begin(__r), ranges::end(__r),
2930	std::move(__comp), std::move(__proj));
2931	}
2932	};
2933
2934	inline constexpr __is_sorted_fn is_sorted{};
2935
2936	namespace __detail
2937	{
2938	template<typename _Iter, typename _Comp>
2939	constexpr void
2940	__introselect(_Iter __first, _Iter __nth, _Iter __last,
2941	iter_difference_t<_Iter> __depth_limit, _Comp __comp)
2942	{
2943	while (__last - __first > `3`)
2944	{
2945	if (__depth_limit == `0`)
2946	{
2947	__detail::__heap_select(__first, ranges::next(__nth), __last,
2948	__comp);
2949	// Place the nth largest element in its final position.
2950	ranges::iter_swap(__first, __nth);
2951	return;
2952	}
2953	--__depth_limit;
2954	_Iter __cut = __detail::__unguarded_partition_pivot(__first, __last, __comp);
2955	if (__cut <= __nth)
2956	__first = __cut;
2957	else
2958	__last = __cut;
2959	}
2960	__detail::__insertion_sort(__first, __last, __comp);
2961	}
2962	} // namespace __detail
2963
2964	struct __nth_element_fn
2965	{
2966	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2967	typename _Comp = ranges::less, typename _Proj = identity>
2968	requires sortable<_Iter, _Comp, _Proj>
2969	constexpr _Iter
2970	operator()(_Iter __first, _Iter __nth, _Sent __last,
2971	_Comp __comp = {}, _Proj __proj = {}) const
2972	{
2973	if constexpr (!same_as<_Iter, _Sent>)
2974	return (*this)(__first, __nth, ranges::next(__first, __last),
2975	std::move(__comp), std::move(__proj));
2976	else
2977	{
2978	if (__first == __last \|\| __nth == __last)
2979	return __last;
2980
2981	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
2982	auto __n = __detail::__to_unsigned_like(__last - __first);
2983	__detail::__introselect(__first, __nth, __last,
2984	std::__bit_width(__n) * `2`,
2985	__comp_proj);
2986	return __last;
2987	}
2988	}
2989
2990	template<random_access_range _Range,
2991	typename _Comp = ranges::less, typename _Proj = identity>
2992	requires sortable<iterator_t<_Range>, _Comp, _Proj>
2993	constexpr borrowed_iterator_t<_Range>
2994	operator()(_Range&& __r, iterator_t<_Range> __nth,
2995	_Comp __comp = {}, _Proj __proj = {}) const
2996	{
2997	return (*this)(ranges::begin(__r), std::move(__nth),
2998	ranges::end(__r), std::move(__comp), std::move(__proj));
2999	}
3000	};
3001
3002	inline constexpr __nth_element_fn nth_element{};
3003
3004	struct __lower_bound_fn
3005	{
3006	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3007	typename _Proj = identity,
3008	typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
3009	indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
3010	_Comp = ranges::less>
3011	[[nodiscard]] constexpr _Iter
3012	operator()(_Iter __first, _Sent __last,
3013	const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
3014	{
3015	auto __len = ranges::distance(__first, __last);
3016
3017	while (__len > `0`)
3018	{
3019	auto __half = __len / `2`;
3020	auto __middle = __first;
3021	ranges::advance(__middle, __half);
3022	if (std::__invoke(__comp, std::__invoke(__proj, *__middle), __value))
3023	{
3024	__first = __middle;
3025	++__first;
3026	__len = __len - __half - `1`;
3027	}
3028	else
3029	__len = __half;
3030	}
3031	return __first;
3032	}
3033
3034	template<forward_range _Range,
3035	typename _Proj = identity,
3036	typename _Tp
3037	_GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj),
3038	indirect_strict_weak_order<const _Tp*,
3039	projected<iterator_t<_Range>, _Proj>>
3040	_Comp = ranges::less>
3041	[[nodiscard]] constexpr borrowed_iterator_t<_Range>
3042	operator()(_Range&& __r,
3043	const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
3044	{
3045	return (*this)(ranges::begin(__r), ranges::end(__r),
3046	__value, std::move(__comp), std::move(__proj));
3047	}
3048	};
3049
3050	inline constexpr __lower_bound_fn lower_bound{};
3051
3052	struct __upper_bound_fn
3053	{
3054	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3055	typename _Proj = identity,
3056	typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
3057	indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
3058	_Comp = ranges::less>
3059	[[nodiscard]] constexpr _Iter
3060	operator()(_Iter __first, _Sent __last,
3061	const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
3062	{
3063	auto __len = ranges::distance(__first, __last);
3064
3065	while (__len > `0`)
3066	{
3067	auto __half = __len / `2`;
3068	auto __middle = __first;
3069	ranges::advance(__middle, __half);
3070	if (std::__invoke(__comp, __value, std::__invoke(__proj, *__middle)))
3071	__len = __half;
3072	else
3073	{
3074	__first = __middle;
3075	++__first;
3076	__len = __len - __half - `1`;
3077	}
3078	}
3079	return __first;
3080	}
3081
3082	template<forward_range _Range,
3083	typename _Proj = identity,
3084	typename _Tp
3085	_GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj),
3086	indirect_strict_weak_order<const _Tp*,
3087	projected<iterator_t<_Range>, _Proj>>
3088	_Comp = ranges::less>
3089	[[nodiscard]] constexpr borrowed_iterator_t<_Range>
3090	operator()(_Range&& __r,
3091	const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
3092	{
3093	return (*this)(ranges::begin(__r), ranges::end(__r),
3094	__value, std::move(__comp), std::move(__proj));
3095	}
3096	};
3097
3098	inline constexpr __upper_bound_fn upper_bound{};
3099
3100	struct __equal_range_fn
3101	{
3102	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3103	typename _Proj = identity,
3104	typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
3105	indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
3106	_Comp = ranges::less>
3107	[[nodiscard]] constexpr subrange<_Iter>
3108	operator()(_Iter __first, _Sent __last,
3109	const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
3110	{
3111	auto __len = ranges::distance(__first, __last);
3112
3113	while (__len > `0`)
3114	{
3115	auto __half = __len / `2`;
3116	auto __middle = __first;
3117	ranges::advance(__middle, __half);
3118	if (std::__invoke(__comp,
3119	std::__invoke(__proj, *__middle),
3120	__value))
3121	{
3122	__first = __middle;
3123	++__first;
3124	__len = __len - __half - `1`;
3125	}
3126	else if (std::__invoke(__comp,
3127	__value,
3128	std::__invoke(__proj, *__middle)))
3129	__len = __half;
3130	else
3131	{
3132	auto __left
3133	= ranges::lower_bound(__first, __middle,
3134	__value, __comp, __proj);
3135	ranges::advance(__first, __len);
3136	auto __right
3137	= ranges::upper_bound(++__middle, __first,
3138	__value, __comp, __proj);
3139	return {__left, __right};
3140	}
3141	}
3142	return {__first, __first};
3143	}
3144
3145	template<forward_range _Range,
3146	typename _Proj = identity,
3147	typename _Tp
3148	_GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj),
3149	indirect_strict_weak_order<const _Tp*,
3150	projected<iterator_t<_Range>, _Proj>>
3151	_Comp = ranges::less>
3152	[[nodiscard]] constexpr borrowed_subrange_t<_Range>
3153	operator()(_Range&& __r, const _Tp& __value,
3154	_Comp __comp = {}, _Proj __proj = {}) const
3155	{
3156	return (*this)(ranges::begin(__r), ranges::end(__r),
3157	__value, std::move(__comp), std::move(__proj));
3158	}
3159	};
3160
3161	inline constexpr __equal_range_fn equal_range{};
3162
3163	struct __binary_search_fn
3164	{
3165	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3166	typename _Proj = identity,
3167	typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
3168	indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
3169	_Comp = ranges::less>
3170	[[nodiscard]] constexpr bool
3171	operator()(_Iter __first, _Sent __last,
3172	const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
3173	{
3174	auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
3175	if (__i == __last)
3176	return false;
3177	return !(bool)std::__invoke(__comp, __value,
3178	std::__invoke(__proj, *__i));
3179	}
3180
3181	template<forward_range _Range,
3182	typename _Proj = identity,
3183	typename _Tp
3184	_GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj),
3185	indirect_strict_weak_order<const _Tp*,
3186	projected<iterator_t<_Range>, _Proj>>
3187	_Comp = ranges::less>
3188	[[nodiscard]] constexpr bool
3189	operator()(_Range&& __r, const _Tp& __value, _Comp __comp = {},
3190	_Proj __proj = {}) const
3191	{
3192	return (*this)(ranges::begin(__r), ranges::end(__r),
3193	__value, std::move(__comp), std::move(__proj));
3194	}
3195	};
3196
3197	inline constexpr __binary_search_fn binary_search{};
3198
3199	struct __is_partitioned_fn
3200	{
3201	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3202	typename _Proj = identity,
3203	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3204	[[nodiscard]] constexpr bool
3205	operator()(_Iter __first, _Sent __last,
3206	_Pred __pred, _Proj __proj = {}) const
3207	{
3208	__first = ranges::find_if_not(std::move(__first), __last,
3209	__pred, __proj);
3210	if (__first == __last)
3211	return true;
3212	++__first;
3213	return ranges::none_of(std::move(__first), std::move(__last),
3214	std::move(__pred), std::move(__proj));
3215	}
3216
3217	template<input_range _Range, typename _Proj = identity,
3218	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
3219	_Pred>
3220	[[nodiscard]] constexpr bool
3221	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
3222	{
3223	return (*this)(ranges::begin(__r), ranges::end(__r),
3224	std::move(__pred), std::move(__proj));
3225	}
3226	};
3227
3228	inline constexpr __is_partitioned_fn is_partitioned{};
3229
3230	struct __partition_fn
3231	{
3232	template<permutable _Iter, sentinel_for<_Iter> _Sent,
3233	typename _Proj = identity,
3234	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3235	constexpr subrange<_Iter>
3236	operator()(_Iter __first, _Sent __last,
3237	_Pred __pred, _Proj __proj = {}) const
3238	{
3239	if constexpr (bidirectional_iterator<_Iter>)
3240	{
3241	auto __lasti = ranges::next(__first, __last);
3242	auto __tail = __lasti;
3243	for (;;)
3244	{
3245	for (;;)
3246	if (__first == __tail)
3247	return {std::move(__first), std::move(__lasti)};
3248	else if (std::__invoke(__pred,
3249	std::__invoke(__proj, *__first)))
3250	++__first;
3251	else
3252	break;
3253	--__tail;
3254	for (;;)
3255	if (__first == __tail)
3256	return {std::move(__first), std::move(__lasti)};
3257	else if (!(bool)std::__invoke(__pred,
3258	std::__invoke(__proj, *__tail)))
3259	--__tail;
3260	else
3261	break;
3262	ranges::iter_swap(__first, __tail);
3263	++__first;
3264	}
3265	}
3266	else
3267	{
3268	if (__first == __last)
3269	return {__first, __first};
3270
3271	while (std::__invoke(__pred, std::__invoke(__proj, *__first)))
3272	if (++__first == __last)
3273	return {__first, __first};
3274
3275	auto __next = __first;
3276	while (++__next != __last)
3277	if (std::__invoke(__pred, std::__invoke(__proj, *__next)))
3278	{
3279	ranges::iter_swap(__first, __next);
3280	++__first;
3281	}
3282
3283	return {std::move(__first), std::move(__next)};
3284	}
3285	}
3286
3287	template<forward_range _Range, typename _Proj = identity,
3288	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
3289	_Pred>
3290	requires permutable<iterator_t<_Range>>
3291	constexpr borrowed_subrange_t<_Range>
3292	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
3293	{
3294	return (*this)(ranges::begin(__r), ranges::end(__r),
3295	std::move(__pred), std::move(__proj));
3296	}
3297	};
3298
3299	inline constexpr __partition_fn partition{};
3300
3301	#if _GLIBCXX_HOSTED
3302	namespace __detail
3303	{
3304	// Like find_if_not(), but uses and updates a count of the
3305	// remaining range length instead of comparing against an end
3306	// iterator.
3307	template<typename _Iter, typename _Pred, typename _Distance>
3308	constexpr _Iter
3309	__find_if_not_n(_Iter __first, _Distance& __len, _Pred __pred)
3310	{
3311	for (; __len; --__len, (void) ++__first)
3312	if (!__pred(*__first))
3313	break;
3314	return __first;
3315	}
3316
3317	template<typename _Iter, typename _Sent, typename _Pointer,
3318	typename _Pred, typename _Distance>
3319	constexpr subrange<_Iter>
3320	__stable_partition_adaptive(_Iter __first, _Sent __last,
3321	_Pred __pred, _Distance __len,
3322	_Pointer __buffer,
3323	_Distance __buffer_size)
3324	{
3325	if (__len == `1`)
3326	return {__first, ranges::next(__first, `1`)};
3327
3328	if (__len <= __buffer_size)
3329	{
3330	_Iter __result1 = __first;
3331	_Pointer __result2 = __buffer;
3332
3333	// The precondition guarantees that !__pred(__first), so
3334	// move that element to the buffer before starting the loop.
3335	// This ensures that we only call __pred once per element.
3336	*__result2 = ranges::iter_move(__first);
3337	++__result2;
3338	++__first;
3339	for (; __first != __last; ++__first)
3340	if (__pred(*__first))
3341	{
3342	*__result1 = ranges::iter_move(__first);
3343	++__result1;
3344	}
3345	else
3346	{
3347	*__result2 = ranges::iter_move(__first);
3348	++__result2;
3349	}
3350
3351	ranges::move(__buffer, __result2, __result1);
3352	return {__result1, __first};
3353	}
3354
3355	_Iter __middle = __first;
3356	ranges::advance(__middle, __len / `2`);
3357	_Iter __left_split
3358	= __detail::__stable_partition_adaptive(__first, __middle, __pred,
3359	__len / `2`, __buffer,
3360	__buffer_size).begin();
3361
3362	// Advance past true-predicate values to satisfy this
3363	// function's preconditions.
3364	_Distance __right_len = __len - __len / `2`;
3365	_Iter __right_split = __detail::__find_if_not_n(__middle, __right_len, __pred);
3366
3367	if (__right_len)
3368	__right_split
3369	= __detail::__stable_partition_adaptive(__right_split, __last, __pred,
3370	__right_len, __buffer, __buffer_size).begin();
3371
3372	return ranges::rotate(__left_split, __middle, __right_split);
3373	}
3374	} // namespace __detail
3375
3376	struct __stable_partition_fn
3377	{
3378	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3379	typename _Proj = identity,
3380	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3381	requires permutable<_Iter>
3382	_GLIBCXX26_CONSTEXPR
3383	subrange<_Iter>
3384	operator()(_Iter __first, _Sent __last,
3385	_Pred __pred, _Proj __proj = {}) const
3386	{
3387	__first = ranges::find_if_not(__first, __last, __pred, __proj);
3388
3389	if (__first == __last)
3390	return {__first, __first};
3391
3392	using _DistanceType = iter_difference_t<_Iter>;
3393	const _DistanceType __len = ranges::distance(__first, __last);
3394
3395	auto __pred_proj = __detail::__make_pred_proj(__pred, __proj);
3396
3397	#if __glibcxx_constexpr_algorithms >= 202306L // >= C++26
3398	if consteval {
3399	// Simulate a _Temporary_buffer of length 1:
3400	iter_value_t<_Iter> __buf = ranges::iter_move(__first);
3401	*__first = std::move(__buf);
3402	return __detail::__stable_partition_adaptive(__first, __last,
3403	__pred_proj,
3404	__len, &__buf,
3405	_DistanceType(`1`));
3406	}
3407	#endif
3408
3409	_Temporary_buffer<_Iter, iter_value_t<_Iter>> __buf(__first, ptrdiff_t(__len));
3410	return __detail::__stable_partition_adaptive(__first, __last,
3411	__pred_proj,
3412	__len, __buf.begin(),
3413	_DistanceType(__buf.size()));
3414	}
3415
3416	template<bidirectional_range _Range, typename _Proj = identity,
3417	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
3418	_Pred>
3419	requires permutable<iterator_t<_Range>>
3420	_GLIBCXX26_CONSTEXPR
3421	borrowed_subrange_t<_Range>
3422	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
3423	{
3424	return (*this)(ranges::begin(__r), ranges::end(__r),
3425	std::move(__pred), std::move(__proj));
3426	}
3427	};
3428
3429	inline constexpr __stable_partition_fn stable_partition{};
3430	#endif
3431
3432	template<typename _Iter, typename _Out1, typename _Out2>
3433	struct in_out_out_result
3434	{
3435	[[no_unique_address]] _Iter in;
3436	[[no_unique_address]] _Out1 out1;
3437	[[no_unique_address]] _Out2 out2;
3438
3439	template<typename _IIter, typename _OOut1, typename _OOut2>
3440	requires convertible_to<const _Iter&, _IIter>
3441	&& convertible_to<const _Out1&, _OOut1>
3442	&& convertible_to<const _Out2&, _OOut2>
3443	constexpr
3444	operator in_out_out_result<_IIter, _OOut1, _OOut2>() const &
3445	{ return {in, out1, out2}; }
3446
3447	template<typename _IIter, typename _OOut1, typename _OOut2>
3448	requires convertible_to<_Iter, _IIter>
3449	&& convertible_to<_Out1, _OOut1>
3450	&& convertible_to<_Out2, _OOut2>
3451	constexpr
3452	operator in_out_out_result<_IIter, _OOut1, _OOut2>() &&
3453	{ return {std::move(in), std::move(out1), std::move(out2)}; }
3454	};
3455
3456	template<typename _Iter, typename _Out1, typename _Out2>
3457	using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>;
3458
3459	struct __partition_copy_fn
3460	{
3461	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3462	weakly_incrementable _Out1, weakly_incrementable _Out2,
3463	typename _Proj = identity,
3464	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3465	requires indirectly_copyable<_Iter, _Out1>
3466	&& indirectly_copyable<_Iter, _Out2>
3467	constexpr partition_copy_result<_Iter, _Out1, _Out2>
3468	operator()(_Iter __first, _Sent __last,
3469	_Out1 __out_true, _Out2 __out_false,
3470	_Pred __pred, _Proj __proj = {}) const
3471	{
3472	for (; __first != __last; ++__first)
3473	if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
3474	{
3475	__out_true = __first;
3476	++__out_true;
3477	}
3478	else
3479	{
3480	__out_false = __first;
3481	++__out_false;
3482	}
3483
3484	return {std::move(__first),
3485	std::move(__out_true), std::move(__out_false)};
3486	}
3487
3488	template<input_range _Range, weakly_incrementable _Out1,
3489	weakly_incrementable _Out2,
3490	typename _Proj = identity,
3491	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
3492	_Pred>
3493	requires indirectly_copyable<iterator_t<_Range>, _Out1>
3494	&& indirectly_copyable<iterator_t<_Range>, _Out2>
3495	constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _Out2>
3496	operator()(_Range&& __r, _Out1 __out_true, _Out2 __out_false,
3497	_Pred __pred, _Proj __proj = {}) const
3498	{
3499	return (*this)(ranges::begin(__r), ranges::end(__r),
3500	std::move(__out_true), std::move(__out_false),
3501	std::move(__pred), std::move(__proj));
3502	}
3503	};
3504
3505	inline constexpr __partition_copy_fn partition_copy{};
3506
3507	struct __partition_point_fn
3508	{
3509	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3510	typename _Proj = identity,
3511	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3512	[[nodiscard]] constexpr _Iter
3513	operator()(_Iter __first, _Sent __last,
3514	_Pred __pred, _Proj __proj = {}) const
3515	{
3516	auto __len = ranges::distance(__first, __last);
3517
3518	while (__len > `0`)
3519	{
3520	auto __half = __len / `2`;
3521	auto __middle = __first;
3522	ranges::advance(__middle, __half);
3523	if (std::__invoke(__pred, std::__invoke(__proj, *__middle)))
3524	{
3525	__first = __middle;
3526	++__first;
3527	__len = __len - __half - `1`;
3528	}
3529	else
3530	__len = __half;
3531	}
3532	return __first;
3533	}
3534
3535	template<forward_range _Range, typename _Proj = identity,
3536	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
3537	_Pred>
3538	[[nodiscard]] constexpr borrowed_iterator_t<_Range>
3539	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
3540	{
3541	return (*this)(ranges::begin(__r), ranges::end(__r),
3542	std::move(__pred), std::move(__proj));
3543	}
3544	};
3545
3546	inline constexpr __partition_point_fn partition_point{};
3547
3548	template<typename _Iter1, typename _Iter2, typename _Out>
3549	using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>;
3550
3551	struct __merge_fn
3552	{
3553	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3554	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3555	weakly_incrementable _Out, typename _Comp = ranges::less,
3556	typename _Proj1 = identity, typename _Proj2 = identity>
3557	requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
3558	constexpr merge_result<_Iter1, _Iter2, _Out>
3559	operator()(_Iter1 __first1, _Sent1 __last1,
3560	_Iter2 __first2, _Sent2 __last2, _Out __result,
3561	_Comp __comp = {},
3562	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3563	{
3564	while (__first1 != __last1 && __first2 != __last2)
3565	{
3566	if (std::__invoke(__comp,
3567	std::__invoke(__proj2, *__first2),
3568	std::__invoke(__proj1, *__first1)))
3569	{
3570	__result = __first2;
3571	++__first2;
3572	}
3573	else
3574	{
3575	__result = __first1;
3576	++__first1;
3577	}
3578	++__result;
3579	}
3580	auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
3581	std::move(__result));
3582	auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
3583	std::move(__copy1.out));
3584	return { std::move(__copy1.in), std::move(__copy2.in),
3585	std::move(__copy2.out) };
3586	}
3587
3588	template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
3589	typename _Comp = ranges::less,
3590	typename _Proj1 = identity, typename _Proj2 = identity>
3591	requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
3592	_Comp, _Proj1, _Proj2>
3593	constexpr merge_result<borrowed_iterator_t<_Range1>,
3594	borrowed_iterator_t<_Range2>,
3595	_Out>
3596	operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
3597	_Comp __comp = {},
3598	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3599	{
3600	return (*this)(ranges::begin(__r1), ranges::end(__r1),
3601	ranges::begin(__r2), ranges::end(__r2),
3602	std::move(__result), std::move(__comp),
3603	std::move(__proj1), std::move(__proj2));
3604	}
3605	};
3606
3607	inline constexpr __merge_fn merge{};
3608
3609	namespace __detail
3610	{
3611	template<typename _Iter1, typename _Iter2, typename _Out, typename _Comp>
3612	void
3613	__move_merge_adaptive(_Iter1 __first1, _Iter1 __last1,
3614	_Iter2 __first2, _Iter2 __last2,
3615	_Out __result, _Comp __comp)
3616	{
3617	while (__first1 != __last1 && __first2 != __last2)
3618	{
3619	if (__comp(__first2, __first1))
3620	{
3621	*__result = ranges::iter_move(__first2);
3622	++__first2;
3623	}
3624	else
3625	{
3626	*__result = ranges::iter_move(__first1);
3627	++__first1;
3628	}
3629	++__result;
3630	}
3631	if (__first1 != __last1)
3632	ranges::move(__first1, __last1, __result);
3633	}
3634
3635	template<typename _Iter1, typename _Iter2, typename _Iter3, typename _Comp>
3636	void
3637	__move_merge_adaptive_backward(_Iter1 __first1, _Iter1 __last1,
3638	_Iter2 __first2, _Iter2 __last2,
3639	_Iter3 __result, _Comp __comp)
3640	{
3641	if (__first1 == __last1)
3642	{
3643	ranges::move_backward(__first2, __last2, __result);
3644	return;
3645	}
3646	else if (__first2 == __last2)
3647	return;
3648
3649	--__last1;
3650	--__last2;
3651	while (true)
3652	{
3653	if (__comp(__last2, __last1))
3654	{
3655	*--__result = ranges::iter_move(__last1);
3656	if (__first1 == __last1)
3657	{
3658	ranges::move_backward(__first2, ++__last2, __result);
3659	return;
3660	}
3661	--__last1;
3662	}
3663	else
3664	{
3665	*--__result = ranges::iter_move(__last2);
3666	if (__first2 == __last2)
3667	return;
3668	--__last2;
3669	}
3670	}
3671	}
3672
3673	template<typename _Iter1, typename _Iter2>
3674	_Iter1
3675	__rotate_adaptive(_Iter1 __first, _Iter1 __middle, _Iter1 __last,
3676	iter_difference_t<_Iter1> __len1,
3677	iter_difference_t<_Iter1> __len2,
3678	_Iter2 __buffer,
3679	iter_difference_t<_Iter1> __buffer_size)
3680	{
3681	_Iter2 __buffer_end;
3682	if (__len1 > __len2 && __len2 <= __buffer_size)
3683	{
3684	if (__len2)
3685	{
3686	__buffer_end = ranges::move(__middle, __last, __buffer).out;
3687	ranges::move_backward(__first, __middle, __last);
3688	return ranges::move(__buffer, __buffer_end, __first).out;
3689	}
3690	else
3691	return __first;
3692	}
3693	else if (__len1 <= __buffer_size)
3694	{
3695	if (__len1)
3696	{
3697	__buffer_end = ranges::move(__first, __middle, __buffer).out;
3698	ranges::move(__middle, __last, __first);
3699	return ranges::move_backward(__buffer, __buffer_end, __last).out;
3700	}
3701	else
3702	return __last;
3703	}
3704	else
3705	return ranges::rotate(__first, __middle, __last).begin();
3706	}
3707
3708	template<typename _Iter, typename _Pointer, typename _Comp>
3709	void
3710	__merge_adaptive(_Iter __first, _Iter __middle, _Iter __last,
3711	iter_difference_t<_Iter> __len1,
3712	iter_difference_t<_Iter> __len2,
3713	_Pointer __buffer, _Comp __comp)
3714	{
3715	if (__len1 <= __len2)
3716	{
3717	_Pointer __buffer_end = ranges::move(__first, __middle, __buffer).out;
3718	__detail::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
3719	__first, __comp);
3720	}
3721	else
3722	{
3723	_Pointer __buffer_end = ranges::move(__middle, __last, __buffer).out;
3724	__detail::__move_merge_adaptive_backward(__first, __middle, __buffer,
3725	__buffer_end, __last, __comp);
3726	}
3727	}
3728
3729	template<typename _Iter, typename _Distance, typename _Pointer, typename _Comp>
3730	void
3731	__merge_adaptive_resize(_Iter __first, _Iter __middle, _Iter __last,
3732	_Distance __len1, _Distance __len2,
3733	_Pointer __buffer, _Distance __buffer_size,
3734	_Comp __comp)
3735	{
3736	if (__len1 <= __buffer_size \|\| __len2 <= __buffer_size)
3737	__detail::__merge_adaptive(__first, __middle, __last,
3738	__len1, __len2, __buffer, __comp);
3739	else
3740	{
3741	_Iter __first_cut = __first;
3742	_Iter __second_cut = __middle;
3743	_Distance __len11 = `0`;
3744	_Distance __len22 = `0`;
3745	if (__len1 > __len2)
3746	{
3747	__len11 = __len1 / `2`;
3748	ranges::advance(__first_cut, __len11);
3749	__second_cut = ranges::lower_bound(__middle, __last, *__first_cut,
3750	__comp);
3751	__len22 = ranges::distance(__middle, __second_cut);
3752	}
3753	else
3754	{
3755	__len22 = __len2 / `2`;
3756	ranges::advance(__second_cut, __len22);
3757	__first_cut = ranges::upper_bound(__first, __middle, *__second_cut,
3758	__comp);
3759	__len11 = ranges::distance(__first, __first_cut);
3760	}
3761
3762	_Iter __new_middle
3763	= __detail::__rotate_adaptive(__first_cut, __middle, __second_cut,
3764	_Distance(__len1 - __len11), __len22,
3765	__buffer, __buffer_size);
3766	__detail::__merge_adaptive_resize(__first, __first_cut, __new_middle,
3767	__len11, __len22,
3768	__buffer, __buffer_size, __comp);
3769	__detail::__merge_adaptive_resize(__new_middle, __second_cut, __last,
3770	_Distance(__len1 - __len11),
3771	_Distance(__len2 - __len22),
3772	__buffer, __buffer_size, __comp);
3773	}
3774	}
3775
3776	template<typename _Iter, typename _Distance, typename _Comp>
3777	constexpr void
3778	__merge_without_buffer(_Iter __first, _Iter __middle, _Iter __last,
3779	_Distance __len1, _Distance __len2, _Comp __comp)
3780	{
3781	if (__len1 == `0` \|\| __len2 == `0`)
3782	return;
3783
3784	if (__len1 + __len2 == `2`)
3785	{
3786	if (__comp(__middle, __first))
3787	ranges::iter_swap(__first, __middle);
3788	return;
3789	}
3790
3791	_Iter __first_cut = __first;
3792	_Iter __second_cut = __middle;
3793	_Distance __len11 = `0`;
3794	_Distance __len22 = `0`;
3795	if (__len1 > __len2)
3796	{
3797	__len11 = __len1 / `2`;
3798	ranges::advance(__first_cut, __len11);
3799	__second_cut = ranges::lower_bound(__middle, __last, *__first_cut, __comp);
3800	__len22 = ranges::distance(__middle, __second_cut);
3801	}
3802	else
3803	{
3804	__len22 = __len2 / `2`;
3805	ranges::advance(__second_cut, __len22);
3806	__first_cut = ranges::upper_bound(__first, __middle, *__second_cut, __comp);
3807	__len11 = ranges::distance(__first, __first_cut);
3808	}
3809
3810	_Iter __new_middle = ranges::rotate(__first_cut, __middle, __second_cut).begin();
3811	__detail::__merge_without_buffer(__first, __first_cut, __new_middle,
3812	__len11, __len22, __comp);
3813	__detail::__merge_without_buffer(__new_middle, __second_cut, __last,
3814	__len1 - __len11, __len2 - __len22, __comp);
3815	}
3816	} // namespace __detail
3817
3818	struct __inplace_merge_fn
3819	{
3820	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3821	typename _Comp = ranges::less,
3822	typename _Proj = identity>
3823	requires sortable<_Iter, _Comp, _Proj>
3824	_GLIBCXX26_CONSTEXPR
3825	_Iter
3826	operator()(_Iter __first, _Iter __middle, _Sent __last,
3827	_Comp __comp = {}, _Proj __proj = {}) const
3828	{
3829	if constexpr (!same_as<_Iter, _Sent>)
3830	return (*this)(__first, __middle, ranges::next(__middle, __last),
3831	std::move(__comp), std::move(__proj));
3832	else
3833	{
3834	using _DistanceType = iter_difference_t<_Iter>;
3835
3836	if (__first == __middle \|\| __middle == __last)
3837	return __last;
3838
3839	const _DistanceType __len1 = ranges::distance(__first, __middle);
3840	const _DistanceType __len2 = ranges::distance(__middle, __last);
3841
3842	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3843
3844	#if _GLIBCXX_HOSTED
3845	# if __glibcxx_constexpr_algorithms >= 202306L // >= C++26
3846	if consteval {
3847	__detail::__merge_without_buffer(__first, __middle, __last,
3848	__len1, __len2, __comp_proj);
3849	return __last;
3850	}
3851	# endif
3852	using _TmpBuf = _Temporary_buffer<_Iter, iter_value_t<_Iter>>;
3853	// __merge_adaptive will use a buffer for the smaller of
3854	// [first,middle) and [middle,last).
3855	_TmpBuf __buf(__first, ptrdiff_t(ranges::min(__len1, __len2)));
3856
3857	if (__buf.size() == __buf._M_requested_size()) [[likely]]
3858	__detail::__merge_adaptive
3859	(__first, __middle, __last, __len1, __len2, __buf.begin(), __comp_proj);
3860	else if (__buf.begin() == `0`) [[unlikely]]
3861	__detail::__merge_without_buffer
3862	(__first, __middle, __last, __len1, __len2, __comp_proj);
3863	else
3864	__detail::__merge_adaptive_resize
3865	(__first, __middle, __last, __len1, __len2, __buf.begin(),
3866	_DistanceType(__buf.size()), __comp_proj);
3867	#else
3868	__detail::__merge_without_buffer
3869	(__first, __middle, __last, __len1, __len2, __comp_proj);
3870	#endif
3871	return __last;
3872	}
3873	}
3874
3875	template<bidirectional_range _Range,
3876	typename _Comp = ranges::less, typename _Proj = identity>
3877	requires sortable<iterator_t<_Range>, _Comp, _Proj>
3878	_GLIBCXX26_CONSTEXPR
3879	borrowed_iterator_t<_Range>
3880	operator()(_Range&& __r, iterator_t<_Range> __middle,
3881	_Comp __comp = {}, _Proj __proj = {}) const
3882	{
3883	return (*this)(ranges::begin(__r), std::move(__middle),
3884	ranges::end(__r),
3885	std::move(__comp), std::move(__proj));
3886	}
3887	};
3888
3889	inline constexpr __inplace_merge_fn inplace_merge{};
3890
3891	struct __includes_fn
3892	{
3893	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3894	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3895	typename _Proj1 = identity, typename _Proj2 = identity,
3896	indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3897	projected<_Iter2, _Proj2>>
3898	_Comp = ranges::less>
3899	[[nodiscard]] constexpr bool
3900	operator()(_Iter1 __first1, _Sent1 __last1,
3901	_Iter2 __first2, _Sent2 __last2,
3902	_Comp __comp = {},
3903	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3904	{
3905	while (__first1 != __last1 && __first2 != __last2)
3906	if (std::__invoke(__comp,
3907	std::__invoke(__proj2, *__first2),
3908	std::__invoke(__proj1, *__first1)))
3909	return false;
3910	else if (std::__invoke(__comp,
3911	std::__invoke(__proj1, *__first1),
3912	std::__invoke(__proj2, *__first2)))
3913	++__first1;
3914	else
3915	{
3916	++__first1;
3917	++__first2;
3918	}
3919
3920	return __first2 == __last2;
3921	}
3922
3923	template<input_range _Range1, input_range _Range2,
3924	typename _Proj1 = identity, typename _Proj2 = identity,
3925	indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
3926	projected<iterator_t<_Range2>, _Proj2>>
3927	_Comp = ranges::less>
3928	[[nodiscard]] constexpr bool
3929	operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
3930	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3931	{
3932	return (*this)(ranges::begin(__r1), ranges::end(__r1),
3933	ranges::begin(__r2), ranges::end(__r2),
3934	std::move(__comp),
3935	std::move(__proj1), std::move(__proj2));
3936	}
3937	};
3938
3939	inline constexpr __includes_fn includes{};
3940
3941	template<typename _Iter1, typename _Iter2, typename _Out>
3942	using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>;
3943
3944	struct __set_union_fn
3945	{
3946	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3947	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3948	weakly_incrementable _Out, typename _Comp = ranges::less,
3949	typename _Proj1 = identity, typename _Proj2 = identity>
3950	requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
3951	constexpr set_union_result<_Iter1, _Iter2, _Out>
3952	operator()(_Iter1 __first1, _Sent1 __last1,
3953	_Iter2 __first2, _Sent2 __last2,
3954	_Out __result, _Comp __comp = {},
3955	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3956	{
3957	while (__first1 != __last1 && __first2 != __last2)
3958	{
3959	if (std::__invoke(__comp,
3960	std::__invoke(__proj1, *__first1),
3961	std::__invoke(__proj2, *__first2)))
3962	{
3963	__result = __first1;
3964	++__first1;
3965	}
3966	else if (std::__invoke(__comp,
3967	std::__invoke(__proj2, *__first2),
3968	std::__invoke(__proj1, *__first1)))
3969	{
3970	__result = __first2;
3971	++__first2;
3972	}
3973	else
3974	{
3975	__result = __first1;
3976	++__first1;
3977	++__first2;
3978	}
3979	++__result;
3980	}
3981	auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
3982	std::move(__result));
3983	auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
3984	std::move(__copy1.out));
3985	return {std::move(__copy1.in), std::move(__copy2.in),
3986	std::move(__copy2.out)};
3987	}
3988
3989	template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
3990	typename _Comp = ranges::less,
3991	typename _Proj1 = identity, typename _Proj2 = identity>
3992	requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
3993	_Comp, _Proj1, _Proj2>
3994	constexpr set_union_result<borrowed_iterator_t<_Range1>,
3995	borrowed_iterator_t<_Range2>, _Out>
3996	operator()(_Range1&& __r1, _Range2&& __r2,
3997	_Out __result, _Comp __comp = {},
3998	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3999	{
4000	return (*this)(ranges::begin(__r1), ranges::end(__r1),
4001	ranges::begin(__r2), ranges::end(__r2),
4002	std::move(__result), std::move(__comp),
4003	std::move(__proj1), std::move(__proj2));
4004	}
4005	};
4006
4007	inline constexpr __set_union_fn set_union{};
4008
4009	template<typename _Iter1, typename _Iter2, typename _Out>
4010	using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>;
4011
4012	struct __set_intersection_fn
4013	{
4014	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
4015	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
4016	weakly_incrementable _Out, typename _Comp = ranges::less,
4017	typename _Proj1 = identity, typename _Proj2 = identity>
4018	requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
4019	constexpr set_intersection_result<_Iter1, _Iter2, _Out>
4020	operator()(_Iter1 __first1, _Sent1 __last1,
4021	_Iter2 __first2, _Sent2 __last2, _Out __result,
4022	_Comp __comp = {},
4023	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
4024	{
4025	while (__first1 != __last1 && __first2 != __last2)
4026	if (std::__invoke(__comp,
4027	std::__invoke(__proj1, *__first1),
4028	std::__invoke(__proj2, *__first2)))
4029	++__first1;
4030	else if (std::__invoke(__comp,
4031	std::__invoke(__proj2, *__first2),
4032	std::__invoke(__proj1, *__first1)))
4033	++__first2;
4034	else
4035	{
4036	__result = __first1;
4037	++__first1;
4038	++__first2;
4039	++__result;
4040	}
4041	// TODO: Eliminating these variables triggers an ICE.
4042	auto __last1i = ranges::next(std::move(__first1), std::move(__last1));
4043	auto __last2i = ranges::next(std::move(__first2), std::move(__last2));
4044	return {std::move(__last1i), std::move(__last2i), std::move(__result)};
4045	}
4046
4047	template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
4048	typename _Comp = ranges::less,
4049	typename _Proj1 = identity, typename _Proj2 = identity>
4050	requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
4051	_Comp, _Proj1, _Proj2>
4052	constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
4053	borrowed_iterator_t<_Range2>, _Out>
4054	operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
4055	_Comp __comp = {},
4056	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
4057	{
4058	return (*this)(ranges::begin(__r1), ranges::end(__r1),
4059	ranges::begin(__r2), ranges::end(__r2),
4060	std::move(__result), std::move(__comp),
4061	std::move(__proj1), std::move(__proj2));
4062	}
4063	};
4064
4065	inline constexpr __set_intersection_fn set_intersection{};
4066
4067	template<typename _Iter, typename _Out>
4068	using set_difference_result = in_out_result<_Iter, _Out>;
4069
4070	struct __set_difference_fn
4071	{
4072	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
4073	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
4074	weakly_incrementable _Out, typename _Comp = ranges::less,
4075	typename _Proj1 = identity, typename _Proj2 = identity>
4076	requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
4077	constexpr set_difference_result<_Iter1, _Out>
4078	operator()(_Iter1 __first1, _Sent1 __last1,
4079	_Iter2 __first2, _Sent2 __last2, _Out __result,
4080	_Comp __comp = {},
4081	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
4082	{
4083	while (__first1 != __last1 && __first2 != __last2)
4084	if (std::__invoke(__comp,
4085	std::__invoke(__proj1, *__first1),
4086	std::__invoke(__proj2, *__first2)))
4087	{
4088	__result = __first1;
4089	++__first1;
4090	++__result;
4091	}
4092	else if (std::__invoke(__comp,
4093	std::__invoke(__proj2, *__first2),
4094	std::__invoke(__proj1, *__first1)))
4095	++__first2;
4096	else
4097	{
4098	++__first1;
4099	++__first2;
4100	}
4101	return ranges::copy(std::move(__first1), std::move(__last1),
4102	std::move(__result));
4103	}
4104
4105	template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
4106	typename _Comp = ranges::less,
4107	typename _Proj1 = identity, typename _Proj2 = identity>
4108	requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
4109	_Comp, _Proj1, _Proj2>
4110	constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out>
4111	operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
4112	_Comp __comp = {},
4113	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
4114	{
4115	return (*this)(ranges::begin(__r1), ranges::end(__r1),
4116	ranges::begin(__r2), ranges::end(__r2),
4117	std::move(__result), std::move(__comp),
4118	std::move(__proj1), std::move(__proj2));
4119	}
4120	};
4121
4122	inline constexpr __set_difference_fn set_difference{};
4123
4124	template<typename _Iter1, typename _Iter2, typename _Out>
4125	using set_symmetric_difference_result
4126	= in_in_out_result<_Iter1, _Iter2, _Out>;
4127
4128	struct __set_symmetric_difference_fn
4129	{
4130	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
4131	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
4132	weakly_incrementable _Out, typename _Comp = ranges::less,
4133	typename _Proj1 = identity, typename _Proj2 = identity>
4134	requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
4135	constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
4136	operator()(_Iter1 __first1, _Sent1 __last1,
4137	_Iter2 __first2, _Sent2 __last2,
4138	_Out __result, _Comp __comp = {},
4139	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
4140	{
4141	while (__first1 != __last1 && __first2 != __last2)
4142	if (std::__invoke(__comp,
4143	std::__invoke(__proj1, *__first1),
4144	std::__invoke(__proj2, *__first2)))
4145	{
4146	__result = __first1;
4147	++__first1;
4148	++__result;
4149	}
4150	else if (std::__invoke(__comp,
4151	std::__invoke(__proj2, *__first2),
4152	std::__invoke(__proj1, *__first1)))
4153	{
4154	__result = __first2;
4155	++__first2;
4156	++__result;
4157	}
4158	else
4159	{
4160	++__first1;
4161	++__first2;
4162	}
4163	auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
4164	std::move(__result));
4165	auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
4166	std::move(__copy1.out));
4167	return {std::move(__copy1.in), std::move(__copy2.in),
4168	std::move(__copy2.out)};
4169	}
4170
4171	template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
4172	typename _Comp = ranges::less,
4173	typename _Proj1 = identity, typename _Proj2 = identity>
4174	requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
4175	_Comp, _Proj1, _Proj2>
4176	constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>,
4177	borrowed_iterator_t<_Range2>,
4178	_Out>
4179	operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
4180	_Comp __comp = {},
4181	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
4182	{
4183	return (*this)(ranges::begin(__r1), ranges::end(__r1),
4184	ranges::begin(__r2), ranges::end(__r2),
4185	std::move(__result), std::move(__comp),
4186	std::move(__proj1), std::move(__proj2));
4187	}
4188	};
4189
4190	inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};
4191
4192	// min is defined in <bits/ranges_util.h>.
4193
4194	struct __max_fn
4195	{
4196	template<typename _Tp, typename _Proj = identity,
4197	indirect_strict_weak_order<projected<const _Tp*, _Proj>>
4198	_Comp = ranges::less>
4199	[[nodiscard]] constexpr const _Tp&
4200	operator()(const _Tp& __a, const _Tp& __b,
4201	_Comp __comp = {}, _Proj __proj = {}) const
4202	{
4203	if (std::__invoke(__comp,
4204	std::__invoke(__proj, __a),
4205	std::__invoke(__proj, __b)))
4206	return __b;
4207	else
4208	return __a;
4209	}
4210
4211	template<input_range _Range, typename _Proj = identity,
4212	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
4213	_Comp = ranges::less>
4214	requires indirectly_copyable_storable<iterator_t<_Range>,
4215	range_value_t<_Range>*>
4216	[[nodiscard]] constexpr range_value_t<_Range>
4217	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
4218	{
4219	auto __first = ranges::begin(__r);
4220	auto __last = ranges::end(__r);
4221	__glibcxx_assert(__first != __last);
4222	range_value_t<_Range> __result(*__first);
4223	while (++__first != __last)
4224	{
4225	auto&& __tmp = *__first;
4226	if (std::__invoke(__comp,
4227	std::__invoke(__proj, __result),
4228	std::__invoke(__proj, __tmp)))
4229	__result = std::forward<decltype(__tmp)>(__tmp);
4230	}
4231	return __result;
4232	}
4233
4234	template<copyable _Tp, typename _Proj = identity,
4235	indirect_strict_weak_order<projected<const _Tp*, _Proj>>
4236	_Comp = ranges::less>
4237	[[nodiscard]] constexpr _Tp
4238	operator()(initializer_list<_Tp> __r,
4239	_Comp __comp = {}, _Proj __proj = {}) const
4240	{
4241	return (*this)(ranges::subrange(__r),
4242	std::move(__comp), std::move(__proj));
4243	}
4244	};
4245
4246	inline constexpr __max_fn max{};
4247
4248	struct __clamp_fn
4249	{
4250	template<typename _Tp, typename _Proj = identity,
4251	indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
4252	= ranges::less>
4253	[[nodiscard]] constexpr const _Tp&
4254	operator()(const _Tp& __val, const _Tp& __lo, const _Tp& __hi,
4255	_Comp __comp = {}, _Proj __proj = {}) const
4256	{
4257	__glibcxx_assert(!(std::__invoke(__comp,
4258	std::__invoke(__proj, __hi),
4259	std::__invoke(__proj, __lo))));
4260	auto&& __proj_val = std::__invoke(__proj, __val);
4261	if (std::__invoke(__comp,
4262	std::forward<decltype(__proj_val)>(__proj_val),
4263	std::__invoke(__proj, __lo)))
4264	return __lo;
4265	else if (std::__invoke(__comp,
4266	std::__invoke(__proj, __hi),
4267	std::forward<decltype(__proj_val)>(__proj_val)))
4268	return __hi;
4269	else
4270	return __val;
4271	}
4272	};
4273
4274	inline constexpr __clamp_fn clamp{};
4275
4276	template<typename _Tp>
4277	struct min_max_result
4278	{
4279	[[no_unique_address]] _Tp min;
4280	[[no_unique_address]] _Tp max;
4281
4282	template<typename _Tp2>
4283	requires convertible_to<const _Tp&, _Tp2>
4284	constexpr
4285	operator min_max_result<_Tp2>() const &
4286	{ return {min, max}; }
4287
4288	template<typename _Tp2>
4289	requires convertible_to<_Tp, _Tp2>
4290	constexpr
4291	operator min_max_result<_Tp2>() &&
4292	{ return {std::move(min), std::move(max)}; }
4293	};
4294
4295	template<typename _Tp>
4296	using minmax_result = min_max_result<_Tp>;
4297
4298	struct __minmax_fn
4299	{
4300	template<typename _Tp, typename _Proj = identity,
4301	indirect_strict_weak_order<projected<const _Tp*, _Proj>>
4302	_Comp = ranges::less>
4303	[[nodiscard]] constexpr minmax_result<const _Tp&>
4304	operator()(const _Tp& __a, const _Tp& __b,
4305	_Comp __comp = {}, _Proj __proj = {}) const
4306	{
4307	if (std::__invoke(__comp,
4308	std::__invoke(__proj, __b),
4309	std::__invoke(__proj, __a)))
4310	return {__b, __a};
4311	else
4312	return {__a, __b};
4313	}
4314
4315	template<input_range _Range, typename _Proj = identity,
4316	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
4317	_Comp = ranges::less>
4318	requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*>
4319	[[nodiscard]] constexpr minmax_result<range_value_t<_Range>>
4320	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
4321	{
4322	auto __first = ranges::begin(__r);
4323	auto __last = ranges::end(__r);
4324	__glibcxx_assert(__first != __last);
4325	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
4326	minmax_result<range_value_t<_Range>> __result = {*__first, __result.min};
4327	if (++__first == __last)
4328	return __result;
4329	else
4330	{
4331	// At this point __result.min == __result.max, so a single
4332	// comparison with the next element suffices.
4333	auto&& __val = *__first;
4334	if (__comp_proj(__val, __result.min))
4335	__result.min = std::forward<decltype(__val)>(__val);
4336	else
4337	__result.max = std::forward<decltype(__val)>(__val);
4338	}
4339	while (++__first != __last)
4340	{
4341	// Now process two elements at a time so that we perform at most
4342	// 1 + 3(N-2)/2 comparisons in total (each of the (N-2)/2*
4343	// iterations of this loop performs three comparisons).
4344	range_value_t<_Range> __val1 = *__first;
4345	if (++__first == __last)
4346	{
4347	// N is odd; in this final iteration, we perform at most two
4348	// comparisons, for a total of 1 + 3(N-3)/2 + 2 comparisons,*
4349	// which is not more than 3N/2, as required.*
4350	if (__comp_proj(__val1, __result.min))
4351	__result.min = std::move(__val1);
4352	else if (!__comp_proj(__val1, __result.max))
4353	__result.max = std::move(__val1);
4354	break;
4355	}
4356	auto&& __val2 = *__first;
4357	if (!__comp_proj(__val2, __val1))
4358	{
4359	if (__comp_proj(__val1, __result.min))
4360	__result.min = std::move(__val1);
4361	if (!__comp_proj(__val2, __result.max))
4362	__result.max = std::forward<decltype(__val2)>(__val2);
4363	}
4364	else
4365	{
4366	if (__comp_proj(__val2, __result.min))
4367	__result.min = std::forward<decltype(__val2)>(__val2);
4368	if (!__comp_proj(__val1, __result.max))
4369	__result.max = std::move(__val1);
4370	}
4371	}
4372	return __result;
4373	}
4374
4375	template<copyable _Tp, typename _Proj = identity,
4376	indirect_strict_weak_order<projected<const _Tp*, _Proj>>
4377	_Comp = ranges::less>
4378	[[nodiscard]] constexpr minmax_result<_Tp>
4379	operator()(initializer_list<_Tp> __r,
4380	_Comp __comp = {}, _Proj __proj = {}) const
4381	{
4382	return (*this)(ranges::subrange(__r),
4383	std::move(__comp), std::move(__proj));
4384	}
4385	};
4386
4387	inline constexpr __minmax_fn minmax{};
4388
4389	struct __min_element_fn
4390	{
4391	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
4392	typename _Proj = identity,
4393	indirect_strict_weak_order<projected<_Iter, _Proj>>
4394	_Comp = ranges::less>
4395	[[nodiscard]] constexpr _Iter
4396	operator()(_Iter __first, _Sent __last,
4397	_Comp __comp = {}, _Proj __proj = {}) const
4398	{
4399	if (__first == __last)
4400	return __first;
4401
4402	auto __i = __first;
4403	while (++__i != __last)
4404	{
4405	if (std::__invoke(__comp,
4406	std::__invoke(__proj, *__i),
4407	std::__invoke(__proj, *__first)))
4408	__first = __i;
4409	}
4410	return __first;
4411	}
4412
4413	template<forward_range _Range, typename _Proj = identity,
4414	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
4415	_Comp = ranges::less>
4416	[[nodiscard]] constexpr borrowed_iterator_t<_Range>
4417	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
4418	{
4419	return (*this)(ranges::begin(__r), ranges::end(__r),
4420	std::move(__comp), std::move(__proj));
4421	}
4422	};
4423
4424	inline constexpr __min_element_fn min_element{};
4425
4426	struct __max_element_fn
4427	{
4428	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
4429	typename _Proj = identity,
4430	indirect_strict_weak_order<projected<_Iter, _Proj>>
4431	_Comp = ranges::less>
4432	[[nodiscard]] constexpr _Iter
4433	operator()(_Iter __first, _Sent __last,
4434	_Comp __comp = {}, _Proj __proj = {}) const
4435	{
4436	if (__first == __last)
4437	return __first;
4438
4439	auto __i = __first;
4440	while (++__i != __last)
4441	{
4442	if (std::__invoke(__comp,
4443	std::__invoke(__proj, *__first),
4444	std::__invoke(__proj, *__i)))
4445	__first = __i;
4446	}
4447	return __first;
4448	}
4449
4450	template<forward_range _Range, typename _Proj = identity,
4451	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
4452	_Comp = ranges::less>
4453	[[nodiscard]] constexpr borrowed_iterator_t<_Range>
4454	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
4455	{
4456	return (*this)(ranges::begin(__r), ranges::end(__r),
4457	std::move(__comp), std::move(__proj));
4458	}
4459	};
4460
4461	inline constexpr __max_element_fn max_element{};
4462
4463	template<typename _Iter>
4464	using minmax_element_result = min_max_result<_Iter>;
4465
4466	struct __minmax_element_fn
4467	{
4468	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
4469	typename _Proj = identity,
4470	indirect_strict_weak_order<projected<_Iter, _Proj>>
4471	_Comp = ranges::less>
4472	[[nodiscard]] constexpr minmax_element_result<_Iter>
4473	operator()(_Iter __first, _Sent __last,
4474	_Comp __comp = {}, _Proj __proj = {}) const
4475	{
4476	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
4477	minmax_element_result<_Iter> __result = {__first, __first};
4478	if (__first == __last \|\| ++__first == __last)
4479	return __result;
4480	else
4481	{
4482	// At this point __result.min == __result.max, so a single
4483	// comparison with the next element suffices.
4484	if (__comp_proj(__first, __result.min))
4485	__result.min = __first;
4486	else
4487	__result.max = __first;
4488	}
4489	while (++__first != __last)
4490	{
4491	// Now process two elements at a time so that we perform at most
4492	// 1 + 3(N-2)/2 comparisons in total (each of the (N-2)/2*
4493	// iterations of this loop performs three comparisons).
4494	auto __prev = __first;
4495	if (++__first == __last)
4496	{
4497	// N is odd; in this final iteration, we perform at most two
4498	// comparisons, for a total of 1 + 3(N-3)/2 + 2 comparisons,*
4499	// which is not more than 3N/2, as required.*
4500	if (__comp_proj(__prev, __result.min))
4501	__result.min = __prev;
4502	else if (!__comp_proj(__prev, __result.max))
4503	__result.max = __prev;
4504	break;
4505	}
4506	if (!__comp_proj(__first, __prev))
4507	{
4508	if (__comp_proj(__prev, __result.min))
4509	__result.min = __prev;
4510	if (!__comp_proj(__first, __result.max))
4511	__result.max = __first;
4512	}
4513	else
4514	{
4515	if (__comp_proj(__first, __result.min))
4516	__result.min = __first;
4517	if (!__comp_proj(__prev, __result.max))
4518	__result.max = __prev;
4519	}
4520	}
4521	return __result;
4522	}
4523
4524	template<forward_range _Range, typename _Proj = identity,
4525	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
4526	_Comp = ranges::less>
4527	[[nodiscard]] constexpr minmax_element_result<borrowed_iterator_t<_Range>>
4528	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
4529	{
4530	return (*this)(ranges::begin(__r), ranges::end(__r),
4531	std::move(__comp), std::move(__proj));
4532	}
4533	};
4534
4535	inline constexpr __minmax_element_fn minmax_element{};
4536
4537	struct __lexicographical_compare_fn
4538	{
4539	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
4540	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
4541	typename _Proj1 = identity, typename _Proj2 = identity,
4542	indirect_strict_weak_order<projected<_Iter1, _Proj1>,
4543	projected<_Iter2, _Proj2>>
4544	_Comp = ranges::less>
4545	[[nodiscard]] constexpr bool
4546	operator()(_Iter1 __first1, _Sent1 __last1,
4547	_Iter2 __first2, _Sent2 __last2,
4548	_Comp __comp = {},
4549	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
4550	{
4551	if constexpr (__detail::__is_normal_iterator<_Iter1>
4552	&& same_as<_Iter1, _Sent1>)
4553	return (*this)(__first1.base(), __last1.base(),
4554	std::move(__first2), std::move(__last2),
4555	std::move(__comp),
4556	std::move(__proj1), std::move(__proj2));
4557	else if constexpr (__detail::__is_normal_iterator<_Iter2>
4558	&& same_as<_Iter2, _Sent2>)
4559	return (*this)(std::move(__first1), std::move(__last1),
4560	__first2.base(), __last2.base(),
4561	std::move(__comp),
4562	std::move(__proj1), std::move(__proj2));
4563	else
4564	{
4565	constexpr bool __sized_iters
4566	= (sized_sentinel_for<_Sent1, _Iter1>
4567	&& sized_sentinel_for<_Sent2, _Iter2>);
4568	if constexpr (__sized_iters)
4569	{
4570	using _ValueType1 = iter_value_t<_Iter1>;
4571	using _ValueType2 = iter_value_t<_Iter2>;
4572	// This condition is consistent with the one in
4573	// __lexicographical_compare_aux in <bits/stl_algobase.h>.
4574	constexpr bool __use_memcmp
4575	= (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
4576	&& __ptr_to_nonvolatile<_Iter1>
4577	&& __ptr_to_nonvolatile<_Iter2>
4578	&& (is_same_v<_Comp, ranges::less>
4579	\|\| is_same_v<_Comp, ranges::greater>)
4580	&& is_same_v<_Proj1, identity>
4581	&& is_same_v<_Proj2, identity>);
4582	if constexpr (__use_memcmp)
4583	{
4584	const auto __d1 = __last1 - __first1;
4585	const auto __d2 = __last2 - __first2;
4586
4587	if (const auto __len = std::min(__d1, __d2))
4588	{
4589	const auto __c
4590	= std::__memcmp(__first1, __first2, __len);
4591	if constexpr (is_same_v<_Comp, ranges::less>)
4592	{
4593	if (__c < `0`)
4594	return true;
4595	if (__c > `0`)
4596	return false;
4597	}
4598	else if constexpr (is_same_v<_Comp, ranges::greater>)
4599	{
4600	if (__c > `0`)
4601	return true;
4602	if (__c < `0`)
4603	return false;
4604	}
4605	}
4606	return __d1 < __d2;
4607	}
4608	}
4609
4610	for (; __first1 != __last1 && __first2 != __last2;
4611	++__first1, (void) ++__first2)
4612	{
4613	if (std::__invoke(__comp,
4614	std::__invoke(__proj1, *__first1),
4615	std::__invoke(__proj2, *__first2)))
4616	return true;
4617	if (std::__invoke(__comp,
4618	std::__invoke(__proj2, *__first2),
4619	std::__invoke(__proj1, *__first1)))
4620	return false;
4621	}
4622	return __first1 == __last1 && __first2 != __last2;
4623	}
4624	}
4625
4626	template<input_range _Range1, input_range _Range2,
4627	typename _Proj1 = identity, typename _Proj2 = identity,
4628	indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
4629	projected<iterator_t<_Range2>, _Proj2>>
4630	_Comp = ranges::less>
4631	[[nodiscard]] constexpr bool
4632	operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
4633	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
4634	{
4635	return (*this)(ranges::begin(__r1), ranges::end(__r1),
4636	ranges::begin(__r2), ranges::end(__r2),
4637	std::move(__comp),
4638	std::move(__proj1), std::move(__proj2));
4639	}
4640
4641	private:
4642	template<typename _Iter, typename _Ref = iter_reference_t<_Iter>>
4643	static constexpr bool __ptr_to_nonvolatile
4644	= is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
4645	};
4646
4647	inline constexpr __lexicographical_compare_fn lexicographical_compare;
4648
4649	template<typename _Iter>
4650	struct in_found_result
4651	{
4652	[[no_unique_address]] _Iter in;
4653	bool found;
4654
4655	template<typename _Iter2>
4656	requires convertible_to<const _Iter&, _Iter2>
4657	constexpr
4658	operator in_found_result<_Iter2>() const &
4659	{ return {in, found}; }
4660
4661	template<typename _Iter2>
4662	requires convertible_to<_Iter, _Iter2>
4663	constexpr
4664	operator in_found_result<_Iter2>() &&
4665	{ return {std::move(in), found}; }
4666	};
4667
4668	template<typename _Iter>
4669	using next_permutation_result = in_found_result<_Iter>;
4670
4671	struct __next_permutation_fn
4672	{
4673	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
4674	typename _Comp = ranges::less, typename _Proj = identity>
4675	requires sortable<_Iter, _Comp, _Proj>
4676	constexpr next_permutation_result<_Iter>
4677	operator()(_Iter __first, _Sent __last,
4678	_Comp __comp = {}, _Proj __proj = {}) const
4679	{
4680	if (__first == __last)
4681	return {std::move(__first), false};
4682
4683	auto __i = __first;
4684	++__i;
4685	if (__i == __last)
4686	return {std::move(__i), false};
4687
4688	auto __lasti = ranges::next(__first, __last);
4689	__i = __lasti;
4690	--__i;
4691
4692	for (;;)
4693	{
4694	auto __ii = __i;
4695	--__i;
4696	if (std::__invoke(__comp,
4697	std::__invoke(__proj, *__i),
4698	std::__invoke(__proj, *__ii)))
4699	{
4700	auto __j = __lasti;
4701	while (!(bool)std::__invoke(__comp,
4702	std::__invoke(__proj, *__i),
4703	std::__invoke(__proj, *--__j)))
4704	;
4705	ranges::iter_swap(__i, __j);
4706	ranges::reverse(__ii, __last);
4707	return {std::move(__lasti), true};
4708	}
4709	if (__i == __first)
4710	{
4711	ranges::reverse(__first, __last);
4712	return {std::move(__lasti), false};
4713	}
4714	}
4715	}
4716
4717	template<bidirectional_range _Range, typename _Comp = ranges::less,
4718	typename _Proj = identity>
4719	requires sortable<iterator_t<_Range>, _Comp, _Proj>
4720	constexpr next_permutation_result<borrowed_iterator_t<_Range>>
4721	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
4722	{
4723	return (*this)(ranges::begin(__r), ranges::end(__r),
4724	std::move(__comp), std::move(__proj));
4725	}
4726	};
4727
4728	inline constexpr __next_permutation_fn next_permutation{};
4729
4730	template<typename _Iter>
4731	using prev_permutation_result = in_found_result<_Iter>;
4732
4733	struct __prev_permutation_fn
4734	{
4735	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
4736	typename _Comp = ranges::less, typename _Proj = identity>
4737	requires sortable<_Iter, _Comp, _Proj>
4738	constexpr prev_permutation_result<_Iter>
4739	operator()(_Iter __first, _Sent __last,
4740	_Comp __comp = {}, _Proj __proj = {}) const
4741	{
4742	if (__first == __last)
4743	return {std::move(__first), false};
4744
4745	auto __i = __first;
4746	++__i;
4747	if (__i == __last)
4748	return {std::move(__i), false};
4749
4750	auto __lasti = ranges::next(__first, __last);
4751	__i = __lasti;
4752	--__i;
4753
4754	for (;;)
4755	{
4756	auto __ii = __i;
4757	--__i;
4758	if (std::__invoke(__comp,
4759	std::__invoke(__proj, *__ii),
4760	std::__invoke(__proj, *__i)))
4761	{
4762	auto __j = __lasti;
4763	while (!(bool)std::__invoke(__comp,
4764	std::__invoke(__proj, *--__j),
4765	std::__invoke(__proj, *__i)))
4766	;
4767	ranges::iter_swap(__i, __j);
4768	ranges::reverse(__ii, __last);
4769	return {std::move(__lasti), true};
4770	}
4771	if (__i == __first)
4772	{
4773	ranges::reverse(__first, __last);
4774	return {std::move(__lasti), false};
4775	}
4776	}
4777	}
4778
4779	template<bidirectional_range _Range, typename _Comp = ranges::less,
4780	typename _Proj = identity>
4781	requires sortable<iterator_t<_Range>, _Comp, _Proj>
4782	constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
4783	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
4784	{
4785	return (*this)(ranges::begin(__r), ranges::end(__r),
4786	std::move(__comp), std::move(__proj));
4787	}
4788	};
4789
4790	inline constexpr __prev_permutation_fn prev_permutation{};
4791
4792	#if __glibcxx_ranges_contains >= 202207L // C++ >= 23
4793	struct __contains_fn
4794	{
4795	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
4796	typename _Proj = identity,
4797	typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
4798	requires indirect_binary_predicate<ranges::equal_to,
4799	projected<_Iter, _Proj>, const _Tp*>
4800	constexpr bool
4801	operator()(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {}) const
4802	{ return ranges::find(std::move(__first), __last, __value, std::move(__proj)) != __last; }
4803
4804	template<input_range _Range,
4805	typename _Proj = identity,
4806	typename _Tp
4807	_GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)>
4808	requires indirect_binary_predicate<ranges::equal_to,
4809	projected<iterator_t<_Range>, _Proj>, const _Tp*>
4810	constexpr bool
4811	operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
4812	{ return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); }
4813	};
4814
4815	inline constexpr __contains_fn contains{};
4816
4817	struct __contains_subrange_fn
4818	{
4819	template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
4820	forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
4821	typename _Pred = ranges::equal_to,
4822	typename _Proj1 = identity, typename _Proj2 = identity>
4823	requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
4824	constexpr bool
4825	operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
4826	_Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
4827	{
4828	return __first2 == __last2
4829	\|\| !ranges::search(__first1, __last1, __first2, __last2,
4830	std::move(__pred), std::move(__proj1), std::move(__proj2)).empty();
4831	}
4832
4833	template<forward_range _Range1, forward_range _Range2,
4834	typename _Pred = ranges::equal_to,
4835	typename _Proj1 = identity, typename _Proj2 = identity>
4836	requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
4837	_Pred, _Proj1, _Proj2>
4838	constexpr bool
4839	operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
4840	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
4841	{
4842	return (*this)(ranges::begin(__r1), ranges::end(__r1),
4843	ranges::begin(__r2), ranges::end(__r2),
4844	std::move(__pred), std::move(__proj1), std::move(__proj2));
4845	}
4846	};
4847
4848	inline constexpr __contains_subrange_fn contains_subrange{};
4849
4850	#endif // __glibcxx_ranges_contains
4851
4852	#if __glibcxx_ranges_find_last >= 202207L // C++ >= 23
4853
4854	struct __find_last_fn
4855	{
4856	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
4857	typename _Proj = identity,
4858	typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
4859	requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Tp*>
4860	[[nodiscard]] constexpr subrange<_Iter>
4861	operator()(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {}) const
4862	{
4863	if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
4864	{
4865	_Iter __found = ranges::find(reverse_iterator<_Iter>{__last},
4866	reverse_iterator<_Iter>{__first},
4867	__value, std::move(__proj)).base();
4868	if (__found == __first)
4869	return {__last, __last};
4870	else
4871	return {ranges::prev(__found), __last};
4872	}
4873	else
4874	{
4875	_Iter __found = ranges::find(__first, __last, __value, __proj);
4876	if (__found == __last)
4877	return {__found, __found};
4878	__first = __found;
4879	for (;;)
4880	{
4881	__first = ranges::find(ranges::next(__first), __last, __value, __proj);
4882	if (__first == __last)
4883	return {__found, __first};
4884	__found = __first;
4885	}
4886	}
4887	}
4888
4889	template<forward_range _Range, typename _Proj = identity,
4890	typename _Tp
4891	_GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)>
4892	requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Tp*>
4893	[[nodiscard]] constexpr borrowed_subrange_t<_Range>
4894	operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
4895	{ return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); }
4896	};
4897
4898	inline constexpr __find_last_fn find_last{};
4899
4900	struct __find_last_if_fn
4901	{
4902	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Proj = identity,
4903	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
4904	[[nodiscard]] constexpr subrange<_Iter>
4905	operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const
4906	{
4907	if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
4908	{
4909	_Iter __found = ranges::find_if(reverse_iterator<_Iter>{__last},
4910	reverse_iterator<_Iter>{__first},
4911	std::move(__pred), std::move(__proj)).base();
4912	if (__found == __first)
4913	return {__last, __last};
4914	else
4915	return {ranges::prev(__found), __last};
4916	}
4917	else
4918	{
4919	_Iter __found = ranges::find_if(__first, __last, __pred, __proj);
4920	if (__found == __last)
4921	return {__found, __found};
4922	__first = __found;
4923	for (;;)
4924	{
4925	__first = ranges::find_if(ranges::next(__first), __last, __pred, __proj);
4926	if (__first == __last)
4927	return {__found, __first};
4928	__found = __first;
4929	}
4930	}
4931	}
4932
4933	template<forward_range _Range, typename _Proj = identity,
4934	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
4935	[[nodiscard]] constexpr borrowed_subrange_t<_Range>
4936	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
4937	{ return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__pred), std::move(__proj)); }
4938	};
4939
4940	inline constexpr __find_last_if_fn find_last_if{};
4941
4942	struct __find_last_if_not_fn
4943	{
4944	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Proj = identity,
4945	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
4946	[[nodiscard]] constexpr subrange<_Iter>
4947	operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const
4948	{
4949	if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
4950	{
4951	_Iter __found = ranges::find_if_not(reverse_iterator<_Iter>{__last},
4952	reverse_iterator<_Iter>{__first},
4953	std::move(__pred), std::move(__proj)).base();
4954	if (__found == __first)
4955	return {__last, __last};
4956	else
4957	return {ranges::prev(__found), __last};
4958	}
4959	else
4960	{
4961	_Iter __found = ranges::find_if_not(__first, __last, __pred, __proj);
4962	if (__found == __last)
4963	return {__found, __found};
4964	__first = __found;
4965	for (;;)
4966	{
4967	__first = ranges::find_if_not(ranges::next(__first), __last, __pred, __proj);
4968	if (__first == __last)
4969	return {__found, __first};
4970	__found = __first;
4971	}
4972	}
4973	}
4974
4975	template<forward_range _Range, typename _Proj = identity,
4976	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
4977	[[nodiscard]] constexpr borrowed_subrange_t<_Range>
4978	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
4979	{ return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__pred), std::move(__proj)); }
4980	};
4981
4982	inline constexpr __find_last_if_not_fn find_last_if_not{};
4983
4984	#endif // __glibcxx_ranges_find_last
4985
4986	#if __glibcxx_ranges_fold >= 202207L // C++ >= 23
4987
4988	template<typename _Iter, typename _Tp>
4989	struct in_value_result
4990	{
4991	[[no_unique_address]] _Iter in;
4992	[[no_unique_address]] _Tp value;
4993
4994	template<typename _Iter2, typename _Tp2>
4995	requires convertible_to<const _Iter&, _Iter2>
4996	&& convertible_to<const _Tp&, _Tp2>
4997	constexpr
4998	operator in_value_result<_Iter2, _Tp2>() const &
4999	{ return {in, value}; }
5000
5001	template<typename _Iter2, typename _Tp2>
5002	requires convertible_to<_Iter, _Iter2>
5003	&& convertible_to<_Tp, _Tp2>
5004	constexpr
5005	operator in_value_result<_Iter2, _Tp2>() &&
5006	{ return {std::move(in), std::move(value)}; }
5007	};
5008
5009	namespace __detail
5010	{
5011	template<typename _Fp>
5012	class __flipped
5013	{
5014	_Fp _M_f;
5015
5016	public:
5017	template<typename _Tp, typename _Up>
5018	requires invocable<_Fp&, _Up, _Tp>
5019	invoke_result_t<_Fp&, _Up, _Tp>
5020	operator()(_Tp&&, _Up&&); // not defined
5021	};
5022
5023	template<typename _Fp, typename _Tp, typename _Iter, typename _Up>
5024	concept __indirectly_binary_left_foldable_impl = movable<_Tp> && movable<_Up>
5025	&& convertible_to<_Tp, _Up>
5026	&& invocable<_Fp&, _Up, iter_reference_t<_Iter>>
5027	&& assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Iter>>>;
5028
5029	template<typename _Fp, typename _Tp, typename _Iter>
5030	concept __indirectly_binary_left_foldable = copy_constructible<_Fp>
5031	&& indirectly_readable<_Iter>
5032	&& invocable<_Fp&, _Tp, iter_reference_t<_Iter>>
5033	&& convertible_to<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>,
5034	decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>
5035	&& __indirectly_binary_left_foldable_impl
5036	<_Fp, _Tp, _Iter, decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>;
5037
5038	template <typename _Fp, typename _Tp, typename _Iter>
5039	concept __indirectly_binary_right_foldable
5040	= __indirectly_binary_left_foldable<__flipped<_Fp>, _Tp, _Iter>;
5041	} // namespace __detail
5042
5043	template<typename _Iter, typename _Tp>
5044	using fold_left_with_iter_result = in_value_result<_Iter, _Tp>;
5045
5046	struct __fold_left_with_iter_fn
5047	{
5048	template<typename _Ret_iter,
5049	typename _Iter, typename _Sent, typename _Tp, typename _Fp>
5050	static constexpr auto
5051	_S_impl(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
5052	{
5053	using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>;
5054	using _Ret = fold_left_with_iter_result<_Ret_iter, _Up>;
5055
5056	if (__first == __last)
5057	return _Ret{std::move(__first), _Up(std::move(__init))};
5058
5059	_Up __accum = std::__invoke(__f, std::move(__init), *__first);
5060	for (++__first; __first != __last; ++__first)
5061	__accum = std::__invoke(__f, std::move(__accum), *__first);
5062	return _Ret{std::move(__first), std::move(__accum)};
5063	}
5064
5065	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
5066	typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>),
5067	__detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
5068	constexpr auto
5069	operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const
5070	{
5071	using _Ret_iter = _Iter;
5072	return _S_impl<_Ret_iter>(std::move(__first), __last,
5073	std::move(__init), std::move(__f));
5074	}
5075
5076	template<input_range _Range,
5077	typename _Tp _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>),
5078	__detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
5079	constexpr auto
5080	operator()(_Range&& __r, _Tp __init, _Fp __f) const
5081	{
5082	using _Ret_iter = borrowed_iterator_t<_Range>;
5083	return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r),
5084	std::move(__init), std::move(__f));
5085	}
5086	};
5087
5088	inline constexpr __fold_left_with_iter_fn fold_left_with_iter{};
5089
5090	struct __fold_left_fn
5091	{
5092	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
5093	typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>),
5094	__detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
5095	constexpr auto
5096	operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const
5097	{
5098	return ranges::fold_left_with_iter(std::move(__first), __last,
5099	std::move(__init), std::move(__f)).value;
5100	}
5101
5102	template<input_range _Range,
5103	typename _Tp _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>),
5104	__detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
5105	constexpr auto
5106	operator()(_Range&& __r, _Tp __init, _Fp __f) const
5107	{ return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__init), std::move(__f)); }
5108	};
5109
5110	inline constexpr __fold_left_fn fold_left{};
5111
5112	template<typename _Iter, typename _Tp>
5113	using fold_left_first_with_iter_result = in_value_result<_Iter, _Tp>;
5114
5115	struct __fold_left_first_with_iter_fn
5116	{
5117	template<typename _Ret_iter, typename _Iter, typename _Sent, typename _Fp>
5118	static constexpr auto
5119	_S_impl(_Iter __first, _Sent __last, _Fp __f)
5120	{
5121	using _Up = decltype(ranges::fold_left(std::move(__first), __last,
5122	iter_value_t<_Iter>(*__first), __f));
5123	using _Ret = fold_left_first_with_iter_result<_Ret_iter, optional<_Up>>;
5124
5125	if (__first == __last)
5126	return _Ret{std::move(__first), optional<_Up>()};
5127
5128	optional<_Up> __init(in_place, *__first);
5129	for (++__first; __first != __last; ++__first)
5130	__init = std::__invoke(__f, std::move(__init), *__first);
5131	return _Ret{std::move(__first), std::move(__init)};
5132	}
5133
5134	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
5135	__detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
5136	requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
5137	constexpr auto
5138	operator()(_Iter __first, _Sent __last, _Fp __f) const
5139	{
5140	using _Ret_iter = _Iter;
5141	return _S_impl<_Ret_iter>(std::move(__first), __last, std::move(__f));
5142	}
5143
5144	template<input_range _Range,
5145	__detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
5146	requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
5147	constexpr auto
5148	operator()(_Range&& __r, _Fp __f) const
5149	{
5150	using _Ret_iter = borrowed_iterator_t<_Range>;
5151	return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r), std::move(__f));
5152	}
5153	};
5154
5155	inline constexpr __fold_left_first_with_iter_fn fold_left_first_with_iter{};
5156
5157	struct __fold_left_first_fn
5158	{
5159	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
5160	__detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
5161	requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
5162	constexpr auto
5163	operator()(_Iter __first, _Sent __last, _Fp __f) const
5164	{
5165	return ranges::fold_left_first_with_iter(std::move(__first), __last,
5166	std::move(__f)).value;
5167	}
5168
5169	template<input_range _Range,
5170	__detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
5171	requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
5172	constexpr auto
5173	operator()(_Range&& __r, _Fp __f) const
5174	{ return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__f)); }
5175	};
5176
5177	inline constexpr __fold_left_first_fn fold_left_first{};
5178
5179	struct __fold_right_fn
5180	{
5181	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
5182	typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>),
5183	__detail::__indirectly_binary_right_foldable<_Tp, _Iter> _Fp>
5184	constexpr auto
5185	operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const
5186	{
5187	using _Up = decay_t<invoke_result_t<_Fp&, iter_reference_t<_Iter>, _Tp>>;
5188
5189	if (__first == __last)
5190	return _Up(std::move(__init));
5191
5192	_Iter __tail = ranges::next(__first, __last);
5193	_Up __accum = std::__invoke(__f, *--__tail, std::move(__init));
5194	while (__first != __tail)
5195	__accum = std::__invoke(__f, *--__tail, std::move(__accum));
5196	return __accum;
5197	}
5198
5199	template<bidirectional_range _Range,
5200	typename _Tp _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>),
5201	__detail::__indirectly_binary_right_foldable<_Tp, iterator_t<_Range>> _Fp>
5202	constexpr auto
5203	operator()(_Range&& __r, _Tp __init, _Fp __f) const
5204	{ return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__init), std::move(__f)); }
5205	};
5206
5207	inline constexpr __fold_right_fn fold_right{};
5208
5209	struct __fold_right_last_fn
5210	{
5211	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
5212	__detail::__indirectly_binary_right_foldable<iter_value_t<_Iter>, _Iter> _Fp>
5213	requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
5214	constexpr auto
5215	operator()(_Iter __first, _Sent __last, _Fp __f) const
5216	{
5217	using _Up = decltype(ranges::fold_right(__first, __last,
5218	iter_value_t<_Iter>(*__first), __f));
5219
5220	if (__first == __last)
5221	return optional<_Up>();
5222
5223	_Iter __tail = ranges::prev(ranges::next(__first, std::move(__last)));
5224	return optional<_Up>(in_place,
5225	ranges::fold_right(std::move(__first), __tail,
5226	iter_value_t<_Iter>(*__tail),
5227	std::move(__f)));
5228	}
5229
5230	template<bidirectional_range _Range,
5231	__detail::__indirectly_binary_right_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
5232	requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
5233	constexpr auto
5234	operator()(_Range&& __r, _Fp __f) const
5235	{ return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__f)); }
5236	};
5237
5238	inline constexpr __fold_right_last_fn fold_right_last{};
5239	#endif // __glibcxx_ranges_fold
5240	} // namespace ranges
5241
5242	#if __glibcxx_shift >= 201806L // C++ >= 20
5243	template<typename _ForwardIterator>
5244	constexpr _ForwardIterator
5245	shift_left(_ForwardIterator __first, _ForwardIterator __last,
5246	typename iterator_traits<_ForwardIterator>::difference_type __n)
5247	{
5248	__glibcxx_assert(__n >= `0`);
5249	if (__n == `0`)
5250	return __last;
5251
5252	auto __mid = ranges::next(__first, __n, __last);
5253	if (__mid == __last)
5254	return __first;
5255	return std::move(std::move(__mid), std::move(__last), std::move(__first));
5256	}
5257
5258	template<typename _ForwardIterator>
5259	constexpr _ForwardIterator
5260	shift_right(_ForwardIterator __first, _ForwardIterator __last,
5261	typename iterator_traits<_ForwardIterator>::difference_type __n)
5262	{
5263	__glibcxx_assert(__n >= `0`);
5264	if (__n == `0`)
5265	return __first;
5266
5267	using _Cat
5268	= typename iterator_traits<_ForwardIterator>::iterator_category;
5269	if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
5270	{
5271	auto __mid = ranges::next(__last, -__n, __first);
5272	if (__mid == __first)
5273	return __last;
5274
5275	return std::move_backward(std::move(__first), std::move(__mid),
5276	std::move(__last));
5277	}
5278	else
5279	{
5280	auto __result = ranges::next(__first, __n, __last);
5281	if (__result == __last)
5282	return __last;
5283
5284	auto __dest_head = __first, __dest_tail = __result;
5285	while (__dest_head != __result)
5286	{
5287	if (__dest_tail == __last)
5288	{
5289	// If we get here, then we must have
5290	// 2n >= distance(__first, __last)*
5291	// i.e. we are shifting out at least half of the range. In
5292	// this case we can safely perform the shift with a single
5293	// move.
5294	std::move(std::move(__first), std::move(__dest_head), __result);
5295	return __result;
5296	}
5297	++__dest_head;
5298	++__dest_tail;
5299	}
5300
5301	for (;;)
5302	{
5303	// At the start of each iteration of this outer loop, the range
5304	// [__first, __result) contains those elements that after shifting
5305	// the whole range right by __n, should end up in
5306	// [__dest_head, __dest_tail) in order.
5307
5308	// The below inner loop swaps the elements of [__first, __result)
5309	// and [__dest_head, __dest_tail), while simultaneously shifting
5310	// the latter range by __n.
5311	auto __cursor = __first;
5312	while (__cursor != __result)
5313	{
5314	if (__dest_tail == __last)
5315	{
5316	// At this point the ranges [__first, result) and
5317	// [__dest_head, dest_tail) are disjoint, so we can safely
5318	// move the remaining elements.
5319	__dest_head = std::move(__cursor, __result,
5320	std::move(__dest_head));
5321	std::move(std::move(__first), std::move(__cursor),
5322	std::move(__dest_head));
5323	return __result;
5324	}
5325	std::iter_swap(__cursor, __dest_head);
5326	++__dest_head;
5327	++__dest_tail;
5328	++__cursor;
5329	}
5330	}
5331	}
5332	}
5333	#endif
5334
5335	namespace ranges
5336	{
5337	#if __glibcxx_shift >= 202202L // C++ >= 23
5338	struct __shift_left_fn
5339	{
5340	template<permutable _Iter, sentinel_for<_Iter> _Sent>
5341	constexpr subrange<_Iter>
5342	operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __n) const
5343	{
5344	__glibcxx_assert(__n >= `0`);
5345	if (__n == `0`)
5346	return {__first, ranges::next(__first, __last)};
5347
5348	auto __mid = ranges::next(__first, __n, __last);
5349	if (__mid == __last)
5350	return {__first, __first};
5351	return {__first, ranges::move(__mid, __last, __first).out};
5352	}
5353
5354	template<forward_range _Range>
5355	requires permutable<iterator_t<_Range>>
5356	constexpr borrowed_subrange_t<_Range>
5357	operator()(_Range&& __r, range_difference_t<_Range> __n) const
5358	{ return (*this)(ranges::begin(__r), ranges::end(__r), __n); }
5359	};
5360
5361	inline constexpr __shift_left_fn shift_left{};
5362
5363	struct __shift_right_fn
5364	{
5365	template<permutable _Iter, sentinel_for<_Iter> _Sent>
5366	constexpr subrange<_Iter>
5367	operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __n) const
5368	{
5369	__glibcxx_assert(__n >= `0`);
5370	if (__n == `0`)
5371	return {__first, ranges::next(__first, __last)};
5372
5373	if constexpr (bidirectional_iterator<_Iter> && same_as<_Iter, _Sent>)
5374	{
5375	auto __mid = ranges::next(__last, -__n, __first);
5376	if (__mid == __first)
5377	return {__last, __last};
5378
5379	return {ranges::move_backward(__first, __mid, __last).out, __last};
5380	}
5381	else
5382	{
5383	auto __result = ranges::next(__first, __n, __last);
5384	if (__result == __last)
5385	return {__result, __result};
5386
5387	auto __dest_head = __first, __dest_tail = __result;
5388	while (__dest_head != __result)
5389	{
5390	if (__dest_tail == __last)
5391	{
5392	// If we get here, then we must have
5393	// 2n >= distance(__first, __last)*
5394	// i.e. we are shifting out at least half of the range. In
5395	// this case we can safely perform the shift with a single
5396	// move.
5397	auto __lasti = ranges::move(__first, __dest_head, __result).out;
5398	// __glibcxx_assert(__lasti == __last);
5399	return {__result, __lasti};
5400	}
5401	++__dest_head;
5402	++__dest_tail;
5403	}
5404
5405	for (;;)
5406	{
5407	// At the start of each iteration of this outer loop, the range
5408	// [__first, __result) contains those elements that after shifting
5409	// the whole range right by __n, should end up in
5410	// [__dest_head, __dest_tail) in order.
5411
5412	// The below inner loop swaps the elements of [__first, __result)
5413	// and [__dest_head, __dest_tail), while simultaneously shifting
5414	// the latter range by __n.
5415	auto __cursor = __first;
5416	while (__cursor != __result)
5417	{
5418	if (__dest_tail == __last)
5419	{
5420	// At this point the ranges [__first, result) and
5421	// [__dest_head, dest_tail) are disjoint, so we can safely
5422	// move the remaining elements.
5423	__dest_head = ranges::move(__cursor, __result, __dest_head).out;
5424	auto __lasti = ranges::move(__first, __cursor, __dest_head).out;
5425	// __glibcxx_assert(__lasti == __last);
5426	return {__result, __lasti};
5427	}
5428	ranges::iter_swap(__cursor, __dest_head);
5429	++__dest_head;
5430	++__dest_tail;
5431	++__cursor;
5432	}
5433	}
5434	}
5435	}
5436
5437	template<forward_range _Range>
5438	requires permutable<iterator_t<_Range>>
5439	constexpr borrowed_subrange_t<_Range>
5440	operator()(_Range&& __r, range_difference_t<_Range> __n) const
5441	{ return (*this)(ranges::begin(__r), ranges::end(__r), __n); }
5442	};
5443
5444	inline constexpr __shift_right_fn shift_right{};
5445	#endif // C++23
5446	} // namespace ranges
5447
5448	_GLIBCXX_END_NAMESPACE_VERSION
5449	} // namespace std
5450	#endif // concepts
5451	#endif // C++20
5452	#endif // _RANGES_ALGO_H
5453

Browse the source code of include/c++/16.1.1/bits/ranges_algo.h