1	// <ranges> -*- C++ -*-
2
3	// Copyright (C) 2019-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 include/ranges
26	* This is a Standard C++ Library header.
27	* @ingroup concepts
28	*/
29
30	#ifndef _GLIBCXX_RANGES
31	#define _GLIBCXX_RANGES 1
32
33	#if __cplusplus > 201703L
34
35	#pragma GCC system_header
36
37	#include <concepts>
38
39	#if __cpp_lib_concepts
40
41	#include <compare>
42	#include <initializer_list>
43	#include <iterator>
44	#include <optional>
45	#include <tuple>
46	#include <bits/ranges_util.h>
47	#include <bits/refwrap.h>
48
49	/**
50	* @defgroup ranges Ranges
51	*
52	* Components for dealing with ranges of elements.
53	*/
54
55	namespace std _GLIBCXX_VISIBILITY(default)
56	{
57	_GLIBCXX_BEGIN_NAMESPACE_VERSION
58	namespace ranges
59	{
60	// [range.access] customization point objects
61	// [range.req] range and view concepts
62	// [range.dangling] dangling iterator handling
63	// Defined in <bits/ranges_base.h>
64
65	// [view.interface] View interface
66	// [range.subrange] Sub-ranges
67	// Defined in <bits/ranges_util.h>
68
69	// C++20 24.6 [range.factories] Range factories
70
71	/// A view that contains no elements.
72	template<typename _Tp> requires is_object_v<_Tp>
73	class empty_view
74	: public view_interface<empty_view<_Tp>>
75	{
76	public:
77	static constexpr _Tp* begin() noexcept { return nullptr; }
78	static constexpr _Tp* end() noexcept { return nullptr; }
79	static constexpr _Tp* data() noexcept { return nullptr; }
80	static constexpr size_t size() noexcept { return 0; }
81	static constexpr bool empty() noexcept { return true; }
82	};
83
84	template<typename _Tp>
85	inline constexpr bool enable_borrowed_range<empty_view<_Tp>> = true;
86
87	namespace __detail
88	{
89	template<typename _Tp>
90	concept __boxable = copy_constructible<_Tp> && is_object_v<_Tp>;
91
92	template<__boxable _Tp>
93	struct __box : std::optional<_Tp>
94	{
95	using std::optional<_Tp>::optional;
96
97	constexpr
98	__box()
99	noexcept(is_nothrow_default_constructible_v<_Tp>)
100	requires default_initializable<_Tp>
101	: std::optional<_Tp>{std::in_place}
102	{ }
103
104	__box(const __box&) = default;
105	__box(__box&&) = default;
106
107	using std::optional<_Tp>::operator=;
108
109	// _GLIBCXX_RESOLVE_LIB_DEFECTS
110	// 3477. Simplify constraints for semiregular-box
111	__box&
112	operator=(const __box& __that)
113	noexcept(is_nothrow_copy_constructible_v<_Tp>)
114	requires (!copyable<_Tp>)
115	{
116	if (this != std::__addressof(__that))
117	{
118	if ((bool)__that)
119	this->emplace(*__that);
120	else
121	this->reset();
122	}
123	return *this;
124	}
125
126	__box&
127	operator=(__box&& __that)
128	noexcept(is_nothrow_move_constructible_v<_Tp>)
129	requires (!movable<_Tp>)
130	{
131	if (this != std::__addressof(__that))
132	{
133	if ((bool)__that)
134	this->emplace(std::move(*__that));
135	else
136	this->reset();
137	}
138	return *this;
139	}
140	};
141
142	// For types which are already copyable, this specialization of the
143	// copyable wrapper stores the object directly without going through
144	// std::optional. It provides just the subset of the primary template's
145	// API that we currently use.
146	template<__boxable _Tp>
147	requires copyable<_Tp>
148	struct __box<_Tp>
149	{
150	private:
151	[[no_unique_address]] _Tp _M_value = _Tp();
152
153	public:
154	__box() requires default_initializable<_Tp> = default;
155
156	constexpr explicit
157	__box(const _Tp& __t)
158	noexcept(is_nothrow_copy_constructible_v<_Tp>)
159	: _M_value(__t)
160	{ }
161
162	constexpr explicit
163	__box(_Tp&& __t)
164	noexcept(is_nothrow_move_constructible_v<_Tp>)
165	: _M_value(std::move(__t))
166	{ }
167
168	template<typename... _Args>
169	requires constructible_from<_Tp, _Args...>
170	constexpr explicit
171	__box(in_place_t, _Args&&... __args)
172	noexcept(is_nothrow_constructible_v<_Tp, _Args...>)
173	: _M_value(std::forward<_Args>(__args)...)
174	{ }
175
176	constexpr bool
177	has_value() const noexcept
178	{ return true; };
179
180	constexpr _Tp&
181	operator*() noexcept
182	{ return _M_value; }
183
184	constexpr const _Tp&
185	operator*() const noexcept
186	{ return _M_value; }
187
188	constexpr _Tp*
189	operator->() noexcept
190	{ return std::__addressof(_M_value); }
191
192	constexpr const _Tp*
193	operator->() const noexcept
194	{ return std::__addressof(_M_value); }
195	};
196	} // namespace __detail
197
198	/// A view that contains exactly one element.
199	template<copy_constructible _Tp> requires is_object_v<_Tp>
200	class single_view : public view_interface<single_view<_Tp>>
201	{
202	public:
203	single_view() = default;
204
205	constexpr explicit
206	single_view(const _Tp& __t)
207	: _M_value(__t)
208	{ }
209
210	constexpr explicit
211	single_view(_Tp&& __t)
212	: _M_value(std::move(__t))
213	{ }
214
215	// _GLIBCXX_RESOLVE_LIB_DEFECTS
216	// 3428. single_view's in place constructor should be explicit
217	template<typename... _Args>
218	requires constructible_from<_Tp, _Args...>
219	constexpr explicit
220	single_view(in_place_t, _Args&&... __args)
221	: _M_value{in_place, std::forward<_Args>(__args)...}
222	{ }
223
224	constexpr _Tp*
225	begin() noexcept
226	{ return data(); }
227
228	constexpr const _Tp*
229	begin() const noexcept
230	{ return data(); }
231
232	constexpr _Tp*
233	end() noexcept
234	{ return data() + 1; }
235
236	constexpr const _Tp*
237	end() const noexcept
238	{ return data() + 1; }
239
240	static constexpr size_t
241	size() noexcept
242	{ return 1; }
243
244	constexpr _Tp*
245	data() noexcept
246	{ return _M_value.operator->(); }
247
248	constexpr const _Tp*
249	data() const noexcept
250	{ return _M_value.operator->(); }
251
252	private:
253	[[no_unique_address]] __detail::__box<_Tp> _M_value;
254	};
255
256	template<typename _Tp>
257	single_view(_Tp) -> single_view<_Tp>;
258
259	namespace __detail
260	{
261	template<typename _Wp>
262	constexpr auto __to_signed_like(_Wp __w) noexcept
263	{
264	if constexpr (!integral<_Wp>)
265	return iter_difference_t<_Wp>();
266	else if constexpr (sizeof(iter_difference_t<_Wp>) > sizeof(_Wp))
267	return iter_difference_t<_Wp>(__w);
268	else if constexpr (sizeof(ptrdiff_t) > sizeof(_Wp))
269	return ptrdiff_t(__w);
270	else if constexpr (sizeof(long long) > sizeof(_Wp))
271	return (long long)(__w);
272	#ifdef __SIZEOF_INT128__
273	else if constexpr (__SIZEOF_INT128__ > sizeof(_Wp))
274	return __int128(__w);
275	#endif
276	else
277	return __max_diff_type(__w);
278	}
279
280	template<typename _Wp>
281	using __iota_diff_t = decltype(__to_signed_like(std::declval<_Wp>()));
282
283	template<typename _It>
284	concept __decrementable = incrementable<_It>
285	&& requires(_It __i)
286	{
287	{ --__i } -> same_as<_It&>;
288	{ __i-- } -> same_as<_It>;
289	};
290
291	template<typename _It>
292	concept __advanceable = __decrementable<_It> && totally_ordered<_It>
293	&& requires( _It __i, const _It __j, const __iota_diff_t<_It> __n)
294	{
295	{ __i += __n } -> same_as<_It&>;
296	{ __i -= __n } -> same_as<_It&>;
297	_It(__j + __n);
298	_It(__n + __j);
299	_It(__j - __n);
300	{ __j - __j } -> convertible_to<__iota_diff_t<_It>>;
301	};
302
303	template<typename _Winc>
304	struct __iota_view_iter_cat
305	{ };
306
307	template<incrementable _Winc>
308	struct __iota_view_iter_cat<_Winc>
309	{ using iterator_category = input_iterator_tag; };
310	} // namespace __detail
311
312	template<weakly_incrementable _Winc,
313	semiregular _Bound = unreachable_sentinel_t>
314	requires std::__detail::__weakly_eq_cmp_with<_Winc, _Bound>
315	&& copyable<_Winc>
316	class iota_view : public view_interface<iota_view<_Winc, _Bound>>
317	{
318	private:
319	struct _Sentinel;
320
321	struct _Iterator : __detail::__iota_view_iter_cat<_Winc>
322	{
323	private:
324	static auto
325	_S_iter_concept()
326	{
327	using namespace __detail;
328	if constexpr (__advanceable<_Winc>)
329	return random_access_iterator_tag{};
330	else if constexpr (__decrementable<_Winc>)
331	return bidirectional_iterator_tag{};
332	else if constexpr (incrementable<_Winc>)
333	return forward_iterator_tag{};
334	else
335	return input_iterator_tag{};
336	}
337
338	public:
339	using iterator_concept = decltype(_S_iter_concept());
340	// iterator_category defined in __iota_view_iter_cat
341	using value_type = _Winc;
342	using difference_type = __detail::__iota_diff_t<_Winc>;
343
344	_Iterator() requires default_initializable<_Winc> = default;
345
346	constexpr explicit
347	_Iterator(_Winc __value)
348	: _M_value(__value) { }
349
350	constexpr _Winc
351	operator*() const noexcept(is_nothrow_copy_constructible_v<_Winc>)
352	{ return _M_value; }
353
354	constexpr _Iterator&
355	operator++()
356	{
357	++_M_value;
358	return *this;
359	}
360
361	constexpr void
362	operator++(int)
363	{ ++*this; }
364
365	constexpr _Iterator
366	operator++(int) requires incrementable<_Winc>
367	{
368	auto __tmp = *this;
369	++*this;
370	return __tmp;
371	}
372
373	constexpr _Iterator&
374	operator--() requires __detail::__decrementable<_Winc>
375	{
376	--_M_value;
377	return *this;
378	}
379
380	constexpr _Iterator
381	operator--(int) requires __detail::__decrementable<_Winc>
382	{
383	auto __tmp = *this;
384	--*this;
385	return __tmp;
386	}
387
388	constexpr _Iterator&
389	operator+=(difference_type __n) requires __detail::__advanceable<_Winc>
390	{
391	using __detail::__is_integer_like;
392	using __detail::__is_signed_integer_like;
393	if constexpr (__is_integer_like<_Winc>
394	&& !__is_signed_integer_like<_Winc>)
395	{
396	if (__n >= difference_type(0))
397	_M_value += static_cast<_Winc>(__n);
398	else
399	_M_value -= static_cast<_Winc>(-__n);
400	}
401	else
402	_M_value += __n;
403	return *this;
404	}
405
406	constexpr _Iterator&
407	operator-=(difference_type __n) requires __detail::__advanceable<_Winc>
408	{
409	using __detail::__is_integer_like;
410	using __detail::__is_signed_integer_like;
411	if constexpr (__is_integer_like<_Winc>
412	&& !__is_signed_integer_like<_Winc>)
413	{
414	if (__n >= difference_type(0))
415	_M_value -= static_cast<_Winc>(__n);
416	else
417	_M_value += static_cast<_Winc>(-__n);
418	}
419	else
420	_M_value -= __n;
421	return *this;
422	}
423
424	constexpr _Winc
425	operator[](difference_type __n) const
426	requires __detail::__advanceable<_Winc>
427	{ return _Winc(_M_value + __n); }
428
429	friend constexpr bool
430	operator==(const _Iterator& __x, const _Iterator& __y)
431	requires equality_comparable<_Winc>
432	{ return __x._M_value == __y._M_value; }
433
434	friend constexpr bool
435	operator<(const _Iterator& __x, const _Iterator& __y)
436	requires totally_ordered<_Winc>
437	{ return __x._M_value < __y._M_value; }
438
439	friend constexpr bool
440	operator>(const _Iterator& __x, const _Iterator& __y)
441	requires totally_ordered<_Winc>
442	{ return __y < __x; }
443
444	friend constexpr bool
445	operator<=(const _Iterator& __x, const _Iterator& __y)
446	requires totally_ordered<_Winc>
447	{ return !(__y < __x); }
448
449	friend constexpr bool
450	operator>=(const _Iterator& __x, const _Iterator& __y)
451	requires totally_ordered<_Winc>
452	{ return !(__x < __y); }
453
454	#ifdef __cpp_lib_three_way_comparison
455	friend constexpr auto
456	operator<=>(const _Iterator& __x, const _Iterator& __y)
457	requires totally_ordered<_Winc> && three_way_comparable<_Winc>
458	{ return __x._M_value <=> __y._M_value; }
459	#endif
460
461	friend constexpr _Iterator
462	operator+(_Iterator __i, difference_type __n)
463	requires __detail::__advanceable<_Winc>
464	{
465	__i += __n;
466	return __i;
467	}
468
469	friend constexpr _Iterator
470	operator+(difference_type __n, _Iterator __i)
471	requires __detail::__advanceable<_Winc>
472	{ return __i += __n; }
473
474	friend constexpr _Iterator
475	operator-(_Iterator __i, difference_type __n)
476	requires __detail::__advanceable<_Winc>
477	{
478	__i -= __n;
479	return __i;
480	}
481
482	friend constexpr difference_type
483	operator-(const _Iterator& __x, const _Iterator& __y)
484	requires __detail::__advanceable<_Winc>
485	{
486	using __detail::__is_integer_like;
487	using __detail::__is_signed_integer_like;
488	using _Dt = difference_type;
489	if constexpr (__is_integer_like<_Winc>)
490	{
491	if constexpr (__is_signed_integer_like<_Winc>)
492	return _Dt(_Dt(__x._M_value) - _Dt(__y._M_value));
493	else
494	return (__y._M_value > __x._M_value)
495	? _Dt(-_Dt(__y._M_value - __x._M_value))
496	: _Dt(__x._M_value - __y._M_value);
497	}
498	else
499	return __x._M_value - __y._M_value;
500	}
501
502	private:
503	_Winc _M_value = _Winc();
504
505	friend iota_view;
506	friend _Sentinel;
507	};
508
509	struct _Sentinel
510	{
511	private:
512	constexpr bool
513	_M_equal(const _Iterator& __x) const
514	{ return __x._M_value == _M_bound; }
515
516	constexpr auto
517	_M_distance_from(const _Iterator& __x) const
518	{ return _M_bound - __x._M_value; }
519
520	_Bound _M_bound = _Bound();
521
522	public:
523	_Sentinel() = default;
524
525	constexpr explicit
526	_Sentinel(_Bound __bound)
527	: _M_bound(__bound) { }
528
529	friend constexpr bool
530	operator==(const _Iterator& __x, const _Sentinel& __y)
531	{ return __y._M_equal(__x); }
532
533	friend constexpr iter_difference_t<_Winc>
534	operator-(const _Iterator& __x, const _Sentinel& __y)
535	requires sized_sentinel_for<_Bound, _Winc>
536	{ return -__y._M_distance_from(__x); }
537
538	friend constexpr iter_difference_t<_Winc>
539	operator-(const _Sentinel& __x, const _Iterator& __y)
540	requires sized_sentinel_for<_Bound, _Winc>
541	{ return __x._M_distance_from(__y); }
542
543	friend iota_view;
544	};
545
546	_Winc _M_value = _Winc();
547	[[no_unique_address]] _Bound _M_bound = _Bound();
548
549	public:
550	iota_view() requires default_initializable<_Winc> = default;
551
552	constexpr explicit
553	iota_view(_Winc __value)
554	: _M_value(__value)
555	{ }
556
557	constexpr
558	iota_view(type_identity_t<_Winc> __value,
559	type_identity_t<_Bound> __bound)
560	: _M_value(__value), _M_bound(__bound)
561	{
562	if constexpr (totally_ordered_with<_Winc, _Bound>)
563	__glibcxx_assert( bool(__value <= __bound) );
564	}
565
566	constexpr
567	iota_view(_Iterator __first, _Iterator __last)
568	requires same_as<_Winc, _Bound>
569	: iota_view(__first._M_value, __last._M_value)
570	{ }
571
572	constexpr
573	iota_view(_Iterator __first, unreachable_sentinel_t __last)
574	requires same_as<_Bound, unreachable_sentinel_t>
575	: iota_view(__first._M_value, __last)
576	{ }
577
578	constexpr
579	iota_view(_Iterator __first, _Sentinel __last)
580	requires (!same_as<_Winc, _Bound>) && (!same_as<_Bound, unreachable_sentinel_t>)
581	: iota_view(__first._M_value, __last._M_bound)
582	{ }
583
584	constexpr _Iterator
585	begin() const { return _Iterator{_M_value}; }
586
587	constexpr auto
588	end() const
589	{
590	if constexpr (same_as<_Bound, unreachable_sentinel_t>)
591	return unreachable_sentinel;
592	else
593	return _Sentinel{_M_bound};
594	}
595
596	constexpr _Iterator
597	end() const requires same_as<_Winc, _Bound>
598	{ return _Iterator{_M_bound}; }
599
600	constexpr auto
601	size() const
602	requires (same_as<_Winc, _Bound> && __detail::__advanceable<_Winc>)
603	|| (integral<_Winc> && integral<_Bound>)
604	|| sized_sentinel_for<_Bound, _Winc>
605	{
606	using __detail::__is_integer_like;
607	using __detail::__to_unsigned_like;
608	if constexpr (integral<_Winc> && integral<_Bound>)
609	{
610	using _Up = make_unsigned_t<decltype(_M_bound - _M_value)>;
611	return _Up(_M_bound) - _Up(_M_value);
612	}
613	else if constexpr (__is_integer_like<_Winc>)
614	return __to_unsigned_like(_M_bound) - __to_unsigned_like(_M_value);
615	else
616	return __to_unsigned_like(_M_bound - _M_value);
617	}
618	};
619
620	template<typename _Winc, typename _Bound>
621	requires (!__detail::__is_integer_like<_Winc>
622	|| !__detail::__is_integer_like<_Bound>
623	|| (__detail::__is_signed_integer_like<_Winc>
624	== __detail::__is_signed_integer_like<_Bound>))
625	iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>;
626
627	template<weakly_incrementable _Winc, semiregular _Bound>
628	inline constexpr bool
629	enable_borrowed_range<iota_view<_Winc, _Bound>> = true;
630
631	namespace views
632	{
633	template<typename _Tp>
634	inline constexpr empty_view<_Tp> empty{};
635
636	struct _Single
637	{
638	template<typename _Tp>
639	constexpr auto
640	operator()(_Tp&& __e) const
641	{ return single_view<decay_t<_Tp>>(std::forward<_Tp>(__e)); }
642	};
643
644	inline constexpr _Single single{};
645
646	struct _Iota
647	{
648	template<typename _Tp>
649	constexpr auto
650	operator()(_Tp&& __e) const
651	{ return iota_view(std::forward<_Tp>(__e)); }
652
653	template<typename _Tp, typename _Up>
654	constexpr auto
655	operator()(_Tp&& __e, _Up&& __f) const
656	{ return iota_view(std::forward<_Tp>(__e), std::forward<_Up>(__f)); }
657	};
658
659	inline constexpr _Iota iota{};
660	} // namespace views
661
662	namespace __detail
663	{
664	template<typename _Val, typename _CharT, typename _Traits>
665	concept __stream_extractable
666	= requires(basic_istream<_CharT, _Traits>& is, _Val& t) { is >> t; };
667	} // namespace __detail
668
669	template<movable _Val, typename _CharT,
670	typename _Traits = char_traits<_CharT>>
671	requires default_initializable<_Val>
672	&& __detail::__stream_extractable<_Val, _CharT, _Traits>
673	class basic_istream_view
674	: public view_interface<basic_istream_view<_Val, _CharT, _Traits>>
675	{
676	public:
677	basic_istream_view() = default;
678
679	constexpr explicit
680	basic_istream_view(basic_istream<_CharT, _Traits>& __stream)
681	: _M_stream(std::__addressof(__stream))
682	{ }
683
684	constexpr auto
685	begin()
686	{
687	if (_M_stream != nullptr)
688	*_M_stream >> _M_object;
689	return _Iterator{this};
690	}
691
692	constexpr default_sentinel_t
693	end() const noexcept
694	{ return default_sentinel; }
695
696	private:
697	basic_istream<_CharT, _Traits>* _M_stream = nullptr;
698	_Val _M_object = _Val();
699
700	struct _Iterator
701	{
702	public:
703	using iterator_concept = input_iterator_tag;
704	using difference_type = ptrdiff_t;
705	using value_type = _Val;
706
707	_Iterator() = default;
708
709	constexpr explicit
710	_Iterator(basic_istream_view* __parent) noexcept
711	: _M_parent(__parent)
712	{ }
713
714	_Iterator(const _Iterator&) = delete;
715	_Iterator(_Iterator&&) = default;
716	_Iterator& operator=(const _Iterator&) = delete;
717	_Iterator& operator=(_Iterator&&) = default;
718
719	_Iterator&
720	operator++()
721	{
722	__glibcxx_assert(_M_parent->_M_stream != nullptr);
723	*_M_parent->_M_stream >> _M_parent->_M_object;
724	return *this;
725	}
726
727	void
728	operator++(int)
729	{ ++*this; }
730
731	_Val&
732	operator*() const
733	{
734	__glibcxx_assert(_M_parent->_M_stream != nullptr);
735	return _M_parent->_M_object;
736	}
737
738	friend bool
739	operator==(const _Iterator& __x, default_sentinel_t)
740	{ return __x._M_at_end(); }
741
742	private:
743	basic_istream_view* _M_parent = nullptr;
744
745	bool
746	_M_at_end() const
747	{ return _M_parent == nullptr || !*_M_parent->_M_stream; }
748	};
749
750	friend _Iterator;
751	};
752
753	template<typename _Val, typename _CharT, typename _Traits>
754	basic_istream_view<_Val, _CharT, _Traits>
755	istream_view(basic_istream<_CharT, _Traits>& __s)
756	{ return basic_istream_view<_Val, _CharT, _Traits>{__s}; }
757
758	// C++20 24.7 [range.adaptors] Range adaptors
759
760	namespace __detail
761	{
762	struct _Empty { };
763
764	// Alias for a type that is conditionally present
765	// (and is an empty type otherwise).
766	// Data members using this alias should use [[no_unique_address]] so that
767	// they take no space when not needed.
768	template<bool _Present, typename _Tp>
769	using __maybe_present_t = conditional_t<_Present, _Tp, _Empty>;
770
771	// Alias for a type that is conditionally const.
772	template<bool _Const, typename _Tp>
773	using __maybe_const_t = conditional_t<_Const, const _Tp, _Tp>;
774
775	} // namespace __detail
776
777	namespace views::__adaptor
778	{
779	// True if the range adaptor _Adaptor can be applied with _Args.
780	template<typename _Adaptor, typename... _Args>
781	concept __adaptor_invocable
782	= requires { std::declval<_Adaptor>()(declval<_Args>()...); };
783
784	// True if the range adaptor non-closure _Adaptor can be partially applied
785	// with _Args.
786	template<typename _Adaptor, typename... _Args>
787	concept __adaptor_partial_app_viable = (_Adaptor::_S_arity > 1)
788	&& (sizeof...(_Args) == _Adaptor::_S_arity - 1)
789	&& (constructible_from<decay_t<_Args>, _Args> && ...);
790
791	template<typename _Adaptor, typename... _Args>
792	struct _Partial;
793
794	template<typename _Lhs, typename _Rhs>
795	struct _Pipe;
796
797	// The base class of every range adaptor closure.
798	//
799	// The derived class should define the optional static data member
800	// _S_has_simple_call_op to true if the behavior of this adaptor is
801	// independent of the constness/value category of the adaptor object.
802	struct _RangeAdaptorClosure
803	{
804	// range | adaptor is equivalent to adaptor(range).
805	template<typename _Self, typename _Range>
806	requires derived_from<remove_cvref_t<_Self>, _RangeAdaptorClosure>
807	&& __adaptor_invocable<_Self, _Range>
808	friend constexpr auto
809	operator|(_Range&& __r, _Self&& __self)
810	{ return std::forward<_Self>(__self)(std::forward<_Range>(__r)); }
811
812	// Compose the adaptors __lhs and __rhs into a pipeline, returning
813	// another range adaptor closure object.
814	template<typename _Lhs, typename _Rhs>
815	requires derived_from<_Lhs, _RangeAdaptorClosure>
816	&& derived_from<_Rhs, _RangeAdaptorClosure>
817	friend constexpr auto
818	operator|(_Lhs __lhs, _Rhs __rhs)
819	{ return _Pipe<_Lhs, _Rhs>{std::move(__lhs), std::move(__rhs)}; }
820	};
821
822	// The base class of every range adaptor non-closure.
823	//
824	// The static data member _Derived::_S_arity must contain the total number of
825	// arguments that the adaptor takes, and the class _Derived must introduce
826	// _RangeAdaptor::operator() into the class scope via a using-declaration.
827	//
828	// The optional static data member _Derived::_S_has_simple_extra_args should
829	// be defined to true if the behavior of this adaptor is independent of the
830	// constness/value category of the extra arguments. This data member could
831	// also be defined as a variable template parameterized by the types of the
832	// extra arguments.
833	template<typename _Derived>
834	struct _RangeAdaptor
835	{
836	// Partially apply the arguments __args to the range adaptor _Derived,
837	// returning a range adaptor closure object.
838	template<typename... _Args>
839	requires __adaptor_partial_app_viable<_Derived, _Args...>
840	constexpr auto
841	operator()(_Args&&... __args) const
842	{
843	return _Partial<_Derived, decay_t<_Args>...>{std::forward<_Args>(__args)...};
844	}
845	};
846
847	// True if the range adaptor closure _Adaptor has a simple operator(), i.e.
848	// one that's not overloaded according to constness or value category of the
849	// _Adaptor object.
850	template<typename _Adaptor>
851	concept __closure_has_simple_call_op = _Adaptor::_S_has_simple_call_op;
852
853	// True if the behavior of the range adaptor non-closure _Adaptor is
854	// independent of the value category of its extra arguments _Args.
855	template<typename _Adaptor, typename... _Args>
856	concept __adaptor_has_simple_extra_args = _Adaptor::_S_has_simple_extra_args
857	|| _Adaptor::template _S_has_simple_extra_args<_Args...>;
858
859	// A range adaptor closure that represents partial application of
860	// the range adaptor _Adaptor with arguments _Args.
861	template<typename _Adaptor, typename... _Args>
862	struct _Partial : _RangeAdaptorClosure
863	{
864	tuple<_Args...> _M_args;
865
866	constexpr
867	_Partial(_Args... __args)
868	: _M_args(std::move(__args)...)
869	{ }
870
871	// Invoke _Adaptor with arguments __r, _M_args... according to the
872	// value category of this _Partial object.
873	template<typename _Range>
874	requires __adaptor_invocable<_Adaptor, _Range, const _Args&...>
875	constexpr auto
876	operator()(_Range&& __r) const &
877	{
878	auto __forwarder = [&__r] (const auto&... __args) {
879	return _Adaptor{}(std::forward<_Range>(__r), __args...);
880	};
881	return std::apply(__forwarder, _M_args);
882	}
883
884	template<typename _Range>
885	requires __adaptor_invocable<_Adaptor, _Range, _Args...>
886	constexpr auto
887	operator()(_Range&& __r) &&
888	{
889	auto __forwarder = [&__r] (auto&... __args) {
890	return _Adaptor{}(std::forward<_Range>(__r), std::move(__args)...);
891	};
892	return std::apply(__forwarder, _M_args);
893	}
894
895	template<typename _Range>
896	constexpr auto
897	operator()(_Range&& __r) const && = delete;
898	};
899
900	// A lightweight specialization of the above primary template for
901	// the common case where _Adaptor accepts a single extra argument.
902	template<typename _Adaptor, typename _Arg>
903	struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure
904	{
905	_Arg _M_arg;
906
907	constexpr
908	_Partial(_Arg __arg)
909	: _M_arg(std::move(__arg))
910	{ }
911
912	template<typename _Range>
913	requires __adaptor_invocable<_Adaptor, _Range, const _Arg&>
914	constexpr auto
915	operator()(_Range&& __r) const &
916	{ return _Adaptor{}(std::forward<_Range>(__r), _M_arg); }
917
918	template<typename _Range>
919	requires __adaptor_invocable<_Adaptor, _Range, _Arg>
920	constexpr auto
921	operator()(_Range&& __r) &&
922	{ return _Adaptor{}(std::forward<_Range>(__r), std::move(_M_arg)); }
923
924	template<typename _Range>
925	constexpr auto
926	operator()(_Range&& __r) const && = delete;
927	};
928
929	// Partial specialization of the primary template for the case where the extra
930	// arguments of the adaptor can always be safely and efficiently forwarded by
931	// const reference. This lets us get away with a single operator() overload,
932	// which makes overload resolution failure diagnostics more concise.
933	template<typename _Adaptor, typename... _Args>
934	requires __adaptor_has_simple_extra_args<_Adaptor, _Args...>
935	&& (is_trivially_copyable_v<_Args> && ...)
936	struct _Partial<_Adaptor, _Args...> : _RangeAdaptorClosure
937	{
938	tuple<_Args...> _M_args;
939
940	constexpr
941	_Partial(_Args... __args)
942	: _M_args(std::move(__args)...)
943	{ }
944
945	// Invoke _Adaptor with arguments __r, const _M_args&... regardless
946	// of the value category of this _Partial object.
947	template<typename _Range>
948	requires __adaptor_invocable<_Adaptor, _Range, const _Args&...>
949	constexpr auto
950	operator()(_Range&& __r) const
951	{
952	auto __forwarder = [&__r] (const auto&... __args) {
953	return _Adaptor{}(std::forward<_Range>(__r), __args...);
954	};
955	return std::apply(__forwarder, _M_args);
956	}
957
958	static constexpr bool _S_has_simple_call_op = true;
959	};
960
961	// A lightweight specialization of the above template for the common case
962	// where _Adaptor accepts a single extra argument.
963	template<typename _Adaptor, typename _Arg>
964	requires __adaptor_has_simple_extra_args<_Adaptor, _Arg>
965	&& is_trivially_copyable_v<_Arg>
966	struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure
967	{
968	_Arg _M_arg;
969
970	constexpr
971	_Partial(_Arg __arg)
972	: _M_arg(std::move(__arg))
973	{ }
974
975	template<typename _Range>
976	requires __adaptor_invocable<_Adaptor, _Range, const _Arg&>
977	constexpr auto
978	operator()(_Range&& __r) const
979	{ return _Adaptor{}(std::forward<_Range>(__r), _M_arg); }
980
981	static constexpr bool _S_has_simple_call_op = true;
982	};
983
984	template<typename _Lhs, typename _Rhs, typename _Range>
985	concept __pipe_invocable
986	= requires { std::declval<_Rhs>()(std::declval<_Lhs>()(std::declval<_Range>())); };
987
988	// A range adaptor closure that represents composition of the range
989	// adaptor closures _Lhs and _Rhs.
990	template<typename _Lhs, typename _Rhs>
991	struct _Pipe : _RangeAdaptorClosure
992	{
993	[[no_unique_address]] _Lhs _M_lhs;
994	[[no_unique_address]] _Rhs _M_rhs;
995
996	constexpr
997	_Pipe(_Lhs __lhs, _Rhs __rhs)
998	: _M_lhs(std::move(__lhs)), _M_rhs(std::move(__rhs))
999	{ }
1000
1001	// Invoke _M_rhs(_M_lhs(__r)) according to the value category of this
1002	// range adaptor closure object.
1003	template<typename _Range>
1004	requires __pipe_invocable<const _Lhs&, const _Rhs&, _Range>
1005	constexpr auto
1006	operator()(_Range&& __r) const &
1007	{ return _M_rhs(_M_lhs(std::forward<_Range>(__r))); }
1008
1009	template<typename _Range>
1010	requires __pipe_invocable<_Lhs, _Rhs, _Range>
1011	constexpr auto
1012	operator()(_Range&& __r) &&
1013	{ return std::move(_M_rhs)(std::move(_M_lhs)(std::forward<_Range>(__r))); }
1014
1015	template<typename _Range>
1016	constexpr auto
1017	operator()(_Range&& __r) const && = delete;
1018	};
1019
1020	// A partial specialization of the above primary template for the case where
1021	// both adaptor operands have a simple operator(). This in turn lets us
1022	// implement composition using a single simple operator(), which makes
1023	// overload resolution failure diagnostics more concise.
1024	template<typename _Lhs, typename _Rhs>
1025	requires __closure_has_simple_call_op<_Lhs>
1026	&& __closure_has_simple_call_op<_Rhs>
1027	struct _Pipe<_Lhs, _Rhs> : _RangeAdaptorClosure
1028	{
1029	[[no_unique_address]] _Lhs _M_lhs;
1030	[[no_unique_address]] _Rhs _M_rhs;
1031
1032	constexpr
1033	_Pipe(_Lhs __lhs, _Rhs __rhs)
1034	: _M_lhs(std::move(__lhs)), _M_rhs(std::move(__rhs))
1035	{ }
1036
1037	template<typename _Range>
1038	requires __pipe_invocable<const _Lhs&, const _Rhs&, _Range>
1039	constexpr auto
1040	operator()(_Range&& __r) const
1041	{ return _M_rhs(_M_lhs(std::forward<_Range>(__r))); }
1042
1043	static constexpr bool _S_has_simple_call_op = true;
1044	};
1045	} // namespace views::__adaptor
1046
1047	template<range _Range> requires is_object_v<_Range>
1048	class ref_view : public view_interface<ref_view<_Range>>
1049	{
1050	private:
1051	_Range* _M_r = nullptr;
1052
1053	static void _S_fun(_Range&); // not defined
1054	static void _S_fun(_Range&&) = delete;
1055
1056	public:
1057	constexpr
1058	ref_view() noexcept = default;
1059
1060	template<__detail::__not_same_as<ref_view> _Tp>
1061	requires convertible_to<_Tp, _Range&>
1062	&& requires { _S_fun(declval<_Tp>()); }
1063	constexpr
1064	ref_view(_Tp&& __t)
1065	: _M_r(std::__addressof(static_cast<_Range&>(std::forward<_Tp>(__t))))
1066	{ }
1067
1068	constexpr _Range&
1069	base() const
1070	{ return *_M_r; }
1071
1072	constexpr iterator_t<_Range>
1073	begin() const
1074	{ return ranges::begin(*_M_r); }
1075
1076	constexpr sentinel_t<_Range>
1077	end() const
1078	{ return ranges::end(*_M_r); }
1079
1080	constexpr bool
1081	empty() const requires requires { ranges::empty(*_M_r); }
1082	{ return ranges::empty(*_M_r); }
1083
1084	constexpr auto
1085	size() const requires sized_range<_Range>
1086	{ return ranges::size(*_M_r); }
1087
1088	constexpr auto
1089	data() const requires contiguous_range<_Range>
1090	{ return ranges::data(*_M_r); }
1091	};
1092
1093	template<typename _Range>
1094	ref_view(_Range&) -> ref_view<_Range>;
1095
1096	template<typename _Tp>
1097	inline constexpr bool enable_borrowed_range<ref_view<_Tp>> = true;
1098
1099	namespace views
1100	{
1101	namespace __detail
1102	{
1103	template<typename _Range>
1104	concept __can_ref_view = requires { ref_view{std::declval<_Range>()}; };
1105
1106	template<typename _Range>
1107	concept __can_subrange = requires { subrange{std::declval<_Range>()}; };
1108	} // namespace __detail
1109
1110	struct _All : __adaptor::_RangeAdaptorClosure
1111	{
1112	template<viewable_range _Range>
1113	requires view<decay_t<_Range>>
1114	|| __detail::__can_ref_view<_Range>
1115	|| __detail::__can_subrange<_Range>
1116	constexpr auto
1117	operator()(_Range&& __r) const
1118	{
1119	if constexpr (view<decay_t<_Range>>)
1120	return std::forward<_Range>(__r);
1121	else if constexpr (__detail::__can_ref_view<_Range>)
1122	return ref_view{std::forward<_Range>(__r)};
1123	else
1124	return subrange{std::forward<_Range>(__r)};
1125	}
1126
1127	static constexpr bool _S_has_simple_call_op = true;
1128	};
1129
1130	inline constexpr _All all;
1131
1132	template<viewable_range _Range>
1133	using all_t = decltype(all(std::declval<_Range>()));
1134	} // namespace views
1135
1136	namespace __detail
1137	{
1138	template<typename _Tp>
1139	struct __non_propagating_cache
1140	{
1141	// When _Tp is not an object type (e.g. is a reference type), we make
1142	// __non_propagating_cache<_Tp> empty rather than ill-formed so that
1143	// users can easily conditionally declare data members with this type
1144	// (such as join_view::_M_inner).
1145	};
1146
1147	template<typename _Tp>
1148	requires is_object_v<_Tp>
1149	struct __non_propagating_cache<_Tp> : protected _Optional_base<_Tp>
1150	{
1151	__non_propagating_cache() = default;
1152
1153	constexpr
1154	__non_propagating_cache(const __non_propagating_cache&) noexcept
1155	{ }
1156
1157	constexpr
1158	__non_propagating_cache(__non_propagating_cache&& __other) noexcept
1159	{ __other._M_reset(); }
1160
1161	constexpr __non_propagating_cache&
1162	operator=(const __non_propagating_cache& __other) noexcept
1163	{
1164	if (std::__addressof(__other) != this)
1165	this->_M_reset();
1166	return *this;
1167	}
1168
1169	constexpr __non_propagating_cache&
1170	operator=(__non_propagating_cache&& __other) noexcept
1171	{
1172	this->_M_reset();
1173	__other._M_reset();
1174	return *this;
1175	}
1176
1177	constexpr _Tp&
1178	operator*() noexcept
1179	{ return this->_M_get(); }
1180
1181	constexpr const _Tp&
1182	operator*() const noexcept
1183	{ return this->_M_get(); }
1184
1185	template<typename _Iter>
1186	_Tp&
1187	_M_emplace_deref(const _Iter& __i)
1188	{
1189	this->_M_reset();
1190	// Using _Optional_base::_M_construct to initialize from '*__i'
1191	// would incur an extra move due to the indirection, so we instead
1192	// use placement new directly.
1193	::new ((void *) std::__addressof(this->_M_payload._M_payload)) _Tp(*__i);
1194	this->_M_payload._M_engaged = true;
1195	return this->_M_get();
1196	}
1197	};
1198
1199	template<range _Range>
1200	struct _CachedPosition
1201	{
1202	constexpr bool
1203	_M_has_value() const
1204	{ return false; }
1205
1206	constexpr iterator_t<_Range>
1207	_M_get(const _Range&) const
1208	{
1209	__glibcxx_assert(false);
1210	__builtin_unreachable();
1211	}
1212
1213	constexpr void
1214	_M_set(const _Range&, const iterator_t<_Range>&) const
1215	{ }
1216	};
1217
1218	template<forward_range _Range>
1219	struct _CachedPosition<_Range>
1220	: protected __non_propagating_cache<iterator_t<_Range>>
1221	{
1222	constexpr bool
1223	_M_has_value() const
1224	{ return this->_M_is_engaged(); }
1225
1226	constexpr iterator_t<_Range>
1227	_M_get(const _Range&) const
1228	{
1229	__glibcxx_assert(_M_has_value());
1230	return **this;
1231	}
1232
1233	constexpr void
1234	_M_set(const _Range&, const iterator_t<_Range>& __it)
1235	{
1236	__glibcxx_assert(!_M_has_value());
1237	std::construct_at(std::__addressof(this->_M_payload._M_payload),
1238	in_place, __it);
1239	this->_M_payload._M_engaged = true;
1240	}
1241	};
1242
1243	template<random_access_range _Range>
1244	requires (sizeof(range_difference_t<_Range>)
1245	<= sizeof(iterator_t<_Range>))
1246	struct _CachedPosition<_Range>
1247	{
1248	private:
1249	range_difference_t<_Range> _M_offset = -1;
1250
1251	public:
1252	_CachedPosition() = default;
1253
1254	constexpr
1255	_CachedPosition(const _CachedPosition&) = default;
1256
1257	constexpr
1258	_CachedPosition(_CachedPosition&& __other) noexcept
1259	{ *this = std::move(__other); }
1260
1261	constexpr _CachedPosition&
1262	operator=(const _CachedPosition&) = default;
1263
1264	constexpr _CachedPosition&
1265	operator=(_CachedPosition&& __other) noexcept
1266	{
1267	// Propagate the cached offset, but invalidate the source.
1268	_M_offset = __other._M_offset;
1269	__other._M_offset = -1;
1270	return *this;
1271	}
1272
1273	constexpr bool
1274	_M_has_value() const
1275	{ return _M_offset >= 0; }
1276
1277	constexpr iterator_t<_Range>
1278	_M_get(_Range& __r) const
1279	{
1280	__glibcxx_assert(_M_has_value());
1281	return ranges::begin(__r) + _M_offset;
1282	}
1283
1284	constexpr void
1285	_M_set(_Range& __r, const iterator_t<_Range>& __it)
1286	{
1287	__glibcxx_assert(!_M_has_value());
1288	_M_offset = __it - ranges::begin(__r);
1289	}
1290	};
1291	} // namespace __detail
1292
1293	namespace __detail
1294	{
1295	template<typename _Base>
1296	struct __filter_view_iter_cat
1297	{ };
1298
1299	template<forward_range _Base>
1300	struct __filter_view_iter_cat<_Base>
1301	{
1302	private:
1303	static auto
1304	_S_iter_cat()
1305	{
1306	using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
1307	if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
1308	return bidirectional_iterator_tag{};
1309	else if constexpr (derived_from<_Cat, forward_iterator_tag>)
1310	return forward_iterator_tag{};
1311	else
1312	return _Cat{};
1313	}
1314	public:
1315	using iterator_category = decltype(_S_iter_cat());
1316	};
1317	} // namespace __detail
1318
1319	template<input_range _Vp,
1320	indirect_unary_predicate<iterator_t<_Vp>> _Pred>
1321	requires view<_Vp> && is_object_v<_Pred>
1322	class filter_view : public view_interface<filter_view<_Vp, _Pred>>
1323	{
1324	private:
1325	struct _Sentinel;
1326
1327	struct _Iterator : __detail::__filter_view_iter_cat<_Vp>
1328	{
1329	private:
1330	static constexpr auto
1331	_S_iter_concept()
1332	{
1333	if constexpr (bidirectional_range<_Vp>)
1334	return bidirectional_iterator_tag{};
1335	else if constexpr (forward_range<_Vp>)
1336	return forward_iterator_tag{};
1337	else
1338	return input_iterator_tag{};
1339	}
1340
1341	friend filter_view;
1342
1343	using _Vp_iter = iterator_t<_Vp>;
1344
1345	_Vp_iter _M_current = _Vp_iter();
1346	filter_view* _M_parent = nullptr;
1347
1348	public:
1349	using iterator_concept = decltype(_S_iter_concept());
1350	// iterator_category defined in __filter_view_iter_cat
1351	using value_type = range_value_t<_Vp>;
1352	using difference_type = range_difference_t<_Vp>;
1353
1354	_Iterator() requires default_initializable<_Vp_iter> = default;
1355
1356	constexpr
1357	_Iterator(filter_view* __parent, _Vp_iter __current)
1358	: _M_current(std::move(__current)),
1359	_M_parent(__parent)
1360	{ }
1361
1362	constexpr const _Vp_iter&
1363	base() const & noexcept
1364	{ return _M_current; }
1365
1366	constexpr _Vp_iter
1367	base() &&
1368	{ return std::move(_M_current); }
1369
1370	constexpr range_reference_t<_Vp>
1371	operator*() const
1372	{ return *_M_current; }
1373
1374	constexpr _Vp_iter
1375	operator->() const
1376	requires __detail::__has_arrow<_Vp_iter>
1377	&& copyable<_Vp_iter>
1378	{ return _M_current; }
1379
1380	constexpr _Iterator&
1381	operator++()
1382	{
1383	_M_current = ranges::find_if(std::move(++_M_current),
1384	ranges::end(_M_parent->_M_base),
1385	std::ref(*_M_parent->_M_pred));
1386	return *this;
1387	}
1388
1389	constexpr void
1390	operator++(int)
1391	{ ++*this; }
1392
1393	constexpr _Iterator
1394	operator++(int) requires forward_range<_Vp>
1395	{
1396	auto __tmp = *this;
1397	++*this;
1398	return __tmp;
1399	}
1400
1401	constexpr _Iterator&
1402	operator--() requires bidirectional_range<_Vp>
1403	{
1404	do
1405	--_M_current;
1406	while (!std::__invoke(*_M_parent->_M_pred, *_M_current));
1407	return *this;
1408	}
1409
1410	constexpr _Iterator
1411	operator--(int) requires bidirectional_range<_Vp>
1412	{
1413	auto __tmp = *this;
1414	--*this;
1415	return __tmp;
1416	}
1417
1418	friend constexpr bool
1419	operator==(const _Iterator& __x, const _Iterator& __y)
1420	requires equality_comparable<_Vp_iter>
1421	{ return __x._M_current == __y._M_current; }
1422
1423	friend constexpr range_rvalue_reference_t<_Vp>
1424	iter_move(const _Iterator& __i)
1425	noexcept(noexcept(ranges::iter_move(__i._M_current)))
1426	{ return ranges::iter_move(__i._M_current); }
1427
1428	friend constexpr void
1429	iter_swap(const _Iterator& __x, const _Iterator& __y)
1430	noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1431	requires indirectly_swappable<_Vp_iter>
1432	{ ranges::iter_swap(__x._M_current, __y._M_current); }
1433	};
1434
1435	struct _Sentinel
1436	{
1437	private:
1438	sentinel_t<_Vp> _M_end = sentinel_t<_Vp>();
1439
1440	constexpr bool
1441	__equal(const _Iterator& __i) const
1442	{ return __i._M_current == _M_end; }
1443
1444	public:
1445	_Sentinel() = default;
1446
1447	constexpr explicit
1448	_Sentinel(filter_view* __parent)
1449	: _M_end(ranges::end(__parent->_M_base))
1450	{ }
1451
1452	constexpr sentinel_t<_Vp>
1453	base() const
1454	{ return _M_end; }
1455
1456	friend constexpr bool
1457	operator==(const _Iterator& __x, const _Sentinel& __y)
1458	{ return __y.__equal(__x); }
1459	};
1460
1461	[[no_unique_address]] __detail::__box<_Pred> _M_pred;
1462	[[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
1463	_Vp _M_base = _Vp();
1464
1465	public:
1466	filter_view() requires default_initializable<_Vp> = default;
1467
1468	constexpr
1469	filter_view(_Vp __base, _Pred __pred)
1470	: _M_pred(std::move(__pred)), _M_base(std::move(__base))
1471	{ }
1472
1473	constexpr _Vp
1474	base() const& requires copy_constructible<_Vp>
1475	{ return _M_base; }
1476
1477	constexpr _Vp
1478	base() &&
1479	{ return std::move(_M_base); }
1480
1481	constexpr const _Pred&
1482	pred() const
1483	{ return *_M_pred; }
1484
1485	constexpr _Iterator
1486	begin()
1487	{
1488	if (_M_cached_begin._M_has_value())
1489	return {this, _M_cached_begin._M_get(_M_base)};
1490
1491	__glibcxx_assert(_M_pred.has_value());
1492	auto __it = ranges::find_if(ranges::begin(_M_base),
1493	ranges::end(_M_base),
1494	std::ref(*_M_pred));
1495	_M_cached_begin._M_set(_M_base, __it);
1496	return {this, std::move(__it)};
1497	}
1498
1499	constexpr auto
1500	end()
1501	{
1502	if constexpr (common_range<_Vp>)
1503	return _Iterator{this, ranges::end(_M_base)};
1504	else
1505	return _Sentinel{this};
1506	}
1507	};
1508
1509	template<typename _Range, typename _Pred>
1510	filter_view(_Range&&, _Pred) -> filter_view<views::all_t<_Range>, _Pred>;
1511
1512	namespace views
1513	{
1514	namespace __detail
1515	{
1516	template<typename _Range, typename _Pred>
1517	concept __can_filter_view
1518	= requires { filter_view(std::declval<_Range>(), std::declval<_Pred>()); };
1519	} // namespace __detail
1520
1521	struct _Filter : __adaptor::_RangeAdaptor<_Filter>
1522	{
1523	template<viewable_range _Range, typename _Pred>
1524	requires __detail::__can_filter_view<_Range, _Pred>
1525	constexpr auto
1526	operator()(_Range&& __r, _Pred&& __p) const
1527	{
1528	return filter_view(std::forward<_Range>(__r), std::forward<_Pred>(__p));
1529	}
1530
1531	using _RangeAdaptor<_Filter>::operator();
1532	static constexpr int _S_arity = 2;
1533	static constexpr bool _S_has_simple_extra_args = true;
1534	};
1535
1536	inline constexpr _Filter filter;
1537	} // namespace views
1538
1539	template<input_range _Vp, copy_constructible _Fp>
1540	requires view<_Vp> && is_object_v<_Fp>
1541	&& regular_invocable<_Fp&, range_reference_t<_Vp>>
1542	&& std::__detail::__can_reference<invoke_result_t<_Fp&,
1543	range_reference_t<_Vp>>>
1544	class transform_view : public view_interface<transform_view<_Vp, _Fp>>
1545	{
1546	private:
1547	template<bool _Const>
1548	using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1549
1550	template<bool _Const>
1551	struct __iter_cat
1552	{ };
1553
1554	template<bool _Const>
1555	requires forward_range<_Base<_Const>>
1556	struct __iter_cat<_Const>
1557	{
1558	private:
1559	static auto
1560	_S_iter_cat()
1561	{
1562	using _Base = transform_view::_Base<_Const>;
1563	using _Res = invoke_result_t<_Fp&, range_reference_t<_Base>>;
1564	if constexpr (is_lvalue_reference_v<_Res>)
1565	{
1566	using _Cat
1567	= typename iterator_traits<iterator_t<_Base>>::iterator_category;
1568	if constexpr (derived_from<_Cat, contiguous_iterator_tag>)
1569	return random_access_iterator_tag{};
1570	else
1571	return _Cat{};
1572	}
1573	else
1574	return input_iterator_tag{};
1575	}
1576	public:
1577	using iterator_category = decltype(_S_iter_cat());
1578	};
1579
1580	template<bool _Const>
1581	struct _Sentinel;
1582
1583	template<bool _Const>
1584	struct _Iterator : __iter_cat<_Const>
1585	{
1586	private:
1587	using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1588	using _Base = transform_view::_Base<_Const>;
1589
1590	static auto
1591	_S_iter_concept()
1592	{
1593	if constexpr (random_access_range<_Base>)
1594	return random_access_iterator_tag{};
1595	else if constexpr (bidirectional_range<_Base>)
1596	return bidirectional_iterator_tag{};
1597	else if constexpr (forward_range<_Base>)
1598	return forward_iterator_tag{};
1599	else
1600	return input_iterator_tag{};
1601	}
1602
1603	using _Base_iter = iterator_t<_Base>;
1604
1605	_Base_iter _M_current = _Base_iter();
1606	_Parent* _M_parent = nullptr;
1607
1608	public:
1609	using iterator_concept = decltype(_S_iter_concept());
1610	// iterator_category defined in __transform_view_iter_cat
1611	using value_type
1612	= remove_cvref_t<invoke_result_t<_Fp&, range_reference_t<_Base>>>;
1613	using difference_type = range_difference_t<_Base>;
1614
1615	_Iterator() requires default_initializable<_Base_iter> = default;
1616
1617	constexpr
1618	_Iterator(_Parent* __parent, _Base_iter __current)
1619	: _M_current(std::move(__current)),
1620	_M_parent(__parent)
1621	{ }
1622
1623	constexpr
1624	_Iterator(_Iterator<!_Const> __i)
1625	requires _Const
1626	&& convertible_to<iterator_t<_Vp>, _Base_iter>
1627	: _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent)
1628	{ }
1629
1630	constexpr const _Base_iter&
1631	base() const & noexcept
1632	{ return _M_current; }
1633
1634	constexpr _Base_iter
1635	base() &&
1636	{ return std::move(_M_current); }
1637
1638	constexpr decltype(auto)
1639	operator*() const
1640	noexcept(noexcept(std::__invoke(*_M_parent->_M_fun, *_M_current)))
1641	{ return std::__invoke(*_M_parent->_M_fun, *_M_current); }
1642
1643	constexpr _Iterator&
1644	operator++()
1645	{
1646	++_M_current;
1647	return *this;
1648	}
1649
1650	constexpr void
1651	operator++(int)
1652	{ ++_M_current; }
1653
1654	constexpr _Iterator
1655	operator++(int) requires forward_range<_Base>
1656	{
1657	auto __tmp = *this;
1658	++*this;
1659	return __tmp;
1660	}
1661
1662	constexpr _Iterator&
1663	operator--() requires bidirectional_range<_Base>
1664	{
1665	--_M_current;
1666	return *this;
1667	}
1668
1669	constexpr _Iterator
1670	operator--(int) requires bidirectional_range<_Base>
1671	{
1672	auto __tmp = *this;
1673	--*this;
1674	return __tmp;
1675	}
1676
1677	constexpr _Iterator&
1678	operator+=(difference_type __n) requires random_access_range<_Base>
1679	{
1680	_M_current += __n;
1681	return *this;
1682	}
1683
1684	constexpr _Iterator&
1685	operator-=(difference_type __n) requires random_access_range<_Base>
1686	{
1687	_M_current -= __n;
1688	return *this;
1689	}
1690
1691	constexpr decltype(auto)
1692	operator[](difference_type __n) const
1693	requires random_access_range<_Base>
1694	{ return std::__invoke(*_M_parent->_M_fun, _M_current[__n]); }
1695
1696	friend constexpr bool
1697	operator==(const _Iterator& __x, const _Iterator& __y)
1698	requires equality_comparable<_Base_iter>
1699	{ return __x._M_current == __y._M_current; }
1700
1701	friend constexpr bool
1702	operator<(const _Iterator& __x, const _Iterator& __y)
1703	requires random_access_range<_Base>
1704	{ return __x._M_current < __y._M_current; }
1705
1706	friend constexpr bool
1707	operator>(const _Iterator& __x, const _Iterator& __y)
1708	requires random_access_range<_Base>
1709	{ return __y < __x; }
1710
1711	friend constexpr bool
1712	operator<=(const _Iterator& __x, const _Iterator& __y)
1713	requires random_access_range<_Base>
1714	{ return !(__y < __x); }
1715
1716	friend constexpr bool
1717	operator>=(const _Iterator& __x, const _Iterator& __y)
1718	requires random_access_range<_Base>
1719	{ return !(__x < __y); }
1720
1721	#ifdef __cpp_lib_three_way_comparison
1722	friend constexpr auto
1723	operator<=>(const _Iterator& __x, const _Iterator& __y)
1724	requires random_access_range<_Base>
1725	&& three_way_comparable<_Base_iter>
1726	{ return __x._M_current <=> __y._M_current; }
1727	#endif
1728
1729	friend constexpr _Iterator
1730	operator+(_Iterator __i, difference_type __n)
1731	requires random_access_range<_Base>
1732	{ return {__i._M_parent, __i._M_current + __n}; }
1733
1734	friend constexpr _Iterator
1735	operator+(difference_type __n, _Iterator __i)
1736	requires random_access_range<_Base>
1737	{ return {__i._M_parent, __i._M_current + __n}; }
1738
1739	friend constexpr _Iterator
1740	operator-(_Iterator __i, difference_type __n)
1741	requires random_access_range<_Base>
1742	{ return {__i._M_parent, __i._M_current - __n}; }
1743
1744	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1745	// 3483. transform_view::iterator's difference is overconstrained
1746	friend constexpr difference_type
1747	operator-(const _Iterator& __x, const _Iterator& __y)
1748	requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
1749	{ return __x._M_current - __y._M_current; }
1750
1751	friend constexpr decltype(auto)
1752	iter_move(const _Iterator& __i) noexcept(noexcept(*__i))
1753	{
1754	if constexpr (is_lvalue_reference_v<decltype(*__i)>)
1755	return std::move(*__i);
1756	else
1757	return *__i;
1758	}
1759
1760	friend _Iterator<!_Const>;
1761	template<bool> friend struct _Sentinel;
1762	};
1763
1764	template<bool _Const>
1765	struct _Sentinel
1766	{
1767	private:
1768	using _Parent = __detail::__maybe_const_t<_Const, transform_view>;
1769	using _Base = transform_view::_Base<_Const>;
1770
1771	template<bool _Const2>
1772	constexpr auto
1773	__distance_from(const _Iterator<_Const2>& __i) const
1774	{ return _M_end - __i._M_current; }
1775
1776	template<bool _Const2>
1777	constexpr bool
1778	__equal(const _Iterator<_Const2>& __i) const
1779	{ return __i._M_current == _M_end; }
1780
1781	sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1782
1783	public:
1784	_Sentinel() = default;
1785
1786	constexpr explicit
1787	_Sentinel(sentinel_t<_Base> __end)
1788	: _M_end(__end)
1789	{ }
1790
1791	constexpr
1792	_Sentinel(_Sentinel<!_Const> __i)
1793	requires _Const
1794	&& convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1795	: _M_end(std::move(__i._M_end))
1796	{ }
1797
1798	constexpr sentinel_t<_Base>
1799	base() const
1800	{ return _M_end; }
1801
1802	template<bool _Const2>
1803	requires sentinel_for<sentinel_t<_Base>,
1804	iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
1805	friend constexpr bool
1806	operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1807	{ return __y.__equal(__x); }
1808
1809	template<bool _Const2,
1810	typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1811	requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1812	friend constexpr range_difference_t<_Base2>
1813	operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
1814	{ return -__y.__distance_from(__x); }
1815
1816	template<bool _Const2,
1817	typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
1818	requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1819	friend constexpr range_difference_t<_Base2>
1820	operator-(const _Sentinel& __y, const _Iterator<_Const2>& __x)
1821	{ return __y.__distance_from(__x); }
1822
1823	friend _Sentinel<!_Const>;
1824	};
1825
1826	[[no_unique_address]] __detail::__box<_Fp> _M_fun;
1827	_Vp _M_base = _Vp();
1828
1829	public:
1830	transform_view() requires default_initializable<_Vp> = default;
1831
1832	constexpr
1833	transform_view(_Vp __base, _Fp __fun)
1834	: _M_fun(std::move(__fun)), _M_base(std::move(__base))
1835	{ }
1836
1837	constexpr _Vp
1838	base() const& requires copy_constructible<_Vp>
1839	{ return _M_base ; }
1840
1841	constexpr _Vp
1842	base() &&
1843	{ return std::move(_M_base); }
1844
1845	constexpr _Iterator<false>
1846	begin()
1847	{ return _Iterator<false>{this, ranges::begin(_M_base)}; }
1848
1849	constexpr _Iterator<true>
1850	begin() const
1851	requires range<const _Vp>
1852	&& regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1853	{ return _Iterator<true>{this, ranges::begin(_M_base)}; }
1854
1855	constexpr _Sentinel<false>
1856	end()
1857	{ return _Sentinel<false>{ranges::end(_M_base)}; }
1858
1859	constexpr _Iterator<false>
1860	end() requires common_range<_Vp>
1861	{ return _Iterator<false>{this, ranges::end(_M_base)}; }
1862
1863	constexpr _Sentinel<true>
1864	end() const
1865	requires range<const _Vp>
1866	&& regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1867	{ return _Sentinel<true>{ranges::end(_M_base)}; }
1868
1869	constexpr _Iterator<true>
1870	end() const
1871	requires common_range<const _Vp>
1872	&& regular_invocable<const _Fp&, range_reference_t<const _Vp>>
1873	{ return _Iterator<true>{this, ranges::end(_M_base)}; }
1874
1875	constexpr auto
1876	size() requires sized_range<_Vp>
1877	{ return ranges::size(_M_base); }
1878
1879	constexpr auto
1880	size() const requires sized_range<const _Vp>
1881	{ return ranges::size(_M_base); }
1882	};
1883
1884	template<typename _Range, typename _Fp>
1885	transform_view(_Range&&, _Fp) -> transform_view<views::all_t<_Range>, _Fp>;
1886
1887	namespace views
1888	{
1889	namespace __detail
1890	{
1891	template<typename _Range, typename _Fp>
1892	concept __can_transform_view
1893	= requires { transform_view(std::declval<_Range>(), std::declval<_Fp>()); };
1894	} // namespace __detail
1895
1896	struct _Transform : __adaptor::_RangeAdaptor<_Transform>
1897	{
1898	template<viewable_range _Range, typename _Fp>
1899	requires __detail::__can_transform_view<_Range, _Fp>
1900	constexpr auto
1901	operator()(_Range&& __r, _Fp&& __f) const
1902	{
1903	return transform_view(std::forward<_Range>(__r), std::forward<_Fp>(__f));
1904	}
1905
1906	using _RangeAdaptor<_Transform>::operator();
1907	static constexpr int _S_arity = 2;
1908	static constexpr bool _S_has_simple_extra_args = true;
1909	};
1910
1911	inline constexpr _Transform transform;
1912	} // namespace views
1913
1914	template<view _Vp>
1915	class take_view : public view_interface<take_view<_Vp>>
1916	{
1917	private:
1918	template<bool _Const>
1919	using _CI = counted_iterator<
1920	iterator_t<__detail::__maybe_const_t<_Const, _Vp>>>;
1921
1922	template<bool _Const>
1923	struct _Sentinel
1924	{
1925	private:
1926	using _Base = __detail::__maybe_const_t<_Const, _Vp>;
1927	sentinel_t<_Base> _M_end = sentinel_t<_Base>();
1928
1929	public:
1930	_Sentinel() = default;
1931
1932	constexpr explicit
1933	_Sentinel(sentinel_t<_Base> __end)
1934	: _M_end(__end)
1935	{ }
1936
1937	constexpr
1938	_Sentinel(_Sentinel<!_Const> __s)
1939	requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
1940	: _M_end(std::move(__s._M_end))
1941	{ }
1942
1943	constexpr sentinel_t<_Base>
1944	base() const
1945	{ return _M_end; }
1946
1947	friend constexpr bool
1948	operator==(const _CI<_Const>& __y, const _Sentinel& __x)
1949	{ return __y.count() == 0 || __y.base() == __x._M_end; }
1950
1951	template<bool _OtherConst = !_Const,
1952	typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
1953	requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
1954	friend constexpr bool
1955	operator==(const _CI<_OtherConst>& __y, const _Sentinel& __x)
1956	{ return __y.count() == 0 || __y.base() == __x._M_end; }
1957
1958	friend _Sentinel<!_Const>;
1959	};
1960
1961	range_difference_t<_Vp> _M_count = 0;
1962	_Vp _M_base = _Vp();
1963
1964	public:
1965	take_view() requires default_initializable<_Vp> = default;
1966
1967	constexpr
1968	take_view(_Vp base, range_difference_t<_Vp> __count)
1969	: _M_count(std::move(__count)), _M_base(std::move(base))
1970	{ }
1971
1972	constexpr _Vp
1973	base() const& requires copy_constructible<_Vp>
1974	{ return _M_base; }
1975
1976	constexpr _Vp
1977	base() &&
1978	{ return std::move(_M_base); }
1979
1980	constexpr auto
1981	begin() requires (!__detail::__simple_view<_Vp>)
1982	{
1983	if constexpr (sized_range<_Vp>)
1984	{
1985	if constexpr (random_access_range<_Vp>)
1986	return ranges::begin(_M_base);
1987	else
1988	{
1989	auto __sz = size();
1990	return counted_iterator(ranges::begin(_M_base), __sz);
1991	}
1992	}
1993	else
1994	return counted_iterator(ranges::begin(_M_base), _M_count);
1995	}
1996
1997	constexpr auto
1998	begin() const requires range<const _Vp>
1999	{
2000	if constexpr (sized_range<const _Vp>)
2001	{
2002	if constexpr (random_access_range<const _Vp>)
2003	return ranges::begin(_M_base);
2004	else
2005	{
2006	auto __sz = size();
2007	return counted_iterator(ranges::begin(_M_base), __sz);
2008	}
2009	}
2010	else
2011	return counted_iterator(ranges::begin(_M_base), _M_count);
2012	}
2013
2014	constexpr auto
2015	end() requires (!__detail::__simple_view<_Vp>)
2016	{
2017	if constexpr (sized_range<_Vp>)
2018	{
2019	if constexpr (random_access_range<_Vp>)
2020	return ranges::begin(_M_base) + size();
2021	else
2022	return default_sentinel;
2023	}
2024	else
2025	return _Sentinel<false>{ranges::end(_M_base)};
2026	}
2027
2028	constexpr auto
2029	end() const requires range<const _Vp>
2030	{
2031	if constexpr (sized_range<const _Vp>)
2032	{
2033	if constexpr (random_access_range<const _Vp>)
2034	return ranges::begin(_M_base) + size();
2035	else
2036	return default_sentinel;
2037	}
2038	else
2039	return _Sentinel<true>{ranges::end(_M_base)};
2040	}
2041
2042	constexpr auto
2043	size() requires sized_range<_Vp>
2044	{
2045	auto __n = ranges::size(_M_base);
2046	return std::min(__n, static_cast<decltype(__n)>(_M_count));
2047	}
2048
2049	constexpr auto
2050	size() const requires sized_range<const _Vp>
2051	{
2052	auto __n = ranges::size(_M_base);
2053	return std::min(__n, static_cast<decltype(__n)>(_M_count));
2054	}
2055	};
2056
2057	// _GLIBCXX_RESOLVE_LIB_DEFECTS
2058	// 3447. Deduction guides for take_view and drop_view have different
2059	// constraints
2060	template<typename _Range>
2061	take_view(_Range&&, range_difference_t<_Range>)
2062	-> take_view<views::all_t<_Range>>;
2063
2064	template<typename _Tp>
2065	inline constexpr bool enable_borrowed_range<take_view<_Tp>>
2066	= enable_borrowed_range<_Tp>;
2067
2068	namespace views
2069	{
2070	namespace __detail
2071	{
2072	template<typename _Range, typename _Tp>
2073	concept __can_take_view
2074	= requires { take_view(std::declval<_Range>(), std::declval<_Tp>()); };
2075	} // namespace __detail
2076
2077	struct _Take : __adaptor::_RangeAdaptor<_Take>
2078	{
2079	template<viewable_range _Range, typename _Tp>
2080	requires __detail::__can_take_view<_Range, _Tp>
2081	constexpr auto
2082	operator()(_Range&& __r, _Tp&& __n) const
2083	{
2084	return take_view(std::forward<_Range>(__r), std::forward<_Tp>(__n));
2085	}
2086
2087	using _RangeAdaptor<_Take>::operator();
2088	static constexpr int _S_arity = 2;
2089	// The count argument of views::take is not always simple -- it can be
2090	// e.g. a move-only class that's implicitly convertible to the difference
2091	// type. But an integer-like count argument is surely simple.
2092	template<typename _Tp>
2093	static constexpr bool _S_has_simple_extra_args
2094	= ranges::__detail::__is_integer_like<_Tp>;
2095	};
2096
2097	inline constexpr _Take take;
2098	} // namespace views
2099
2100	template<view _Vp, typename _Pred>
2101	requires input_range<_Vp> && is_object_v<_Pred>
2102	&& indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2103	class take_while_view : public view_interface<take_while_view<_Vp, _Pred>>
2104	{
2105	template<bool _Const>
2106	struct _Sentinel
2107	{
2108	private:
2109	using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2110
2111	sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2112	const _Pred* _M_pred = nullptr;
2113
2114	public:
2115	_Sentinel() = default;
2116
2117	constexpr explicit
2118	_Sentinel(sentinel_t<_Base> __end, const _Pred* __pred)
2119	: _M_end(__end), _M_pred(__pred)
2120	{ }
2121
2122	constexpr
2123	_Sentinel(_Sentinel<!_Const> __s)
2124	requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2125	: _M_end(__s._M_end), _M_pred(__s._M_pred)
2126	{ }
2127
2128	constexpr sentinel_t<_Base>
2129	base() const { return _M_end; }
2130
2131	friend constexpr bool
2132	operator==(const iterator_t<_Base>& __x, const _Sentinel& __y)
2133	{ return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
2134
2135	template<bool _OtherConst = !_Const,
2136	typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>>
2137	requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
2138	friend constexpr bool
2139	operator==(const iterator_t<_Base2>& __x, const _Sentinel& __y)
2140	{ return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); }
2141
2142	friend _Sentinel<!_Const>;
2143	};
2144
2145	[[no_unique_address]] __detail::__box<_Pred> _M_pred;
2146	_Vp _M_base = _Vp();
2147
2148	public:
2149	take_while_view() requires default_initializable<_Vp> = default;
2150
2151	constexpr
2152	take_while_view(_Vp base, _Pred __pred)
2153	: _M_pred(std::move(__pred)), _M_base(std::move(base))
2154	{ }
2155
2156	constexpr _Vp
2157	base() const& requires copy_constructible<_Vp>
2158	{ return _M_base; }
2159
2160	constexpr _Vp
2161	base() &&
2162	{ return std::move(_M_base); }
2163
2164	constexpr const _Pred&
2165	pred() const
2166	{ return *_M_pred; }
2167
2168	constexpr auto
2169	begin() requires (!__detail::__simple_view<_Vp>)
2170	{ return ranges::begin(_M_base); }
2171
2172	constexpr auto
2173	begin() const requires range<const _Vp>
2174	&& indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
2175	{ return ranges::begin(_M_base); }
2176
2177	constexpr auto
2178	end() requires (!__detail::__simple_view<_Vp>)
2179	{ return _Sentinel<false>(ranges::end(_M_base),
2180	std::__addressof(*_M_pred)); }
2181
2182	constexpr auto
2183	end() const requires range<const _Vp>
2184	&& indirect_unary_predicate<const _Pred, iterator_t<const _Vp>>
2185	{ return _Sentinel<true>(ranges::end(_M_base),
2186	std::__addressof(*_M_pred)); }
2187	};
2188
2189	template<typename _Range, typename _Pred>
2190	take_while_view(_Range&&, _Pred)
2191	-> take_while_view<views::all_t<_Range>, _Pred>;
2192
2193	namespace views
2194	{
2195	namespace __detail
2196	{
2197	template<typename _Range, typename _Pred>
2198	concept __can_take_while_view
2199	= requires { take_while_view(std::declval<_Range>(), std::declval<_Pred>()); };
2200	} // namespace __detail
2201
2202	struct _TakeWhile : __adaptor::_RangeAdaptor<_TakeWhile>
2203	{
2204	template<viewable_range _Range, typename _Pred>
2205	requires __detail::__can_take_while_view<_Range, _Pred>
2206	constexpr auto
2207	operator()(_Range&& __r, _Pred&& __p) const
2208	{
2209	return take_while_view(std::forward<_Range>(__r), std::forward<_Pred>(__p));
2210	}
2211
2212	using _RangeAdaptor<_TakeWhile>::operator();
2213	static constexpr int _S_arity = 2;
2214	static constexpr bool _S_has_simple_extra_args = true;
2215	};
2216
2217	inline constexpr _TakeWhile take_while;
2218	} // namespace views
2219
2220	template<view _Vp>
2221	class drop_view : public view_interface<drop_view<_Vp>>
2222	{
2223	private:
2224	range_difference_t<_Vp> _M_count = 0;
2225	_Vp _M_base = _Vp();
2226
2227	// ranges::next(begin(base), count, end(base)) is O(1) if _Vp satisfies
2228	// both random_access_range and sized_range. Otherwise, cache its result.
2229	static constexpr bool _S_needs_cached_begin
2230	= !(random_access_range<const _Vp> && sized_range<const _Vp>);
2231	[[no_unique_address]]
2232	__detail::__maybe_present_t<_S_needs_cached_begin,
2233	__detail::_CachedPosition<_Vp>>
2234	_M_cached_begin;
2235
2236	public:
2237	drop_view() requires default_initializable<_Vp> = default;
2238
2239	constexpr
2240	drop_view(_Vp __base, range_difference_t<_Vp> __count)
2241	: _M_count(__count), _M_base(std::move(__base))
2242	{ __glibcxx_assert(__count >= 0); }
2243
2244	constexpr _Vp
2245	base() const& requires copy_constructible<_Vp>
2246	{ return _M_base; }
2247
2248	constexpr _Vp
2249	base() &&
2250	{ return std::move(_M_base); }
2251
2252	// This overload is disabled for simple views with constant-time begin().
2253	constexpr auto
2254	begin()
2255	requires (!(__detail::__simple_view<_Vp>
2256	&& random_access_range<const _Vp>
2257	&& sized_range<const _Vp>))
2258	{
2259	if constexpr (_S_needs_cached_begin)
2260	if (_M_cached_begin._M_has_value())
2261	return _M_cached_begin._M_get(_M_base);
2262
2263	auto __it = ranges::next(ranges::begin(_M_base),
2264	_M_count, ranges::end(_M_base));
2265	if constexpr (_S_needs_cached_begin)
2266	_M_cached_begin._M_set(_M_base, __it);
2267	return __it;
2268	}
2269
2270	// _GLIBCXX_RESOLVE_LIB_DEFECTS
2271	// 3482. drop_view's const begin should additionally require sized_range
2272	constexpr auto
2273	begin() const
2274	requires random_access_range<const _Vp> && sized_range<const _Vp>
2275	{
2276	return ranges::next(ranges::begin(_M_base), _M_count,
2277	ranges::end(_M_base));
2278	}
2279
2280	constexpr auto
2281	end() requires (!__detail::__simple_view<_Vp>)
2282	{ return ranges::end(_M_base); }
2283
2284	constexpr auto
2285	end() const requires range<const _Vp>
2286	{ return ranges::end(_M_base); }
2287
2288	constexpr auto
2289	size() requires sized_range<_Vp>
2290	{
2291	const auto __s = ranges::size(_M_base);
2292	const auto __c = static_cast<decltype(__s)>(_M_count);
2293	return __s < __c ? 0 : __s - __c;
2294	}
2295
2296	constexpr auto
2297	size() const requires sized_range<const _Vp>
2298	{
2299	const auto __s = ranges::size(_M_base);
2300	const auto __c = static_cast<decltype(__s)>(_M_count);
2301	return __s < __c ? 0 : __s - __c;
2302	}
2303	};
2304
2305	template<typename _Range>
2306	drop_view(_Range&&, range_difference_t<_Range>)
2307	-> drop_view<views::all_t<_Range>>;
2308
2309	template<typename _Tp>
2310	inline constexpr bool enable_borrowed_range<drop_view<_Tp>>
2311	= enable_borrowed_range<_Tp>;
2312
2313	namespace views
2314	{
2315	namespace __detail
2316	{
2317	template<typename _Range, typename _Tp>
2318	concept __can_drop_view
2319	= requires { drop_view(std::declval<_Range>(), std::declval<_Tp>()); };
2320	} // namespace __detail
2321
2322	struct _Drop : __adaptor::_RangeAdaptor<_Drop>
2323	{
2324	template<viewable_range _Range, typename _Tp>
2325	requires __detail::__can_drop_view<_Range, _Tp>
2326	constexpr auto
2327	operator()(_Range&& __r, _Tp&& __n) const
2328	{
2329	return drop_view(std::forward<_Range>(__r), std::forward<_Tp>(__n));
2330	}
2331
2332	using _RangeAdaptor<_Drop>::operator();
2333	static constexpr int _S_arity = 2;
2334	template<typename _Tp>
2335	static constexpr bool _S_has_simple_extra_args
2336	= _Take::_S_has_simple_extra_args<_Tp>;
2337	};
2338
2339	inline constexpr _Drop drop;
2340	} // namespace views
2341
2342	template<view _Vp, typename _Pred>
2343	requires input_range<_Vp> && is_object_v<_Pred>
2344	&& indirect_unary_predicate<const _Pred, iterator_t<_Vp>>
2345	class drop_while_view : public view_interface<drop_while_view<_Vp, _Pred>>
2346	{
2347	private:
2348	[[no_unique_address]] __detail::__box<_Pred> _M_pred;
2349	[[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin;
2350	_Vp _M_base = _Vp();
2351
2352	public:
2353	drop_while_view() requires default_initializable<_Vp> = default;
2354
2355	constexpr
2356	drop_while_view(_Vp __base, _Pred __pred)
2357	: _M_pred(std::move(__pred)), _M_base(std::move(__base))
2358	{ }
2359
2360	constexpr _Vp
2361	base() const& requires copy_constructible<_Vp>
2362	{ return _M_base; }
2363
2364	constexpr _Vp
2365	base() &&
2366	{ return std::move(_M_base); }
2367
2368	constexpr const _Pred&
2369	pred() const
2370	{ return *_M_pred; }
2371
2372	constexpr auto
2373	begin()
2374	{
2375	if (_M_cached_begin._M_has_value())
2376	return _M_cached_begin._M_get(_M_base);
2377
2378	__glibcxx_assert(_M_pred.has_value());
2379	auto __it = ranges::find_if_not(ranges::begin(_M_base),
2380	ranges::end(_M_base),
2381	std::cref(*_M_pred));
2382	_M_cached_begin._M_set(_M_base, __it);
2383	return __it;
2384	}
2385
2386	constexpr auto
2387	end()
2388	{ return ranges::end(_M_base); }
2389	};
2390
2391	template<typename _Range, typename _Pred>
2392	drop_while_view(_Range&&, _Pred)
2393	-> drop_while_view<views::all_t<_Range>, _Pred>;
2394
2395	template<typename _Tp, typename _Pred>
2396	inline constexpr bool enable_borrowed_range<drop_while_view<_Tp, _Pred>>
2397	= enable_borrowed_range<_Tp>;
2398
2399	namespace views
2400	{
2401	namespace __detail
2402	{
2403	template<typename _Range, typename _Pred>
2404	concept __can_drop_while_view
2405	= requires { drop_while_view(std::declval<_Range>(), std::declval<_Pred>()); };
2406	} // namespace __detail
2407
2408	struct _DropWhile : __adaptor::_RangeAdaptor<_DropWhile>
2409	{
2410	template<viewable_range _Range, typename _Pred>
2411	requires __detail::__can_drop_while_view<_Range, _Pred>
2412	constexpr auto
2413	operator()(_Range&& __r, _Pred&& __p) const
2414	{
2415	return drop_while_view(std::forward<_Range>(__r),
2416	std::forward<_Pred>(__p));
2417	}
2418
2419	using _RangeAdaptor<_DropWhile>::operator();
2420	static constexpr int _S_arity = 2;
2421	static constexpr bool _S_has_simple_extra_args = true;
2422	};
2423
2424	inline constexpr _DropWhile drop_while;
2425	} // namespace views
2426
2427	template<input_range _Vp>
2428	requires view<_Vp> && input_range<range_reference_t<_Vp>>
2429	class join_view : public view_interface<join_view<_Vp>>
2430	{
2431	private:
2432	using _InnerRange = range_reference_t<_Vp>;
2433
2434	template<bool _Const>
2435	using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2436
2437	template<bool _Const>
2438	using _Outer_iter = iterator_t<_Base<_Const>>;
2439
2440	template<bool _Const>
2441	using _Inner_iter = iterator_t<range_reference_t<_Base<_Const>>>;
2442
2443	template<bool _Const>
2444	static constexpr bool _S_ref_is_glvalue
2445	= is_reference_v<range_reference_t<_Base<_Const>>>;
2446
2447	template<bool _Const>
2448	struct __iter_cat
2449	{ };
2450
2451	template<bool _Const>
2452	requires _S_ref_is_glvalue<_Const>
2453	&& forward_range<_Base<_Const>>
2454	&& forward_range<range_reference_t<_Base<_Const>>>
2455	struct __iter_cat<_Const>
2456	{
2457	private:
2458	static constexpr auto
2459	_S_iter_cat()
2460	{
2461	using _Outer_iter = join_view::_Outer_iter<_Const>;
2462	using _Inner_iter = join_view::_Inner_iter<_Const>;
2463	using _OuterCat = typename iterator_traits<_Outer_iter>::iterator_category;
2464	using _InnerCat = typename iterator_traits<_Inner_iter>::iterator_category;
2465	if constexpr (derived_from<_OuterCat, bidirectional_iterator_tag>
2466	&& derived_from<_InnerCat, bidirectional_iterator_tag>
2467	&& common_range<range_reference_t<_Base<_Const>>>)
2468	return bidirectional_iterator_tag{};
2469	else if constexpr (derived_from<_OuterCat, forward_iterator_tag>
2470	&& derived_from<_InnerCat, forward_iterator_tag>)
2471	return forward_iterator_tag{};
2472	else
2473	return input_iterator_tag{};
2474	}
2475	public:
2476	using iterator_category = decltype(_S_iter_cat());
2477	};
2478
2479	template<bool _Const>
2480	struct _Sentinel;
2481
2482	template<bool _Const>
2483	struct _Iterator : __iter_cat<_Const>
2484	{
2485	private:
2486	using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2487	using _Base = join_view::_Base<_Const>;
2488
2489	static constexpr bool _S_ref_is_glvalue
2490	= join_view::_S_ref_is_glvalue<_Const>;
2491
2492	constexpr void
2493	_M_satisfy()
2494	{
2495	auto __update_inner = [this] (const iterator_t<_Base>& __x) -> auto&& {
2496	if constexpr (_S_ref_is_glvalue)
2497	return *__x;
2498	else
2499	return _M_parent->_M_inner._M_emplace_deref(__x);
2500	};
2501
2502	for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer)
2503	{
2504	auto&& __inner = __update_inner(_M_outer);
2505	_M_inner = ranges::begin(__inner);
2506	if (_M_inner != ranges::end(__inner))
2507	return;
2508	}
2509
2510	if constexpr (_S_ref_is_glvalue)
2511	_M_inner = _Inner_iter();
2512	}
2513
2514	static constexpr auto
2515	_S_iter_concept()
2516	{
2517	if constexpr (_S_ref_is_glvalue
2518	&& bidirectional_range<_Base>
2519	&& bidirectional_range<range_reference_t<_Base>>
2520	&& common_range<range_reference_t<_Base>>)
2521	return bidirectional_iterator_tag{};
2522	else if constexpr (_S_ref_is_glvalue
2523	&& forward_range<_Base>
2524	&& forward_range<range_reference_t<_Base>>)
2525	return forward_iterator_tag{};
2526	else
2527	return input_iterator_tag{};
2528	}
2529
2530	using _Outer_iter = join_view::_Outer_iter<_Const>;
2531	using _Inner_iter = join_view::_Inner_iter<_Const>;
2532
2533	_Outer_iter _M_outer = _Outer_iter();
2534	_Inner_iter _M_inner = _Inner_iter();
2535	_Parent* _M_parent = nullptr;
2536
2537	public:
2538	using iterator_concept = decltype(_S_iter_concept());
2539	// iterator_category defined in __join_view_iter_cat
2540	using value_type = range_value_t<range_reference_t<_Base>>;
2541	using difference_type
2542	= common_type_t<range_difference_t<_Base>,
2543	range_difference_t<range_reference_t<_Base>>>;
2544
2545	_Iterator() requires (default_initializable<_Outer_iter>
2546	&& default_initializable<_Inner_iter>)
2547	= default;
2548
2549	constexpr
2550	_Iterator(_Parent* __parent, _Outer_iter __outer)
2551	: _M_outer(std::move(__outer)),
2552	_M_parent(__parent)
2553	{ _M_satisfy(); }
2554
2555	constexpr
2556	_Iterator(_Iterator<!_Const> __i)
2557	requires _Const
2558	&& convertible_to<iterator_t<_Vp>, _Outer_iter>
2559	&& convertible_to<iterator_t<_InnerRange>, _Inner_iter>
2560	: _M_outer(std::move(__i._M_outer)), _M_inner(std::move(__i._M_inner)),
2561	_M_parent(__i._M_parent)
2562	{ }
2563
2564	constexpr decltype(auto)
2565	operator*() const
2566	{ return *_M_inner; }
2567
2568	// _GLIBCXX_RESOLVE_LIB_DEFECTS
2569	// 3500. join_view::iterator::operator->() is bogus
2570	constexpr _Inner_iter
2571	operator->() const
2572	requires __detail::__has_arrow<_Inner_iter>
2573	&& copyable<_Inner_iter>
2574	{ return _M_inner; }
2575
2576	constexpr _Iterator&
2577	operator++()
2578	{
2579	auto&& __inner_range = [this] () -> auto&& {
2580	if constexpr (_S_ref_is_glvalue)
2581	return *_M_outer;
2582	else
2583	return *_M_parent->_M_inner;
2584	}();
2585	if (++_M_inner == ranges::end(__inner_range))
2586	{
2587	++_M_outer;
2588	_M_satisfy();
2589	}
2590	return *this;
2591	}
2592
2593	constexpr void
2594	operator++(int)
2595	{ ++*this; }
2596
2597	constexpr _Iterator
2598	operator++(int)
2599	requires _S_ref_is_glvalue && forward_range<_Base>
2600	&& forward_range<range_reference_t<_Base>>
2601	{
2602	auto __tmp = *this;
2603	++*this;
2604	return __tmp;
2605	}
2606
2607	constexpr _Iterator&
2608	operator--()
2609	requires _S_ref_is_glvalue && bidirectional_range<_Base>
2610	&& bidirectional_range<range_reference_t<_Base>>
2611	&& common_range<range_reference_t<_Base>>
2612	{
2613	if (_M_outer == ranges::end(_M_parent->_M_base))
2614	_M_inner = ranges::end(*--_M_outer);
2615	while (_M_inner == ranges::begin(*_M_outer))
2616	_M_inner = ranges::end(*--_M_outer);
2617	--_M_inner;
2618	return *this;
2619	}
2620
2621	constexpr _Iterator
2622	operator--(int)
2623	requires _S_ref_is_glvalue && bidirectional_range<_Base>
2624	&& bidirectional_range<range_reference_t<_Base>>
2625	&& common_range<range_reference_t<_Base>>
2626	{
2627	auto __tmp = *this;
2628	--*this;
2629	return __tmp;
2630	}
2631
2632	friend constexpr bool
2633	operator==(const _Iterator& __x, const _Iterator& __y)
2634	requires _S_ref_is_glvalue
2635	&& equality_comparable<_Outer_iter>
2636	&& equality_comparable<_Inner_iter>
2637	{
2638	return (__x._M_outer == __y._M_outer
2639	&& __x._M_inner == __y._M_inner);
2640	}
2641
2642	friend constexpr decltype(auto)
2643	iter_move(const _Iterator& __i)
2644	noexcept(noexcept(ranges::iter_move(__i._M_inner)))
2645	{ return ranges::iter_move(__i._M_inner); }
2646
2647	friend constexpr void
2648	iter_swap(const _Iterator& __x, const _Iterator& __y)
2649	noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner)))
2650	requires indirectly_swappable<_Inner_iter>
2651	{ return ranges::iter_swap(__x._M_inner, __y._M_inner); }
2652
2653	friend _Iterator<!_Const>;
2654	template<bool> friend struct _Sentinel;
2655	};
2656
2657	template<bool _Const>
2658	struct _Sentinel
2659	{
2660	private:
2661	using _Parent = __detail::__maybe_const_t<_Const, join_view>;
2662	using _Base = join_view::_Base<_Const>;
2663
2664	template<bool _Const2>
2665	constexpr bool
2666	__equal(const _Iterator<_Const2>& __i) const
2667	{ return __i._M_outer == _M_end; }
2668
2669	sentinel_t<_Base> _M_end = sentinel_t<_Base>();
2670
2671	public:
2672	_Sentinel() = default;
2673
2674	constexpr explicit
2675	_Sentinel(_Parent* __parent)
2676	: _M_end(ranges::end(__parent->_M_base))
2677	{ }
2678
2679	constexpr
2680	_Sentinel(_Sentinel<!_Const> __s)
2681	requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
2682	: _M_end(std::move(__s._M_end))
2683	{ }
2684
2685	template<bool _Const2>
2686	requires sentinel_for<sentinel_t<_Base>,
2687	iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
2688	friend constexpr bool
2689	operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
2690	{ return __y.__equal(__x); }
2691
2692	friend _Sentinel<!_Const>;
2693	};
2694
2695	[[no_unique_address]]
2696	__detail::__non_propagating_cache<remove_cv_t<_InnerRange>> _M_inner;
2697	_Vp _M_base = _Vp();
2698
2699	public:
2700	join_view() requires default_initializable<_Vp> = default;
2701
2702	constexpr explicit
2703	join_view(_Vp __base)
2704	: _M_base(std::move(__base))
2705	{ }
2706
2707	constexpr _Vp
2708	base() const& requires copy_constructible<_Vp>
2709	{ return _M_base; }
2710
2711	constexpr _Vp
2712	base() &&
2713	{ return std::move(_M_base); }
2714
2715	constexpr auto
2716	begin()
2717	{
2718	constexpr bool __use_const
2719	= (__detail::__simple_view<_Vp>
2720	&& is_reference_v<range_reference_t<_Vp>>);
2721	return _Iterator<__use_const>{this, ranges::begin(_M_base)};
2722	}
2723
2724	constexpr auto
2725	begin() const
2726	requires input_range<const _Vp>
2727	&& is_reference_v<range_reference_t<const _Vp>>
2728	{
2729	return _Iterator<true>{this, ranges::begin(_M_base)};
2730	}
2731
2732	constexpr auto
2733	end()
2734	{
2735	if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange>
2736	&& forward_range<_InnerRange>
2737	&& common_range<_Vp> && common_range<_InnerRange>)
2738	return _Iterator<__detail::__simple_view<_Vp>>{this,
2739	ranges::end(_M_base)};
2740	else
2741	return _Sentinel<__detail::__simple_view<_Vp>>{this};
2742	}
2743
2744	constexpr auto
2745	end() const
2746	requires input_range<const _Vp>
2747	&& is_reference_v<range_reference_t<const _Vp>>
2748	{
2749	if constexpr (forward_range<const _Vp>
2750	&& is_reference_v<range_reference_t<const _Vp>>
2751	&& forward_range<range_reference_t<const _Vp>>
2752	&& common_range<const _Vp>
2753	&& common_range<range_reference_t<const _Vp>>)
2754	return _Iterator<true>{this, ranges::end(_M_base)};
2755	else
2756	return _Sentinel<true>{this};
2757	}
2758	};
2759
2760	template<typename _Range>
2761	explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
2762
2763	namespace views
2764	{
2765	namespace __detail
2766	{
2767	template<typename _Range>
2768	concept __can_join_view
2769	= requires { join_view<all_t<_Range>>{std::declval<_Range>()}; };
2770	} // namespace __detail
2771
2772	struct _Join : __adaptor::_RangeAdaptorClosure
2773	{
2774	template<viewable_range _Range>
2775	requires __detail::__can_join_view<_Range>
2776	constexpr auto
2777	operator()(_Range&& __r) const
2778	{
2779	// _GLIBCXX_RESOLVE_LIB_DEFECTS
2780	// 3474. Nesting join_views is broken because of CTAD
2781	return join_view<all_t<_Range>>{std::forward<_Range>(__r)};
2782	}
2783
2784	static constexpr bool _S_has_simple_call_op = true;
2785	};
2786
2787	inline constexpr _Join join;
2788	} // namespace views
2789
2790	namespace __detail
2791	{
2792	template<auto>
2793	struct __require_constant;
2794
2795	template<typename _Range>
2796	concept __tiny_range = sized_range<_Range>
2797	&& requires
2798	{ typename __require_constant<remove_reference_t<_Range>::size()>; }
2799	&& (remove_reference_t<_Range>::size() <= 1);
2800
2801	template<typename _Base>
2802	struct __split_view_outer_iter_cat
2803	{ };
2804
2805	template<forward_range _Base>
2806	struct __split_view_outer_iter_cat<_Base>
2807	{ using iterator_category = input_iterator_tag; };
2808
2809	template<typename _Base>
2810	struct __split_view_inner_iter_cat
2811	{ };
2812
2813	template<forward_range _Base>
2814	struct __split_view_inner_iter_cat<_Base>
2815	{
2816	private:
2817	static constexpr auto
2818	_S_iter_cat()
2819	{
2820	using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
2821	if constexpr (derived_from<_Cat, forward_iterator_tag>)
2822	return forward_iterator_tag{};
2823	else
2824	return _Cat{};
2825	}
2826	public:
2827	using iterator_category = decltype(_S_iter_cat());
2828	};
2829	}
2830
2831	template<input_range _Vp, forward_range _Pattern>
2832	requires view<_Vp> && view<_Pattern>
2833	&& indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>,
2834	ranges::equal_to>
2835	&& (forward_range<_Vp> || __detail::__tiny_range<_Pattern>)
2836	class split_view : public view_interface<split_view<_Vp, _Pattern>>
2837	{
2838	private:
2839	template<bool _Const>
2840	using _Base = __detail::__maybe_const_t<_Const, _Vp>;
2841
2842	template<bool _Const>
2843	struct _InnerIter;
2844
2845	template<bool _Const>
2846	struct _OuterIter
2847	: __detail::__split_view_outer_iter_cat<_Base<_Const>>
2848	{
2849	private:
2850	using _Parent = __detail::__maybe_const_t<_Const, split_view>;
2851	using _Base = split_view::_Base<_Const>;
2852
2853	constexpr bool
2854	__at_end() const
2855	{ return __current() == ranges::end(_M_parent->_M_base); }
2856
2857	// [range.split.outer] p1
2858	// Many of the following specifications refer to the notional member
2859	// current of outer-iterator. current is equivalent to current_ if
2860	// V models forward_range, and parent_->current_ otherwise.
2861	constexpr auto&
2862	__current() noexcept
2863	{
2864	if constexpr (forward_range<_Vp>)
2865	return _M_current;
2866	else
2867	return _M_parent->_M_current;
2868	}
2869
2870	constexpr auto&
2871	__current() const noexcept
2872	{
2873	if constexpr (forward_range<_Vp>)
2874	return _M_current;
2875	else
2876	return _M_parent->_M_current;
2877	}
2878
2879	_Parent* _M_parent = nullptr;
2880
2881	// XXX: _M_current is present only if "V models forward_range"
2882	[[no_unique_address]]
2883	__detail::__maybe_present_t<forward_range<_Vp>,
2884	iterator_t<_Base>> _M_current;
2885
2886	public:
2887	using iterator_concept = conditional_t<forward_range<_Base>,
2888	forward_iterator_tag,
2889	input_iterator_tag>;
2890	// iterator_category defined in __split_view_outer_iter_cat
2891	using difference_type = range_difference_t<_Base>;
2892
2893	struct value_type : view_interface<value_type>
2894	{
2895	private:
2896	_OuterIter _M_i = _OuterIter();
2897
2898	public:
2899	value_type() = default;
2900
2901	constexpr explicit
2902	value_type(_OuterIter __i)
2903	: _M_i(std::move(__i))
2904	{ }
2905
2906	constexpr _InnerIter<_Const>
2907	begin() const
2908	{ return _InnerIter<_Const>{_M_i}; }
2909
2910	constexpr default_sentinel_t
2911	end() const noexcept
2912	{ return default_sentinel; }
2913	};
2914
2915	_OuterIter() = default;
2916
2917	constexpr explicit
2918	_OuterIter(_Parent* __parent) requires (!forward_range<_Base>)
2919	: _M_parent(__parent)
2920	{ }
2921
2922	constexpr
2923	_OuterIter(_Parent* __parent, iterator_t<_Base> __current)
2924	requires forward_range<_Base>
2925	: _M_parent(__parent),
2926	_M_current(std::move(__current))
2927	{ }
2928
2929	constexpr
2930	_OuterIter(_OuterIter<!_Const> __i)
2931	requires _Const
2932	&& convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
2933	: _M_parent(__i._M_parent), _M_current(std::move(__i._M_current))
2934	{ }
2935
2936	constexpr value_type
2937	operator*() const
2938	{ return value_type{*this}; }
2939
2940	constexpr _OuterIter&
2941	operator++()
2942	{
2943	// _GLIBCXX_RESOLVE_LIB_DEFECTS
2944	// 3505. split_view::outer-iterator::operator++ misspecified
2945	const auto __end = ranges::end(_M_parent->_M_base);
2946	if (__current() == __end)
2947	return *this;
2948	const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern};
2949	if (__pbegin == __pend)
2950	++__current();
2951	else if constexpr (__detail::__tiny_range<_Pattern>)
2952	{
2953	__current() = ranges::find(std::move(__current()), __end,
2954	*__pbegin);
2955	if (__current() != __end)
2956	++__current();
2957	}
2958	else
2959	do
2960	{
2961	auto [__b, __p]
2962	= ranges::mismatch(__current(), __end, __pbegin, __pend);
2963	if (__p == __pend)
2964	{
2965	__current() = __b;
2966	break;
2967	}
2968	} while (++__current() != __end);
2969	return *this;
2970	}
2971
2972	constexpr decltype(auto)
2973	operator++(int)
2974	{
2975	if constexpr (forward_range<_Base>)
2976	{
2977	auto __tmp = *this;
2978	++*this;
2979	return __tmp;
2980	}
2981	else
2982	++*this;
2983	}
2984
2985	friend constexpr bool
2986	operator==(const _OuterIter& __x, const _OuterIter& __y)
2987	requires forward_range<_Base>
2988	{ return __x._M_current == __y._M_current; }
2989
2990	friend constexpr bool
2991	operator==(const _OuterIter& __x, default_sentinel_t)
2992	{ return __x.__at_end(); };
2993
2994	friend _OuterIter<!_Const>;
2995	friend _InnerIter<_Const>;
2996	};
2997
2998	template<bool _Const>
2999	struct _InnerIter
3000	: __detail::__split_view_inner_iter_cat<_Base<_Const>>
3001	{
3002	private:
3003	using _Base = split_view::_Base<_Const>;
3004
3005	constexpr bool
3006	__at_end() const
3007	{
3008	auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern};
3009	auto __end = ranges::end(_M_i._M_parent->_M_base);
3010	if constexpr (__detail::__tiny_range<_Pattern>)
3011	{
3012	const auto& __cur = _M_i_current();
3013	if (__cur == __end)
3014	return true;
3015	if (__pcur == __pend)
3016	return _M_incremented;
3017	return *__cur == *__pcur;
3018	}
3019	else
3020	{
3021	auto __cur = _M_i_current();
3022	if (__cur == __end)
3023	return true;
3024	if (__pcur == __pend)
3025	return _M_incremented;
3026	do
3027	{
3028	if (*__cur != *__pcur)
3029	return false;
3030	if (++__pcur == __pend)
3031	return true;
3032	} while (++__cur != __end);
3033	return false;
3034	}
3035	}
3036
3037	constexpr auto&
3038	_M_i_current() noexcept
3039	{ return _M_i.__current(); }
3040
3041	constexpr auto&
3042	_M_i_current() const noexcept
3043	{ return _M_i.__current(); }
3044
3045	_OuterIter<_Const> _M_i = _OuterIter<_Const>();
3046	bool _M_incremented = false;
3047
3048	public:
3049	using iterator_concept
3050	= typename _OuterIter<_Const>::iterator_concept;
3051	// iterator_category defined in __split_view_inner_iter_cat
3052	using value_type = range_value_t<_Base>;
3053	using difference_type = range_difference_t<_Base>;
3054
3055	_InnerIter() = default;
3056
3057	constexpr explicit
3058	_InnerIter(_OuterIter<_Const> __i)
3059	: _M_i(std::move(__i))
3060	{ }
3061
3062	constexpr const iterator_t<_Base>&
3063	base() const& noexcept
3064	{ return _M_i_current(); }
3065
3066	constexpr iterator_t<_Base>
3067	base() && requires forward_range<_Vp>
3068	{ return std::move(_M_i_current()); }
3069
3070	constexpr decltype(auto)
3071	operator*() const
3072	{ return *_M_i_current(); }
3073
3074	constexpr _InnerIter&
3075	operator++()
3076	{
3077	_M_incremented = true;
3078	if constexpr (!forward_range<_Base>)
3079	if constexpr (_Pattern::size() == 0)
3080	return *this;
3081	++_M_i_current();
3082	return *this;
3083	}
3084
3085	constexpr decltype(auto)
3086	operator++(int)
3087	{
3088	if constexpr (forward_range<_Base>)
3089	{
3090	auto __tmp = *this;
3091	++*this;
3092	return __tmp;
3093	}
3094	else
3095	++*this;
3096	}
3097
3098	friend constexpr bool
3099	operator==(const _InnerIter& __x, const _InnerIter& __y)
3100	requires forward_range<_Base>
3101	{ return __x._M_i == __y._M_i; }
3102
3103	friend constexpr bool
3104	operator==(const _InnerIter& __x, default_sentinel_t)
3105	{ return __x.__at_end(); }
3106
3107	friend constexpr decltype(auto)
3108	iter_move(const _InnerIter& __i)
3109	noexcept(noexcept(ranges::iter_move(__i._M_i_current())))
3110	{ return ranges::iter_move(__i._M_i_current()); }
3111
3112	friend constexpr void
3113	iter_swap(const _InnerIter& __x, const _InnerIter& __y)
3114	noexcept(noexcept(ranges::iter_swap(__x._M_i_current(),
3115	__y._M_i_current())))
3116	requires indirectly_swappable<iterator_t<_Base>>
3117	{ ranges::iter_swap(__x._M_i_current(), __y._M_i_current()); }
3118	};
3119
3120	_Pattern _M_pattern = _Pattern();
3121	// XXX: _M_current is "present only if !forward_range<V>"
3122	[[no_unique_address]]
3123	__detail::__maybe_present_t<!forward_range<_Vp>,
3124	iterator_t<_Vp>> _M_current;
3125	_Vp _M_base = _Vp();
3126
3127
3128	public:
3129	split_view() requires (default_initializable<_Vp>
3130	&& default_initializable<_Pattern>
3131	&& (forward_range<_Vp>
3132	|| default_initializable<iterator_t<_Vp>>))
3133	= default;
3134
3135	constexpr
3136	split_view(_Vp __base, _Pattern __pattern)
3137	: _M_pattern(std::move(__pattern)), _M_base(std::move(__base))
3138	{ }
3139
3140	template<input_range _Range>
3141	requires constructible_from<_Vp, views::all_t<_Range>>
3142	&& constructible_from<_Pattern, single_view<range_value_t<_Range>>>
3143	constexpr
3144	split_view(_Range&& __r, range_value_t<_Range> __e)
3145	: _M_pattern(views::single(std::move(__e))),
3146	_M_base(views::all(std::forward<_Range>(__r)))
3147	{ }
3148
3149	constexpr _Vp
3150	base() const& requires copy_constructible<_Vp>
3151	{ return _M_base; }
3152
3153	constexpr _Vp
3154	base() &&
3155	{ return std::move(_M_base); }
3156
3157	constexpr auto
3158	begin()
3159	{
3160	if constexpr (forward_range<_Vp>)
3161	{
3162	constexpr bool __simple
3163	= __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>;
3164	return _OuterIter<__simple>{this, ranges::begin(_M_base)};
3165	}
3166	else
3167	{
3168	_M_current = ranges::begin(_M_base);
3169	return _OuterIter<false>{this};
3170	}
3171	}
3172
3173	constexpr auto
3174	begin() const requires forward_range<_Vp> && forward_range<const _Vp>
3175	{
3176	return _OuterIter<true>{this, ranges::begin(_M_base)};
3177	}
3178
3179	constexpr auto
3180	end() requires forward_range<_Vp> && common_range<_Vp>
3181	{
3182	constexpr bool __simple
3183	= __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>;
3184	return _OuterIter<__simple>{this, ranges::end(_M_base)};
3185	}
3186
3187	constexpr auto
3188	end() const
3189	{
3190	if constexpr (forward_range<_Vp>
3191	&& forward_range<const _Vp>
3192	&& common_range<const _Vp>)
3193	return _OuterIter<true>{this, ranges::end(_M_base)};
3194	else
3195	return default_sentinel;
3196	}
3197	};
3198
3199	template<typename _Range, typename _Pattern>
3200	split_view(_Range&&, _Pattern&&)
3201	-> split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
3202
3203	template<input_range _Range>
3204	split_view(_Range&&, range_value_t<_Range>)
3205	-> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
3206
3207	namespace views
3208	{
3209	namespace __detail
3210	{
3211	template<typename _Range, typename _Pattern>
3212	concept __can_split_view
3213	= requires { split_view(std::declval<_Range>(), std::declval<_Pattern>()); };
3214	} // namespace __detail
3215
3216	struct _Split : __adaptor::_RangeAdaptor<_Split>
3217	{
3218	template<viewable_range _Range, typename _Pattern>
3219	requires __detail::__can_split_view<_Range, _Pattern>
3220	constexpr auto
3221	operator()(_Range&& __r, _Pattern&& __f) const
3222	{
3223	return split_view(std::forward<_Range>(__r), std::forward<_Pattern>(__f));
3224	}
3225
3226	using _RangeAdaptor<_Split>::operator();
3227	static constexpr int _S_arity = 2;
3228	// The pattern argument of views::split is not always simple -- it can be
3229	// a non-view range, the value category of which affects whether the call
3230	// is well-formed. But a scalar or a view pattern argument is surely
3231	// simple.
3232	template<typename _Pattern>
3233	static constexpr bool _S_has_simple_extra_args
3234	= is_scalar_v<_Pattern> || (view<_Pattern>
3235	&& copy_constructible<_Pattern>);
3236	};
3237
3238	inline constexpr _Split split;
3239	} // namespace views
3240
3241	namespace views
3242	{
3243	struct _Counted
3244	{
3245	template<input_or_output_iterator _Iter>
3246	constexpr auto
3247	operator()(_Iter __i, iter_difference_t<_Iter> __n) const
3248	{
3249	if constexpr (random_access_iterator<_Iter>)
3250	return subrange(__i, __i + __n);
3251	else
3252	return subrange(counted_iterator(std::move(__i), __n),
3253	default_sentinel);
3254	}
3255	};
3256
3257	inline constexpr _Counted counted{};
3258	} // namespace views
3259
3260	template<view _Vp>
3261	requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>>
3262	class common_view : public view_interface<common_view<_Vp>>
3263	{
3264	private:
3265	_Vp _M_base = _Vp();
3266
3267	public:
3268	common_view() requires default_initializable<_Vp> = default;
3269
3270	constexpr explicit
3271	common_view(_Vp __r)
3272	: _M_base(std::move(__r))
3273	{ }
3274
3275	/* XXX: LWG 3280 didn't remove this constructor, but I think it should?
3276	template<viewable_range _Range>
3277	requires (!common_range<_Range>)
3278	&& constructible_from<_Vp, views::all_t<_Range>>
3279	constexpr explicit
3280	common_view(_Range&& __r)
3281	: _M_base(views::all(std::forward<_Range>(__r)))
3282	{ }
3283	*/
3284
3285	constexpr _Vp
3286	base() const& requires copy_constructible<_Vp>
3287	{ return _M_base; }
3288
3289	constexpr _Vp
3290	base() &&
3291	{ return std::move(_M_base); }
3292
3293	constexpr auto
3294	begin()
3295	{
3296	if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3297	return ranges::begin(_M_base);
3298	else
3299	return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3300	(ranges::begin(_M_base));
3301	}
3302
3303	constexpr auto
3304	begin() const requires range<const _Vp>
3305	{
3306	if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3307	return ranges::begin(_M_base);
3308	else
3309	return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3310	(ranges::begin(_M_base));
3311	}
3312
3313	constexpr auto
3314	end()
3315	{
3316	if constexpr (random_access_range<_Vp> && sized_range<_Vp>)
3317	return ranges::begin(_M_base) + ranges::size(_M_base);
3318	else
3319	return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>>
3320	(ranges::end(_M_base));
3321	}
3322
3323	constexpr auto
3324	end() const requires range<const _Vp>
3325	{
3326	if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>)
3327	return ranges::begin(_M_base) + ranges::size(_M_base);
3328	else
3329	return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>>
3330	(ranges::end(_M_base));
3331	}
3332
3333	constexpr auto
3334	size() requires sized_range<_Vp>
3335	{ return ranges::size(_M_base); }
3336
3337	constexpr auto
3338	size() const requires sized_range<const _Vp>
3339	{ return ranges::size(_M_base); }
3340	};
3341
3342	template<typename _Range>
3343	common_view(_Range&&) -> common_view<views::all_t<_Range>>;
3344
3345	template<typename _Tp>
3346	inline constexpr bool enable_borrowed_range<common_view<_Tp>>
3347	= enable_borrowed_range<_Tp>;
3348
3349	namespace views
3350	{
3351	namespace __detail
3352	{
3353	template<typename _Range>
3354	concept __already_common = common_range<_Range>
3355	&& requires { views::all(std::declval<_Range>()); };
3356
3357	template<typename _Range>
3358	concept __can_common_view
3359	= requires { common_view{std::declval<_Range>()}; };
3360	} // namespace __detail
3361
3362	struct _Common : __adaptor::_RangeAdaptorClosure
3363	{
3364	template<viewable_range _Range>
3365	requires __detail::__already_common<_Range>
3366	|| __detail::__can_common_view<_Range>
3367	constexpr auto
3368	operator()(_Range&& __r) const
3369	{
3370	if constexpr (__detail::__already_common<_Range>)
3371	return views::all(std::forward<_Range>(__r));
3372	else
3373	return common_view{std::forward<_Range>(__r)};
3374	}
3375
3376	static constexpr bool _S_has_simple_call_op = true;
3377	};
3378
3379	inline constexpr _Common common;
3380	} // namespace views
3381
3382	template<view _Vp>
3383	requires bidirectional_range<_Vp>
3384	class reverse_view : public view_interface<reverse_view<_Vp>>
3385	{
3386	private:
3387	static constexpr bool _S_needs_cached_begin
3388	= !common_range<_Vp> && !random_access_range<_Vp>;
3389
3390	[[no_unique_address]]
3391	__detail::__maybe_present_t<_S_needs_cached_begin,
3392	__detail::_CachedPosition<_Vp>>
3393	_M_cached_begin;
3394	_Vp _M_base = _Vp();
3395
3396	public:
3397	reverse_view() requires default_initializable<_Vp> = default;
3398
3399	constexpr explicit
3400	reverse_view(_Vp __r)
3401	: _M_base(std::move(__r))
3402	{ }
3403
3404	constexpr _Vp
3405	base() const& requires copy_constructible<_Vp>
3406	{ return _M_base; }
3407
3408	constexpr _Vp
3409	base() &&
3410	{ return std::move(_M_base); }
3411
3412	constexpr reverse_iterator<iterator_t<_Vp>>
3413	begin()
3414	{
3415	if constexpr (_S_needs_cached_begin)
3416	if (_M_cached_begin._M_has_value())
3417	return std::make_reverse_iterator(_M_cached_begin._M_get(_M_base));
3418
3419	auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base));
3420	if constexpr (_S_needs_cached_begin)
3421	_M_cached_begin._M_set(_M_base, __it);
3422	return std::make_reverse_iterator(std::move(__it));
3423	}
3424
3425	constexpr auto
3426	begin() requires common_range<_Vp>
3427	{ return std::make_reverse_iterator(ranges::end(_M_base)); }
3428
3429	constexpr auto
3430	begin() const requires common_range<const _Vp>
3431	{ return std::make_reverse_iterator(ranges::end(_M_base)); }
3432
3433	constexpr reverse_iterator<iterator_t<_Vp>>
3434	end()
3435	{ return std::make_reverse_iterator(ranges::begin(_M_base)); }
3436
3437	constexpr auto
3438	end() const requires common_range<const _Vp>
3439	{ return std::make_reverse_iterator(ranges::begin(_M_base)); }
3440
3441	constexpr auto
3442	size() requires sized_range<_Vp>
3443	{ return ranges::size(_M_base); }
3444
3445	constexpr auto
3446	size() const requires sized_range<const _Vp>
3447	{ return ranges::size(_M_base); }
3448	};
3449
3450	template<typename _Range>
3451	reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
3452
3453	template<typename _Tp>
3454	inline constexpr bool enable_borrowed_range<reverse_view<_Tp>>
3455	= enable_borrowed_range<_Tp>;
3456
3457	namespace views
3458	{
3459	namespace __detail
3460	{
3461	template<typename>
3462	inline constexpr bool __is_reversible_subrange = false;
3463
3464	template<typename _Iter, subrange_kind _Kind>
3465	inline constexpr bool
3466	__is_reversible_subrange<subrange<reverse_iterator<_Iter>,
3467	reverse_iterator<_Iter>,
3468	_Kind>> = true;
3469
3470	template<typename>
3471	inline constexpr bool __is_reverse_view = false;
3472
3473	template<typename _Vp>
3474	inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true;
3475
3476	template<typename _Range>
3477	concept __can_reverse_view
3478	= requires { reverse_view{std::declval<_Range>()}; };
3479	} // namespace __detail
3480
3481	struct _Reverse : __adaptor::_RangeAdaptorClosure
3482	{
3483	template<viewable_range _Range>
3484	requires __detail::__is_reverse_view<remove_cvref_t<_Range>>
3485	|| __detail::__is_reversible_subrange<remove_cvref_t<_Range>>
3486	|| __detail::__can_reverse_view<_Range>
3487	constexpr auto
3488	operator()(_Range&& __r) const
3489	{
3490	using _Tp = remove_cvref_t<_Range>;
3491	if constexpr (__detail::__is_reverse_view<_Tp>)
3492	return std::forward<_Range>(__r).base();
3493	else if constexpr (__detail::__is_reversible_subrange<_Tp>)
3494	{
3495	using _Iter = decltype(ranges::begin(__r).base());
3496	if constexpr (sized_range<_Tp>)
3497	return subrange<_Iter, _Iter, subrange_kind::sized>
3498	{__r.end().base(), __r.begin().base(), __r.size()};
3499	else
3500	return subrange<_Iter, _Iter, subrange_kind::unsized>
3501	{__r.end().base(), __r.begin().base()};
3502	}
3503	else
3504	return reverse_view{std::forward<_Range>(__r)};
3505	}
3506
3507	static constexpr bool _S_has_simple_call_op = true;
3508	};
3509
3510	inline constexpr _Reverse reverse;
3511	} // namespace views
3512
3513	namespace __detail
3514	{
3515	template<typename _Tp, size_t _Nm>
3516	concept __has_tuple_element = requires(_Tp __t)
3517	{
3518	typename tuple_size<_Tp>::type;
3519	requires _Nm < tuple_size_v<_Tp>;
3520	typename tuple_element_t<_Nm, _Tp>;
3521	{ std::get<_Nm>(__t) }
3522	-> convertible_to<const tuple_element_t<_Nm, _Tp>&>;
3523	};
3524
3525	template<typename _Tp, size_t _Nm>
3526	concept __returnable_element
3527	= is_reference_v<_Tp> || move_constructible<tuple_element_t<_Nm, _Tp>>;
3528	}
3529
3530	template<input_range _Vp, size_t _Nm>
3531	requires view<_Vp>
3532	&& __detail::__has_tuple_element<range_value_t<_Vp>, _Nm>
3533	&& __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>,
3534	_Nm>
3535	&& __detail::__returnable_element<range_reference_t<_Vp>, _Nm>
3536	class elements_view : public view_interface<elements_view<_Vp, _Nm>>
3537	{
3538	public:
3539	elements_view() requires default_initializable<_Vp> = default;
3540
3541	constexpr explicit
3542	elements_view(_Vp base)
3543	: _M_base(std::move(base))
3544	{ }
3545
3546	constexpr _Vp
3547	base() const& requires copy_constructible<_Vp>
3548	{ return _M_base; }
3549
3550	constexpr _Vp
3551	base() &&
3552	{ return std::move(_M_base); }
3553
3554	constexpr auto
3555	begin() requires (!__detail::__simple_view<_Vp>)
3556	{ return _Iterator<false>(ranges::begin(_M_base)); }
3557
3558	constexpr auto
3559	begin() const requires range<const _Vp>
3560	{ return _Iterator<true>(ranges::begin(_M_base)); }
3561
3562	constexpr auto
3563	end() requires (!__detail::__simple_view<_Vp> && !common_range<_Vp>)
3564	{ return _Sentinel<false>{ranges::end(_M_base)}; }
3565
3566	constexpr auto
3567	end() requires (!__detail::__simple_view<_Vp> && common_range<_Vp>)
3568	{ return _Iterator<false>{ranges::end(_M_base)}; }
3569
3570	constexpr auto
3571	end() const requires range<const _Vp>
3572	{ return _Sentinel<true>{ranges::end(_M_base)}; }
3573
3574	constexpr auto
3575	end() const requires common_range<const _Vp>
3576	{ return _Iterator<true>{ranges::end(_M_base)}; }
3577
3578	constexpr auto
3579	size() requires sized_range<_Vp>
3580	{ return ranges::size(_M_base); }
3581
3582	constexpr auto
3583	size() const requires sized_range<const _Vp>
3584	{ return ranges::size(_M_base); }
3585
3586	private:
3587	template<bool _Const>
3588	using _Base = __detail::__maybe_const_t<_Const, _Vp>;
3589
3590	template<bool _Const>
3591	struct __iter_cat
3592	{ };
3593
3594	template<bool _Const>
3595	requires forward_range<_Base<_Const>>
3596	struct __iter_cat<_Const>
3597	{
3598	private:
3599	static auto _S_iter_cat()
3600	{
3601	using _Base = elements_view::_Base<_Const>;
3602	using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category;
3603	using _Res = decltype((std::get<_Nm>(*std::declval<iterator_t<_Base>>())));
3604	if constexpr (!is_lvalue_reference_v<_Res>)
3605	return input_iterator_tag{};
3606	else if constexpr (derived_from<_Cat, random_access_iterator_tag>)
3607	return random_access_iterator_tag{};
3608	else
3609	return _Cat{};
3610	}
3611	public:
3612	using iterator_category = decltype(_S_iter_cat());
3613	};
3614
3615	template<bool _Const>
3616	struct _Sentinel;
3617
3618	template<bool _Const>
3619	struct _Iterator : __iter_cat<_Const>
3620	{
3621	private:
3622	using _Base = elements_view::_Base<_Const>;
3623
3624	iterator_t<_Base> _M_current = iterator_t<_Base>();
3625
3626	static constexpr decltype(auto)
3627	_S_get_element(const iterator_t<_Base>& __i)
3628	{
3629	if constexpr (is_reference_v<range_reference_t<_Base>>)
3630	return std::get<_Nm>(*__i);
3631	else
3632	{
3633	using _Et = remove_cv_t<tuple_element_t<_Nm, range_reference_t<_Base>>>;
3634	return static_cast<_Et>(std::get<_Nm>(*__i));
3635	}
3636	}
3637
3638	static auto
3639	_S_iter_concept()
3640	{
3641	if constexpr (random_access_range<_Base>)
3642	return random_access_iterator_tag{};
3643	else if constexpr (bidirectional_range<_Base>)
3644	return bidirectional_iterator_tag{};
3645	else if constexpr (forward_range<_Base>)
3646	return forward_iterator_tag{};
3647	else
3648	return input_iterator_tag{};
3649	}
3650
3651	friend _Iterator<!_Const>;
3652
3653	public:
3654	using iterator_concept = decltype(_S_iter_concept());
3655	// iterator_category defined in elements_view::__iter_cat
3656	using value_type
3657	= remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>;
3658	using difference_type = range_difference_t<_Base>;
3659
3660	_Iterator() requires default_initializable<iterator_t<_Base>> = default;
3661
3662	constexpr explicit
3663	_Iterator(iterator_t<_Base> current)
3664	: _M_current(std::move(current))
3665	{ }
3666
3667	constexpr
3668	_Iterator(_Iterator<!_Const> i)
3669	requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
3670	: _M_current(std::move(i._M_current))
3671	{ }
3672
3673	constexpr const iterator_t<_Base>&
3674	base() const& noexcept
3675	{ return _M_current; }
3676
3677	constexpr iterator_t<_Base>
3678	base() &&
3679	{ return std::move(_M_current); }
3680
3681	constexpr decltype(auto)
3682	operator*() const
3683	{ return _S_get_element(_M_current); }
3684
3685	constexpr _Iterator&
3686	operator++()
3687	{
3688	++_M_current;
3689	return *this;
3690	}
3691
3692	constexpr void
3693	operator++(int)
3694	{ ++_M_current; }
3695
3696	constexpr _Iterator
3697	operator++(int) requires forward_range<_Base>
3698	{
3699	auto __tmp = *this;
3700	++_M_current;
3701	return __tmp;
3702	}
3703
3704	constexpr _Iterator&
3705	operator--() requires bidirectional_range<_Base>
3706	{
3707	--_M_current;
3708	return *this;
3709	}
3710
3711	constexpr _Iterator
3712	operator--(int) requires bidirectional_range<_Base>
3713	{
3714	auto __tmp = *this;
3715	--_M_current;
3716	return __tmp;
3717	}
3718
3719	constexpr _Iterator&
3720	operator+=(difference_type __n)
3721	requires random_access_range<_Base>
3722	{
3723	_M_current += __n;
3724	return *this;
3725	}
3726
3727	constexpr _Iterator&
3728	operator-=(difference_type __n)
3729	requires random_access_range<_Base>
3730	{
3731	_M_current -= __n;
3732	return *this;
3733	}
3734
3735	constexpr decltype(auto)
3736	operator[](difference_type __n) const
3737	requires random_access_range<_Base>
3738	{ return _S_get_element(_M_current + __n); }
3739
3740	friend constexpr bool
3741	operator==(const _Iterator& __x, const _Iterator& __y)
3742	requires equality_comparable<iterator_t<_Base>>
3743	{ return __x._M_current == __y._M_current; }
3744
3745	friend constexpr bool
3746	operator<(const _Iterator& __x, const _Iterator& __y)
3747	requires random_access_range<_Base>
3748	{ return __x._M_current < __y._M_current; }
3749
3750	friend constexpr bool
3751	operator>(const _Iterator& __x, const _Iterator& __y)
3752	requires random_access_range<_Base>
3753	{ return __y._M_current < __x._M_current; }
3754
3755	friend constexpr bool
3756	operator<=(const _Iterator& __x, const _Iterator& __y)
3757	requires random_access_range<_Base>
3758	{ return !(__y._M_current > __x._M_current); }
3759
3760	friend constexpr bool
3761	operator>=(const _Iterator& __x, const _Iterator& __y)
3762	requires random_access_range<_Base>
3763	{ return !(__x._M_current > __y._M_current); }
3764
3765	#ifdef __cpp_lib_three_way_comparison
3766	friend constexpr auto
3767	operator<=>(const _Iterator& __x, const _Iterator& __y)
3768	requires random_access_range<_Base>
3769	&& three_way_comparable<iterator_t<_Base>>
3770	{ return __x._M_current <=> __y._M_current; }
3771	#endif
3772
3773	friend constexpr _Iterator
3774	operator+(const _Iterator& __x, difference_type __y)
3775	requires random_access_range<_Base>
3776	{ return _Iterator{__x} += __y; }
3777
3778	friend constexpr _Iterator
3779	operator+(difference_type __x, const _Iterator& __y)
3780	requires random_access_range<_Base>
3781	{ return __y + __x; }
3782
3783	friend constexpr _Iterator
3784	operator-(const _Iterator& __x, difference_type __y)
3785	requires random_access_range<_Base>
3786	{ return _Iterator{__x} -= __y; }
3787
3788	// _GLIBCXX_RESOLVE_LIB_DEFECTS
3789	// 3483. transform_view::iterator's difference is overconstrained
3790	friend constexpr difference_type
3791	operator-(const _Iterator& __x, const _Iterator& __y)
3792	requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
3793	{ return __x._M_current - __y._M_current; }
3794
3795	template <bool> friend struct _Sentinel;
3796	};
3797
3798	template<bool _Const>
3799	struct _Sentinel
3800	{
3801	private:
3802	template<bool _Const2>
3803	constexpr bool
3804	_M_equal(const _Iterator<_Const2>& __x) const
3805	{ return __x._M_current == _M_end; }
3806
3807	template<bool _Const2>
3808	constexpr auto
3809	_M_distance_from(const _Iterator<_Const2>& __i) const
3810	{ return _M_end - __i._M_current; }
3811
3812	using _Base = elements_view::_Base<_Const>;
3813	sentinel_t<_Base> _M_end = sentinel_t<_Base>();
3814
3815	public:
3816	_Sentinel() = default;
3817
3818	constexpr explicit
3819	_Sentinel(sentinel_t<_Base> __end)
3820	: _M_end(std::move(__end))
3821	{ }
3822
3823	constexpr
3824	_Sentinel(_Sentinel<!_Const> __other)
3825	requires _Const
3826	&& convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
3827	: _M_end(std::move(__other._M_end))
3828	{ }
3829
3830	constexpr sentinel_t<_Base>
3831	base() const
3832	{ return _M_end; }
3833
3834	template<bool _Const2>
3835	requires sentinel_for<sentinel_t<_Base>,
3836	iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>>
3837	friend constexpr bool
3838	operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y)
3839	{ return __y._M_equal(__x); }
3840
3841	template<bool _Const2,
3842	typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
3843	requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
3844	friend constexpr range_difference_t<_Base2>
3845	operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y)
3846	{ return -__y._M_distance_from(__x); }
3847
3848	template<bool _Const2,
3849	typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>>
3850	requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>>
3851	friend constexpr range_difference_t<_Base2>
3852	operator-(const _Sentinel& __x, const _Iterator<_Const2>& __y)
3853	{ return __x._M_distance_from(__y); }
3854
3855	friend _Sentinel<!_Const>;
3856	};
3857
3858	_Vp _M_base = _Vp();
3859	};
3860
3861	template<typename _Tp, size_t _Nm>
3862	inline constexpr bool enable_borrowed_range<elements_view<_Tp, _Nm>>
3863	= enable_borrowed_range<_Tp>;
3864
3865	template<typename _Range>
3866	using keys_view = elements_view<views::all_t<_Range>, 0>;
3867
3868	template<typename _Range>
3869	using values_view = elements_view<views::all_t<_Range>, 1>;
3870
3871	namespace views
3872	{
3873	namespace __detail
3874	{
3875	template<size_t _Nm, typename _Range>
3876	concept __can_elements_view
3877	= requires { elements_view<all_t<_Range>, _Nm>{std::declval<_Range>()}; };
3878	} // namespace __detail
3879
3880	template<size_t _Nm>
3881	struct _Elements : __adaptor::_RangeAdaptorClosure
3882	{
3883	template<viewable_range _Range>
3884	requires __detail::__can_elements_view<_Nm, _Range>
3885	constexpr auto
3886	operator()(_Range&& __r) const
3887	{
3888	return elements_view<all_t<_Range>, _Nm>{std::forward<_Range>(__r)};
3889	}
3890
3891	static constexpr bool _S_has_simple_call_op = true;
3892	};
3893
3894	template<size_t _Nm>
3895	inline constexpr _Elements<_Nm> elements;
3896	inline constexpr auto keys = elements<0>;
3897	inline constexpr auto values = elements<1>;
3898	} // namespace views
3899
3900	} // namespace ranges
3901
3902	namespace views = ranges::views;
3903
3904	_GLIBCXX_END_NAMESPACE_VERSION
3905	} // namespace
3906	#endif // library concepts
3907	#endif // C++2a
3908	#endif /* _GLIBCXX_RANGES */
3909