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