1	// Core algorithmic facilities -*- C++ -*-
2
3	// Copyright (C) 2020-2023 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	#if __cplusplus > 202002L
36	#include <optional>
37	#endif
38	#include <bits/ranges_algobase.h>
39	#include <bits/ranges_util.h>
40	#include <bits/uniform_int_dist.h> // concept uniform_random_bit_generator
41
42	#if __cpp_lib_concepts
43	namespace std _GLIBCXX_VISIBILITY(default)
44	{
45	_GLIBCXX_BEGIN_NAMESPACE_VERSION
46	namespace ranges
47	{
48	namespace __detail
49	{
50	template<typename _Comp, typename _Proj>
51	constexpr auto
52	__make_comp_proj(_Comp& __comp, _Proj& __proj)
53	{
54	return [&] (auto&& __lhs, auto&& __rhs) -> bool {
55	using _TL = decltype(__lhs);
56	using _TR = decltype(__rhs);
57	return std::__invoke(__comp,
58	std::__invoke(__proj, std::forward<_TL>(__lhs)),
59	std::__invoke(__proj, std::forward<_TR>(__rhs)));
60	};
61	}
62
63	template<typename _Pred, typename _Proj>
64	constexpr auto
65	__make_pred_proj(_Pred& __pred, _Proj& __proj)
66	{
67	return [&] <typename _Tp> (_Tp&& __arg) -> bool {
68	return std::__invoke(__pred,
69	std::__invoke(__proj, std::forward<_Tp>(__arg)));
70	};
71	}
72	} // namespace __detail
73
74	struct __all_of_fn
75	{
76	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
77	typename _Proj = identity,
78	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
79	constexpr bool
80	operator()(_Iter __first, _Sent __last,
81	_Pred __pred, _Proj __proj = {}) const
82	{
83	for (; __first != __last; ++__first)
84	if (!(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
85	return false;
86	return true;
87	}
88
89	template<input_range _Range, typename _Proj = identity,
90	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
91	_Pred>
92	constexpr bool
93	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
94	{
95	return (*this)(ranges::begin(__r), ranges::end(__r),
96	std::move(__pred), std::move(__proj));
97	}
98	};
99
100	inline constexpr __all_of_fn all_of{};
101
102	struct __any_of_fn
103	{
104	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
105	typename _Proj = identity,
106	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
107	constexpr bool
108	operator()(_Iter __first, _Sent __last,
109	_Pred __pred, _Proj __proj = {}) const
110	{
111	for (; __first != __last; ++__first)
112	if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
113	return true;
114	return false;
115	}
116
117	template<input_range _Range, typename _Proj = identity,
118	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
119	_Pred>
120	constexpr bool
121	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
122	{
123	return (*this)(ranges::begin(__r), ranges::end(__r),
124	std::move(__pred), std::move(__proj));
125	}
126	};
127
128	inline constexpr __any_of_fn any_of{};
129
130	struct __none_of_fn
131	{
132	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
133	typename _Proj = identity,
134	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
135	constexpr bool
136	operator()(_Iter __first, _Sent __last,
137	_Pred __pred, _Proj __proj = {}) const
138	{
139	for (; __first != __last; ++__first)
140	if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
141	return false;
142	return true;
143	}
144
145	template<input_range _Range, typename _Proj = identity,
146	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
147	_Pred>
148	constexpr bool
149	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
150	{
151	return (*this)(ranges::begin(__r), ranges::end(__r),
152	std::move(__pred), std::move(__proj));
153	}
154	};
155
156	inline constexpr __none_of_fn none_of{};
157
158	template<typename _Iter, typename _Fp>
159	struct in_fun_result
160	{
161	[[no_unique_address]] _Iter in;
162	[[no_unique_address]] _Fp fun;
163
164	template<typename _Iter2, typename _F2p>
165	requires convertible_to<const _Iter&, _Iter2>
166	&& convertible_to<const _Fp&, _F2p>
167	constexpr
168	operator in_fun_result<_Iter2, _F2p>() const &
169	{ return {in, fun}; }
170
171	template<typename _Iter2, typename _F2p>
172	requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p>
173	constexpr
174	operator in_fun_result<_Iter2, _F2p>() &&
175	{ return {std::move(in), std::move(fun)}; }
176	};
177
178	template<typename _Iter, typename _Fp>
179	using for_each_result = in_fun_result<_Iter, _Fp>;
180
181	struct __for_each_fn
182	{
183	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
184	typename _Proj = identity,
185	indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
186	constexpr for_each_result<_Iter, _Fun>
187	operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {}) const
188	{
189	for (; __first != __last; ++__first)
190	std::__invoke(__f, std::__invoke(__proj, *__first));
191	return { std::move(__first), std::move(__f) };
192	}
193
194	template<input_range _Range, typename _Proj = identity,
195	indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>>
196	_Fun>
197	constexpr for_each_result<borrowed_iterator_t<_Range>, _Fun>
198	operator()(_Range&& __r, _Fun __f, _Proj __proj = {}) const
199	{
200	return (*this)(ranges::begin(__r), ranges::end(__r),
201	std::move(__f), std::move(__proj));
202	}
203	};
204
205	inline constexpr __for_each_fn for_each{};
206
207	template<typename _Iter, typename _Fp>
208	using for_each_n_result = in_fun_result<_Iter, _Fp>;
209
210	struct __for_each_n_fn
211	{
212	template<input_iterator _Iter, typename _Proj = identity,
213	indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
214	constexpr for_each_n_result<_Iter, _Fun>
215	operator()(_Iter __first, iter_difference_t<_Iter> __n,
216	_Fun __f, _Proj __proj = {}) const
217	{
218	if constexpr (random_access_iterator<_Iter>)
219	{
220	if (__n <= 0)
221	return {std::move(__first), std::move(__f)};
222	auto __last = __first + __n;
223	return ranges::for_each(std::move(__first), std::move(__last),
224	std::move(__f), std::move(__proj));
225	}
226	else
227	{
228	while (__n-- > 0)
229	{
230	std::__invoke(__f, std::__invoke(__proj, *__first));
231	++__first;
232	}
233	return {std::move(__first), std::move(__f)};
234	}
235	}
236	};
237
238	inline constexpr __for_each_n_fn for_each_n{};
239
240	// find, find_if and find_if_not are defined in <bits/ranges_util.h>.
241
242	struct __find_first_of_fn
243	{
244	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
245	forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
246	typename _Pred = ranges::equal_to,
247	typename _Proj1 = identity, typename _Proj2 = identity>
248	requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
249	constexpr _Iter1
250	operator()(_Iter1 __first1, _Sent1 __last1,
251	_Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
252	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
253	{
254	for (; __first1 != __last1; ++__first1)
255	for (auto __iter = __first2; __iter != __last2; ++__iter)
256	if (std::__invoke(__pred,
257	std::__invoke(__proj1, *__first1),
258	std::__invoke(__proj2, *__iter)))
259	return __first1;
260	return __first1;
261	}
262
263	template<input_range _Range1, forward_range _Range2,
264	typename _Pred = ranges::equal_to,
265	typename _Proj1 = identity, typename _Proj2 = identity>
266	requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
267	_Pred, _Proj1, _Proj2>
268	constexpr borrowed_iterator_t<_Range1>
269	operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
270	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
271	{
272	return (*this)(ranges::begin(__r1), ranges::end(__r1),
273	ranges::begin(__r2), ranges::end(__r2),
274	std::move(__pred),
275	std::move(__proj1), std::move(__proj2));
276	}
277	};
278
279	inline constexpr __find_first_of_fn find_first_of{};
280
281	struct __count_fn
282	{
283	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
284	typename _Tp, typename _Proj = identity>
285	requires indirect_binary_predicate<ranges::equal_to,
286	projected<_Iter, _Proj>,
287	const _Tp*>
288	constexpr iter_difference_t<_Iter>
289	operator()(_Iter __first, _Sent __last,
290	const _Tp& __value, _Proj __proj = {}) const
291	{
292	iter_difference_t<_Iter> __n = 0;
293	for (; __first != __last; ++__first)
294	if (std::__invoke(__proj, *__first) == __value)
295	++__n;
296	return __n;
297	}
298
299	template<input_range _Range, typename _Tp, typename _Proj = identity>
300	requires indirect_binary_predicate<ranges::equal_to,
301	projected<iterator_t<_Range>, _Proj>,
302	const _Tp*>
303	constexpr range_difference_t<_Range>
304	operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
305	{
306	return (*this)(ranges::begin(__r), ranges::end(__r),
307	__value, std::move(__proj));
308	}
309	};
310
311	inline constexpr __count_fn count{};
312
313	struct __count_if_fn
314	{
315	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
316	typename _Proj = identity,
317	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
318	constexpr iter_difference_t<_Iter>
319	operator()(_Iter __first, _Sent __last,
320	_Pred __pred, _Proj __proj = {}) const
321	{
322	iter_difference_t<_Iter> __n = 0;
323	for (; __first != __last; ++__first)
324	if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
325	++__n;
326	return __n;
327	}
328
329	template<input_range _Range,
330	typename _Proj = identity,
331	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
332	_Pred>
333	constexpr range_difference_t<_Range>
334	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
335	{
336	return (*this)(ranges::begin(__r), ranges::end(__r),
337	std::move(__pred), std::move(__proj));
338	}
339	};
340
341	inline constexpr __count_if_fn count_if{};
342
343	// in_in_result, mismatch and search are defined in <bits/ranges_util.h>.
344
345	struct __search_n_fn
346	{
347	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
348	typename _Pred = ranges::equal_to, typename _Proj = identity>
349	requires indirectly_comparable<_Iter, const _Tp*, _Pred, _Proj>
350	constexpr subrange<_Iter>
351	operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __count,
352	const _Tp& __value, _Pred __pred = {}, _Proj __proj = {}) const
353	{
354	if (__count <= 0)
355	return {__first, __first};
356
357	auto __value_comp = [&] <typename _Rp> (_Rp&& __arg) -> bool {
358	return std::__invoke(__pred, std::forward<_Rp>(__arg), __value);
359	};
360	if (__count == 1)
361	{
362	__first = ranges::find_if(std::move(__first), __last,
363	std::move(__value_comp),
364	std::move(__proj));
365	if (__first == __last)
366	return {__first, __first};
367	else
368	{
369	auto __end = __first;
370	return {__first, ++__end};
371	}
372	}
373
374	if constexpr (sized_sentinel_for<_Sent, _Iter>
375	&& random_access_iterator<_Iter>)
376	{
377	auto __tail_size = __last - __first;
378	auto __remainder = __count;
379
380	while (__remainder <= __tail_size)
381	{
382	__first += __remainder;
383	__tail_size -= __remainder;
384	auto __backtrack = __first;
385	while (__value_comp(std::__invoke(__proj, *--__backtrack)))
386	{
387	if (--__remainder == 0)
388	return {__first - __count, __first};
389	}
390	__remainder = __count + 1 - (__first - __backtrack);
391	}
392	auto __i = __first + __tail_size;
393	return {__i, __i};
394	}
395	else
396	{
397	__first = ranges::find_if(__first, __last, __value_comp, __proj);
398	while (__first != __last)
399	{
400	auto __n = __count;
401	auto __i = __first;
402	++__i;
403	while (__i != __last && __n != 1
404	&& __value_comp(std::__invoke(__proj, *__i)))
405	{
406	++__i;
407	--__n;
408	}
409	if (__n == 1)
410	return {__first, __i};
411	if (__i == __last)
412	return {__i, __i};
413	__first = ranges::find_if(++__i, __last, __value_comp, __proj);
414	}
415	return {__first, __first};
416	}
417	}
418
419	template<forward_range _Range, typename _Tp,
420	typename _Pred = ranges::equal_to, typename _Proj = identity>
421	requires indirectly_comparable<iterator_t<_Range>, const _Tp*,
422	_Pred, _Proj>
423	constexpr borrowed_subrange_t<_Range>
424	operator()(_Range&& __r, range_difference_t<_Range> __count,
425	const _Tp& __value, _Pred __pred = {}, _Proj __proj = {}) const
426	{
427	return (*this)(ranges::begin(__r), ranges::end(__r),
428	std::move(__count), __value,
429	std::move(__pred), std::move(__proj));
430	}
431	};
432
433	inline constexpr __search_n_fn search_n{};
434
435	struct __find_end_fn
436	{
437	template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
438	forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
439	typename _Pred = ranges::equal_to,
440	typename _Proj1 = identity, typename _Proj2 = identity>
441	requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
442	constexpr subrange<_Iter1>
443	operator()(_Iter1 __first1, _Sent1 __last1,
444	_Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
445	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
446	{
447	if constexpr (bidirectional_iterator<_Iter1>
448	&& bidirectional_iterator<_Iter2>)
449	{
450	auto __i1 = ranges::next(__first1, __last1);
451	auto __i2 = ranges::next(__first2, __last2);
452	auto __rresult
453	= ranges::search(reverse_iterator<_Iter1>{__i1},
454	reverse_iterator<_Iter1>{__first1},
455	reverse_iterator<_Iter2>{__i2},
456	reverse_iterator<_Iter2>{__first2},
457	std::move(__pred),
458	std::move(__proj1), std::move(__proj2));
459	auto __result_first = ranges::end(__rresult).base();
460	auto __result_last = ranges::begin(__rresult).base();
461	if (__result_last == __first1)
462	return {__i1, __i1};
463	else
464	return {__result_first, __result_last};
465	}
466	else
467	{
468	auto __i = ranges::next(__first1, __last1);
469	if (__first2 == __last2)
470	return {__i, __i};
471
472	auto __result_begin = __i;
473	auto __result_end = __i;
474	for (;;)
475	{
476	auto __new_range = ranges::search(__first1, __last1,
477	__first2, __last2,
478	__pred, __proj1, __proj2);
479	auto __new_result_begin = ranges::begin(__new_range);
480	auto __new_result_end = ranges::end(__new_range);
481	if (__new_result_begin == __last1)
482	return {__result_begin, __result_end};
483	else
484	{
485	__result_begin = __new_result_begin;
486	__result_end = __new_result_end;
487	__first1 = __result_begin;
488	++__first1;
489	}
490	}
491	}
492	}
493
494	template<forward_range _Range1, forward_range _Range2,
495	typename _Pred = ranges::equal_to,
496	typename _Proj1 = identity, typename _Proj2 = identity>
497	requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
498	_Pred, _Proj1, _Proj2>
499	constexpr borrowed_subrange_t<_Range1>
500	operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
501	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
502	{
503	return (*this)(ranges::begin(__r1), ranges::end(__r1),
504	ranges::begin(__r2), ranges::end(__r2),
505	std::move(__pred),
506	std::move(__proj1), std::move(__proj2));
507	}
508	};
509
510	inline constexpr __find_end_fn find_end{};
511
512	// adjacent_find is defined in <bits/ranges_util.h>.
513
514	struct __is_permutation_fn
515	{
516	template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
517	forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
518	typename _Proj1 = identity, typename _Proj2 = identity,
519	indirect_equivalence_relation<projected<_Iter1, _Proj1>,
520	projected<_Iter2, _Proj2>> _Pred
521	= ranges::equal_to>
522	constexpr bool
523	operator()(_Iter1 __first1, _Sent1 __last1,
524	_Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
525	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
526	{
527	constexpr bool __sized_iters
528	= (sized_sentinel_for<_Sent1, _Iter1>
529	&& sized_sentinel_for<_Sent2, _Iter2>);
530	if constexpr (__sized_iters)
531	{
532	auto __d1 = ranges::distance(__first1, __last1);
533	auto __d2 = ranges::distance(__first2, __last2);
534	if (__d1 != __d2)
535	return false;
536	}
537
538	// Efficiently compare identical prefixes: O(N) if sequences
539	// have the same elements in the same order.
540	for (; __first1 != __last1 && __first2 != __last2;
541	++__first1, (void)++__first2)
542	if (!(bool)std::__invoke(__pred,
543	std::__invoke(__proj1, *__first1),
544	std::__invoke(__proj2, *__first2)))
545	break;
546
547	if constexpr (__sized_iters)
548	{
549	if (__first1 == __last1)
550	return true;
551	}
552	else
553	{
554	auto __d1 = ranges::distance(__first1, __last1);
555	auto __d2 = ranges::distance(__first2, __last2);
556	if (__d1 == 0 && __d2 == 0)
557	return true;
558	if (__d1 != __d2)
559	return false;
560	}
561
562	for (auto __scan = __first1; __scan != __last1; ++__scan)
563	{
564	auto&& __proj_scan = std::__invoke(__proj1, *__scan);
565	auto __comp_scan = [&] <typename _Tp> (_Tp&& __arg) -> bool {
566	return std::__invoke(__pred, __proj_scan,
567	std::forward<_Tp>(__arg));
568	};
569	if (__scan != ranges::find_if(__first1, __scan,
570	__comp_scan, __proj1))
571	continue; // We've seen this one before.
572
573	auto __matches = ranges::count_if(__first2, __last2,
574	__comp_scan, __proj2);
575	if (__matches == 0
576	|| ranges::count_if(__scan, __last1,
577	__comp_scan, __proj1) != __matches)
578	return false;
579	}
580	return true;
581	}
582
583	template<forward_range _Range1, forward_range _Range2,
584	typename _Proj1 = identity, typename _Proj2 = identity,
585	indirect_equivalence_relation<
586	projected<iterator_t<_Range1>, _Proj1>,
587	projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to>
588	constexpr bool
589	operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
590	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
591	{
592	return (*this)(ranges::begin(__r1), ranges::end(__r1),
593	ranges::begin(__r2), ranges::end(__r2),
594	std::move(__pred),
595	std::move(__proj1), std::move(__proj2));
596	}
597	};
598
599	inline constexpr __is_permutation_fn is_permutation{};
600
601	template<typename _Iter, typename _Out>
602	using copy_if_result = in_out_result<_Iter, _Out>;
603
604	struct __copy_if_fn
605	{
606	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
607	weakly_incrementable _Out, typename _Proj = identity,
608	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
609	requires indirectly_copyable<_Iter, _Out>
610	constexpr copy_if_result<_Iter, _Out>
611	operator()(_Iter __first, _Sent __last, _Out __result,
612	_Pred __pred, _Proj __proj = {}) const
613	{
614	for (; __first != __last; ++__first)
615	if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
616	{
617	*__result = *__first;
618	++__result;
619	}
620	return {std::move(__first), std::move(__result)};
621	}
622
623	template<input_range _Range, weakly_incrementable _Out,
624	typename _Proj = identity,
625	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
626	_Pred>
627	requires indirectly_copyable<iterator_t<_Range>, _Out>
628	constexpr copy_if_result<borrowed_iterator_t<_Range>, _Out>
629	operator()(_Range&& __r, _Out __result,
630	_Pred __pred, _Proj __proj = {}) const
631	{
632	return (*this)(ranges::begin(__r), ranges::end(__r),
633	std::move(__result),
634	std::move(__pred), std::move(__proj));
635	}
636	};
637
638	inline constexpr __copy_if_fn copy_if{};
639
640	template<typename _Iter1, typename _Iter2>
641	using swap_ranges_result = in_in_result<_Iter1, _Iter2>;
642
643	struct __swap_ranges_fn
644	{
645	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
646	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2>
647	requires indirectly_swappable<_Iter1, _Iter2>
648	constexpr swap_ranges_result<_Iter1, _Iter2>
649	operator()(_Iter1 __first1, _Sent1 __last1,
650	_Iter2 __first2, _Sent2 __last2) const
651	{
652	for (; __first1 != __last1 && __first2 != __last2;
653	++__first1, (void)++__first2)
654	ranges::iter_swap(__first1, __first2);
655	return {std::move(__first1), std::move(__first2)};
656	}
657
658	template<input_range _Range1, input_range _Range2>
659	requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>>
660	constexpr swap_ranges_result<borrowed_iterator_t<_Range1>,
661	borrowed_iterator_t<_Range2>>
662	operator()(_Range1&& __r1, _Range2&& __r2) const
663	{
664	return (*this)(ranges::begin(__r1), ranges::end(__r1),
665	ranges::begin(__r2), ranges::end(__r2));
666	}
667	};
668
669	inline constexpr __swap_ranges_fn swap_ranges{};
670
671	template<typename _Iter, typename _Out>
672	using unary_transform_result = in_out_result<_Iter, _Out>;
673
674	template<typename _Iter1, typename _Iter2, typename _Out>
675	struct in_in_out_result
676	{
677	[[no_unique_address]] _Iter1 in1;
678	[[no_unique_address]] _Iter2 in2;
679	[[no_unique_address]] _Out out;
680
681	template<typename _IIter1, typename _IIter2, typename _OOut>
682	requires convertible_to<const _Iter1&, _IIter1>
683	&& convertible_to<const _Iter2&, _IIter2>
684	&& convertible_to<const _Out&, _OOut>
685	constexpr
686	operator in_in_out_result<_IIter1, _IIter2, _OOut>() const &
687	{ return {in1, in2, out}; }
688
689	template<typename _IIter1, typename _IIter2, typename _OOut>
690	requires convertible_to<_Iter1, _IIter1>
691	&& convertible_to<_Iter2, _IIter2>
692	&& convertible_to<_Out, _OOut>
693	constexpr
694	operator in_in_out_result<_IIter1, _IIter2, _OOut>() &&
695	{ return {std::move(in1), std::move(in2), std::move(out)}; }
696	};
697
698	template<typename _Iter1, typename _Iter2, typename _Out>
699	using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>;
700
701	struct __transform_fn
702	{
703	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
704	weakly_incrementable _Out,
705	copy_constructible _Fp, typename _Proj = identity>
706	requires indirectly_writable<_Out,
707	indirect_result_t<_Fp&,
708	projected<_Iter, _Proj>>>
709	constexpr unary_transform_result<_Iter, _Out>
710	operator()(_Iter __first1, _Sent __last1, _Out __result,
711	_Fp __op, _Proj __proj = {}) const
712	{
713	for (; __first1 != __last1; ++__first1, (void)++__result)
714	*__result = std::__invoke(__op, std::__invoke(__proj, *__first1));
715	return {std::move(__first1), std::move(__result)};
716	}
717
718	template<input_range _Range, weakly_incrementable _Out,
719	copy_constructible _Fp, typename _Proj = identity>
720	requires indirectly_writable<_Out,
721	indirect_result_t<_Fp&,
722	projected<iterator_t<_Range>, _Proj>>>
723	constexpr unary_transform_result<borrowed_iterator_t<_Range>, _Out>
724	operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {}) const
725	{
726	return (*this)(ranges::begin(__r), ranges::end(__r),
727	std::move(__result),
728	std::move(__op), std::move(__proj));
729	}
730
731	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
732	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
733	weakly_incrementable _Out, copy_constructible _Fp,
734	typename _Proj1 = identity, typename _Proj2 = identity>
735	requires indirectly_writable<_Out,
736	indirect_result_t<_Fp&,
737	projected<_Iter1, _Proj1>,
738	projected<_Iter2, _Proj2>>>
739	constexpr binary_transform_result<_Iter1, _Iter2, _Out>
740	operator()(_Iter1 __first1, _Sent1 __last1,
741	_Iter2 __first2, _Sent2 __last2,
742	_Out __result, _Fp __binary_op,
743	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
744	{
745	for (; __first1 != __last1 && __first2 != __last2;
746	++__first1, (void)++__first2, ++__result)
747	*__result = std::__invoke(__binary_op,
748	std::__invoke(__proj1, *__first1),
749	std::__invoke(__proj2, *__first2));
750	return {std::move(__first1), std::move(__first2), std::move(__result)};
751	}
752
753	template<input_range _Range1, input_range _Range2,
754	weakly_incrementable _Out, copy_constructible _Fp,
755	typename _Proj1 = identity, typename _Proj2 = identity>
756	requires indirectly_writable<_Out,
757	indirect_result_t<_Fp&,
758	projected<iterator_t<_Range1>, _Proj1>,
759	projected<iterator_t<_Range2>, _Proj2>>>
760	constexpr binary_transform_result<borrowed_iterator_t<_Range1>,
761	borrowed_iterator_t<_Range2>, _Out>
762	operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op,
763	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
764	{
765	return (*this)(ranges::begin(__r1), ranges::end(__r1),
766	ranges::begin(__r2), ranges::end(__r2),
767	std::move(__result), std::move(__binary_op),
768	std::move(__proj1), std::move(__proj2));
769	}
770	};
771
772	inline constexpr __transform_fn transform{};
773
774	struct __replace_fn
775	{
776	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
777	typename _Tp1, typename _Tp2, typename _Proj = identity>
778	requires indirectly_writable<_Iter, const _Tp2&>
779	&& indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
780	const _Tp1*>
781	constexpr _Iter
782	operator()(_Iter __first, _Sent __last,
783	const _Tp1& __old_value, const _Tp2& __new_value,
784	_Proj __proj = {}) const
785	{
786	for (; __first != __last; ++__first)
787	if (std::__invoke(__proj, *__first) == __old_value)
788	*__first = __new_value;
789	return __first;
790	}
791
792	template<input_range _Range,
793	typename _Tp1, typename _Tp2, typename _Proj = identity>
794	requires indirectly_writable<iterator_t<_Range>, const _Tp2&>
795	&& indirect_binary_predicate<ranges::equal_to,
796	projected<iterator_t<_Range>, _Proj>,
797	const _Tp1*>
798	constexpr borrowed_iterator_t<_Range>
799	operator()(_Range&& __r,
800	const _Tp1& __old_value, const _Tp2& __new_value,
801	_Proj __proj = {}) const
802	{
803	return (*this)(ranges::begin(__r), ranges::end(__r),
804	__old_value, __new_value, std::move(__proj));
805	}
806	};
807
808	inline constexpr __replace_fn replace{};
809
810	struct __replace_if_fn
811	{
812	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
813	typename _Tp, typename _Proj = identity,
814	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
815	requires indirectly_writable<_Iter, const _Tp&>
816	constexpr _Iter
817	operator()(_Iter __first, _Sent __last,
818	_Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
819	{
820	for (; __first != __last; ++__first)
821	if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
822	*__first = __new_value;
823	return std::move(__first);
824	}
825
826	template<input_range _Range, typename _Tp, typename _Proj = identity,
827	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
828	_Pred>
829	requires indirectly_writable<iterator_t<_Range>, const _Tp&>
830	constexpr borrowed_iterator_t<_Range>
831	operator()(_Range&& __r,
832	_Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
833	{
834	return (*this)(ranges::begin(__r), ranges::end(__r),
835	std::move(__pred), __new_value, std::move(__proj));
836	}
837	};
838
839	inline constexpr __replace_if_fn replace_if{};
840
841	template<typename _Iter, typename _Out>
842	using replace_copy_result = in_out_result<_Iter, _Out>;
843
844	struct __replace_copy_fn
845	{
846	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
847	typename _Tp1, typename _Tp2, output_iterator<const _Tp2&> _Out,
848	typename _Proj = identity>
849	requires indirectly_copyable<_Iter, _Out>
850	&& indirect_binary_predicate<ranges::equal_to,
851	projected<_Iter, _Proj>, const _Tp1*>
852	constexpr replace_copy_result<_Iter, _Out>
853	operator()(_Iter __first, _Sent __last, _Out __result,
854	const _Tp1& __old_value, const _Tp2& __new_value,
855	_Proj __proj = {}) const
856	{
857	for (; __first != __last; ++__first, (void)++__result)
858	if (std::__invoke(__proj, *__first) == __old_value)
859	*__result = __new_value;
860	else
861	*__result = *__first;
862	return {std::move(__first), std::move(__result)};
863	}
864
865	template<input_range _Range, typename _Tp1, typename _Tp2,
866	output_iterator<const _Tp2&> _Out, typename _Proj = identity>
867	requires indirectly_copyable<iterator_t<_Range>, _Out>
868	&& indirect_binary_predicate<ranges::equal_to,
869	projected<iterator_t<_Range>, _Proj>,
870	const _Tp1*>
871	constexpr replace_copy_result<borrowed_iterator_t<_Range>, _Out>
872	operator()(_Range&& __r, _Out __result,
873	const _Tp1& __old_value, const _Tp2& __new_value,
874	_Proj __proj = {}) const
875	{
876	return (*this)(ranges::begin(__r), ranges::end(__r),
877	std::move(__result), __old_value,
878	__new_value, std::move(__proj));
879	}
880	};
881
882	inline constexpr __replace_copy_fn replace_copy{};
883
884	template<typename _Iter, typename _Out>
885	using replace_copy_if_result = in_out_result<_Iter, _Out>;
886
887	struct __replace_copy_if_fn
888	{
889	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
890	typename _Tp, output_iterator<const _Tp&> _Out,
891	typename _Proj = identity,
892	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
893	requires indirectly_copyable<_Iter, _Out>
894	constexpr replace_copy_if_result<_Iter, _Out>
895	operator()(_Iter __first, _Sent __last, _Out __result,
896	_Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
897	{
898	for (; __first != __last; ++__first, (void)++__result)
899	if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
900	*__result = __new_value;
901	else
902	*__result = *__first;
903	return {std::move(__first), std::move(__result)};
904	}
905
906	template<input_range _Range,
907	typename _Tp, output_iterator<const _Tp&> _Out,
908	typename _Proj = identity,
909	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
910	_Pred>
911	requires indirectly_copyable<iterator_t<_Range>, _Out>
912	constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _Out>
913	operator()(_Range&& __r, _Out __result,
914	_Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
915	{
916	return (*this)(ranges::begin(__r), ranges::end(__r),
917	std::move(__result), std::move(__pred),
918	__new_value, std::move(__proj));
919	}
920	};
921
922	inline constexpr __replace_copy_if_fn replace_copy_if{};
923
924	struct __generate_n_fn
925	{
926	template<input_or_output_iterator _Out, copy_constructible _Fp>
927	requires invocable<_Fp&>
928	&& indirectly_writable<_Out, invoke_result_t<_Fp&>>
929	constexpr _Out
930	operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen) const
931	{
932	for (; __n > 0; --__n, (void)++__first)
933	*__first = std::__invoke(__gen);
934	return __first;
935	}
936	};
937
938	inline constexpr __generate_n_fn generate_n{};
939
940	struct __generate_fn
941	{
942	template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent,
943	copy_constructible _Fp>
944	requires invocable<_Fp&>
945	&& indirectly_writable<_Out, invoke_result_t<_Fp&>>
946	constexpr _Out
947	operator()(_Out __first, _Sent __last, _Fp __gen) const
948	{
949	for (; __first != __last; ++__first)
950	*__first = std::__invoke(__gen);
951	return __first;
952	}
953
954	template<typename _Range, copy_constructible _Fp>
955	requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>>
956	constexpr borrowed_iterator_t<_Range>
957	operator()(_Range&& __r, _Fp __gen) const
958	{
959	return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__gen));
960	}
961	};
962
963	inline constexpr __generate_fn generate{};
964
965	struct __remove_if_fn
966	{
967	template<permutable _Iter, sentinel_for<_Iter> _Sent,
968	typename _Proj = identity,
969	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
970	constexpr subrange<_Iter>
971	operator()(_Iter __first, _Sent __last,
972	_Pred __pred, _Proj __proj = {}) const
973	{
974	__first = ranges::find_if(__first, __last, __pred, __proj);
975	if (__first == __last)
976	return {__first, __first};
977
978	auto __result = __first;
979	++__first;
980	for (; __first != __last; ++__first)
981	if (!std::__invoke(__pred, std::__invoke(__proj, *__first)))
982	{
983	*__result = std::move(*__first);
984	++__result;
985	}
986
987	return {__result, __first};
988	}
989
990	template<forward_range _Range, typename _Proj = identity,
991	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
992	_Pred>
993	requires permutable<iterator_t<_Range>>
994	constexpr borrowed_subrange_t<_Range>
995	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
996	{
997	return (*this)(ranges::begin(__r), ranges::end(__r),
998	std::move(__pred), std::move(__proj));
999	}
1000	};
1001
1002	inline constexpr __remove_if_fn remove_if{};
1003
1004	struct __remove_fn
1005	{
1006	template<permutable _Iter, sentinel_for<_Iter> _Sent,
1007	typename _Tp, typename _Proj = identity>
1008	requires indirect_binary_predicate<ranges::equal_to,
1009	projected<_Iter, _Proj>,
1010	const _Tp*>
1011	constexpr subrange<_Iter>
1012	operator()(_Iter __first, _Sent __last,
1013	const _Tp& __value, _Proj __proj = {}) const
1014	{
1015	auto __pred = [&] (auto&& __arg) -> bool {
1016	return std::forward<decltype(__arg)>(__arg) == __value;
1017	};
1018	return ranges::remove_if(__first, __last,
1019	std::move(__pred), std::move(__proj));
1020	}
1021
1022	template<forward_range _Range, typename _Tp, typename _Proj = identity>
1023	requires permutable<iterator_t<_Range>>
1024	&& indirect_binary_predicate<ranges::equal_to,
1025	projected<iterator_t<_Range>, _Proj>,
1026	const _Tp*>
1027	constexpr borrowed_subrange_t<_Range>
1028	operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
1029	{
1030	return (*this)(ranges::begin(__r), ranges::end(__r),
1031	__value, std::move(__proj));
1032	}
1033	};
1034
1035	inline constexpr __remove_fn remove{};
1036
1037	template<typename _Iter, typename _Out>
1038	using remove_copy_if_result = in_out_result<_Iter, _Out>;
1039
1040	struct __remove_copy_if_fn
1041	{
1042	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1043	weakly_incrementable _Out, typename _Proj = identity,
1044	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1045	requires indirectly_copyable<_Iter, _Out>
1046	constexpr remove_copy_if_result<_Iter, _Out>
1047	operator()(_Iter __first, _Sent __last, _Out __result,
1048	_Pred __pred, _Proj __proj = {}) const
1049	{
1050	for (; __first != __last; ++__first)
1051	if (!std::__invoke(__pred, std::__invoke(__proj, *__first)))
1052	{
1053	*__result = *__first;
1054	++__result;
1055	}
1056	return {std::move(__first), std::move(__result)};
1057	}
1058
1059	template<input_range _Range, weakly_incrementable _Out,
1060	typename _Proj = identity,
1061	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1062	_Pred>
1063	requires indirectly_copyable<iterator_t<_Range>, _Out>
1064	constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _Out>
1065	operator()(_Range&& __r, _Out __result,
1066	_Pred __pred, _Proj __proj = {}) const
1067	{
1068	return (*this)(ranges::begin(__r), ranges::end(__r),
1069	std::move(__result),
1070	std::move(__pred), std::move(__proj));
1071	}
1072	};
1073
1074	inline constexpr __remove_copy_if_fn remove_copy_if{};
1075
1076	template<typename _Iter, typename _Out>
1077	using remove_copy_result = in_out_result<_Iter, _Out>;
1078
1079	struct __remove_copy_fn
1080	{
1081	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1082	weakly_incrementable _Out, typename _Tp, typename _Proj = identity>
1083	requires indirectly_copyable<_Iter, _Out>
1084	&& indirect_binary_predicate<ranges::equal_to,
1085	projected<_Iter, _Proj>,
1086	const _Tp*>
1087	constexpr remove_copy_result<_Iter, _Out>
1088	operator()(_Iter __first, _Sent __last, _Out __result,
1089	const _Tp& __value, _Proj __proj = {}) const
1090	{
1091	for (; __first != __last; ++__first)
1092	if (!(std::__invoke(__proj, *__first) == __value))
1093	{
1094	*__result = *__first;
1095	++__result;
1096	}
1097	return {std::move(__first), std::move(__result)};
1098	}
1099
1100	template<input_range _Range, weakly_incrementable _Out,
1101	typename _Tp, typename _Proj = identity>
1102	requires indirectly_copyable<iterator_t<_Range>, _Out>
1103	&& indirect_binary_predicate<ranges::equal_to,
1104	projected<iterator_t<_Range>, _Proj>,
1105	const _Tp*>
1106	constexpr remove_copy_result<borrowed_iterator_t<_Range>, _Out>
1107	operator()(_Range&& __r, _Out __result,
1108	const _Tp& __value, _Proj __proj = {}) const
1109	{
1110	return (*this)(ranges::begin(__r), ranges::end(__r),
1111	std::move(__result), __value, std::move(__proj));
1112	}
1113	};
1114
1115	inline constexpr __remove_copy_fn remove_copy{};
1116
1117	struct __unique_fn
1118	{
1119	template<permutable _Iter, sentinel_for<_Iter> _Sent,
1120	typename _Proj = identity,
1121	indirect_equivalence_relation<
1122	projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1123	constexpr subrange<_Iter>
1124	operator()(_Iter __first, _Sent __last,
1125	_Comp __comp = {}, _Proj __proj = {}) const
1126	{
1127	__first = ranges::adjacent_find(__first, __last, __comp, __proj);
1128	if (__first == __last)
1129	return {__first, __first};
1130
1131	auto __dest = __first;
1132	++__first;
1133	while (++__first != __last)
1134	if (!std::__invoke(__comp,
1135	std::__invoke(__proj, *__dest),
1136	std::__invoke(__proj, *__first)))
1137	*++__dest = std::move(*__first);
1138	return {++__dest, __first};
1139	}
1140
1141	template<forward_range _Range, typename _Proj = identity,
1142	indirect_equivalence_relation<
1143	projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1144	requires permutable<iterator_t<_Range>>
1145	constexpr borrowed_subrange_t<_Range>
1146	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1147	{
1148	return (*this)(ranges::begin(__r), ranges::end(__r),
1149	std::move(__comp), std::move(__proj));
1150	}
1151	};
1152
1153	inline constexpr __unique_fn unique{};
1154
1155	namespace __detail
1156	{
1157	template<typename _Out, typename _Tp>
1158	concept __can_reread_output = input_iterator<_Out>
1159	&& same_as<_Tp, iter_value_t<_Out>>;
1160	}
1161
1162	template<typename _Iter, typename _Out>
1163	using unique_copy_result = in_out_result<_Iter, _Out>;
1164
1165	struct __unique_copy_fn
1166	{
1167	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1168	weakly_incrementable _Out, typename _Proj = identity,
1169	indirect_equivalence_relation<
1170	projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1171	requires indirectly_copyable<_Iter, _Out>
1172	&& (forward_iterator<_Iter>
1173	|| __detail::__can_reread_output<_Out, iter_value_t<_Iter>>
1174	|| indirectly_copyable_storable<_Iter, _Out>)
1175	constexpr unique_copy_result<_Iter, _Out>
1176	operator()(_Iter __first, _Sent __last, _Out __result,
1177	_Comp __comp = {}, _Proj __proj = {}) const
1178	{
1179	if (__first == __last)
1180	return {std::move(__first), std::move(__result)};
1181
1182	// TODO: perform a closer comparison with reference implementations
1183	if constexpr (forward_iterator<_Iter>)
1184	{
1185	auto __next = __first;
1186	*__result = *__next;
1187	while (++__next != __last)
1188	if (!std::__invoke(__comp,
1189	std::__invoke(__proj, *__first),
1190	std::__invoke(__proj, *__next)))
1191	{
1192	__first = __next;
1193	*++__result = *__first;
1194	}
1195	return {__next, std::move(++__result)};
1196	}
1197	else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>)
1198	{
1199	*__result = *__first;
1200	while (++__first != __last)
1201	if (!std::__invoke(__comp,
1202	std::__invoke(__proj, *__result),
1203	std::__invoke(__proj, *__first)))
1204	*++__result = *__first;
1205	return {std::move(__first), std::move(++__result)};
1206	}
1207	else // indirectly_copyable_storable<_Iter, _Out>
1208	{
1209	auto __value = *__first;
1210	*__result = __value;
1211	while (++__first != __last)
1212	{
1213	if (!(bool)std::__invoke(__comp,
1214	std::__invoke(__proj, *__first),
1215	std::__invoke(__proj, __value)))
1216	{
1217	__value = *__first;
1218	*++__result = __value;
1219	}
1220	}
1221	return {std::move(__first), std::move(++__result)};
1222	}
1223	}
1224
1225	template<input_range _Range,
1226	weakly_incrementable _Out, typename _Proj = identity,
1227	indirect_equivalence_relation<
1228	projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1229	requires indirectly_copyable<iterator_t<_Range>, _Out>
1230	&& (forward_iterator<iterator_t<_Range>>
1231	|| __detail::__can_reread_output<_Out, range_value_t<_Range>>
1232	|| indirectly_copyable_storable<iterator_t<_Range>, _Out>)
1233	constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out>
1234	operator()(_Range&& __r, _Out __result,
1235	_Comp __comp = {}, _Proj __proj = {}) const
1236	{
1237	return (*this)(ranges::begin(__r), ranges::end(__r),
1238	std::move(__result),
1239	std::move(__comp), std::move(__proj));
1240	}
1241	};
1242
1243	inline constexpr __unique_copy_fn unique_copy{};
1244
1245	struct __reverse_fn
1246	{
1247	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
1248	requires permutable<_Iter>
1249	constexpr _Iter
1250	operator()(_Iter __first, _Sent __last) const
1251	{
1252	auto __i = ranges::next(__first, __last);
1253	auto __tail = __i;
1254
1255	if constexpr (random_access_iterator<_Iter>)
1256	{
1257	if (__first != __last)
1258	{
1259	--__tail;
1260	while (__first < __tail)
1261	{
1262	ranges::iter_swap(__first, __tail);
1263	++__first;
1264	--__tail;
1265	}
1266	}
1267	return __i;
1268	}
1269	else
1270	{
1271	for (;;)
1272	if (__first == __tail || __first == --__tail)
1273	break;
1274	else
1275	{
1276	ranges::iter_swap(__first, __tail);
1277	++__first;
1278	}
1279	return __i;
1280	}
1281	}
1282
1283	template<bidirectional_range _Range>
1284	requires permutable<iterator_t<_Range>>
1285	constexpr borrowed_iterator_t<_Range>
1286	operator()(_Range&& __r) const
1287	{
1288	return (*this)(ranges::begin(__r), ranges::end(__r));
1289	}
1290	};
1291
1292	inline constexpr __reverse_fn reverse{};
1293
1294	template<typename _Iter, typename _Out>
1295	using reverse_copy_result = in_out_result<_Iter, _Out>;
1296
1297	struct __reverse_copy_fn
1298	{
1299	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
1300	weakly_incrementable _Out>
1301	requires indirectly_copyable<_Iter, _Out>
1302	constexpr reverse_copy_result<_Iter, _Out>
1303	operator()(_Iter __first, _Sent __last, _Out __result) const
1304	{
1305	auto __i = ranges::next(__first, __last);
1306	auto __tail = __i;
1307	while (__first != __tail)
1308	{
1309	--__tail;
1310	*__result = *__tail;
1311	++__result;
1312	}
1313	return {__i, std::move(__result)};
1314	}
1315
1316	template<bidirectional_range _Range, weakly_incrementable _Out>
1317	requires indirectly_copyable<iterator_t<_Range>, _Out>
1318	constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out>
1319	operator()(_Range&& __r, _Out __result) const
1320	{
1321	return (*this)(ranges::begin(__r), ranges::end(__r),
1322	std::move(__result));
1323	}
1324	};
1325
1326	inline constexpr __reverse_copy_fn reverse_copy{};
1327
1328	struct __rotate_fn
1329	{
1330	template<permutable _Iter, sentinel_for<_Iter> _Sent>
1331	constexpr subrange<_Iter>
1332	operator()(_Iter __first, _Iter __middle, _Sent __last) const
1333	{
1334	auto __lasti = ranges::next(__first, __last);
1335	if (__first == __middle)
1336	return {__lasti, __lasti};
1337	if (__last == __middle)
1338	return {std::move(__first), std::move(__lasti)};
1339
1340	if constexpr (random_access_iterator<_Iter>)
1341	{
1342	auto __n = __lasti - __first;
1343	auto __k = __middle - __first;
1344
1345	if (__k == __n - __k)
1346	{
1347	ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
1348	return {std::move(__middle), std::move(__lasti)};
1349	}
1350
1351	auto __p = __first;
1352	auto __ret = __first + (__lasti - __middle);
1353
1354	for (;;)
1355	{
1356	if (__k < __n - __k)
1357	{
1358	// TODO: is_pod is deprecated, but this condition is
1359	// consistent with the STL implementation.
1360	if constexpr (__is_pod(iter_value_t<_Iter>))
1361	if (__k == 1)
1362	{
1363	auto __t = std::move(*__p);
1364	ranges::move(__p + 1, __p + __n, __p);
1365	*(__p + __n - 1) = std::move(__t);
1366	return {std::move(__ret), std::move(__lasti)};
1367	}
1368	auto __q = __p + __k;
1369	for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1370	{
1371	ranges::iter_swap(__p, __q);
1372	++__p;
1373	++__q;
1374	}
1375	__n %= __k;
1376	if (__n == 0)
1377	return {std::move(__ret), std::move(__lasti)};
1378	ranges::swap(__n, __k);
1379	__k = __n - __k;
1380	}
1381	else
1382	{
1383	__k = __n - __k;
1384	// TODO: is_pod is deprecated, but this condition is
1385	// consistent with the STL implementation.
1386	if constexpr (__is_pod(iter_value_t<_Iter>))
1387	if (__k == 1)
1388	{
1389	auto __t = std::move(*(__p + __n - 1));
1390	ranges::move_backward(__p, __p + __n - 1, __p + __n);
1391	*__p = std::move(__t);
1392	return {std::move(__ret), std::move(__lasti)};
1393	}
1394	auto __q = __p + __n;
1395	__p = __q - __k;
1396	for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1397	{
1398	--__p;
1399	--__q;
1400	ranges::iter_swap(__p, __q);
1401	}
1402	__n %= __k;
1403	if (__n == 0)
1404	return {std::move(__ret), std::move(__lasti)};
1405	std::swap(__n, __k);
1406	}
1407	}
1408	}
1409	else if constexpr (bidirectional_iterator<_Iter>)
1410	{
1411	auto __tail = __lasti;
1412
1413	ranges::reverse(__first, __middle);
1414	ranges::reverse(__middle, __tail);
1415
1416	while (__first != __middle && __middle != __tail)
1417	{
1418	ranges::iter_swap(__first, --__tail);
1419	++__first;
1420	}
1421
1422	if (__first == __middle)
1423	{
1424	ranges::reverse(__middle, __tail);
1425	return {std::move(__tail), std::move(__lasti)};
1426	}
1427	else
1428	{
1429	ranges::reverse(__first, __middle);
1430	return {std::move(__first), std::move(__lasti)};
1431	}
1432	}
1433	else
1434	{
1435	auto __first2 = __middle;
1436	do
1437	{
1438	ranges::iter_swap(__first, __first2);
1439	++__first;
1440	++__first2;
1441	if (__first == __middle)
1442	__middle = __first2;
1443	} while (__first2 != __last);
1444
1445	auto __ret = __first;
1446
1447	__first2 = __middle;
1448
1449	while (__first2 != __last)
1450	{
1451	ranges::iter_swap(__first, __first2);
1452	++__first;
1453	++__first2;
1454	if (__first == __middle)
1455	__middle = __first2;
1456	else if (__first2 == __last)
1457	__first2 = __middle;
1458	}
1459	return {std::move(__ret), std::move(__lasti)};
1460	}
1461	}
1462
1463	template<forward_range _Range>
1464	requires permutable<iterator_t<_Range>>
1465	constexpr borrowed_subrange_t<_Range>
1466	operator()(_Range&& __r, iterator_t<_Range> __middle) const
1467	{
1468	return (*this)(ranges::begin(__r), std::move(__middle),
1469	ranges::end(__r));
1470	}
1471	};
1472
1473	inline constexpr __rotate_fn rotate{};
1474
1475	template<typename _Iter, typename _Out>
1476	using rotate_copy_result = in_out_result<_Iter, _Out>;
1477
1478	struct __rotate_copy_fn
1479	{
1480	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1481	weakly_incrementable _Out>
1482	requires indirectly_copyable<_Iter, _Out>
1483	constexpr rotate_copy_result<_Iter, _Out>
1484	operator()(_Iter __first, _Iter __middle, _Sent __last,
1485	_Out __result) const
1486	{
1487	auto __copy1 = ranges::copy(__middle,
1488	std::move(__last),
1489	std::move(__result));
1490	auto __copy2 = ranges::copy(std::move(__first),
1491	std::move(__middle),
1492	std::move(__copy1.out));
1493	return { std::move(__copy1.in), std::move(__copy2.out) };
1494	}
1495
1496	template<forward_range _Range, weakly_incrementable _Out>
1497	requires indirectly_copyable<iterator_t<_Range>, _Out>
1498	constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out>
1499	operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result) const
1500	{
1501	return (*this)(ranges::begin(__r), std::move(__middle),
1502	ranges::end(__r), std::move(__result));
1503	}
1504	};
1505
1506	inline constexpr __rotate_copy_fn rotate_copy{};
1507
1508	struct __sample_fn
1509	{
1510	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1511	weakly_incrementable _Out, typename _Gen>
1512	requires (forward_iterator<_Iter> || random_access_iterator<_Out>)
1513	&& indirectly_copyable<_Iter, _Out>
1514	&& uniform_random_bit_generator<remove_reference_t<_Gen>>
1515	_Out
1516	operator()(_Iter __first, _Sent __last, _Out __out,
1517	iter_difference_t<_Iter> __n, _Gen&& __g) const
1518	{
1519	if constexpr (forward_iterator<_Iter>)
1520	{
1521	// FIXME: Forwarding to std::sample here requires computing __lasti
1522	// which may take linear time.
1523	auto __lasti = ranges::next(__first, __last);
1524	return _GLIBCXX_STD_A::
1525	sample(std::move(__first), std::move(__lasti), std::move(__out),
1526	__n, std::forward<_Gen>(__g));
1527	}
1528	else
1529	{
1530	using __distrib_type
1531	= uniform_int_distribution<iter_difference_t<_Iter>>;
1532	using __param_type = typename __distrib_type::param_type;
1533	__distrib_type __d{};
1534	iter_difference_t<_Iter> __sample_sz = 0;
1535	while (__first != __last && __sample_sz != __n)
1536	{
1537	__out[__sample_sz++] = *__first;
1538	++__first;
1539	}
1540	for (auto __pop_sz = __sample_sz; __first != __last;
1541	++__first, (void) ++__pop_sz)
1542	{
1543	const auto __k = __d(__g, __param_type{0, __pop_sz});
1544	if (__k < __n)
1545	__out[__k] = *__first;
1546	}
1547	return __out + __sample_sz;
1548	}
1549	}
1550
1551	template<input_range _Range, weakly_incrementable _Out, typename _Gen>
1552	requires (forward_range<_Range> || random_access_iterator<_Out>)
1553	&& indirectly_copyable<iterator_t<_Range>, _Out>
1554	&& uniform_random_bit_generator<remove_reference_t<_Gen>>
1555	_Out
1556	operator()(_Range&& __r, _Out __out,
1557	range_difference_t<_Range> __n, _Gen&& __g) const
1558	{
1559	return (*this)(ranges::begin(__r), ranges::end(__r),
1560	std::move(__out), __n,
1561	std::forward<_Gen>(__g));
1562	}
1563	};
1564
1565	inline constexpr __sample_fn sample{};
1566
1567	#ifdef _GLIBCXX_USE_C99_STDINT_TR1
1568	struct __shuffle_fn
1569	{
1570	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1571	typename _Gen>
1572	requires permutable<_Iter>
1573	&& uniform_random_bit_generator<remove_reference_t<_Gen>>
1574	_Iter
1575	operator()(_Iter __first, _Sent __last, _Gen&& __g) const
1576	{
1577	auto __lasti = ranges::next(__first, __last);
1578	std::shuffle(std::move(__first), __lasti, std::forward<_Gen>(__g));
1579	return __lasti;
1580	}
1581
1582	template<random_access_range _Range, typename _Gen>
1583	requires permutable<iterator_t<_Range>>
1584	&& uniform_random_bit_generator<remove_reference_t<_Gen>>
1585	borrowed_iterator_t<_Range>
1586	operator()(_Range&& __r, _Gen&& __g) const
1587	{
1588	return (*this)(ranges::begin(__r), ranges::end(__r),
1589	std::forward<_Gen>(__g));
1590	}
1591	};
1592
1593	inline constexpr __shuffle_fn shuffle{};
1594	#endif
1595
1596	struct __push_heap_fn
1597	{
1598	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1599	typename _Comp = ranges::less, typename _Proj = identity>
1600	requires sortable<_Iter, _Comp, _Proj>
1601	constexpr _Iter
1602	operator()(_Iter __first, _Sent __last,
1603	_Comp __comp = {}, _Proj __proj = {}) const
1604	{
1605	auto __lasti = ranges::next(__first, __last);
1606	std::push_heap(__first, __lasti,
1607	__detail::__make_comp_proj(__comp, __proj));
1608	return __lasti;
1609	}
1610
1611	template<random_access_range _Range,
1612	typename _Comp = ranges::less, typename _Proj = identity>
1613	requires sortable<iterator_t<_Range>, _Comp, _Proj>
1614	constexpr borrowed_iterator_t<_Range>
1615	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1616	{
1617	return (*this)(ranges::begin(__r), ranges::end(__r),
1618	std::move(__comp), std::move(__proj));
1619	}
1620	};
1621
1622	inline constexpr __push_heap_fn push_heap{};
1623
1624	struct __pop_heap_fn
1625	{
1626	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1627	typename _Comp = ranges::less, typename _Proj = identity>
1628	requires sortable<_Iter, _Comp, _Proj>
1629	constexpr _Iter
1630	operator()(_Iter __first, _Sent __last,
1631	_Comp __comp = {}, _Proj __proj = {}) const
1632	{
1633	auto __lasti = ranges::next(__first, __last);
1634	std::pop_heap(__first, __lasti,
1635	__detail::__make_comp_proj(__comp, __proj));
1636	return __lasti;
1637	}
1638
1639	template<random_access_range _Range,
1640	typename _Comp = ranges::less, typename _Proj = identity>
1641	requires sortable<iterator_t<_Range>, _Comp, _Proj>
1642	constexpr borrowed_iterator_t<_Range>
1643	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1644	{
1645	return (*this)(ranges::begin(__r), ranges::end(__r),
1646	std::move(__comp), std::move(__proj));
1647	}
1648	};
1649
1650	inline constexpr __pop_heap_fn pop_heap{};
1651
1652	struct __make_heap_fn
1653	{
1654	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1655	typename _Comp = ranges::less, typename _Proj = identity>
1656	requires sortable<_Iter, _Comp, _Proj>
1657	constexpr _Iter
1658	operator()(_Iter __first, _Sent __last,
1659	_Comp __comp = {}, _Proj __proj = {}) const
1660	{
1661	auto __lasti = ranges::next(__first, __last);
1662	std::make_heap(__first, __lasti,
1663	__detail::__make_comp_proj(__comp, __proj));
1664	return __lasti;
1665	}
1666
1667	template<random_access_range _Range,
1668	typename _Comp = ranges::less, typename _Proj = identity>
1669	requires sortable<iterator_t<_Range>, _Comp, _Proj>
1670	constexpr borrowed_iterator_t<_Range>
1671	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1672	{
1673	return (*this)(ranges::begin(__r), ranges::end(__r),
1674	std::move(__comp), std::move(__proj));
1675	}
1676	};
1677
1678	inline constexpr __make_heap_fn make_heap{};
1679
1680	struct __sort_heap_fn
1681	{
1682	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1683	typename _Comp = ranges::less, typename _Proj = identity>
1684	requires sortable<_Iter, _Comp, _Proj>
1685	constexpr _Iter
1686	operator()(_Iter __first, _Sent __last,
1687	_Comp __comp = {}, _Proj __proj = {}) const
1688	{
1689	auto __lasti = ranges::next(__first, __last);
1690	std::sort_heap(__first, __lasti,
1691	__detail::__make_comp_proj(__comp, __proj));
1692	return __lasti;
1693	}
1694
1695	template<random_access_range _Range,
1696	typename _Comp = ranges::less, typename _Proj = identity>
1697	requires sortable<iterator_t<_Range>, _Comp, _Proj>
1698	constexpr borrowed_iterator_t<_Range>
1699	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1700	{
1701	return (*this)(ranges::begin(__r), ranges::end(__r),
1702	std::move(__comp), std::move(__proj));
1703	}
1704	};
1705
1706	inline constexpr __sort_heap_fn sort_heap{};
1707
1708	struct __is_heap_until_fn
1709	{
1710	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1711	typename _Proj = identity,
1712	indirect_strict_weak_order<projected<_Iter, _Proj>>
1713	_Comp = ranges::less>
1714	constexpr _Iter
1715	operator()(_Iter __first, _Sent __last,
1716	_Comp __comp = {}, _Proj __proj = {}) const
1717	{
1718	iter_difference_t<_Iter> __n = ranges::distance(__first, __last);
1719	iter_difference_t<_Iter> __parent = 0, __child = 1;
1720	for (; __child < __n; ++__child)
1721	if (std::__invoke(__comp,
1722	std::__invoke(__proj, *(__first + __parent)),
1723	std::__invoke(__proj, *(__first + __child))))
1724	return __first + __child;
1725	else if ((__child & 1) == 0)
1726	++__parent;
1727
1728	return __first + __n;
1729	}
1730
1731	template<random_access_range _Range,
1732	typename _Proj = identity,
1733	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1734	_Comp = ranges::less>
1735	constexpr borrowed_iterator_t<_Range>
1736	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1737	{
1738	return (*this)(ranges::begin(__r), ranges::end(__r),
1739	std::move(__comp), std::move(__proj));
1740	}
1741	};
1742
1743	inline constexpr __is_heap_until_fn is_heap_until{};
1744
1745	struct __is_heap_fn
1746	{
1747	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1748	typename _Proj = identity,
1749	indirect_strict_weak_order<projected<_Iter, _Proj>>
1750	_Comp = ranges::less>
1751	constexpr bool
1752	operator()(_Iter __first, _Sent __last,
1753	_Comp __comp = {}, _Proj __proj = {}) const
1754	{
1755	return (__last
1756	== ranges::is_heap_until(__first, __last,
1757	std::move(__comp),
1758	std::move(__proj)));
1759	}
1760
1761	template<random_access_range _Range,
1762	typename _Proj = identity,
1763	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1764	_Comp = ranges::less>
1765	constexpr bool
1766	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1767	{
1768	return (*this)(ranges::begin(__r), ranges::end(__r),
1769	std::move(__comp), std::move(__proj));
1770	}
1771	};
1772
1773	inline constexpr __is_heap_fn is_heap{};
1774
1775	struct __sort_fn
1776	{
1777	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1778	typename _Comp = ranges::less, typename _Proj = identity>
1779	requires sortable<_Iter, _Comp, _Proj>
1780	constexpr _Iter
1781	operator()(_Iter __first, _Sent __last,
1782	_Comp __comp = {}, _Proj __proj = {}) const
1783	{
1784	auto __lasti = ranges::next(__first, __last);
1785	_GLIBCXX_STD_A::sort(std::move(__first), __lasti,
1786	__detail::__make_comp_proj(__comp, __proj));
1787	return __lasti;
1788	}
1789
1790	template<random_access_range _Range,
1791	typename _Comp = ranges::less, typename _Proj = identity>
1792	requires sortable<iterator_t<_Range>, _Comp, _Proj>
1793	constexpr borrowed_iterator_t<_Range>
1794	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1795	{
1796	return (*this)(ranges::begin(__r), ranges::end(__r),
1797	std::move(__comp), std::move(__proj));
1798	}
1799	};
1800
1801	inline constexpr __sort_fn sort{};
1802
1803	struct __stable_sort_fn
1804	{
1805	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1806	typename _Comp = ranges::less, typename _Proj = identity>
1807	requires sortable<_Iter, _Comp, _Proj>
1808	_Iter
1809	operator()(_Iter __first, _Sent __last,
1810	_Comp __comp = {}, _Proj __proj = {}) const
1811	{
1812	auto __lasti = ranges::next(__first, __last);
1813	std::stable_sort(std::move(__first), __lasti,
1814	__detail::__make_comp_proj(__comp, __proj));
1815	return __lasti;
1816	}
1817
1818	template<random_access_range _Range,
1819	typename _Comp = ranges::less, typename _Proj = identity>
1820	requires sortable<iterator_t<_Range>, _Comp, _Proj>
1821	borrowed_iterator_t<_Range>
1822	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1823	{
1824	return (*this)(ranges::begin(__r), ranges::end(__r),
1825	std::move(__comp), std::move(__proj));
1826	}
1827	};
1828
1829	inline constexpr __stable_sort_fn stable_sort{};
1830
1831	struct __partial_sort_fn
1832	{
1833	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1834	typename _Comp = ranges::less, typename _Proj = identity>
1835	requires sortable<_Iter, _Comp, _Proj>
1836	constexpr _Iter
1837	operator()(_Iter __first, _Iter __middle, _Sent __last,
1838	_Comp __comp = {}, _Proj __proj = {}) const
1839	{
1840	if (__first == __middle)
1841	return ranges::next(__first, __last);
1842
1843	ranges::make_heap(__first, __middle, __comp, __proj);
1844	auto __i = __middle;
1845	for (; __i != __last; ++__i)
1846	if (std::__invoke(__comp,
1847	std::__invoke(__proj, *__i),
1848	std::__invoke(__proj, *__first)))
1849	{
1850	ranges::pop_heap(__first, __middle, __comp, __proj);
1851	ranges::iter_swap(__middle-1, __i);
1852	ranges::push_heap(__first, __middle, __comp, __proj);
1853	}
1854	ranges::sort_heap(__first, __middle, __comp, __proj);
1855
1856	return __i;
1857	}
1858
1859	template<random_access_range _Range,
1860	typename _Comp = ranges::less, typename _Proj = identity>
1861	requires sortable<iterator_t<_Range>, _Comp, _Proj>
1862	constexpr borrowed_iterator_t<_Range>
1863	operator()(_Range&& __r, iterator_t<_Range> __middle,
1864	_Comp __comp = {}, _Proj __proj = {}) const
1865	{
1866	return (*this)(ranges::begin(__r), std::move(__middle),
1867	ranges::end(__r),
1868	std::move(__comp), std::move(__proj));
1869	}
1870	};
1871
1872	inline constexpr __partial_sort_fn partial_sort{};
1873
1874	template<typename _Iter, typename _Out>
1875	using partial_sort_copy_result = in_out_result<_Iter, _Out>;
1876
1877	struct __partial_sort_copy_fn
1878	{
1879	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
1880	random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
1881	typename _Comp = ranges::less,
1882	typename _Proj1 = identity, typename _Proj2 = identity>
1883	requires indirectly_copyable<_Iter1, _Iter2>
1884	&& sortable<_Iter2, _Comp, _Proj2>
1885	&& indirect_strict_weak_order<_Comp,
1886	projected<_Iter1, _Proj1>,
1887	projected<_Iter2, _Proj2>>
1888	constexpr partial_sort_copy_result<_Iter1, _Iter2>
1889	operator()(_Iter1 __first, _Sent1 __last,
1890	_Iter2 __result_first, _Sent2 __result_last,
1891	_Comp __comp = {},
1892	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
1893	{
1894	if (__result_first == __result_last)
1895	{
1896	// TODO: Eliminating the variable __lasti triggers an ICE.
1897	auto __lasti = ranges::next(std::move(__first),
1898	std::move(__last));
1899	return {std::move(__lasti), std::move(__result_first)};
1900	}
1901
1902	auto __result_real_last = __result_first;
1903	while (__first != __last && __result_real_last != __result_last)
1904	{
1905	*__result_real_last = *__first;
1906	++__result_real_last;
1907	++__first;
1908	}
1909
1910	ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
1911	for (; __first != __last; ++__first)
1912	if (std::__invoke(__comp,
1913	std::__invoke(__proj1, *__first),
1914	std::__invoke(__proj2, *__result_first)))
1915	{
1916	ranges::pop_heap(__result_first, __result_real_last,
1917	__comp, __proj2);
1918	*(__result_real_last-1) = *__first;
1919	ranges::push_heap(__result_first, __result_real_last,
1920	__comp, __proj2);
1921	}
1922	ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
1923
1924	return {std::move(__first), std::move(__result_real_last)};
1925	}
1926
1927	template<input_range _Range1, random_access_range _Range2,
1928	typename _Comp = ranges::less,
1929	typename _Proj1 = identity, typename _Proj2 = identity>
1930	requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
1931	&& sortable<iterator_t<_Range2>, _Comp, _Proj2>
1932	&& indirect_strict_weak_order<_Comp,
1933	projected<iterator_t<_Range1>, _Proj1>,
1934	projected<iterator_t<_Range2>, _Proj2>>
1935	constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>,
1936	borrowed_iterator_t<_Range2>>
1937	operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
1938	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
1939	{
1940	return (*this)(ranges::begin(__r), ranges::end(__r),
1941	ranges::begin(__out), ranges::end(__out),
1942	std::move(__comp),
1943	std::move(__proj1), std::move(__proj2));
1944	}
1945	};
1946
1947	inline constexpr __partial_sort_copy_fn partial_sort_copy{};
1948
1949	struct __is_sorted_until_fn
1950	{
1951	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1952	typename _Proj = identity,
1953	indirect_strict_weak_order<projected<_Iter, _Proj>>
1954	_Comp = ranges::less>
1955	constexpr _Iter
1956	operator()(_Iter __first, _Sent __last,
1957	_Comp __comp = {}, _Proj __proj = {}) const
1958	{
1959	if (__first == __last)
1960	return __first;
1961
1962	auto __next = __first;
1963	for (++__next; __next != __last; __first = __next, (void)++__next)
1964	if (std::__invoke(__comp,
1965	std::__invoke(__proj, *__next),
1966	std::__invoke(__proj, *__first)))
1967	return __next;
1968	return __next;
1969	}
1970
1971	template<forward_range _Range, typename _Proj = identity,
1972	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1973	_Comp = ranges::less>
1974	constexpr borrowed_iterator_t<_Range>
1975	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1976	{
1977	return (*this)(ranges::begin(__r), ranges::end(__r),
1978	std::move(__comp), std::move(__proj));
1979	}
1980	};
1981
1982	inline constexpr __is_sorted_until_fn is_sorted_until{};
1983
1984	struct __is_sorted_fn
1985	{
1986	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1987	typename _Proj = identity,
1988	indirect_strict_weak_order<projected<_Iter, _Proj>>
1989	_Comp = ranges::less>
1990	constexpr bool
1991	operator()(_Iter __first, _Sent __last,
1992	_Comp __comp = {}, _Proj __proj = {}) const
1993	{
1994	if (__first == __last)
1995	return true;
1996
1997	auto __next = __first;
1998	for (++__next; __next != __last; __first = __next, (void)++__next)
1999	if (std::__invoke(__comp,
2000	std::__invoke(__proj, *__next),
2001	std::__invoke(__proj, *__first)))
2002	return false;
2003	return true;
2004	}
2005
2006	template<forward_range _Range, typename _Proj = identity,
2007	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2008	_Comp = ranges::less>
2009	constexpr bool
2010	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2011	{
2012	return (*this)(ranges::begin(__r), ranges::end(__r),
2013	std::move(__comp), std::move(__proj));
2014	}
2015	};
2016
2017	inline constexpr __is_sorted_fn is_sorted{};
2018
2019	struct __nth_element_fn
2020	{
2021	template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2022	typename _Comp = ranges::less, typename _Proj = identity>
2023	requires sortable<_Iter, _Comp, _Proj>
2024	constexpr _Iter
2025	operator()(_Iter __first, _Iter __nth, _Sent __last,
2026	_Comp __comp = {}, _Proj __proj = {}) const
2027	{
2028	auto __lasti = ranges::next(__first, __last);
2029	_GLIBCXX_STD_A::nth_element(std::move(__first), std::move(__nth),
2030	__lasti,
2031	__detail::__make_comp_proj(__comp, __proj));
2032	return __lasti;
2033	}
2034
2035	template<random_access_range _Range,
2036	typename _Comp = ranges::less, typename _Proj = identity>
2037	requires sortable<iterator_t<_Range>, _Comp, _Proj>
2038	constexpr borrowed_iterator_t<_Range>
2039	operator()(_Range&& __r, iterator_t<_Range> __nth,
2040	_Comp __comp = {}, _Proj __proj = {}) const
2041	{
2042	return (*this)(ranges::begin(__r), std::move(__nth),
2043	ranges::end(__r), std::move(__comp), std::move(__proj));
2044	}
2045	};
2046
2047	inline constexpr __nth_element_fn nth_element{};
2048
2049	struct __lower_bound_fn
2050	{
2051	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2052	typename _Tp, typename _Proj = identity,
2053	indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2054	_Comp = ranges::less>
2055	constexpr _Iter
2056	operator()(_Iter __first, _Sent __last,
2057	const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2058	{
2059	auto __len = ranges::distance(__first, __last);
2060
2061	while (__len > 0)
2062	{
2063	auto __half = __len / 2;
2064	auto __middle = __first;
2065	ranges::advance(__middle, __half);
2066	if (std::__invoke(__comp, std::__invoke(__proj, *__middle), __value))
2067	{
2068	__first = __middle;
2069	++__first;
2070	__len = __len - __half - 1;
2071	}
2072	else
2073	__len = __half;
2074	}
2075	return __first;
2076	}
2077
2078	template<forward_range _Range, typename _Tp, typename _Proj = identity,
2079	indirect_strict_weak_order<const _Tp*,
2080	projected<iterator_t<_Range>, _Proj>>
2081	_Comp = ranges::less>
2082	constexpr borrowed_iterator_t<_Range>
2083	operator()(_Range&& __r,
2084	const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2085	{
2086	return (*this)(ranges::begin(__r), ranges::end(__r),
2087	__value, std::move(__comp), std::move(__proj));
2088	}
2089	};
2090
2091	inline constexpr __lower_bound_fn lower_bound{};
2092
2093	struct __upper_bound_fn
2094	{
2095	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2096	typename _Tp, typename _Proj = identity,
2097	indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2098	_Comp = ranges::less>
2099	constexpr _Iter
2100	operator()(_Iter __first, _Sent __last,
2101	const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2102	{
2103	auto __len = ranges::distance(__first, __last);
2104
2105	while (__len > 0)
2106	{
2107	auto __half = __len / 2;
2108	auto __middle = __first;
2109	ranges::advance(__middle, __half);
2110	if (std::__invoke(__comp, __value, std::__invoke(__proj, *__middle)))
2111	__len = __half;
2112	else
2113	{
2114	__first = __middle;
2115	++__first;
2116	__len = __len - __half - 1;
2117	}
2118	}
2119	return __first;
2120	}
2121
2122	template<forward_range _Range, typename _Tp, typename _Proj = identity,
2123	indirect_strict_weak_order<const _Tp*,
2124	projected<iterator_t<_Range>, _Proj>>
2125	_Comp = ranges::less>
2126	constexpr borrowed_iterator_t<_Range>
2127	operator()(_Range&& __r,
2128	const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2129	{
2130	return (*this)(ranges::begin(__r), ranges::end(__r),
2131	__value, std::move(__comp), std::move(__proj));
2132	}
2133	};
2134
2135	inline constexpr __upper_bound_fn upper_bound{};
2136
2137	struct __equal_range_fn
2138	{
2139	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2140	typename _Tp, typename _Proj = identity,
2141	indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2142	_Comp = ranges::less>
2143	constexpr subrange<_Iter>
2144	operator()(_Iter __first, _Sent __last,
2145	const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2146	{
2147	auto __len = ranges::distance(__first, __last);
2148
2149	while (__len > 0)
2150	{
2151	auto __half = __len / 2;
2152	auto __middle = __first;
2153	ranges::advance(__middle, __half);
2154	if (std::__invoke(__comp,
2155	std::__invoke(__proj, *__middle),
2156	__value))
2157	{
2158	__first = __middle;
2159	++__first;
2160	__len = __len - __half - 1;
2161	}
2162	else if (std::__invoke(__comp,
2163	__value,
2164	std::__invoke(__proj, *__middle)))
2165	__len = __half;
2166	else
2167	{
2168	auto __left
2169	= ranges::lower_bound(__first, __middle,
2170	__value, __comp, __proj);
2171	ranges::advance(__first, __len);
2172	auto __right
2173	= ranges::upper_bound(++__middle, __first,
2174	__value, __comp, __proj);
2175	return {__left, __right};
2176	}
2177	}
2178	return {__first, __first};
2179	}
2180
2181	template<forward_range _Range,
2182	typename _Tp, typename _Proj = identity,
2183	indirect_strict_weak_order<const _Tp*,
2184	projected<iterator_t<_Range>, _Proj>>
2185	_Comp = ranges::less>
2186	constexpr borrowed_subrange_t<_Range>
2187	operator()(_Range&& __r, const _Tp& __value,
2188	_Comp __comp = {}, _Proj __proj = {}) const
2189	{
2190	return (*this)(ranges::begin(__r), ranges::end(__r),
2191	__value, std::move(__comp), std::move(__proj));
2192	}
2193	};
2194
2195	inline constexpr __equal_range_fn equal_range{};
2196
2197	struct __binary_search_fn
2198	{
2199	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2200	typename _Tp, typename _Proj = identity,
2201	indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2202	_Comp = ranges::less>
2203	constexpr bool
2204	operator()(_Iter __first, _Sent __last,
2205	const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2206	{
2207	auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
2208	if (__i == __last)
2209	return false;
2210	return !(bool)std::__invoke(__comp, __value,
2211	std::__invoke(__proj, *__i));
2212	}
2213
2214	template<forward_range _Range,
2215	typename _Tp, typename _Proj = identity,
2216	indirect_strict_weak_order<const _Tp*,
2217	projected<iterator_t<_Range>, _Proj>>
2218	_Comp = ranges::less>
2219	constexpr bool
2220	operator()(_Range&& __r, const _Tp& __value, _Comp __comp = {},
2221	_Proj __proj = {}) const
2222	{
2223	return (*this)(ranges::begin(__r), ranges::end(__r),
2224	__value, std::move(__comp), std::move(__proj));
2225	}
2226	};
2227
2228	inline constexpr __binary_search_fn binary_search{};
2229
2230	struct __is_partitioned_fn
2231	{
2232	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2233	typename _Proj = identity,
2234	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2235	constexpr bool
2236	operator()(_Iter __first, _Sent __last,
2237	_Pred __pred, _Proj __proj = {}) const
2238	{
2239	__first = ranges::find_if_not(std::move(__first), __last,
2240	__pred, __proj);
2241	if (__first == __last)
2242	return true;
2243	++__first;
2244	return ranges::none_of(std::move(__first), std::move(__last),
2245	std::move(__pred), std::move(__proj));
2246	}
2247
2248	template<input_range _Range, typename _Proj = identity,
2249	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2250	_Pred>
2251	constexpr bool
2252	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
2253	{
2254	return (*this)(ranges::begin(__r), ranges::end(__r),
2255	std::move(__pred), std::move(__proj));
2256	}
2257	};
2258
2259	inline constexpr __is_partitioned_fn is_partitioned{};
2260
2261	struct __partition_fn
2262	{
2263	template<permutable _Iter, sentinel_for<_Iter> _Sent,
2264	typename _Proj = identity,
2265	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2266	constexpr subrange<_Iter>
2267	operator()(_Iter __first, _Sent __last,
2268	_Pred __pred, _Proj __proj = {}) const
2269	{
2270	if constexpr (bidirectional_iterator<_Iter>)
2271	{
2272	auto __lasti = ranges::next(__first, __last);
2273	auto __tail = __lasti;
2274	for (;;)
2275	{
2276	for (;;)
2277	if (__first == __tail)
2278	return {std::move(__first), std::move(__lasti)};
2279	else if (std::__invoke(__pred,
2280	std::__invoke(__proj, *__first)))
2281	++__first;
2282	else
2283	break;
2284	--__tail;
2285	for (;;)
2286	if (__first == __tail)
2287	return {std::move(__first), std::move(__lasti)};
2288	else if (!(bool)std::__invoke(__pred,
2289	std::__invoke(__proj, *__tail)))
2290	--__tail;
2291	else
2292	break;
2293	ranges::iter_swap(__first, __tail);
2294	++__first;
2295	}
2296	}
2297	else
2298	{
2299	if (__first == __last)
2300	return {__first, __first};
2301
2302	while (std::__invoke(__pred, std::__invoke(__proj, *__first)))
2303	if (++__first == __last)
2304	return {__first, __first};
2305
2306	auto __next = __first;
2307	while (++__next != __last)
2308	if (std::__invoke(__pred, std::__invoke(__proj, *__next)))
2309	{
2310	ranges::iter_swap(__first, __next);
2311	++__first;
2312	}
2313
2314	return {std::move(__first), std::move(__next)};
2315	}
2316	}
2317
2318	template<forward_range _Range, typename _Proj = identity,
2319	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2320	_Pred>
2321	requires permutable<iterator_t<_Range>>
2322	constexpr borrowed_subrange_t<_Range>
2323	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
2324	{
2325	return (*this)(ranges::begin(__r), ranges::end(__r),
2326	std::move(__pred), std::move(__proj));
2327	}
2328	};
2329
2330	inline constexpr __partition_fn partition{};
2331
2332	#if _GLIBCXX_HOSTED
2333	struct __stable_partition_fn
2334	{
2335	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2336	typename _Proj = identity,
2337	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2338	requires permutable<_Iter>
2339	subrange<_Iter>
2340	operator()(_Iter __first, _Sent __last,
2341	_Pred __pred, _Proj __proj = {}) const
2342	{
2343	auto __lasti = ranges::next(__first, __last);
2344	auto __middle
2345	= std::stable_partition(std::move(__first), __lasti,
2346	__detail::__make_pred_proj(__pred, __proj));
2347	return {std::move(__middle), std::move(__lasti)};
2348	}
2349
2350	template<bidirectional_range _Range, typename _Proj = identity,
2351	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2352	_Pred>
2353	requires permutable<iterator_t<_Range>>
2354	borrowed_subrange_t<_Range>
2355	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
2356	{
2357	return (*this)(ranges::begin(__r), ranges::end(__r),
2358	std::move(__pred), std::move(__proj));
2359	}
2360	};
2361
2362	inline constexpr __stable_partition_fn stable_partition{};
2363	#endif
2364
2365	template<typename _Iter, typename _Out1, typename _Out2>
2366	struct in_out_out_result
2367	{
2368	[[no_unique_address]] _Iter in;
2369	[[no_unique_address]] _Out1 out1;
2370	[[no_unique_address]] _Out2 out2;
2371
2372	template<typename _IIter, typename _OOut1, typename _OOut2>
2373	requires convertible_to<const _Iter&, _IIter>
2374	&& convertible_to<const _Out1&, _OOut1>
2375	&& convertible_to<const _Out2&, _OOut2>
2376	constexpr
2377	operator in_out_out_result<_IIter, _OOut1, _OOut2>() const &
2378	{ return {in, out1, out2}; }
2379
2380	template<typename _IIter, typename _OOut1, typename _OOut2>
2381	requires convertible_to<_Iter, _IIter>
2382	&& convertible_to<_Out1, _OOut1>
2383	&& convertible_to<_Out2, _OOut2>
2384	constexpr
2385	operator in_out_out_result<_IIter, _OOut1, _OOut2>() &&
2386	{ return {std::move(in), std::move(out1), std::move(out2)}; }
2387	};
2388
2389	template<typename _Iter, typename _Out1, typename _Out2>
2390	using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>;
2391
2392	struct __partition_copy_fn
2393	{
2394	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2395	weakly_incrementable _Out1, weakly_incrementable _Out2,
2396	typename _Proj = identity,
2397	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2398	requires indirectly_copyable<_Iter, _Out1>
2399	&& indirectly_copyable<_Iter, _Out2>
2400	constexpr partition_copy_result<_Iter, _Out1, _Out2>
2401	operator()(_Iter __first, _Sent __last,
2402	_Out1 __out_true, _Out2 __out_false,
2403	_Pred __pred, _Proj __proj = {}) const
2404	{
2405	for (; __first != __last; ++__first)
2406	if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
2407	{
2408	*__out_true = *__first;
2409	++__out_true;
2410	}
2411	else
2412	{
2413	*__out_false = *__first;
2414	++__out_false;
2415	}
2416
2417	return {std::move(__first),
2418	std::move(__out_true), std::move(__out_false)};
2419	}
2420
2421	template<input_range _Range, weakly_incrementable _Out1,
2422	weakly_incrementable _Out2,
2423	typename _Proj = identity,
2424	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2425	_Pred>
2426	requires indirectly_copyable<iterator_t<_Range>, _Out1>
2427	&& indirectly_copyable<iterator_t<_Range>, _Out2>
2428	constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _Out2>
2429	operator()(_Range&& __r, _Out1 __out_true, _Out2 __out_false,
2430	_Pred __pred, _Proj __proj = {}) const
2431	{
2432	return (*this)(ranges::begin(__r), ranges::end(__r),
2433	std::move(__out_true), std::move(__out_false),
2434	std::move(__pred), std::move(__proj));
2435	}
2436	};
2437
2438	inline constexpr __partition_copy_fn partition_copy{};
2439
2440	struct __partition_point_fn
2441	{
2442	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2443	typename _Proj = identity,
2444	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2445	constexpr _Iter
2446	operator()(_Iter __first, _Sent __last,
2447	_Pred __pred, _Proj __proj = {}) const
2448	{
2449	auto __len = ranges::distance(__first, __last);
2450
2451	while (__len > 0)
2452	{
2453	auto __half = __len / 2;
2454	auto __middle = __first;
2455	ranges::advance(__middle, __half);
2456	if (std::__invoke(__pred, std::__invoke(__proj, *__middle)))
2457	{
2458	__first = __middle;
2459	++__first;
2460	__len = __len - __half - 1;
2461	}
2462	else
2463	__len = __half;
2464	}
2465	return __first;
2466	}
2467
2468	template<forward_range _Range, typename _Proj = identity,
2469	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2470	_Pred>
2471	constexpr borrowed_iterator_t<_Range>
2472	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
2473	{
2474	return (*this)(ranges::begin(__r), ranges::end(__r),
2475	std::move(__pred), std::move(__proj));
2476	}
2477	};
2478
2479	inline constexpr __partition_point_fn partition_point{};
2480
2481	template<typename _Iter1, typename _Iter2, typename _Out>
2482	using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2483
2484	struct __merge_fn
2485	{
2486	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2487	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2488	weakly_incrementable _Out, typename _Comp = ranges::less,
2489	typename _Proj1 = identity, typename _Proj2 = identity>
2490	requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2491	constexpr merge_result<_Iter1, _Iter2, _Out>
2492	operator()(_Iter1 __first1, _Sent1 __last1,
2493	_Iter2 __first2, _Sent2 __last2, _Out __result,
2494	_Comp __comp = {},
2495	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2496	{
2497	while (__first1 != __last1 && __first2 != __last2)
2498	{
2499	if (std::__invoke(__comp,
2500	std::__invoke(__proj2, *__first2),
2501	std::__invoke(__proj1, *__first1)))
2502	{
2503	*__result = *__first2;
2504	++__first2;
2505	}
2506	else
2507	{
2508	*__result = *__first1;
2509	++__first1;
2510	}
2511	++__result;
2512	}
2513	auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
2514	std::move(__result));
2515	auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
2516	std::move(__copy1.out));
2517	return { std::move(__copy1.in), std::move(__copy2.in),
2518	std::move(__copy2.out) };
2519	}
2520
2521	template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2522	typename _Comp = ranges::less,
2523	typename _Proj1 = identity, typename _Proj2 = identity>
2524	requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2525	_Comp, _Proj1, _Proj2>
2526	constexpr merge_result<borrowed_iterator_t<_Range1>,
2527	borrowed_iterator_t<_Range2>,
2528	_Out>
2529	operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2530	_Comp __comp = {},
2531	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2532	{
2533	return (*this)(ranges::begin(__r1), ranges::end(__r1),
2534	ranges::begin(__r2), ranges::end(__r2),
2535	std::move(__result), std::move(__comp),
2536	std::move(__proj1), std::move(__proj2));
2537	}
2538	};
2539
2540	inline constexpr __merge_fn merge{};
2541
2542	struct __inplace_merge_fn
2543	{
2544	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2545	typename _Comp = ranges::less,
2546	typename _Proj = identity>
2547	requires sortable<_Iter, _Comp, _Proj>
2548	_Iter
2549	operator()(_Iter __first, _Iter __middle, _Sent __last,
2550	_Comp __comp = {}, _Proj __proj = {}) const
2551	{
2552	auto __lasti = ranges::next(__first, __last);
2553	std::inplace_merge(std::move(__first), std::move(__middle), __lasti,
2554	__detail::__make_comp_proj(__comp, __proj));
2555	return __lasti;
2556	}
2557
2558	template<bidirectional_range _Range,
2559	typename _Comp = ranges::less, typename _Proj = identity>
2560	requires sortable<iterator_t<_Range>, _Comp, _Proj>
2561	borrowed_iterator_t<_Range>
2562	operator()(_Range&& __r, iterator_t<_Range> __middle,
2563	_Comp __comp = {}, _Proj __proj = {}) const
2564	{
2565	return (*this)(ranges::begin(__r), std::move(__middle),
2566	ranges::end(__r),
2567	std::move(__comp), std::move(__proj));
2568	}
2569	};
2570
2571	inline constexpr __inplace_merge_fn inplace_merge{};
2572
2573	struct __includes_fn
2574	{
2575	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2576	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2577	typename _Proj1 = identity, typename _Proj2 = identity,
2578	indirect_strict_weak_order<projected<_Iter1, _Proj1>,
2579	projected<_Iter2, _Proj2>>
2580	_Comp = ranges::less>
2581	constexpr bool
2582	operator()(_Iter1 __first1, _Sent1 __last1,
2583	_Iter2 __first2, _Sent2 __last2,
2584	_Comp __comp = {},
2585	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2586	{
2587	while (__first1 != __last1 && __first2 != __last2)
2588	if (std::__invoke(__comp,
2589	std::__invoke(__proj2, *__first2),
2590	std::__invoke(__proj1, *__first1)))
2591	return false;
2592	else if (std::__invoke(__comp,
2593	std::__invoke(__proj1, *__first1),
2594	std::__invoke(__proj2, *__first2)))
2595	++__first1;
2596	else
2597	{
2598	++__first1;
2599	++__first2;
2600	}
2601
2602	return __first2 == __last2;
2603	}
2604
2605	template<input_range _Range1, input_range _Range2,
2606	typename _Proj1 = identity, typename _Proj2 = identity,
2607	indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
2608	projected<iterator_t<_Range2>, _Proj2>>
2609	_Comp = ranges::less>
2610	constexpr bool
2611	operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
2612	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2613	{
2614	return (*this)(ranges::begin(__r1), ranges::end(__r1),
2615	ranges::begin(__r2), ranges::end(__r2),
2616	std::move(__comp),
2617	std::move(__proj1), std::move(__proj2));
2618	}
2619	};
2620
2621	inline constexpr __includes_fn includes{};
2622
2623	template<typename _Iter1, typename _Iter2, typename _Out>
2624	using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2625
2626	struct __set_union_fn
2627	{
2628	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2629	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2630	weakly_incrementable _Out, typename _Comp = ranges::less,
2631	typename _Proj1 = identity, typename _Proj2 = identity>
2632	requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2633	constexpr set_union_result<_Iter1, _Iter2, _Out>
2634	operator()(_Iter1 __first1, _Sent1 __last1,
2635	_Iter2 __first2, _Sent2 __last2,
2636	_Out __result, _Comp __comp = {},
2637	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2638	{
2639	while (__first1 != __last1 && __first2 != __last2)
2640	{
2641	if (std::__invoke(__comp,
2642	std::__invoke(__proj1, *__first1),
2643	std::__invoke(__proj2, *__first2)))
2644	{
2645	*__result = *__first1;
2646	++__first1;
2647	}
2648	else if (std::__invoke(__comp,
2649	std::__invoke(__proj2, *__first2),
2650	std::__invoke(__proj1, *__first1)))
2651	{
2652	*__result = *__first2;
2653	++__first2;
2654	}
2655	else
2656	{
2657	*__result = *__first1;
2658	++__first1;
2659	++__first2;
2660	}
2661	++__result;
2662	}
2663	auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
2664	std::move(__result));
2665	auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
2666	std::move(__copy1.out));
2667	return {std::move(__copy1.in), std::move(__copy2.in),
2668	std::move(__copy2.out)};
2669	}
2670
2671	template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2672	typename _Comp = ranges::less,
2673	typename _Proj1 = identity, typename _Proj2 = identity>
2674	requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2675	_Comp, _Proj1, _Proj2>
2676	constexpr set_union_result<borrowed_iterator_t<_Range1>,
2677	borrowed_iterator_t<_Range2>, _Out>
2678	operator()(_Range1&& __r1, _Range2&& __r2,
2679	_Out __result, _Comp __comp = {},
2680	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2681	{
2682	return (*this)(ranges::begin(__r1), ranges::end(__r1),
2683	ranges::begin(__r2), ranges::end(__r2),
2684	std::move(__result), std::move(__comp),
2685	std::move(__proj1), std::move(__proj2));
2686	}
2687	};
2688
2689	inline constexpr __set_union_fn set_union{};
2690
2691	template<typename _Iter1, typename _Iter2, typename _Out>
2692	using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2693
2694	struct __set_intersection_fn
2695	{
2696	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2697	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2698	weakly_incrementable _Out, typename _Comp = ranges::less,
2699	typename _Proj1 = identity, typename _Proj2 = identity>
2700	requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2701	constexpr set_intersection_result<_Iter1, _Iter2, _Out>
2702	operator()(_Iter1 __first1, _Sent1 __last1,
2703	_Iter2 __first2, _Sent2 __last2, _Out __result,
2704	_Comp __comp = {},
2705	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2706	{
2707	while (__first1 != __last1 && __first2 != __last2)
2708	if (std::__invoke(__comp,
2709	std::__invoke(__proj1, *__first1),
2710	std::__invoke(__proj2, *__first2)))
2711	++__first1;
2712	else if (std::__invoke(__comp,
2713	std::__invoke(__proj2, *__first2),
2714	std::__invoke(__proj1, *__first1)))
2715	++__first2;
2716	else
2717	{
2718	*__result = *__first1;
2719	++__first1;
2720	++__first2;
2721	++__result;
2722	}
2723	// TODO: Eliminating these variables triggers an ICE.
2724	auto __last1i = ranges::next(std::move(__first1), std::move(__last1));
2725	auto __last2i = ranges::next(std::move(__first2), std::move(__last2));
2726	return {std::move(__last1i), std::move(__last2i), std::move(__result)};
2727	}
2728
2729	template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2730	typename _Comp = ranges::less,
2731	typename _Proj1 = identity, typename _Proj2 = identity>
2732	requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2733	_Comp, _Proj1, _Proj2>
2734	constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
2735	borrowed_iterator_t<_Range2>, _Out>
2736	operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2737	_Comp __comp = {},
2738	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2739	{
2740	return (*this)(ranges::begin(__r1), ranges::end(__r1),
2741	ranges::begin(__r2), ranges::end(__r2),
2742	std::move(__result), std::move(__comp),
2743	std::move(__proj1), std::move(__proj2));
2744	}
2745	};
2746
2747	inline constexpr __set_intersection_fn set_intersection{};
2748
2749	template<typename _Iter, typename _Out>
2750	using set_difference_result = in_out_result<_Iter, _Out>;
2751
2752	struct __set_difference_fn
2753	{
2754	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2755	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2756	weakly_incrementable _Out, typename _Comp = ranges::less,
2757	typename _Proj1 = identity, typename _Proj2 = identity>
2758	requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2759	constexpr set_difference_result<_Iter1, _Out>
2760	operator()(_Iter1 __first1, _Sent1 __last1,
2761	_Iter2 __first2, _Sent2 __last2, _Out __result,
2762	_Comp __comp = {},
2763	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2764	{
2765	while (__first1 != __last1 && __first2 != __last2)
2766	if (std::__invoke(__comp,
2767	std::__invoke(__proj1, *__first1),
2768	std::__invoke(__proj2, *__first2)))
2769	{
2770	*__result = *__first1;
2771	++__first1;
2772	++__result;
2773	}
2774	else if (std::__invoke(__comp,
2775	std::__invoke(__proj2, *__first2),
2776	std::__invoke(__proj1, *__first1)))
2777	++__first2;
2778	else
2779	{
2780	++__first1;
2781	++__first2;
2782	}
2783	return ranges::copy(std::move(__first1), std::move(__last1),
2784	std::move(__result));
2785	}
2786
2787	template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2788	typename _Comp = ranges::less,
2789	typename _Proj1 = identity, typename _Proj2 = identity>
2790	requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2791	_Comp, _Proj1, _Proj2>
2792	constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out>
2793	operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2794	_Comp __comp = {},
2795	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2796	{
2797	return (*this)(ranges::begin(__r1), ranges::end(__r1),
2798	ranges::begin(__r2), ranges::end(__r2),
2799	std::move(__result), std::move(__comp),
2800	std::move(__proj1), std::move(__proj2));
2801	}
2802	};
2803
2804	inline constexpr __set_difference_fn set_difference{};
2805
2806	template<typename _Iter1, typename _Iter2, typename _Out>
2807	using set_symmetric_difference_result
2808	= in_in_out_result<_Iter1, _Iter2, _Out>;
2809
2810	struct __set_symmetric_difference_fn
2811	{
2812	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2813	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2814	weakly_incrementable _Out, typename _Comp = ranges::less,
2815	typename _Proj1 = identity, typename _Proj2 = identity>
2816	requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2817	constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
2818	operator()(_Iter1 __first1, _Sent1 __last1,
2819	_Iter2 __first2, _Sent2 __last2,
2820	_Out __result, _Comp __comp = {},
2821	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2822	{
2823	while (__first1 != __last1 && __first2 != __last2)
2824	if (std::__invoke(__comp,
2825	std::__invoke(__proj1, *__first1),
2826	std::__invoke(__proj2, *__first2)))
2827	{
2828	*__result = *__first1;
2829	++__first1;
2830	++__result;
2831	}
2832	else if (std::__invoke(__comp,
2833	std::__invoke(__proj2, *__first2),
2834	std::__invoke(__proj1, *__first1)))
2835	{
2836	*__result = *__first2;
2837	++__first2;
2838	++__result;
2839	}
2840	else
2841	{
2842	++__first1;
2843	++__first2;
2844	}
2845	auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
2846	std::move(__result));
2847	auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
2848	std::move(__copy1.out));
2849	return {std::move(__copy1.in), std::move(__copy2.in),
2850	std::move(__copy2.out)};
2851	}
2852
2853	template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2854	typename _Comp = ranges::less,
2855	typename _Proj1 = identity, typename _Proj2 = identity>
2856	requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2857	_Comp, _Proj1, _Proj2>
2858	constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>,
2859	borrowed_iterator_t<_Range2>,
2860	_Out>
2861	operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2862	_Comp __comp = {},
2863	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2864	{
2865	return (*this)(ranges::begin(__r1), ranges::end(__r1),
2866	ranges::begin(__r2), ranges::end(__r2),
2867	std::move(__result), std::move(__comp),
2868	std::move(__proj1), std::move(__proj2));
2869	}
2870	};
2871
2872	inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};
2873
2874	// min is defined in <bits/ranges_util.h>.
2875
2876	struct __max_fn
2877	{
2878	template<typename _Tp, typename _Proj = identity,
2879	indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2880	_Comp = ranges::less>
2881	constexpr const _Tp&
2882	operator()(const _Tp& __a, const _Tp& __b,
2883	_Comp __comp = {}, _Proj __proj = {}) const
2884	{
2885	if (std::__invoke(__comp,
2886	std::__invoke(__proj, __a),
2887	std::__invoke(__proj, __b)))
2888	return __b;
2889	else
2890	return __a;
2891	}
2892
2893	template<input_range _Range, typename _Proj = identity,
2894	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2895	_Comp = ranges::less>
2896	requires indirectly_copyable_storable<iterator_t<_Range>,
2897	range_value_t<_Range>*>
2898	constexpr range_value_t<_Range>
2899	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2900	{
2901	auto __first = ranges::begin(__r);
2902	auto __last = ranges::end(__r);
2903	__glibcxx_assert(__first != __last);
2904	auto __result = *__first;
2905	while (++__first != __last)
2906	{
2907	auto __tmp = *__first;
2908	if (std::__invoke(__comp,
2909	std::__invoke(__proj, __result),
2910	std::__invoke(__proj, __tmp)))
2911	__result = std::move(__tmp);
2912	}
2913	return __result;
2914	}
2915
2916	template<copyable _Tp, typename _Proj = identity,
2917	indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2918	_Comp = ranges::less>
2919	constexpr _Tp
2920	operator()(initializer_list<_Tp> __r,
2921	_Comp __comp = {}, _Proj __proj = {}) const
2922	{
2923	return (*this)(ranges::subrange(__r),
2924	std::move(__comp), std::move(__proj));
2925	}
2926	};
2927
2928	inline constexpr __max_fn max{};
2929
2930	struct __clamp_fn
2931	{
2932	template<typename _Tp, typename _Proj = identity,
2933	indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
2934	= ranges::less>
2935	constexpr const _Tp&
2936	operator()(const _Tp& __val, const _Tp& __lo, const _Tp& __hi,
2937	_Comp __comp = {}, _Proj __proj = {}) const
2938	{
2939	__glibcxx_assert(!(std::__invoke(__comp,
2940	std::__invoke(__proj, __hi),
2941	std::__invoke(__proj, __lo))));
2942	auto&& __proj_val = std::__invoke(__proj, __val);
2943	if (std::__invoke(__comp, __proj_val, std::__invoke(__proj, __lo)))
2944	return __lo;
2945	else if (std::__invoke(__comp, std::__invoke(__proj, __hi), __proj_val))
2946	return __hi;
2947	else
2948	return __val;
2949	}
2950	};
2951
2952	inline constexpr __clamp_fn clamp{};
2953
2954	template<typename _Tp>
2955	struct min_max_result
2956	{
2957	[[no_unique_address]] _Tp min;
2958	[[no_unique_address]] _Tp max;
2959
2960	template<typename _Tp2>
2961	requires convertible_to<const _Tp&, _Tp2>
2962	constexpr
2963	operator min_max_result<_Tp2>() const &
2964	{ return {min, max}; }
2965
2966	template<typename _Tp2>
2967	requires convertible_to<_Tp, _Tp2>
2968	constexpr
2969	operator min_max_result<_Tp2>() &&
2970	{ return {std::move(min), std::move(max)}; }
2971	};
2972
2973	template<typename _Tp>
2974	using minmax_result = min_max_result<_Tp>;
2975
2976	struct __minmax_fn
2977	{
2978	template<typename _Tp, typename _Proj = identity,
2979	indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2980	_Comp = ranges::less>
2981	constexpr minmax_result<const _Tp&>
2982	operator()(const _Tp& __a, const _Tp& __b,
2983	_Comp __comp = {}, _Proj __proj = {}) const
2984	{
2985	if (std::__invoke(__comp,
2986	std::__invoke(__proj, __b),
2987	std::__invoke(__proj, __a)))
2988	return {__b, __a};
2989	else
2990	return {__a, __b};
2991	}
2992
2993	template<input_range _Range, typename _Proj = identity,
2994	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2995	_Comp = ranges::less>
2996	requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*>
2997	constexpr minmax_result<range_value_t<_Range>>
2998	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2999	{
3000	auto __first = ranges::begin(__r);
3001	auto __last = ranges::end(__r);
3002	__glibcxx_assert(__first != __last);
3003	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3004	minmax_result<range_value_t<_Range>> __result = {*__first, __result.min};
3005	if (++__first == __last)
3006	return __result;
3007	else
3008	{
3009	// At this point __result.min == __result.max, so a single
3010	// comparison with the next element suffices.
3011	auto&& __val = *__first;
3012	if (__comp_proj(__val, __result.min))
3013	__result.min = std::forward<decltype(__val)>(__val);
3014	else
3015	__result.max = std::forward<decltype(__val)>(__val);
3016	}
3017	while (++__first != __last)
3018	{
3019	// Now process two elements at a time so that we perform at most
3020	// 1 + 3*(N-2)/2 comparisons in total (each of the (N-2)/2
3021	// iterations of this loop performs three comparisons).
3022	range_value_t<_Range> __val1 = *__first;
3023	if (++__first == __last)
3024	{
3025	// N is odd; in this final iteration, we perform at most two
3026	// comparisons, for a total of 1 + 3*(N-3)/2 + 2 comparisons,
3027	// which is not more than 3*N/2, as required.
3028	if (__comp_proj(__val1, __result.min))
3029	__result.min = std::move(__val1);
3030	else if (!__comp_proj(__val1, __result.max))
3031	__result.max = std::move(__val1);
3032	break;
3033	}
3034	auto&& __val2 = *__first;
3035	if (!__comp_proj(__val2, __val1))
3036	{
3037	if (__comp_proj(__val1, __result.min))
3038	__result.min = std::move(__val1);
3039	if (!__comp_proj(__val2, __result.max))
3040	__result.max = std::forward<decltype(__val2)>(__val2);
3041	}
3042	else
3043	{
3044	if (__comp_proj(__val2, __result.min))
3045	__result.min = std::forward<decltype(__val2)>(__val2);
3046	if (!__comp_proj(__val1, __result.max))
3047	__result.max = std::move(__val1);
3048	}
3049	}
3050	return __result;
3051	}
3052
3053	template<copyable _Tp, typename _Proj = identity,
3054	indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3055	_Comp = ranges::less>
3056	constexpr minmax_result<_Tp>
3057	operator()(initializer_list<_Tp> __r,
3058	_Comp __comp = {}, _Proj __proj = {}) const
3059	{
3060	return (*this)(ranges::subrange(__r),
3061	std::move(__comp), std::move(__proj));
3062	}
3063	};
3064
3065	inline constexpr __minmax_fn minmax{};
3066
3067	struct __min_element_fn
3068	{
3069	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3070	typename _Proj = identity,
3071	indirect_strict_weak_order<projected<_Iter, _Proj>>
3072	_Comp = ranges::less>
3073	constexpr _Iter
3074	operator()(_Iter __first, _Sent __last,
3075	_Comp __comp = {}, _Proj __proj = {}) const
3076	{
3077	if (__first == __last)
3078	return __first;
3079
3080	auto __i = __first;
3081	while (++__i != __last)
3082	{
3083	if (std::__invoke(__comp,
3084	std::__invoke(__proj, *__i),
3085	std::__invoke(__proj, *__first)))
3086	__first = __i;
3087	}
3088	return __first;
3089	}
3090
3091	template<forward_range _Range, typename _Proj = identity,
3092	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3093	_Comp = ranges::less>
3094	constexpr borrowed_iterator_t<_Range>
3095	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3096	{
3097	return (*this)(ranges::begin(__r), ranges::end(__r),
3098	std::move(__comp), std::move(__proj));
3099	}
3100	};
3101
3102	inline constexpr __min_element_fn min_element{};
3103
3104	struct __max_element_fn
3105	{
3106	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3107	typename _Proj = identity,
3108	indirect_strict_weak_order<projected<_Iter, _Proj>>
3109	_Comp = ranges::less>
3110	constexpr _Iter
3111	operator()(_Iter __first, _Sent __last,
3112	_Comp __comp = {}, _Proj __proj = {}) const
3113	{
3114	if (__first == __last)
3115	return __first;
3116
3117	auto __i = __first;
3118	while (++__i != __last)
3119	{
3120	if (std::__invoke(__comp,
3121	std::__invoke(__proj, *__first),
3122	std::__invoke(__proj, *__i)))
3123	__first = __i;
3124	}
3125	return __first;
3126	}
3127
3128	template<forward_range _Range, typename _Proj = identity,
3129	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3130	_Comp = ranges::less>
3131	constexpr borrowed_iterator_t<_Range>
3132	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3133	{
3134	return (*this)(ranges::begin(__r), ranges::end(__r),
3135	std::move(__comp), std::move(__proj));
3136	}
3137	};
3138
3139	inline constexpr __max_element_fn max_element{};
3140
3141	template<typename _Iter>
3142	using minmax_element_result = min_max_result<_Iter>;
3143
3144	struct __minmax_element_fn
3145	{
3146	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3147	typename _Proj = identity,
3148	indirect_strict_weak_order<projected<_Iter, _Proj>>
3149	_Comp = ranges::less>
3150	constexpr minmax_element_result<_Iter>
3151	operator()(_Iter __first, _Sent __last,
3152	_Comp __comp = {}, _Proj __proj = {}) const
3153	{
3154	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3155	minmax_element_result<_Iter> __result = {__first, __first};
3156	if (__first == __last || ++__first == __last)
3157	return __result;
3158	else
3159	{
3160	// At this point __result.min == __result.max, so a single
3161	// comparison with the next element suffices.
3162	if (__comp_proj(*__first, *__result.min))
3163	__result.min = __first;
3164	else
3165	__result.max = __first;
3166	}
3167	while (++__first != __last)
3168	{
3169	// Now process two elements at a time so that we perform at most
3170	// 1 + 3*(N-2)/2 comparisons in total (each of the (N-2)/2
3171	// iterations of this loop performs three comparisons).
3172	auto __prev = __first;
3173	if (++__first == __last)
3174	{
3175	// N is odd; in this final iteration, we perform at most two
3176	// comparisons, for a total of 1 + 3*(N-3)/2 + 2 comparisons,
3177	// which is not more than 3*N/2, as required.
3178	if (__comp_proj(*__prev, *__result.min))
3179	__result.min = __prev;
3180	else if (!__comp_proj(*__prev, *__result.max))
3181	__result.max = __prev;
3182	break;
3183	}
3184	if (!__comp_proj(*__first, *__prev))
3185	{
3186	if (__comp_proj(*__prev, *__result.min))
3187	__result.min = __prev;
3188	if (!__comp_proj(*__first, *__result.max))
3189	__result.max = __first;
3190	}
3191	else
3192	{
3193	if (__comp_proj(*__first, *__result.min))
3194	__result.min = __first;
3195	if (!__comp_proj(*__prev, *__result.max))
3196	__result.max = __prev;
3197	}
3198	}
3199	return __result;
3200	}
3201
3202	template<forward_range _Range, typename _Proj = identity,
3203	indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3204	_Comp = ranges::less>
3205	constexpr minmax_element_result<borrowed_iterator_t<_Range>>
3206	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3207	{
3208	return (*this)(ranges::begin(__r), ranges::end(__r),
3209	std::move(__comp), std::move(__proj));
3210	}
3211	};
3212
3213	inline constexpr __minmax_element_fn minmax_element{};
3214
3215	struct __lexicographical_compare_fn
3216	{
3217	template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3218	input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3219	typename _Proj1 = identity, typename _Proj2 = identity,
3220	indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3221	projected<_Iter2, _Proj2>>
3222	_Comp = ranges::less>
3223	constexpr bool
3224	operator()(_Iter1 __first1, _Sent1 __last1,
3225	_Iter2 __first2, _Sent2 __last2,
3226	_Comp __comp = {},
3227	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3228	{
3229	if constexpr (__detail::__is_normal_iterator<_Iter1>
3230	&& same_as<_Iter1, _Sent1>)
3231	return (*this)(__first1.base(), __last1.base(),
3232	std::move(__first2), std::move(__last2),
3233	std::move(__comp),
3234	std::move(__proj1), std::move(__proj2));
3235	else if constexpr (__detail::__is_normal_iterator<_Iter2>
3236	&& same_as<_Iter2, _Sent2>)
3237	return (*this)(std::move(__first1), std::move(__last1),
3238	__first2.base(), __last2.base(),
3239	std::move(__comp),
3240	std::move(__proj1), std::move(__proj2));
3241	else
3242	{
3243	constexpr bool __sized_iters
3244	= (sized_sentinel_for<_Sent1, _Iter1>
3245	&& sized_sentinel_for<_Sent2, _Iter2>);
3246	if constexpr (__sized_iters)
3247	{
3248	using _ValueType1 = iter_value_t<_Iter1>;
3249	using _ValueType2 = iter_value_t<_Iter2>;
3250	// This condition is consistent with the one in
3251	// __lexicographical_compare_aux in <bits/stl_algobase.h>.
3252	constexpr bool __use_memcmp
3253	= (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
3254	&& __ptr_to_nonvolatile<_Iter1>
3255	&& __ptr_to_nonvolatile<_Iter2>
3256	&& (is_same_v<_Comp, ranges::less>
3257	|| is_same_v<_Comp, ranges::greater>)
3258	&& is_same_v<_Proj1, identity>
3259	&& is_same_v<_Proj2, identity>);
3260	if constexpr (__use_memcmp)
3261	{
3262	const auto __d1 = __last1 - __first1;
3263	const auto __d2 = __last2 - __first2;
3264
3265	if (const auto __len = std::min(__d1, __d2))
3266	{
3267	const auto __c
3268	= std::__memcmp(__first1, __first2, __len);
3269	if constexpr (is_same_v<_Comp, ranges::less>)
3270	{
3271	if (__c < 0)
3272	return true;
3273	if (__c > 0)
3274	return false;
3275	}
3276	else if constexpr (is_same_v<_Comp, ranges::greater>)
3277	{
3278	if (__c > 0)
3279	return true;
3280	if (__c < 0)
3281	return false;
3282	}
3283	}
3284	return __d1 < __d2;
3285	}
3286	}
3287
3288	for (; __first1 != __last1 && __first2 != __last2;
3289	++__first1, (void) ++__first2)
3290	{
3291	if (std::__invoke(__comp,
3292	std::__invoke(__proj1, *__first1),
3293	std::__invoke(__proj2, *__first2)))
3294	return true;
3295	if (std::__invoke(__comp,
3296	std::__invoke(__proj2, *__first2),
3297	std::__invoke(__proj1, *__first1)))
3298	return false;
3299	}
3300	return __first1 == __last1 && __first2 != __last2;
3301	}
3302	}
3303
3304	template<input_range _Range1, input_range _Range2,
3305	typename _Proj1 = identity, typename _Proj2 = identity,
3306	indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
3307	projected<iterator_t<_Range2>, _Proj2>>
3308	_Comp = ranges::less>
3309	constexpr bool
3310	operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
3311	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3312	{
3313	return (*this)(ranges::begin(__r1), ranges::end(__r1),
3314	ranges::begin(__r2), ranges::end(__r2),
3315	std::move(__comp),
3316	std::move(__proj1), std::move(__proj2));
3317	}
3318
3319	private:
3320	template<typename _Iter, typename _Ref = iter_reference_t<_Iter>>
3321	static constexpr bool __ptr_to_nonvolatile
3322	= is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
3323	};
3324
3325	inline constexpr __lexicographical_compare_fn lexicographical_compare;
3326
3327	template<typename _Iter>
3328	struct in_found_result
3329	{
3330	[[no_unique_address]] _Iter in;
3331	bool found;
3332
3333	template<typename _Iter2>
3334	requires convertible_to<const _Iter&, _Iter2>
3335	constexpr
3336	operator in_found_result<_Iter2>() const &
3337	{ return {in, found}; }
3338
3339	template<typename _Iter2>
3340	requires convertible_to<_Iter, _Iter2>
3341	constexpr
3342	operator in_found_result<_Iter2>() &&
3343	{ return {std::move(in), found}; }
3344	};
3345
3346	template<typename _Iter>
3347	using next_permutation_result = in_found_result<_Iter>;
3348
3349	struct __next_permutation_fn
3350	{
3351	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3352	typename _Comp = ranges::less, typename _Proj = identity>
3353	requires sortable<_Iter, _Comp, _Proj>
3354	constexpr next_permutation_result<_Iter>
3355	operator()(_Iter __first, _Sent __last,
3356	_Comp __comp = {}, _Proj __proj = {}) const
3357	{
3358	if (__first == __last)
3359	return {std::move(__first), false};
3360
3361	auto __i = __first;
3362	++__i;
3363	if (__i == __last)
3364	return {std::move(__i), false};
3365
3366	auto __lasti = ranges::next(__first, __last);
3367	__i = __lasti;
3368	--__i;
3369
3370	for (;;)
3371	{
3372	auto __ii = __i;
3373	--__i;
3374	if (std::__invoke(__comp,
3375	std::__invoke(__proj, *__i),
3376	std::__invoke(__proj, *__ii)))
3377	{
3378	auto __j = __lasti;
3379	while (!(bool)std::__invoke(__comp,
3380	std::__invoke(__proj, *__i),
3381	std::__invoke(__proj, *--__j)))
3382	;
3383	ranges::iter_swap(__i, __j);
3384	ranges::reverse(__ii, __last);
3385	return {std::move(__lasti), true};
3386	}
3387	if (__i == __first)
3388	{
3389	ranges::reverse(__first, __last);
3390	return {std::move(__lasti), false};
3391	}
3392	}
3393	}
3394
3395	template<bidirectional_range _Range, typename _Comp = ranges::less,
3396	typename _Proj = identity>
3397	requires sortable<iterator_t<_Range>, _Comp, _Proj>
3398	constexpr next_permutation_result<borrowed_iterator_t<_Range>>
3399	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3400	{
3401	return (*this)(ranges::begin(__r), ranges::end(__r),
3402	std::move(__comp), std::move(__proj));
3403	}
3404	};
3405
3406	inline constexpr __next_permutation_fn next_permutation{};
3407
3408	template<typename _Iter>
3409	using prev_permutation_result = in_found_result<_Iter>;
3410
3411	struct __prev_permutation_fn
3412	{
3413	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3414	typename _Comp = ranges::less, typename _Proj = identity>
3415	requires sortable<_Iter, _Comp, _Proj>
3416	constexpr prev_permutation_result<_Iter>
3417	operator()(_Iter __first, _Sent __last,
3418	_Comp __comp = {}, _Proj __proj = {}) const
3419	{
3420	if (__first == __last)
3421	return {std::move(__first), false};
3422
3423	auto __i = __first;
3424	++__i;
3425	if (__i == __last)
3426	return {std::move(__i), false};
3427
3428	auto __lasti = ranges::next(__first, __last);
3429	__i = __lasti;
3430	--__i;
3431
3432	for (;;)
3433	{
3434	auto __ii = __i;
3435	--__i;
3436	if (std::__invoke(__comp,
3437	std::__invoke(__proj, *__ii),
3438	std::__invoke(__proj, *__i)))
3439	{
3440	auto __j = __lasti;
3441	while (!(bool)std::__invoke(__comp,
3442	std::__invoke(__proj, *--__j),
3443	std::__invoke(__proj, *__i)))
3444	;
3445	ranges::iter_swap(__i, __j);
3446	ranges::reverse(__ii, __last);
3447	return {std::move(__lasti), true};
3448	}
3449	if (__i == __first)
3450	{
3451	ranges::reverse(__first, __last);
3452	return {std::move(__lasti), false};
3453	}
3454	}
3455	}
3456
3457	template<bidirectional_range _Range, typename _Comp = ranges::less,
3458	typename _Proj = identity>
3459	requires sortable<iterator_t<_Range>, _Comp, _Proj>
3460	constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
3461	operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3462	{
3463	return (*this)(ranges::begin(__r), ranges::end(__r),
3464	std::move(__comp), std::move(__proj));
3465	}
3466	};
3467
3468	inline constexpr __prev_permutation_fn prev_permutation{};
3469
3470	#if __cplusplus > 202002L
3471
3472	#define __cpp_lib_ranges_contains 202207L
3473
3474	struct __contains_fn
3475	{
3476	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3477	typename _Tp, typename _Proj = identity>
3478	requires indirect_binary_predicate<ranges::equal_to,
3479	projected<_Iter, _Proj>, const _Tp*>
3480	constexpr bool
3481	operator()(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {}) const
3482	{ return ranges::find(std::move(__first), __last, __value, std::move(__proj)) != __last; }
3483
3484	template<input_range _Range, typename _Tp, typename _Proj = identity>
3485	requires indirect_binary_predicate<ranges::equal_to,
3486	projected<iterator_t<_Range>, _Proj>, const _Tp*>
3487	constexpr bool
3488	operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
3489	{ return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); }
3490	};
3491
3492	inline constexpr __contains_fn contains{};
3493
3494	struct __contains_subrange_fn
3495	{
3496	template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3497	forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3498	typename _Pred = ranges::equal_to,
3499	typename _Proj1 = identity, typename _Proj2 = identity>
3500	requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
3501	constexpr bool
3502	operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
3503	_Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3504	{
3505	return __first2 == __last2
3506	|| !ranges::search(__first1, __last1, __first2, __last2,
3507	std::move(__pred), std::move(__proj1), std::move(__proj2)).empty();
3508	}
3509
3510	template<forward_range _Range1, forward_range _Range2,
3511	typename _Pred = ranges::equal_to,
3512	typename _Proj1 = identity, typename _Proj2 = identity>
3513	requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
3514	_Pred, _Proj1, _Proj2>
3515	constexpr bool
3516	operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
3517	_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3518	{
3519	return (*this)(ranges::begin(__r1), ranges::end(__r1),
3520	ranges::begin(__r2), ranges::end(__r2),
3521	std::move(__pred), std::move(__proj1), std::move(__proj2));
3522	}
3523	};
3524
3525	inline constexpr __contains_subrange_fn contains_subrange{};
3526
3527	#define __cpp_lib_ranges_iota 202202L
3528
3529	template<typename _Out, typename _Tp>
3530	struct out_value_result
3531	{
3532	[[no_unique_address]] _Out out;
3533	[[no_unique_address]] _Tp value;
3534
3535	template<typename _Out2, typename _Tp2>
3536	requires convertible_to<const _Out&, _Out2>
3537	&& convertible_to<const _Tp&, _Tp2>
3538	constexpr
3539	operator out_value_result<_Out2, _Tp2>() const &
3540	{ return {out, value}; }
3541
3542	template<typename _Out2, typename _Tp2>
3543	requires convertible_to<_Out, _Out2>
3544	&& convertible_to<_Tp, _Tp2>
3545	constexpr
3546	operator out_value_result<_Out2, _Tp2>() &&
3547	{ return {std::move(out), std::move(value)}; }
3548	};
3549
3550	template<typename _Out, typename _Tp>
3551	using iota_result = out_value_result<_Out, _Tp>;
3552
3553	struct __iota_fn
3554	{
3555	template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent, weakly_incrementable _Tp>
3556	requires indirectly_writable<_Out, const _Tp&>
3557	constexpr iota_result<_Out, _Tp>
3558	operator()(_Out __first, _Sent __last, _Tp __value) const
3559	{
3560	while (__first != __last)
3561	{
3562	*__first = static_cast<const _Tp&>(__value);
3563	++__first;
3564	++__value;
3565	}
3566	return {std::move(__first), std::move(__value)};
3567	}
3568
3569	template<weakly_incrementable _Tp, output_range<const _Tp&> _Range>
3570	constexpr iota_result<borrowed_iterator_t<_Range>, _Tp>
3571	operator()(_Range&& __r, _Tp __value) const
3572	{ return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__value)); }
3573	};
3574
3575	inline constexpr __iota_fn iota{};
3576
3577	#define __cpp_lib_ranges_find_last 202207L
3578
3579	struct __find_last_fn
3580	{
3581	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp, typename _Proj = identity>
3582	requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Tp*>
3583	constexpr subrange<_Iter>
3584	operator()(_Iter __first, _Sent __last, const _Tp& __value, _Proj __proj = {}) const
3585	{
3586	if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3587	{
3588	_Iter __found = ranges::find(reverse_iterator<_Iter>{__last},
3589	reverse_iterator<_Iter>{__first},
3590	__value, std::move(__proj)).base();
3591	if (__found == __first)
3592	return {__last, __last};
3593	else
3594	return {ranges::prev(__found), __last};
3595	}
3596	else
3597	{
3598	_Iter __found = ranges::find(__first, __last, __value, __proj);
3599	if (__found == __last)
3600	return {__found, __found};
3601	__first = __found;
3602	for (;;)
3603	{
3604	__first = ranges::find(ranges::next(__first), __last, __value, __proj);
3605	if (__first == __last)
3606	return {__found, __first};
3607	__found = __first;
3608	}
3609	}
3610	}
3611
3612	template<forward_range _Range, typename _Tp, typename _Proj = identity>
3613	requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Tp*>
3614	constexpr borrowed_subrange_t<_Range>
3615	operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
3616	{ return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); }
3617	};
3618
3619	inline constexpr __find_last_fn find_last{};
3620
3621	struct __find_last_if_fn
3622	{
3623	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Proj = identity,
3624	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3625	constexpr subrange<_Iter>
3626	operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const
3627	{
3628	if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3629	{
3630	_Iter __found = ranges::find_if(reverse_iterator<_Iter>{__last},
3631	reverse_iterator<_Iter>{__first},
3632	std::move(__pred), std::move(__proj)).base();
3633	if (__found == __first)
3634	return {__last, __last};
3635	else
3636	return {ranges::prev(__found), __last};
3637	}
3638	else
3639	{
3640	_Iter __found = ranges::find_if(__first, __last, __pred, __proj);
3641	if (__found == __last)
3642	return {__found, __found};
3643	__first = __found;
3644	for (;;)
3645	{
3646	__first = ranges::find_if(ranges::next(__first), __last, __pred, __proj);
3647	if (__first == __last)
3648	return {__found, __first};
3649	__found = __first;
3650	}
3651	}
3652	}
3653
3654	template<forward_range _Range, typename _Proj = identity,
3655	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
3656	constexpr borrowed_subrange_t<_Range>
3657	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
3658	{ return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__pred), std::move(__proj)); }
3659	};
3660
3661	inline constexpr __find_last_if_fn find_last_if{};
3662
3663	struct __find_last_if_not_fn
3664	{
3665	template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Proj = identity,
3666	indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3667	constexpr subrange<_Iter>
3668	operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const
3669	{
3670	if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3671	{
3672	_Iter __found = ranges::find_if_not(reverse_iterator<_Iter>{__last},
3673	reverse_iterator<_Iter>{__first},
3674	std::move(__pred), std::move(__proj)).base();
3675	if (__found == __first)
3676	return {__last, __last};
3677	else
3678	return {ranges::prev(__found), __last};
3679	}
3680	else
3681	{
3682	_Iter __found = ranges::find_if_not(__first, __last, __pred, __proj);
3683	if (__found == __last)
3684	return {__found, __found};
3685	__first = __found;
3686	for (;;)
3687	{
3688	__first = ranges::find_if_not(ranges::next(__first), __last, __pred, __proj);
3689	if (__first == __last)
3690	return {__found, __first};
3691	__found = __first;
3692	}
3693	}
3694	}
3695
3696	template<forward_range _Range, typename _Proj = identity,
3697	indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
3698	constexpr borrowed_subrange_t<_Range>
3699	operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
3700	{ return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__pred), std::move(__proj)); }
3701	};
3702
3703	inline constexpr __find_last_if_not_fn find_last_if_not{};
3704
3705	#define __cpp_lib_ranges_fold 202207L
3706
3707	template<typename _Iter, typename _Tp>
3708	struct in_value_result
3709	{
3710	[[no_unique_address]] _Iter in;
3711	[[no_unique_address]] _Tp value;
3712
3713	template<typename _Iter2, typename _Tp2>
3714	requires convertible_to<const _Iter&, _Iter2>
3715	&& convertible_to<const _Tp&, _Tp2>
3716	constexpr
3717	operator in_value_result<_Iter2, _Tp2>() const &
3718	{ return {in, value}; }
3719
3720	template<typename _Iter2, typename _Tp2>
3721	requires convertible_to<_Iter, _Iter2>
3722	&& convertible_to<_Tp, _Tp2>
3723	constexpr
3724	operator in_value_result<_Iter2, _Tp2>() &&
3725	{ return {std::move(in), std::move(value)}; }
3726	};
3727
3728	namespace __detail
3729	{
3730	template<typename _Fp>
3731	class __flipped
3732	{
3733	_Fp _M_f;
3734
3735	public:
3736	template<typename _Tp, typename _Up>
3737	requires invocable<_Fp&, _Up, _Tp>
3738	invoke_result_t<_Fp&, _Up, _Tp>
3739	operator()(_Tp&&, _Up&&); // not defined
3740	};
3741
3742	template<typename _Fp, typename _Tp, typename _Iter, typename _Up>
3743	concept __indirectly_binary_left_foldable_impl = movable<_Tp> && movable<_Up>
3744	&& convertible_to<_Tp, _Up>
3745	&& invocable<_Fp&, _Up, iter_reference_t<_Iter>>
3746	&& assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Iter>>>;
3747
3748	template<typename _Fp, typename _Tp, typename _Iter>
3749	concept __indirectly_binary_left_foldable = copy_constructible<_Fp>
3750	&& indirectly_readable<_Iter>
3751	&& invocable<_Fp&, _Tp, iter_reference_t<_Iter>>
3752	&& convertible_to<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>,
3753	decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>
3754	&& __indirectly_binary_left_foldable_impl
3755	<_Fp, _Tp, _Iter, decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>;
3756
3757	template <typename _Fp, typename _Tp, typename _Iter>
3758	concept __indirectly_binary_right_foldable
3759	= __indirectly_binary_left_foldable<__flipped<_Fp>, _Tp, _Iter>;
3760	} // namespace __detail
3761
3762	template<typename _Iter, typename _Tp>
3763	using fold_left_with_iter_result = in_value_result<_Iter, _Tp>;
3764
3765	struct __fold_left_with_iter_fn
3766	{
3767	template<typename _Ret_iter,
3768	typename _Iter, typename _Sent, typename _Tp, typename _Fp>
3769	static constexpr auto
3770	_S_impl(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
3771	{
3772	using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>;
3773	using _Ret = fold_left_with_iter_result<_Ret_iter, _Up>;
3774
3775	if (__first == __last)
3776	return _Ret{std::move(__first), _Up(std::move(__init))};
3777
3778	_Up __accum = std::__invoke(__f, std::move(__init), *__first);
3779	for (++__first; __first != __last; ++__first)
3780	__accum = std::__invoke(__f, std::move(__accum), *__first);
3781	return _Ret{std::move(__first), std::move(__accum)};
3782	}
3783
3784	template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
3785	__detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
3786	constexpr auto
3787	operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const
3788	{
3789	using _Ret_iter = _Iter;
3790	return _S_impl<_Ret_iter>(std::move(__first), __last,
3791	std::move(__init), std::move(__f));
3792	}
3793
3794	template<input_range _Range, typename _Tp,
3795	__detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
3796	constexpr auto
3797	operator()(_Range&& __r, _Tp __init, _Fp __f) const
3798	{
3799	using _Ret_iter = borrowed_iterator_t<_Range>;
3800	return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r),
3801	std::move(__init), std::move(__f));
3802	}
3803	};
3804
3805	inline constexpr __fold_left_with_iter_fn fold_left_with_iter{};
3806
3807	struct __fold_left_fn
3808	{
3809	template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
3810	__detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
3811	constexpr auto
3812	operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const
3813	{
3814	return ranges::fold_left_with_iter(std::move(__first), __last,
3815	std::move(__init), std::move(__f)).value;
3816	}
3817
3818	template<input_range _Range, typename _Tp,
3819	__detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
3820	constexpr auto
3821	operator()(_Range&& __r, _Tp __init, _Fp __f) const
3822	{ return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__init), std::move(__f)); }
3823	};
3824
3825	inline constexpr __fold_left_fn fold_left{};
3826
3827	template<typename _Iter, typename _Tp>
3828	using fold_left_first_with_iter_result = in_value_result<_Iter, _Tp>;
3829
3830	struct __fold_left_first_with_iter_fn
3831	{
3832	template<typename _Ret_iter, typename _Iter, typename _Sent, typename _Fp>
3833	static constexpr auto
3834	_S_impl(_Iter __first, _Sent __last, _Fp __f)
3835	{
3836	using _Up = decltype(ranges::fold_left(std::move(__first), __last,
3837	iter_value_t<_Iter>(*__first), __f));
3838	using _Ret = fold_left_first_with_iter_result<_Ret_iter, optional<_Up>>;
3839
3840	if (__first == __last)
3841	return _Ret{std::move(__first), optional<_Up>()};
3842
3843	optional<_Up> __init(in_place, *__first);
3844	for (++__first; __first != __last; ++__first)
3845	*__init = std::__invoke(__f, std::move(*__init), *__first);
3846	return _Ret{std::move(__first), std::move(__init)};
3847	}
3848
3849	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3850	__detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3851	requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3852	constexpr auto
3853	operator()(_Iter __first, _Sent __last, _Fp __f) const
3854	{
3855	using _Ret_iter = _Iter;
3856	return _S_impl<_Ret_iter>(std::move(__first), __last, std::move(__f));
3857	}
3858
3859	template<input_range _Range,
3860	__detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3861	requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3862	constexpr auto
3863	operator()(_Range&& __r, _Fp __f) const
3864	{
3865	using _Ret_iter = borrowed_iterator_t<_Range>;
3866	return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r), std::move(__f));
3867	}
3868	};
3869
3870	inline constexpr __fold_left_first_with_iter_fn fold_left_first_with_iter{};
3871
3872	struct __fold_left_first_fn
3873	{
3874	template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3875	__detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3876	requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3877	constexpr auto
3878	operator()(_Iter __first, _Sent __last, _Fp __f) const
3879	{
3880	return ranges::fold_left_first_with_iter(std::move(__first), __last,
3881	std::move(__f)).value;
3882	}
3883
3884	template<input_range _Range,
3885	__detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3886	requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3887	constexpr auto
3888	operator()(_Range&& __r, _Fp __f) const
3889	{ return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__f)); }
3890	};
3891
3892	inline constexpr __fold_left_first_fn fold_left_first{};
3893
3894	struct __fold_right_fn
3895	{
3896	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
3897	__detail::__indirectly_binary_right_foldable<_Tp, _Iter> _Fp>
3898	constexpr auto
3899	operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f) const
3900	{
3901	using _Up = decay_t<invoke_result_t<_Fp&, iter_reference_t<_Iter>, _Tp>>;
3902
3903	if (__first == __last)
3904	return _Up(std::move(__init));
3905
3906	_Iter __tail = ranges::next(__first, __last);
3907	_Up __accum = std::__invoke(__f, *--__tail, std::move(__init));
3908	while (__first != __tail)
3909	__accum = std::__invoke(__f, *--__tail, std::move(__accum));
3910	return __accum;
3911	}
3912
3913	template<bidirectional_range _Range, typename _Tp,
3914	__detail::__indirectly_binary_right_foldable<_Tp, iterator_t<_Range>> _Fp>
3915	constexpr auto
3916	operator()(_Range&& __r, _Tp __init, _Fp __f) const
3917	{ return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__init), std::move(__f)); }
3918	};
3919
3920	inline constexpr __fold_right_fn fold_right{};
3921
3922	struct __fold_right_last_fn
3923	{
3924	template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3925	__detail::__indirectly_binary_right_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3926	requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3927	constexpr auto
3928	operator()(_Iter __first, _Sent __last, _Fp __f) const
3929	{
3930	using _Up = decltype(ranges::fold_right(__first, __last,
3931	iter_value_t<_Iter>(*__first), __f));
3932
3933	if (__first == __last)
3934	return optional<_Up>();
3935
3936	_Iter __tail = ranges::prev(ranges::next(__first, std::move(__last)));
3937	return optional<_Up>(in_place,
3938	ranges::fold_right(std::move(__first), __tail,
3939	iter_value_t<_Iter>(*__tail),
3940	std::move(__f)));
3941	}
3942
3943	template<bidirectional_range _Range,
3944	__detail::__indirectly_binary_right_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3945	requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3946	constexpr auto
3947	operator()(_Range&& __r, _Fp __f) const
3948	{ return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__f)); }
3949	};
3950
3951	inline constexpr __fold_right_last_fn fold_right_last{};
3952	#endif // C++23
3953	} // namespace ranges
3954
3955	#define __cpp_lib_shift 201806L
3956	template<typename _ForwardIterator>
3957	constexpr _ForwardIterator
3958	shift_left(_ForwardIterator __first, _ForwardIterator __last,
3959	typename iterator_traits<_ForwardIterator>::difference_type __n)
3960	{
3961	__glibcxx_assert(__n >= 0);
3962	if (__n == 0)
3963	return __last;
3964
3965	auto __mid = ranges::next(__first, __n, __last);
3966	if (__mid == __last)
3967	return __first;
3968	return std::move(std::move(__mid), std::move(__last), std::move(__first));
3969	}
3970
3971	template<typename _ForwardIterator>
3972	constexpr _ForwardIterator
3973	shift_right(_ForwardIterator __first, _ForwardIterator __last,
3974	typename iterator_traits<_ForwardIterator>::difference_type __n)
3975	{
3976	__glibcxx_assert(__n >= 0);
3977	if (__n == 0)
3978	return __first;
3979
3980	using _Cat
3981	= typename iterator_traits<_ForwardIterator>::iterator_category;
3982	if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
3983	{
3984	auto __mid = ranges::next(__last, -__n, __first);
3985	if (__mid == __first)
3986	return __last;
3987
3988	return std::move_backward(std::move(__first), std::move(__mid),
3989	std::move(__last));
3990	}
3991	else
3992	{
3993	auto __result = ranges::next(__first, __n, __last);
3994	if (__result == __last)
3995	return __last;
3996
3997	auto __dest_head = __first, __dest_tail = __result;
3998	while (__dest_head != __result)
3999	{
4000	if (__dest_tail == __last)
4001	{
4002	// If we get here, then we must have
4003	// 2*n >= distance(__first, __last)
4004	// i.e. we are shifting out at least half of the range. In
4005	// this case we can safely perform the shift with a single
4006	// move.
4007	std::move(std::move(__first), std::move(__dest_head), __result);
4008	return __result;
4009	}
4010	++__dest_head;
4011	++__dest_tail;
4012	}
4013
4014	for (;;)
4015	{
4016	// At the start of each iteration of this outer loop, the range
4017	// [__first, __result) contains those elements that after shifting
4018	// the whole range right by __n, should end up in
4019	// [__dest_head, __dest_tail) in order.
4020
4021	// The below inner loop swaps the elements of [__first, __result)
4022	// and [__dest_head, __dest_tail), while simultaneously shifting
4023	// the latter range by __n.
4024	auto __cursor = __first;
4025	while (__cursor != __result)
4026	{
4027	if (__dest_tail == __last)
4028	{
4029	// At this point the ranges [__first, result) and
4030	// [__dest_head, dest_tail) are disjoint, so we can safely
4031	// move the remaining elements.
4032	__dest_head = std::move(__cursor, __result,
4033	std::move(__dest_head));
4034	std::move(std::move(__first), std::move(__cursor),
4035	std::move(__dest_head));
4036	return __result;
4037	}
4038	std::iter_swap(__cursor, __dest_head);
4039	++__dest_head;
4040	++__dest_tail;
4041	++__cursor;
4042	}
4043	}
4044	}
4045	}
4046
4047	_GLIBCXX_END_NAMESPACE_VERSION
4048	} // namespace std
4049	#endif // concepts
4050	#endif // C++20
4051	#endif // _RANGES_ALGO_H
4052