stl_iterator.h source code [include/c++/14.1.1/bits/stl_iterator.h]

1	// Iterators -- C++ --
2
3	// Copyright (C) 2001-2024 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	/*
26	*
27	* Copyright (c) 1994
28	* Hewlett-Packard Company
29	*
30	* Permission to use, copy, modify, distribute and sell this software
31	* and its documentation for any purpose is hereby granted without fee,
32	* provided that the above copyright notice appear in all copies and
33	* that both that copyright notice and this permission notice appear
34	* in supporting documentation. Hewlett-Packard Company makes no
35	* representations about the suitability of this software for any
36	* purpose. It is provided "as is" without express or implied warranty.
37	*
38	*
39	* Copyright (c) 1996-1998
40	* Silicon Graphics Computer Systems, Inc.
41	*
42	* Permission to use, copy, modify, distribute and sell this software
43	* and its documentation for any purpose is hereby granted without fee,
44	* provided that the above copyright notice appear in all copies and
45	* that both that copyright notice and this permission notice appear
46	* in supporting documentation. Silicon Graphics makes no
47	* representations about the suitability of this software for any
48	* purpose. It is provided "as is" without express or implied warranty.
49	*/
50
51	/* @file bits/stl_iterator.h*
52	* This is an internal header file, included by other library headers.
53	* Do not attempt to use it directly. @headername{iterator}
54	*
55	* This file implements reverse_iterator, back_insert_iterator,
56	* front_insert_iterator, insert_iterator, __normal_iterator, and their
57	* supporting functions and overloaded operators.
58	*/
59
60	#ifndef _STL_ITERATOR_H
61	#define _STL_ITERATOR_H 1
62
63	#include <bits/cpp_type_traits.h>
64	#include <bits/stl_iterator_base_types.h>
65	#include <ext/type_traits.h>
66	#include <bits/move.h>
67	#include <bits/ptr_traits.h>
68
69	#if __cplusplus >= 201103L
70	# include <type_traits>
71	#endif
72
73	#if __cplusplus >= 202002L
74	# include <compare>
75	# include <new>
76	# include <bits/exception_defines.h>
77	# include <bits/iterator_concepts.h>
78	# include <bits/stl_construct.h>
79	#endif
80
81	#if __glibcxx_tuple_like // >= C++23
82	# include <bits/utility.h> // for tuple_element_t
83	#endif
84
85	namespace std _GLIBCXX_VISIBILITY(default)
86	{
87	_GLIBCXX_BEGIN_NAMESPACE_VERSION
88
89	/**
90	* @addtogroup iterators
91	* @{
92	*/
93
94	#if __glibcxx_concepts
95	namespace __detail
96	{
97	// Weaken iterator_category _Cat to _Limit if it is derived from that,
98	// otherwise use _Otherwise.
99	template<typename _Cat, typename _Limit, typename _Otherwise = _Cat>
100	using __clamp_iter_cat
101	= __conditional_t<derived_from<_Cat, _Limit>, _Limit, _Otherwise>;
102	}
103	#endif
104
105	// Ignore warnings about std::iterator.
106	#pragma GCC diagnostic push
107	#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
108
109	// 24.4.1 Reverse iterators
110	/**
111	* Bidirectional and random access iterators have corresponding reverse
112	* %iterator adaptors that iterate through the data structure in the
113	* opposite direction. They have the same signatures as the corresponding
114	* iterators. The fundamental relation between a reverse %iterator and its
115	* corresponding %iterator @c i is established by the identity:
116	* @code
117	* &(reverse_iterator(i)) == &(i - 1)
118	* @endcode
119	*
120	* <em>This mapping is dictated by the fact that while there is always a
121	* pointer past the end of an array, there might not be a valid pointer
122	* before the beginning of an array.</em> [24.4.1]/1,2
123	*
124	* Reverse iterators can be tricky and surprising at first. Their
125	* semantics make sense, however, and the trickiness is a side effect of
126	* the requirement that the iterators must be safe.
127	*/
128	template<typename _Iterator>
129	class reverse_iterator
130	: public iterator<typename iterator_traits<_Iterator>::iterator_category,
131	typename iterator_traits<_Iterator>::value_type,
132	typename iterator_traits<_Iterator>::difference_type,
133	typename iterator_traits<_Iterator>::pointer,
134	typename iterator_traits<_Iterator>::reference>
135	{
136	template<typename _Iter>
137	friend class reverse_iterator;
138
139	#if __glibcxx_concepts
140	// _GLIBCXX_RESOLVE_LIB_DEFECTS
141	// 3435. three_way_comparable_with<reverse_iterator<int>, [...]>*
142	template<typename _Iter>
143	static constexpr bool __convertible = !is_same_v<_Iter, _Iterator>
144	&& convertible_to<const _Iter&, _Iterator>;
145	#endif
146
147	protected:
148	_Iterator current;
149
150	typedef iterator_traits<_Iterator> __traits_type;
151
152	public:
153	typedef _Iterator iterator_type;
154	typedef typename __traits_type::pointer pointer;
155	#if ! __glibcxx_concepts
156	typedef typename __traits_type::difference_type difference_type;
157	typedef typename __traits_type::reference reference;
158	#else
159	using iterator_concept
160	= __conditional_t<random_access_iterator<_Iterator>,
161	random_access_iterator_tag,
162	bidirectional_iterator_tag>;
163	using iterator_category
164	= __detail::__clamp_iter_cat<typename __traits_type::iterator_category,
165	random_access_iterator_tag>;
166	using value_type = iter_value_t<_Iterator>;
167	using difference_type = iter_difference_t<_Iterator>;
168	using reference = iter_reference_t<_Iterator>;
169	#endif
170
171	/**
172	* The default constructor value-initializes member @p current.
173	* If it is a pointer, that means it is zero-initialized.
174	*/
175	// _GLIBCXX_RESOLVE_LIB_DEFECTS
176	// 235 No specification of default ctor for reverse_iterator
177	// 1012. reverse_iterator default ctor should value initialize
178	_GLIBCXX17_CONSTEXPR
179	reverse_iterator()
180	_GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator()))
181	: current()
182	{ }
183
184	/**
185	* This %iterator will move in the opposite direction that @p x does.
186	*/
187	explicit _GLIBCXX17_CONSTEXPR
188	reverse_iterator(iterator_type __x)
189	_GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(__x)))
190	: current(__x)
191	{ }
192
193	/**
194	* The copy constructor is normal.
195	*/
196	_GLIBCXX17_CONSTEXPR
197	reverse_iterator(const reverse_iterator& __x)
198	_GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(__x.current)))
199	: current(__x.current)
200	{ }
201
202	#if __cplusplus >= 201103L
203	reverse_iterator& operator=(const reverse_iterator&) = default;
204	#endif
205
206	/**
207	* A %reverse_iterator across other types can be copied if the
208	* underlying %iterator can be converted to the type of @c current.
209	*/
210	template<typename _Iter>
211	#if __glibcxx_concepts
212	requires __convertible<_Iter>
213	#endif
214	_GLIBCXX17_CONSTEXPR
215	reverse_iterator(const reverse_iterator<_Iter>& __x)
216	_GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(__x.current)))
217	: current(__x.current)
218	{ }
219
220	#if __cplusplus >= 201103L
221	template<typename _Iter>
222	#if __glibcxx_concepts
223	requires __convertible<_Iter>
224	&& assignable_from<_Iterator&, const _Iter&>
225	#endif
226	_GLIBCXX17_CONSTEXPR
227	reverse_iterator&
228	operator=(const reverse_iterator<_Iter>& __x)
229	_GLIBCXX_NOEXCEPT_IF(noexcept(current = __x.current))
230	{
231	current = __x.current;
232	return *this;
233	}
234	#endif
235
236	/**
237	* @return @c current, the %iterator used for underlying work.
238	*/
239	_GLIBCXX_NODISCARD
240	_GLIBCXX17_CONSTEXPR iterator_type
241	base() const
242	_GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(current)))
243	{ return current; }
244
245	/**
246	* @return A reference to the value at @c --current
247	*
248	* This requires that @c --current is dereferenceable.
249	*
250	* @warning This implementation requires that for an iterator of the
251	* underlying iterator type, @c x, a reference obtained by
252	* @c *x remains valid after @c x has been modified or
253	* destroyed. This is a bug: http://gcc.gnu.org/PR51823
254	*/
255	_GLIBCXX_NODISCARD
256	_GLIBCXX17_CONSTEXPR reference
257	operator() const*
258	{
259	_Iterator __tmp = current;
260	return *--__tmp;
261	}
262
263	/**
264	* @return A pointer to the value at @c --current
265	*
266	* This requires that @c --current is dereferenceable.
267	*/
268	_GLIBCXX_NODISCARD
269	_GLIBCXX17_CONSTEXPR pointer
270	operator->() const
271	#if __cplusplus > 201703L && __cpp_concepts >= 201907L
272	requires is_pointer_v<_Iterator>
273	\|\| requires(const _Iterator __i) { __i.operator->(); }
274	#endif
275	{
276	// _GLIBCXX_RESOLVE_LIB_DEFECTS
277	// 1052. operator-> should also support smart pointers
278	_Iterator __tmp = current;
279	--__tmp;
280	return _S_to_pointer(__tmp);
281	}
282
283	/**
284	* @return @c *this
285	*
286	* Decrements the underlying iterator.
287	*/
288	_GLIBCXX17_CONSTEXPR reverse_iterator&
289	operator++()
290	{
291	--current;
292	return *this;
293	}
294
295	/**
296	* @return The original value of @c *this
297	*
298	* Decrements the underlying iterator.
299	*/
300	_GLIBCXX17_CONSTEXPR reverse_iterator
301	operator++(int)
302	{
303	reverse_iterator __tmp = *this;
304	--current;
305	return __tmp;
306	}
307
308	/**
309	* @return @c *this
310	*
311	* Increments the underlying iterator.
312	*/
313	_GLIBCXX17_CONSTEXPR reverse_iterator&
314	operator--()
315	{
316	++current;
317	return *this;
318	}
319
320	/**
321	* @return A reverse_iterator with the previous value of @c *this
322	*
323	* Increments the underlying iterator.
324	*/
325	_GLIBCXX17_CONSTEXPR reverse_iterator
326	operator--(int)
327	{
328	reverse_iterator __tmp = *this;
329	++current;
330	return __tmp;
331	}
332
333	/**
334	* @return A reverse_iterator that refers to @c current - @a __n
335	*
336	* The underlying iterator must be a Random Access Iterator.
337	*/
338	_GLIBCXX_NODISCARD
339	_GLIBCXX17_CONSTEXPR reverse_iterator
340	operator+(difference_type __n) const
341	{ return reverse_iterator(current - __n); }
342
343	/**
344	* @return *this
345	*
346	* Moves the underlying iterator backwards @a __n steps.
347	* The underlying iterator must be a Random Access Iterator.
348	*/
349	_GLIBCXX17_CONSTEXPR reverse_iterator&
350	operator+=(difference_type __n)
351	{
352	current -= __n;
353	return *this;
354	}
355
356	/**
357	* @return A reverse_iterator that refers to @c current - @a __n
358	*
359	* The underlying iterator must be a Random Access Iterator.
360	*/
361	_GLIBCXX_NODISCARD
362	_GLIBCXX17_CONSTEXPR reverse_iterator
363	operator-(difference_type __n) const
364	{ return reverse_iterator(current + __n); }
365
366	/**
367	* @return *this
368	*
369	* Moves the underlying iterator forwards @a __n steps.
370	* The underlying iterator must be a Random Access Iterator.
371	*/
372	_GLIBCXX17_CONSTEXPR reverse_iterator&
373	operator-=(difference_type __n)
374	{
375	current += __n;
376	return *this;
377	}
378
379	/**
380	* @return The value at @c current - @a __n - 1
381	*
382	* The underlying iterator must be a Random Access Iterator.
383	*/
384	_GLIBCXX_NODISCARD
385	_GLIBCXX17_CONSTEXPR reference
386	operator[](difference_type __n) const
387	{ return (this + __n); }
388
389	#if __cplusplus > 201703L && __glibcxx_concepts
390	[[nodiscard]]
391	friend constexpr iter_rvalue_reference_t<_Iterator>
392	iter_move(const reverse_iterator& __i)
393	noexcept(is_nothrow_copy_constructible_v<_Iterator>
394	&& noexcept(ranges::iter_move(--std::declval<_Iterator&>())))
395	{
396	auto __tmp = __i.base();
397	return ranges::iter_move(--__tmp);
398	}
399
400	template<indirectly_swappable<_Iterator> _Iter2>
401	friend constexpr void
402	iter_swap(const reverse_iterator& __x,
403	const reverse_iterator<_Iter2>& __y)
404	noexcept(is_nothrow_copy_constructible_v<_Iterator>
405	&& is_nothrow_copy_constructible_v<_Iter2>
406	&& noexcept(ranges::iter_swap(--std::declval<_Iterator&>(),
407	--std::declval<_Iter2&>())))
408	{
409	auto __xtmp = __x.base();
410	auto __ytmp = __y.base();
411	ranges::iter_swap(--__xtmp, --__ytmp);
412	}
413	#endif
414
415	private:
416	template<typename _Tp>
417	static _GLIBCXX17_CONSTEXPR _Tp*
418	_S_to_pointer(_Tp* __p)
419	{ return __p; }
420
421	template<typename _Tp>
422	static _GLIBCXX17_CONSTEXPR pointer
423	_S_to_pointer(_Tp __t)
424	{ return __t.operator->(); }
425	};
426
427	///@{
428	/**
429	* @param __x A %reverse_iterator.
430	* @param __y A %reverse_iterator.
431	* @return A simple bool.
432	*
433	* Reverse iterators forward comparisons to their underlying base()
434	* iterators.
435	*
436	*/
437	#if __cplusplus <= 201703L \|\| ! defined __glibcxx_concepts
438	template<typename _Iterator>
439	_GLIBCXX_NODISCARD
440	inline _GLIBCXX17_CONSTEXPR bool
441	operator==(const reverse_iterator<_Iterator>& __x,
442	const reverse_iterator<_Iterator>& __y)
443	{ return __x.base() == __y.base(); }
444
445	template<typename _Iterator>
446	_GLIBCXX_NODISCARD
447	inline _GLIBCXX17_CONSTEXPR bool
448	operator<(const reverse_iterator<_Iterator>& __x,
449	const reverse_iterator<_Iterator>& __y)
450	{ return __y.base() < __x.base(); }
451
452	template<typename _Iterator>
453	_GLIBCXX_NODISCARD
454	inline _GLIBCXX17_CONSTEXPR bool
455	operator!=(const reverse_iterator<_Iterator>& __x,
456	const reverse_iterator<_Iterator>& __y)
457	{ return !(__x == __y); }
458
459	template<typename _Iterator>
460	_GLIBCXX_NODISCARD
461	inline _GLIBCXX17_CONSTEXPR bool
462	operator>(const reverse_iterator<_Iterator>& __x,
463	const reverse_iterator<_Iterator>& __y)
464	{ return __y < __x; }
465
466	template<typename _Iterator>
467	_GLIBCXX_NODISCARD
468	inline _GLIBCXX17_CONSTEXPR bool
469	operator<=(const reverse_iterator<_Iterator>& __x,
470	const reverse_iterator<_Iterator>& __y)
471	{ return !(__y < __x); }
472
473	template<typename _Iterator>
474	_GLIBCXX_NODISCARD
475	inline _GLIBCXX17_CONSTEXPR bool
476	operator>=(const reverse_iterator<_Iterator>& __x,
477	const reverse_iterator<_Iterator>& __y)
478	{ return !(__x < __y); }
479
480	// _GLIBCXX_RESOLVE_LIB_DEFECTS
481	// DR 280. Comparison of reverse_iterator to const reverse_iterator.
482
483	template<typename _IteratorL, typename _IteratorR>
484	_GLIBCXX_NODISCARD
485	inline _GLIBCXX17_CONSTEXPR bool
486	operator==(const reverse_iterator<_IteratorL>& __x,
487	const reverse_iterator<_IteratorR>& __y)
488	{ return __x.base() == __y.base(); }
489
490	template<typename _IteratorL, typename _IteratorR>
491	_GLIBCXX_NODISCARD
492	inline _GLIBCXX17_CONSTEXPR bool
493	operator<(const reverse_iterator<_IteratorL>& __x,
494	const reverse_iterator<_IteratorR>& __y)
495	{ return __x.base() > __y.base(); }
496
497	template<typename _IteratorL, typename _IteratorR>
498	_GLIBCXX_NODISCARD
499	inline _GLIBCXX17_CONSTEXPR bool
500	operator!=(const reverse_iterator<_IteratorL>& __x,
501	const reverse_iterator<_IteratorR>& __y)
502	{ return __x.base() != __y.base(); }
503
504	template<typename _IteratorL, typename _IteratorR>
505	_GLIBCXX_NODISCARD
506	inline _GLIBCXX17_CONSTEXPR bool
507	operator>(const reverse_iterator<_IteratorL>& __x,
508	const reverse_iterator<_IteratorR>& __y)
509	{ return __x.base() < __y.base(); }
510
511	template<typename _IteratorL, typename _IteratorR>
512	inline _GLIBCXX17_CONSTEXPR bool
513	operator<=(const reverse_iterator<_IteratorL>& __x,
514	const reverse_iterator<_IteratorR>& __y)
515	{ return __x.base() >= __y.base(); }
516
517	template<typename _IteratorL, typename _IteratorR>
518	_GLIBCXX_NODISCARD
519	inline _GLIBCXX17_CONSTEXPR bool
520	operator>=(const reverse_iterator<_IteratorL>& __x,
521	const reverse_iterator<_IteratorR>& __y)
522	{ return __x.base() <= __y.base(); }
523	#else // C++20
524	template<typename _IteratorL, typename _IteratorR>
525	[[nodiscard]]
526	constexpr bool
527	operator==(const reverse_iterator<_IteratorL>& __x,
528	const reverse_iterator<_IteratorR>& __y)
529	requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
530	{ return __x.base() == __y.base(); }
531
532	template<typename _IteratorL, typename _IteratorR>
533	[[nodiscard]]
534	constexpr bool
535	operator!=(const reverse_iterator<_IteratorL>& __x,
536	const reverse_iterator<_IteratorR>& __y)
537	requires requires { { __x.base() != __y.base() } -> convertible_to<bool>; }
538	{ return __x.base() != __y.base(); }
539
540	template<typename _IteratorL, typename _IteratorR>
541	[[nodiscard]]
542	constexpr bool
543	operator<(const reverse_iterator<_IteratorL>& __x,
544	const reverse_iterator<_IteratorR>& __y)
545	requires requires { { __x.base() > __y.base() } -> convertible_to<bool>; }
546	{ return __x.base() > __y.base(); }
547
548	template<typename _IteratorL, typename _IteratorR>
549	[[nodiscard]]
550	constexpr bool
551	operator>(const reverse_iterator<_IteratorL>& __x,
552	const reverse_iterator<_IteratorR>& __y)
553	requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
554	{ return __x.base() < __y.base(); }
555
556	template<typename _IteratorL, typename _IteratorR>
557	[[nodiscard]]
558	constexpr bool
559	operator<=(const reverse_iterator<_IteratorL>& __x,
560	const reverse_iterator<_IteratorR>& __y)
561	requires requires { { __x.base() >= __y.base() } -> convertible_to<bool>; }
562	{ return __x.base() >= __y.base(); }
563
564	template<typename _IteratorL, typename _IteratorR>
565	[[nodiscard]]
566	constexpr bool
567	operator>=(const reverse_iterator<_IteratorL>& __x,
568	const reverse_iterator<_IteratorR>& __y)
569	requires requires { { __x.base() <= __y.base() } -> convertible_to<bool>; }
570	{ return __x.base() <= __y.base(); }
571
572	template<typename _IteratorL,
573	three_way_comparable_with<_IteratorL> _IteratorR>
574	[[nodiscard]]
575	constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
576	operator<=>(const reverse_iterator<_IteratorL>& __x,
577	const reverse_iterator<_IteratorR>& __y)
578	{ return __y.base() <=> __x.base(); }
579
580	// Additional, non-standard overloads to avoid ambiguities with greedy,
581	// unconstrained overloads in associated namespaces.
582
583	template<typename _Iterator>
584	[[nodiscard]]
585	constexpr bool
586	operator==(const reverse_iterator<_Iterator>& __x,
587	const reverse_iterator<_Iterator>& __y)
588	requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
589	{ return __x.base() == __y.base(); }
590
591	template<three_way_comparable _Iterator>
592	[[nodiscard]]
593	constexpr compare_three_way_result_t<_Iterator, _Iterator>
594	operator<=>(const reverse_iterator<_Iterator>& __x,
595	const reverse_iterator<_Iterator>& __y)
596	{ return __y.base() <=> __x.base(); }
597	#endif // C++20
598	///@}
599
600	#if __cplusplus < 201103L
601	template<typename _Iterator>
602	inline typename reverse_iterator<_Iterator>::difference_type
603	operator-(const reverse_iterator<_Iterator>& __x,
604	const reverse_iterator<_Iterator>& __y)
605	{ return __y.base() - __x.base(); }
606
607	template<typename _IteratorL, typename _IteratorR>
608	inline typename reverse_iterator<_IteratorL>::difference_type
609	operator-(const reverse_iterator<_IteratorL>& __x,
610	const reverse_iterator<_IteratorR>& __y)
611	{ return __y.base() - __x.base(); }
612	#else
613	// _GLIBCXX_RESOLVE_LIB_DEFECTS
614	// DR 685. reverse_iterator/move_iterator difference has invalid signatures
615	template<typename _IteratorL, typename _IteratorR>
616	[[__nodiscard__]]
617	inline _GLIBCXX17_CONSTEXPR auto
618	operator-(const reverse_iterator<_IteratorL>& __x,
619	const reverse_iterator<_IteratorR>& __y)
620	-> decltype(__y.base() - __x.base())
621	{ return __y.base() - __x.base(); }
622	#endif
623
624	template<typename _Iterator>
625	_GLIBCXX_NODISCARD
626	inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
627	operator+(typename reverse_iterator<_Iterator>::difference_type __n,
628	const reverse_iterator<_Iterator>& __x)
629	{ return reverse_iterator<_Iterator>(__x.base() - __n); }
630
631	#if __cplusplus >= 201103L
632	// Same as C++14 make_reverse_iterator but used in C++11 mode too.
633	template<typename _Iterator>
634	inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
635	__make_reverse_iterator(_Iterator __i)
636	{ return reverse_iterator<_Iterator>(__i); }
637
638	# ifdef __glibcxx_make_reverse_iterator // C++ >= 14
639	// _GLIBCXX_RESOLVE_LIB_DEFECTS
640	// DR 2285. make_reverse_iterator
641	/// Generator function for reverse_iterator.
642	template<typename _Iterator>
643	[[__nodiscard__]]
644	inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
645	make_reverse_iterator(_Iterator __i)
646	{ return reverse_iterator<_Iterator>(__i); }
647
648	# if __cplusplus > 201703L && defined __glibcxx_concepts
649	template<typename _Iterator1, typename _Iterator2>
650	requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
651	inline constexpr bool
652	disable_sized_sentinel_for<reverse_iterator<_Iterator1>,
653	reverse_iterator<_Iterator2>> = true;
654	# endif // C++20
655	# endif // __glibcxx_make_reverse_iterator
656
657	template<typename _Iterator>
658	_GLIBCXX20_CONSTEXPR
659	auto
660	__niter_base(reverse_iterator<_Iterator> __it)
661	-> decltype(__make_reverse_iterator(__niter_base(__it.base())))
662	{ return __make_reverse_iterator(__niter_base(__it.base())); }
663
664	template<typename _Iterator>
665	struct __is_move_iterator<reverse_iterator<_Iterator> >
666	: __is_move_iterator<_Iterator>
667	{ };
668
669	template<typename _Iterator>
670	_GLIBCXX20_CONSTEXPR
671	auto
672	__miter_base(reverse_iterator<_Iterator> __it)
673	-> decltype(__make_reverse_iterator(__miter_base(__it.base())))
674	{ return __make_reverse_iterator(__miter_base(__it.base())); }
675	#endif // C++11
676
677	// 24.4.2.2.1 back_insert_iterator
678	/**
679	* @brief Turns assignment into insertion.
680	*
681	* These are output iterators, constructed from a container-of-T.
682	* Assigning a T to the iterator appends it to the container using
683	* push_back.
684	*
685	* Tip: Using the back_inserter function to create these iterators can
686	* save typing.
687	*/
688	template<typename _Container>
689	class back_insert_iterator
690	: public iterator<output_iterator_tag, void, void, void, void>
691	{
692	protected:
693	_Container* container;
694
695	public:
696	/// A nested typedef for the type of whatever container you used.
697	typedef _Container container_type;
698	#if __cplusplus > 201703L
699	using difference_type = ptrdiff_t;
700	#endif
701
702	/// The only way to create this %iterator is with a container.
703	explicit _GLIBCXX20_CONSTEXPR
704	back_insert_iterator(_Container& __x)
705	: container(std::__addressof(__x)) { }
706
707	/**
708	* @param __value An instance of whatever type
709	* container_type::const_reference is; presumably a
710	* reference-to-const T for container<T>.
711	* @return This %iterator, for chained operations.
712	*
713	* This kind of %iterator doesn't really have a @a position in the
714	* container (you can think of the position as being permanently at
715	* the end, if you like). Assigning a value to the %iterator will
716	* always append the value to the end of the container.
717	*/
718	#if __cplusplus < 201103L
719	back_insert_iterator&
720	operator=(typename _Container::const_reference __value)
721	{
722	container->push_back(__value);
723	return *this;
724	}
725	#else
726	_GLIBCXX20_CONSTEXPR
727	back_insert_iterator&
728	operator=(const typename _Container::value_type& __value)
729	{
730	container->push_back(__value);
731	return *this;
732	}
733
734	_GLIBCXX20_CONSTEXPR
735	back_insert_iterator&
736	operator=(typename _Container::value_type&& __value)
737	{
738	container->push_back(std::move(__value));
739	return *this;
740	}
741	#endif
742
743	/// Simply returns this.*
744	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
745	back_insert_iterator&
746	operator*()
747	{ return *this; }
748
749	/// Simply returns this. (This %iterator does not @a move.)*
750	_GLIBCXX20_CONSTEXPR
751	back_insert_iterator&
752	operator++()
753	{ return *this; }
754
755	/// Simply returns this. (This %iterator does not @a move.)*
756	_GLIBCXX20_CONSTEXPR
757	back_insert_iterator
758	operator++(int)
759	{ return *this; }
760	};
761
762	/**
763	* @param __x A container of arbitrary type.
764	* @return An instance of back_insert_iterator working on @p __x.
765	*
766	* This wrapper function helps in creating back_insert_iterator instances.
767	* Typing the name of the %iterator requires knowing the precise full
768	* type of the container, which can be tedious and impedes generic
769	* programming. Using this function lets you take advantage of automatic
770	* template parameter deduction, making the compiler match the correct
771	* types for you.
772	*/
773	template<typename _Container>
774	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
775	inline back_insert_iterator<_Container>
776	back_inserter(_Container& __x)
777	{ return back_insert_iterator<_Container>(__x); }
778
779	/**
780	* @brief Turns assignment into insertion.
781	*
782	* These are output iterators, constructed from a container-of-T.
783	* Assigning a T to the iterator prepends it to the container using
784	* push_front.
785	*
786	* Tip: Using the front_inserter function to create these iterators can
787	* save typing.
788	*/
789	template<typename _Container>
790	class front_insert_iterator
791	: public iterator<output_iterator_tag, void, void, void, void>
792	{
793	protected:
794	_Container* container;
795
796	public:
797	/// A nested typedef for the type of whatever container you used.
798	typedef _Container container_type;
799	#if __cplusplus > 201703L
800	using difference_type = ptrdiff_t;
801	#endif
802
803	/// The only way to create this %iterator is with a container.
804	explicit _GLIBCXX20_CONSTEXPR
805	front_insert_iterator(_Container& __x)
806	: container(std::__addressof(__x)) { }
807
808	/**
809	* @param __value An instance of whatever type
810	* container_type::const_reference is; presumably a
811	* reference-to-const T for container<T>.
812	* @return This %iterator, for chained operations.
813	*
814	* This kind of %iterator doesn't really have a @a position in the
815	* container (you can think of the position as being permanently at
816	* the front, if you like). Assigning a value to the %iterator will
817	* always prepend the value to the front of the container.
818	*/
819	#if __cplusplus < 201103L
820	front_insert_iterator&
821	operator=(typename _Container::const_reference __value)
822	{
823	container->push_front(__value);
824	return *this;
825	}
826	#else
827	_GLIBCXX20_CONSTEXPR
828	front_insert_iterator&
829	operator=(const typename _Container::value_type& __value)
830	{
831	container->push_front(__value);
832	return *this;
833	}
834
835	_GLIBCXX20_CONSTEXPR
836	front_insert_iterator&
837	operator=(typename _Container::value_type&& __value)
838	{
839	container->push_front(std::move(__value));
840	return *this;
841	}
842	#endif
843
844	/// Simply returns this.*
845	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
846	front_insert_iterator&
847	operator*()
848	{ return *this; }
849
850	/// Simply returns this. (This %iterator does not @a move.)*
851	_GLIBCXX20_CONSTEXPR
852	front_insert_iterator&
853	operator++()
854	{ return *this; }
855
856	/// Simply returns this. (This %iterator does not @a move.)*
857	_GLIBCXX20_CONSTEXPR
858	front_insert_iterator
859	operator++(int)
860	{ return *this; }
861	};
862
863	/**
864	* @param __x A container of arbitrary type.
865	* @return An instance of front_insert_iterator working on @p x.
866	*
867	* This wrapper function helps in creating front_insert_iterator instances.
868	* Typing the name of the %iterator requires knowing the precise full
869	* type of the container, which can be tedious and impedes generic
870	* programming. Using this function lets you take advantage of automatic
871	* template parameter deduction, making the compiler match the correct
872	* types for you.
873	*/
874	template<typename _Container>
875	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
876	inline front_insert_iterator<_Container>
877	front_inserter(_Container& __x)
878	{ return front_insert_iterator<_Container>(__x); }
879
880	/**
881	* @brief Turns assignment into insertion.
882	*
883	* These are output iterators, constructed from a container-of-T.
884	* Assigning a T to the iterator inserts it in the container at the
885	* %iterator's position, rather than overwriting the value at that
886	* position.
887	*
888	* (Sequences will actually insert a @e copy of the value before the
889	* %iterator's position.)
890	*
891	* Tip: Using the inserter function to create these iterators can
892	* save typing.
893	*/
894	template<typename _Container>
895	class insert_iterator
896	: public iterator<output_iterator_tag, void, void, void, void>
897	{
898	#if __cplusplus > 201703L && defined __glibcxx_concepts
899	using _Iter = std::__detail::__range_iter_t<_Container>;
900	#else
901	typedef typename _Container::iterator _Iter;
902	#endif
903	protected:
904	_Container* container;
905	_Iter iter;
906
907	public:
908	/// A nested typedef for the type of whatever container you used.
909	typedef _Container container_type;
910
911	#if __cplusplus > 201703L && defined __glibcxx_concepts
912	using difference_type = ptrdiff_t;
913	#endif
914
915	/**
916	* The only way to create this %iterator is with a container and an
917	* initial position (a normal %iterator into the container).
918	*/
919	_GLIBCXX20_CONSTEXPR
920	insert_iterator(_Container& __x, _Iter __i)
921	: container(std::__addressof(__x)), iter(__i) {}
922
923	/**
924	* @param __value An instance of whatever type
925	* container_type::const_reference is; presumably a
926	* reference-to-const T for container<T>.
927	* @return This %iterator, for chained operations.
928	*
929	* This kind of %iterator maintains its own position in the
930	* container. Assigning a value to the %iterator will insert the
931	* value into the container at the place before the %iterator.
932	*
933	* The position is maintained such that subsequent assignments will
934	* insert values immediately after one another. For example,
935	* @code
936	* // vector v contains A and Z
937	*
938	* insert_iterator i (v, ++v.begin());
939	* i = 1;
940	* i = 2;
941	* i = 3;
942	*
943	* // vector v contains A, 1, 2, 3, and Z
944	* @endcode
945	*/
946	#if __cplusplus < 201103L
947	insert_iterator&
948	operator=(typename _Container::const_reference __value)
949	{
950	iter = container->insert(iter, __value);
951	++iter;
952	return *this;
953	}
954	#else
955	_GLIBCXX20_CONSTEXPR
956	insert_iterator&
957	operator=(const typename _Container::value_type& __value)
958	{
959	iter = container->insert(iter, __value);
960	++iter;
961	return *this;
962	}
963
964	_GLIBCXX20_CONSTEXPR
965	insert_iterator&
966	operator=(typename _Container::value_type&& __value)
967	{
968	iter = container->insert(iter, std::move(__value));
969	++iter;
970	return *this;
971	}
972	#endif
973
974	/// Simply returns this.*
975	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
976	insert_iterator&
977	operator*()
978	{ return *this; }
979
980	/// Simply returns this. (This %iterator does not @a move.)*
981	_GLIBCXX20_CONSTEXPR
982	insert_iterator&
983	operator++()
984	{ return *this; }
985
986	/// Simply returns this. (This %iterator does not @a move.)*
987	_GLIBCXX20_CONSTEXPR
988	insert_iterator&
989	operator++(int)
990	{ return *this; }
991	};
992
993	#pragma GCC diagnostic pop
994
995	/**
996	* @param __x A container of arbitrary type.
997	* @param __i An iterator into the container.
998	* @return An instance of insert_iterator working on @p __x.
999	*
1000	* This wrapper function helps in creating insert_iterator instances.
1001	* Typing the name of the %iterator requires knowing the precise full
1002	* type of the container, which can be tedious and impedes generic
1003	* programming. Using this function lets you take advantage of automatic
1004	* template parameter deduction, making the compiler match the correct
1005	* types for you.
1006	*/
1007	#if __cplusplus > 201703L && defined __glibcxx_concepts
1008	template<typename _Container>
1009	[[nodiscard]]
1010	constexpr insert_iterator<_Container>
1011	inserter(_Container& __x, std::__detail::__range_iter_t<_Container> __i)
1012	{ return insert_iterator<_Container>(__x, __i); }
1013	#else
1014	template<typename _Container>
1015	_GLIBCXX_NODISCARD
1016	inline insert_iterator<_Container>
1017	inserter(_Container& __x, typename _Container::iterator __i)
1018	{ return insert_iterator<_Container>(__x, __i); }
1019	#endif
1020
1021	/// @} group iterators
1022
1023	_GLIBCXX_END_NAMESPACE_VERSION
1024	} // namespace
1025
1026	namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
1027	{
1028	_GLIBCXX_BEGIN_NAMESPACE_VERSION
1029
1030	// This iterator adapter is @a normal in the sense that it does not
1031	// change the semantics of any of the operators of its iterator
1032	// parameter. Its primary purpose is to convert an iterator that is
1033	// not a class, e.g. a pointer, into an iterator that is a class.
1034	// The _Container parameter exists solely so that different containers
1035	// using this template can instantiate different types, even if the
1036	// _Iterator parameter is the same.
1037	template<typename _Iterator, typename _Container>
1038	class __normal_iterator
1039	{
1040	protected:
1041	_Iterator _M_current;
1042
1043	typedef std::iterator_traits<_Iterator> __traits_type;
1044
1045	#if __cplusplus >= 201103L
1046	template<typename _Iter>
1047	using __convertible_from
1048	= std::__enable_if_t<std::is_convertible<_Iter, _Iterator>::value>;
1049	#endif
1050
1051	public:
1052	typedef _Iterator iterator_type;
1053	typedef typename __traits_type::iterator_category iterator_category;
1054	typedef typename __traits_type::value_type value_type;
1055	typedef typename __traits_type::difference_type difference_type;
1056	typedef typename __traits_type::reference reference;
1057	typedef typename __traits_type::pointer pointer;
1058
1059	#if __cplusplus > 201703L && __glibcxx_concepts
1060	using iterator_concept = std::__detail::__iter_concept<_Iterator>;
1061	#endif
1062
1063	_GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
1064	: _M_current(_Iterator()) { }
1065
1066	explicit _GLIBCXX20_CONSTEXPR
1067	__normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
1068	: _M_current(__i) { }
1069
1070	// Allow iterator to const_iterator conversion
1071	#if __cplusplus >= 201103L
1072	template<typename _Iter, typename = __convertible_from<_Iter>>
1073	_GLIBCXX20_CONSTEXPR
1074	__normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
1075	noexcept
1076	#else
1077	// N.B. _Container::pointer is not actually in container requirements,
1078	// but is present in std::vector and std::basic_string.
1079	template<typename _Iter>
1080	__normal_iterator(const __normal_iterator<_Iter,
1081	typename __enable_if<
1082	(std::__are_same<_Iter, typename _Container::pointer>::__value),
1083	_Container>::__type>& __i)
1084	#endif
1085	: _M_current(__i.base()) { }
1086
1087	// Forward iterator requirements
1088	_GLIBCXX20_CONSTEXPR
1089	reference
1090	operator() const* _GLIBCXX_NOEXCEPT
1091	{ return *_M_current; }
1092
1093	_GLIBCXX20_CONSTEXPR
1094	pointer
1095	operator->() const _GLIBCXX_NOEXCEPT
1096	{ return _M_current; }
1097
1098	_GLIBCXX20_CONSTEXPR
1099	__normal_iterator&
1100	operator++() _GLIBCXX_NOEXCEPT
1101	{
1102	++_M_current;
1103	return *this;
1104	}
1105
1106	_GLIBCXX20_CONSTEXPR
1107	__normal_iterator
1108	operator++(int) _GLIBCXX_NOEXCEPT
1109	{ return __normal_iterator(_M_current++); }
1110
1111	// Bidirectional iterator requirements
1112	_GLIBCXX20_CONSTEXPR
1113	__normal_iterator&
1114	operator--() _GLIBCXX_NOEXCEPT
1115	{
1116	--_M_current;
1117	return *this;
1118	}
1119
1120	_GLIBCXX20_CONSTEXPR
1121	__normal_iterator
1122	operator--(int) _GLIBCXX_NOEXCEPT
1123	{ return __normal_iterator(_M_current--); }
1124
1125	// Random access iterator requirements
1126	_GLIBCXX20_CONSTEXPR
1127	reference
1128	operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
1129	{ return _M_current[__n]; }
1130
1131	_GLIBCXX20_CONSTEXPR
1132	__normal_iterator&
1133	operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
1134	{ _M_current += __n; return *this; }
1135
1136	_GLIBCXX20_CONSTEXPR
1137	__normal_iterator
1138	operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
1139	{ return __normal_iterator(_M_current + __n); }
1140
1141	_GLIBCXX20_CONSTEXPR
1142	__normal_iterator&
1143	operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
1144	{ _M_current -= __n; return *this; }
1145
1146	_GLIBCXX20_CONSTEXPR
1147	__normal_iterator
1148	operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
1149	{ return __normal_iterator(_M_current - __n); }
1150
1151	_GLIBCXX20_CONSTEXPR
1152	const _Iterator&
1153	base() const _GLIBCXX_NOEXCEPT
1154	{ return _M_current; }
1155	};
1156
1157	// Note: In what follows, the left- and right-hand-side iterators are
1158	// allowed to vary in types (conceptually in cv-qualification) so that
1159	// comparison between cv-qualified and non-cv-qualified iterators be
1160	// valid. However, the greedy and unfriendly operators in std::rel_ops
1161	// will make overload resolution ambiguous (when in scope) if we don't
1162	// provide overloads whose operands are of the same type. Can someone
1163	// remind me what generic programming is about? -- Gaby
1164
1165	#if __cpp_lib_three_way_comparison
1166	template<typename _IteratorL, typename _IteratorR, typename _Container>
1167	[[nodiscard]]
1168	constexpr bool
1169	operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
1170	const __normal_iterator<_IteratorR, _Container>& __rhs)
1171	noexcept(noexcept(__lhs.base() == __rhs.base()))
1172	requires requires {
1173	{ __lhs.base() == __rhs.base() } -> std::convertible_to<bool>;
1174	}
1175	{ return __lhs.base() == __rhs.base(); }
1176
1177	template<typename _IteratorL, typename _IteratorR, typename _Container>
1178	[[nodiscard]]
1179	constexpr std::__detail::__synth3way_t<_IteratorR, _IteratorL>
1180	operator<=>(const __normal_iterator<_IteratorL, _Container>& __lhs,
1181	const __normal_iterator<_IteratorR, _Container>& __rhs)
1182	noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base())))
1183	{ return std::__detail::__synth3way(__lhs.base(), __rhs.base()); }
1184
1185	template<typename _Iterator, typename _Container>
1186	[[nodiscard]]
1187	constexpr bool
1188	operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
1189	const __normal_iterator<_Iterator, _Container>& __rhs)
1190	noexcept(noexcept(__lhs.base() == __rhs.base()))
1191	requires requires {
1192	{ __lhs.base() == __rhs.base() } -> std::convertible_to<bool>;
1193	}
1194	{ return __lhs.base() == __rhs.base(); }
1195
1196	template<typename _Iterator, typename _Container>
1197	[[nodiscard]]
1198	constexpr std::__detail::__synth3way_t<_Iterator>
1199	operator<=>(const __normal_iterator<_Iterator, _Container>& __lhs,
1200	const __normal_iterator<_Iterator, _Container>& __rhs)
1201	noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base())))
1202	{ return std::__detail::__synth3way(__lhs.base(), __rhs.base()); }
1203	#else
1204	// Forward iterator requirements
1205	template<typename _IteratorL, typename _IteratorR, typename _Container>
1206	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1207	inline bool
1208	operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
1209	const __normal_iterator<_IteratorR, _Container>& __rhs)
1210	_GLIBCXX_NOEXCEPT
1211	{ return __lhs.base() == __rhs.base(); }
1212
1213	template<typename _Iterator, typename _Container>
1214	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1215	inline bool
1216	operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
1217	const __normal_iterator<_Iterator, _Container>& __rhs)
1218	_GLIBCXX_NOEXCEPT
1219	{ return __lhs.base() == __rhs.base(); }
1220
1221	template<typename _IteratorL, typename _IteratorR, typename _Container>
1222	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1223	inline bool
1224	operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1225	const __normal_iterator<_IteratorR, _Container>& __rhs)
1226	_GLIBCXX_NOEXCEPT
1227	{ return __lhs.base() != __rhs.base(); }
1228
1229	template<typename _Iterator, typename _Container>
1230	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1231	inline bool
1232	operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
1233	const __normal_iterator<_Iterator, _Container>& __rhs)
1234	_GLIBCXX_NOEXCEPT
1235	{ return __lhs.base() != __rhs.base(); }
1236
1237	// Random access iterator requirements
1238	template<typename _IteratorL, typename _IteratorR, typename _Container>
1239	_GLIBCXX_NODISCARD
1240	inline bool
1241	operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
1242	const __normal_iterator<_IteratorR, _Container>& __rhs)
1243	_GLIBCXX_NOEXCEPT
1244	{ return __lhs.base() < __rhs.base(); }
1245
1246	template<typename _Iterator, typename _Container>
1247	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1248	inline bool
1249	operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
1250	const __normal_iterator<_Iterator, _Container>& __rhs)
1251	_GLIBCXX_NOEXCEPT
1252	{ return __lhs.base() < __rhs.base(); }
1253
1254	template<typename _IteratorL, typename _IteratorR, typename _Container>
1255	_GLIBCXX_NODISCARD
1256	inline bool
1257	operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
1258	const __normal_iterator<_IteratorR, _Container>& __rhs)
1259	_GLIBCXX_NOEXCEPT
1260	{ return __lhs.base() > __rhs.base(); }
1261
1262	template<typename _Iterator, typename _Container>
1263	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1264	inline bool
1265	operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
1266	const __normal_iterator<_Iterator, _Container>& __rhs)
1267	_GLIBCXX_NOEXCEPT
1268	{ return __lhs.base() > __rhs.base(); }
1269
1270	template<typename _IteratorL, typename _IteratorR, typename _Container>
1271	_GLIBCXX_NODISCARD
1272	inline bool
1273	operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1274	const __normal_iterator<_IteratorR, _Container>& __rhs)
1275	_GLIBCXX_NOEXCEPT
1276	{ return __lhs.base() <= __rhs.base(); }
1277
1278	template<typename _Iterator, typename _Container>
1279	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1280	inline bool
1281	operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
1282	const __normal_iterator<_Iterator, _Container>& __rhs)
1283	_GLIBCXX_NOEXCEPT
1284	{ return __lhs.base() <= __rhs.base(); }
1285
1286	template<typename _IteratorL, typename _IteratorR, typename _Container>
1287	_GLIBCXX_NODISCARD
1288	inline bool
1289	operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1290	const __normal_iterator<_IteratorR, _Container>& __rhs)
1291	_GLIBCXX_NOEXCEPT
1292	{ return __lhs.base() >= __rhs.base(); }
1293
1294	template<typename _Iterator, typename _Container>
1295	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1296	inline bool
1297	operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
1298	const __normal_iterator<_Iterator, _Container>& __rhs)
1299	_GLIBCXX_NOEXCEPT
1300	{ return __lhs.base() >= __rhs.base(); }
1301	#endif // three-way comparison
1302
1303	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1304	// According to the resolution of DR179 not only the various comparison
1305	// operators but also operator- must accept mixed iterator/const_iterator
1306	// parameters.
1307	template<typename _IteratorL, typename _IteratorR, typename _Container>
1308	#if __cplusplus >= 201103L
1309	// DR 685.
1310	[[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1311	inline auto
1312	operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
1313	const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
1314	-> decltype(__lhs.base() - __rhs.base())
1315	#else
1316	inline typename __normal_iterator<_IteratorL, _Container>::difference_type
1317	operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
1318	const __normal_iterator<_IteratorR, _Container>& __rhs)
1319	#endif
1320	{ return __lhs.base() - __rhs.base(); }
1321
1322	template<typename _Iterator, typename _Container>
1323	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1324	inline typename __normal_iterator<_Iterator, _Container>::difference_type
1325	operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
1326	const __normal_iterator<_Iterator, _Container>& __rhs)
1327	_GLIBCXX_NOEXCEPT
1328	{ return __lhs.base() - __rhs.base(); }
1329
1330	template<typename _Iterator, typename _Container>
1331	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1332	inline __normal_iterator<_Iterator, _Container>
1333	operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
1334	__n, const __normal_iterator<_Iterator, _Container>& __i)
1335	_GLIBCXX_NOEXCEPT
1336	{ return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
1337
1338	_GLIBCXX_END_NAMESPACE_VERSION
1339	} // namespace
1340
1341	namespace std _GLIBCXX_VISIBILITY(default)
1342	{
1343	_GLIBCXX_BEGIN_NAMESPACE_VERSION
1344
1345	template<typename _Iterator, typename _Container>
1346	_GLIBCXX20_CONSTEXPR
1347	_Iterator
1348	__niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
1349	_GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
1350	{ return __it.base(); }
1351
1352	#if __cplusplus >= 201103L
1353
1354	#if __cplusplus <= 201703L
1355	// Need to overload __to_address because the pointer_traits primary template
1356	// will deduce element_type of __normal_iterator<T, C> as T* rather than T.*
1357	template<typename _Iterator, typename _Container>
1358	constexpr auto
1359	__to_address(const __gnu_cxx::__normal_iterator<_Iterator,
1360	_Container>& __it) noexcept
1361	-> decltype(std::__to_address(__it.base()))
1362	{ return std::__to_address(__it.base()); }
1363	#endif
1364
1365	/**
1366	* @addtogroup iterators
1367	* @{
1368	*/
1369
1370	#if __cplusplus > 201703L && __glibcxx_concepts
1371	template<semiregular _Sent>
1372	class move_sentinel
1373	{
1374	public:
1375	constexpr
1376	move_sentinel()
1377	noexcept(is_nothrow_default_constructible_v<_Sent>)
1378	: _M_last() { }
1379
1380	constexpr explicit
1381	move_sentinel(_Sent __s)
1382	noexcept(is_nothrow_move_constructible_v<_Sent>)
1383	: _M_last(std::move(__s)) { }
1384
1385	template<typename _S2> requires convertible_to<const _S2&, _Sent>
1386	constexpr
1387	move_sentinel(const move_sentinel<_S2>& __s)
1388	noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
1389	: _M_last(__s.base())
1390	{ }
1391
1392	template<typename _S2> requires assignable_from<_Sent&, const _S2&>
1393	constexpr move_sentinel&
1394	operator=(const move_sentinel<_S2>& __s)
1395	noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
1396	{
1397	_M_last = __s.base();
1398	return *this;
1399	}
1400
1401	[[nodiscard]]
1402	constexpr _Sent
1403	base() const
1404	noexcept(is_nothrow_copy_constructible_v<_Sent>)
1405	{ return _M_last; }
1406
1407	private:
1408	_Sent _M_last;
1409	};
1410	#endif // C++20
1411
1412	namespace __detail
1413	{
1414	#if __cplusplus > 201703L && __glibcxx_concepts
1415	template<typename _Iterator>
1416	struct __move_iter_cat
1417	{ };
1418
1419	template<typename _Iterator>
1420	requires requires { typename __iter_category_t<_Iterator>; }
1421	struct __move_iter_cat<_Iterator>
1422	{
1423	using iterator_category
1424	= __clamp_iter_cat<__iter_category_t<_Iterator>,
1425	random_access_iterator_tag>;
1426	};
1427	#endif
1428	}
1429
1430	// 24.4.3 Move iterators
1431	/**
1432	* Class template move_iterator is an iterator adapter with the same
1433	* behavior as the underlying iterator except that its dereference
1434	* operator implicitly converts the value returned by the underlying
1435	* iterator's dereference operator to an rvalue reference. Some
1436	* generic algorithms can be called with move iterators to replace
1437	* copying with moving.
1438	*/
1439	template<typename _Iterator>
1440	class move_iterator
1441	#if __cplusplus > 201703L && __glibcxx_concepts
1442	: public __detail::__move_iter_cat<_Iterator>
1443	#endif
1444	{
1445	_Iterator _M_current;
1446
1447	using __traits_type = iterator_traits<_Iterator>;
1448	#if ! (__cplusplus > 201703L && __glibcxx_concepts)
1449	using __base_ref = typename __traits_type::reference;
1450	#endif
1451
1452	template<typename _Iter2>
1453	friend class move_iterator;
1454
1455	#if __glibcxx_concepts // C++20 && concepts
1456	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1457	// 3435. three_way_comparable_with<reverse_iterator<int>, [...]>*
1458	template<typename _Iter2>
1459	static constexpr bool __convertible = !is_same_v<_Iter2, _Iterator>
1460	&& convertible_to<const _Iter2&, _Iterator>;
1461	#endif
1462
1463	#if __cplusplus > 201703L && __glibcxx_concepts
1464	static auto
1465	_S_iter_concept()
1466	{
1467	if constexpr (random_access_iterator<_Iterator>)
1468	return random_access_iterator_tag{};
1469	else if constexpr (bidirectional_iterator<_Iterator>)
1470	return bidirectional_iterator_tag{};
1471	else if constexpr (forward_iterator<_Iterator>)
1472	return forward_iterator_tag{};
1473	else
1474	return input_iterator_tag{};
1475	}
1476	#endif
1477
1478	public:
1479	using iterator_type = _Iterator;
1480
1481	#ifdef __glibcxx_move_iterator_concept // C++ >= 20 && lib_concepts
1482	using iterator_concept = decltype(_S_iter_concept());
1483
1484	// iterator_category defined in __move_iter_cat
1485	using value_type = iter_value_t<_Iterator>;
1486	using difference_type = iter_difference_t<_Iterator>;
1487	using pointer = _Iterator;
1488	using reference = iter_rvalue_reference_t<_Iterator>;
1489	#else
1490	typedef typename __traits_type::iterator_category iterator_category;
1491	typedef typename __traits_type::value_type value_type;
1492	typedef typename __traits_type::difference_type difference_type;
1493	// NB: DR 680.
1494	typedef _Iterator pointer;
1495	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1496	// 2106. move_iterator wrapping iterators returning prvalues
1497	using reference
1498	= __conditional_t<is_reference<__base_ref>::value,
1499	typename remove_reference<__base_ref>::type&&,
1500	__base_ref>;
1501	#endif
1502
1503	_GLIBCXX17_CONSTEXPR
1504	move_iterator()
1505	: _M_current() { }
1506
1507	explicit _GLIBCXX17_CONSTEXPR
1508	move_iterator(iterator_type __i)
1509	: _M_current(std::move(__i)) { }
1510
1511	template<typename _Iter>
1512	#if __glibcxx_concepts
1513	requires __convertible<_Iter>
1514	#endif
1515	_GLIBCXX17_CONSTEXPR
1516	move_iterator(const move_iterator<_Iter>& __i)
1517	: _M_current(__i._M_current) { }
1518
1519	template<typename _Iter>
1520	#if __glibcxx_concepts
1521	requires __convertible<_Iter>
1522	&& assignable_from<_Iterator&, const _Iter&>
1523	#endif
1524	_GLIBCXX17_CONSTEXPR
1525	move_iterator& operator=(const move_iterator<_Iter>& __i)
1526	{
1527	_M_current = __i._M_current;
1528	return *this;
1529	}
1530
1531	#if __cplusplus <= 201703L
1532	[[__nodiscard__]]
1533	_GLIBCXX17_CONSTEXPR iterator_type
1534	base() const
1535	{ return _M_current; }
1536	#else
1537	[[nodiscard]]
1538	constexpr const iterator_type&
1539	base() const & noexcept
1540	{ return _M_current; }
1541
1542	[[nodiscard]]
1543	constexpr iterator_type
1544	base() &&
1545	{ return std::move(_M_current); }
1546	#endif
1547
1548	[[__nodiscard__]]
1549	_GLIBCXX17_CONSTEXPR reference
1550	operator() const*
1551	#if __cplusplus > 201703L && __glibcxx_concepts
1552	{ return ranges::iter_move(_M_current); }
1553	#else
1554	{ return static_cast<reference>(*_M_current); }
1555	#endif
1556
1557	[[__nodiscard__]]
1558	_GLIBCXX17_CONSTEXPR pointer
1559	operator->() const
1560	{ return _M_current; }
1561
1562	_GLIBCXX17_CONSTEXPR move_iterator&
1563	operator++()
1564	{
1565	++_M_current;
1566	return *this;
1567	}
1568
1569	_GLIBCXX17_CONSTEXPR move_iterator
1570	operator++(int)
1571	{
1572	move_iterator __tmp = *this;
1573	++_M_current;
1574	return __tmp;
1575	}
1576
1577	#if __glibcxx_concepts
1578	constexpr void
1579	operator++(int) requires (!forward_iterator<_Iterator>)
1580	{ ++_M_current; }
1581	#endif
1582
1583	_GLIBCXX17_CONSTEXPR move_iterator&
1584	operator--()
1585	{
1586	--_M_current;
1587	return *this;
1588	}
1589
1590	_GLIBCXX17_CONSTEXPR move_iterator
1591	operator--(int)
1592	{
1593	move_iterator __tmp = *this;
1594	--_M_current;
1595	return __tmp;
1596	}
1597
1598	[[__nodiscard__]]
1599	_GLIBCXX17_CONSTEXPR move_iterator
1600	operator+(difference_type __n) const
1601	{ return move_iterator(_M_current + __n); }
1602
1603	_GLIBCXX17_CONSTEXPR move_iterator&
1604	operator+=(difference_type __n)
1605	{
1606	_M_current += __n;
1607	return *this;
1608	}
1609
1610	[[__nodiscard__]]
1611	_GLIBCXX17_CONSTEXPR move_iterator
1612	operator-(difference_type __n) const
1613	{ return move_iterator(_M_current - __n); }
1614
1615	_GLIBCXX17_CONSTEXPR move_iterator&
1616	operator-=(difference_type __n)
1617	{
1618	_M_current -= __n;
1619	return *this;
1620	}
1621
1622	[[__nodiscard__]]
1623	_GLIBCXX17_CONSTEXPR reference
1624	operator[](difference_type __n) const
1625	#if __cplusplus > 201703L && __glibcxx_concepts
1626	{ return ranges::iter_move(_M_current + __n); }
1627	#else
1628	{ return std::move(_M_current[__n]); }
1629	#endif
1630
1631	#if __cplusplus > 201703L && __glibcxx_concepts
1632	template<sentinel_for<_Iterator> _Sent>
1633	[[nodiscard]]
1634	friend constexpr bool
1635	operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1636	{ return __x.base() == __y.base(); }
1637
1638	template<sized_sentinel_for<_Iterator> _Sent>
1639	[[nodiscard]]
1640	friend constexpr iter_difference_t<_Iterator>
1641	operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
1642	{ return __x.base() - __y.base(); }
1643
1644	template<sized_sentinel_for<_Iterator> _Sent>
1645	[[nodiscard]]
1646	friend constexpr iter_difference_t<_Iterator>
1647	operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1648	{ return __x.base() - __y.base(); }
1649
1650	[[nodiscard]]
1651	friend constexpr iter_rvalue_reference_t<_Iterator>
1652	iter_move(const move_iterator& __i)
1653	noexcept(noexcept(ranges::iter_move(__i._M_current)))
1654	{ return ranges::iter_move(__i._M_current); }
1655
1656	template<indirectly_swappable<_Iterator> _Iter2>
1657	friend constexpr void
1658	iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
1659	noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1660	{ return ranges::iter_swap(__x._M_current, __y._M_current); }
1661	#endif // C++20
1662	};
1663
1664	template<typename _IteratorL, typename _IteratorR>
1665	[[__nodiscard__]]
1666	inline _GLIBCXX17_CONSTEXPR bool
1667	operator==(const move_iterator<_IteratorL>& __x,
1668	const move_iterator<_IteratorR>& __y)
1669	#if __cplusplus > 201703L && __glibcxx_concepts
1670	requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1671	#endif
1672	{ return __x.base() == __y.base(); }
1673
1674	#if __cpp_lib_three_way_comparison
1675	template<typename _IteratorL,
1676	three_way_comparable_with<_IteratorL> _IteratorR>
1677	[[__nodiscard__]]
1678	constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
1679	operator<=>(const move_iterator<_IteratorL>& __x,
1680	const move_iterator<_IteratorR>& __y)
1681	{ return __x.base() <=> __y.base(); }
1682	#else
1683	template<typename _IteratorL, typename _IteratorR>
1684	[[__nodiscard__]]
1685	inline _GLIBCXX17_CONSTEXPR bool
1686	operator!=(const move_iterator<_IteratorL>& __x,
1687	const move_iterator<_IteratorR>& __y)
1688	{ return !(__x == __y); }
1689	#endif
1690
1691	template<typename _IteratorL, typename _IteratorR>
1692	[[__nodiscard__]]
1693	inline _GLIBCXX17_CONSTEXPR bool
1694	operator<(const move_iterator<_IteratorL>& __x,
1695	const move_iterator<_IteratorR>& __y)
1696	#if __cplusplus > 201703L && __glibcxx_concepts
1697	requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1698	#endif
1699	{ return __x.base() < __y.base(); }
1700
1701	template<typename _IteratorL, typename _IteratorR>
1702	[[__nodiscard__]]
1703	inline _GLIBCXX17_CONSTEXPR bool
1704	operator<=(const move_iterator<_IteratorL>& __x,
1705	const move_iterator<_IteratorR>& __y)
1706	#if __cplusplus > 201703L && __glibcxx_concepts
1707	requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1708	#endif
1709	{ return !(__y < __x); }
1710
1711	template<typename _IteratorL, typename _IteratorR>
1712	[[__nodiscard__]]
1713	inline _GLIBCXX17_CONSTEXPR bool
1714	operator>(const move_iterator<_IteratorL>& __x,
1715	const move_iterator<_IteratorR>& __y)
1716	#if __cplusplus > 201703L && __glibcxx_concepts
1717	requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1718	#endif
1719	{ return __y < __x; }
1720
1721	template<typename _IteratorL, typename _IteratorR>
1722	[[__nodiscard__]]
1723	inline _GLIBCXX17_CONSTEXPR bool
1724	operator>=(const move_iterator<_IteratorL>& __x,
1725	const move_iterator<_IteratorR>& __y)
1726	#if __cplusplus > 201703L && __glibcxx_concepts
1727	requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1728	#endif
1729	{ return !(__x < __y); }
1730
1731	// Note: See __normal_iterator operators note from Gaby to understand
1732	// why we have these extra overloads for some move_iterator operators.
1733
1734	template<typename _Iterator>
1735	[[__nodiscard__]]
1736	inline _GLIBCXX17_CONSTEXPR bool
1737	operator==(const move_iterator<_Iterator>& __x,
1738	const move_iterator<_Iterator>& __y)
1739	{ return __x.base() == __y.base(); }
1740
1741	#if __cpp_lib_three_way_comparison
1742	template<three_way_comparable _Iterator>
1743	[[__nodiscard__]]
1744	constexpr compare_three_way_result_t<_Iterator>
1745	operator<=>(const move_iterator<_Iterator>& __x,
1746	const move_iterator<_Iterator>& __y)
1747	{ return __x.base() <=> __y.base(); }
1748	#else
1749	template<typename _Iterator>
1750	[[__nodiscard__]]
1751	inline _GLIBCXX17_CONSTEXPR bool
1752	operator!=(const move_iterator<_Iterator>& __x,
1753	const move_iterator<_Iterator>& __y)
1754	{ return !(__x == __y); }
1755
1756	template<typename _Iterator>
1757	[[__nodiscard__]]
1758	inline _GLIBCXX17_CONSTEXPR bool
1759	operator<(const move_iterator<_Iterator>& __x,
1760	const move_iterator<_Iterator>& __y)
1761	{ return __x.base() < __y.base(); }
1762
1763	template<typename _Iterator>
1764	[[__nodiscard__]]
1765	inline _GLIBCXX17_CONSTEXPR bool
1766	operator<=(const move_iterator<_Iterator>& __x,
1767	const move_iterator<_Iterator>& __y)
1768	{ return !(__y < __x); }
1769
1770	template<typename _Iterator>
1771	[[__nodiscard__]]
1772	inline _GLIBCXX17_CONSTEXPR bool
1773	operator>(const move_iterator<_Iterator>& __x,
1774	const move_iterator<_Iterator>& __y)
1775	{ return __y < __x; }
1776
1777	template<typename _Iterator>
1778	[[__nodiscard__]]
1779	inline _GLIBCXX17_CONSTEXPR bool
1780	operator>=(const move_iterator<_Iterator>& __x,
1781	const move_iterator<_Iterator>& __y)
1782	{ return !(__x < __y); }
1783	#endif // ! C++20
1784
1785	// DR 685.
1786	template<typename _IteratorL, typename _IteratorR>
1787	[[__nodiscard__]]
1788	inline _GLIBCXX17_CONSTEXPR auto
1789	operator-(const move_iterator<_IteratorL>& __x,
1790	const move_iterator<_IteratorR>& __y)
1791	-> decltype(__x.base() - __y.base())
1792	{ return __x.base() - __y.base(); }
1793
1794	template<typename _Iterator>
1795	[[__nodiscard__]]
1796	inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1797	operator+(typename move_iterator<_Iterator>::difference_type __n,
1798	const move_iterator<_Iterator>& __x)
1799	{ return __x + __n; }
1800
1801	template<typename _Iterator>
1802	[[__nodiscard__]]
1803	inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1804	make_move_iterator(_Iterator __i)
1805	{ return move_iterator<_Iterator>(std::move(__i)); }
1806
1807	template<typename _Iterator, typename _ReturnType
1808	= __conditional_t<__move_if_noexcept_cond
1809	<typename iterator_traits<_Iterator>::value_type>::value,
1810	_Iterator, move_iterator<_Iterator>>>
1811	inline _GLIBCXX17_CONSTEXPR _ReturnType
1812	__make_move_if_noexcept_iterator(_Iterator __i)
1813	{ return _ReturnType(__i); }
1814
1815	// Overload for pointers that matches std::move_if_noexcept more closely,
1816	// returning a constant iterator when we don't want to move.
1817	template<typename _Tp, typename _ReturnType
1818	= __conditional_t<__move_if_noexcept_cond<_Tp>::value,
1819	const _Tp, move_iterator<_Tp>>>
1820	inline _GLIBCXX17_CONSTEXPR _ReturnType
1821	__make_move_if_noexcept_iterator(_Tp* __i)
1822	{ return _ReturnType(__i); }
1823
1824	#if __cplusplus > 201703L && __glibcxx_concepts
1825	// [iterators.common] Common iterators
1826
1827	namespace __detail
1828	{
1829	template<typename _It>
1830	concept __common_iter_has_arrow = indirectly_readable<const _It>
1831	&& (requires(const _It& __it) { __it.operator->(); }
1832	\|\| is_reference_v<iter_reference_t<_It>>
1833	\|\| constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1834
1835	template<typename _It>
1836	concept __common_iter_use_postfix_proxy
1837	= (!requires (_It& __i) { { *__i++ } -> __can_reference; })
1838	&& constructible_from<iter_value_t<_It>, iter_reference_t<_It>>
1839	&& move_constructible<iter_value_t<_It>>;
1840	} // namespace __detail
1841
1842	/// An iterator/sentinel adaptor for representing a non-common range.
1843	template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1844	requires (!same_as<_It, _Sent>) && copyable<_It>
1845	class common_iterator
1846	{
1847	template<typename _Tp, typename _Up>
1848	static constexpr bool
1849	_S_noexcept1()
1850	{
1851	if constexpr (is_trivially_default_constructible_v<_Tp>)
1852	return is_nothrow_assignable_v<_Tp&, _Up>;
1853	else
1854	return is_nothrow_constructible_v<_Tp, _Up>;
1855	}
1856
1857	template<typename _It2, typename _Sent2>
1858	static constexpr bool
1859	_S_noexcept()
1860	{ return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1861
1862	class __arrow_proxy
1863	{
1864	iter_value_t<_It> _M_keep;
1865
1866	constexpr
1867	__arrow_proxy(iter_reference_t<_It>&& __x)
1868	: _M_keep(std::move(__x)) { }
1869
1870	friend class common_iterator;
1871
1872	public:
1873	constexpr const iter_value_t<_It>*
1874	operator->() const noexcept
1875	{ return std::__addressof(_M_keep); }
1876	};
1877
1878	class __postfix_proxy
1879	{
1880	iter_value_t<_It> _M_keep;
1881
1882	constexpr
1883	__postfix_proxy(iter_reference_t<_It>&& __x)
1884	: _M_keep(std::forward<iter_reference_t<_It>>(__x)) { }
1885
1886	friend class common_iterator;
1887
1888	public:
1889	constexpr const iter_value_t<_It>&
1890	operator() const* noexcept
1891	{ return _M_keep; }
1892	};
1893
1894	public:
1895	constexpr
1896	common_iterator()
1897	noexcept(is_nothrow_default_constructible_v<_It>)
1898	requires default_initializable<_It>
1899	: _M_it(), _M_index(`0`)
1900	{ }
1901
1902	constexpr
1903	common_iterator(_It __i)
1904	noexcept(is_nothrow_move_constructible_v<_It>)
1905	: _M_it(std::move(__i)), _M_index(`0`)
1906	{ }
1907
1908	constexpr
1909	common_iterator(_Sent __s)
1910	noexcept(is_nothrow_move_constructible_v<_Sent>)
1911	: _M_sent(std::move(__s)), _M_index(`1`)
1912	{ }
1913
1914	template<typename _It2, typename _Sent2>
1915	requires convertible_to<const _It2&, _It>
1916	&& convertible_to<const _Sent2&, _Sent>
1917	constexpr
1918	common_iterator(const common_iterator<_It2, _Sent2>& __x)
1919	noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1920	: _M_valueless(), _M_index(__x._M_index)
1921	{
1922	__glibcxx_assert(__x._M_has_value());
1923	if (_M_index == `0`)
1924	{
1925	if constexpr (is_trivially_default_constructible_v<_It>)
1926	_M_it = std::move(__x._M_it);
1927	else
1928	std::construct_at(std::__addressof(_M_it), __x._M_it);
1929	}
1930	else if (_M_index == `1`)
1931	{
1932	if constexpr (is_trivially_default_constructible_v<_Sent>)
1933	_M_sent = std::move(__x._M_sent);
1934	else
1935	std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1936	}
1937	}
1938
1939	common_iterator(const common_iterator&) = default;
1940
1941	constexpr
1942	common_iterator(const common_iterator& __x)
1943	noexcept(_S_noexcept<const _It&, const _Sent&>())
1944	requires (!is_trivially_copyable_v<_It> \|\| !is_trivially_copyable_v<_Sent>)
1945	: _M_valueless(), _M_index(__x._M_index)
1946	{
1947	if (_M_index == `0`)
1948	{
1949	if constexpr (is_trivially_default_constructible_v<_It>)
1950	_M_it = __x._M_it;
1951	else
1952	std::construct_at(std::__addressof(_M_it), __x._M_it);
1953	}
1954	else if (_M_index == `1`)
1955	{
1956	if constexpr (is_trivially_default_constructible_v<_Sent>)
1957	_M_sent = __x._M_sent;
1958	else
1959	std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1960	}
1961	}
1962
1963	common_iterator(common_iterator&&) = default;
1964
1965	constexpr
1966	common_iterator(common_iterator&& __x)
1967	noexcept(_S_noexcept<_It, _Sent>())
1968	requires (!is_trivially_copyable_v<_It> \|\| !is_trivially_copyable_v<_Sent>)
1969	: _M_valueless(), _M_index(__x._M_index)
1970	{
1971	if (_M_index == `0`)
1972	{
1973	if constexpr (is_trivially_default_constructible_v<_It>)
1974	_M_it = std::move(__x._M_it);
1975	else
1976	std::construct_at(std::__addressof(_M_it), std::move(__x._M_it));
1977	}
1978	else if (_M_index == `1`)
1979	{
1980	if constexpr (is_trivially_default_constructible_v<_Sent>)
1981	_M_sent = std::move(__x._M_sent);
1982	else
1983	std::construct_at(std::__addressof(_M_sent),
1984	std::move(__x._M_sent));
1985	}
1986	}
1987
1988	constexpr common_iterator&
1989	operator=(const common_iterator&) = default;
1990
1991	constexpr common_iterator&
1992	operator=(const common_iterator& __x)
1993	noexcept(is_nothrow_copy_assignable_v<_It>
1994	&& is_nothrow_copy_assignable_v<_Sent>
1995	&& is_nothrow_copy_constructible_v<_It>
1996	&& is_nothrow_copy_constructible_v<_Sent>)
1997	requires (!is_trivially_copy_assignable_v<_It>
1998	\|\| !is_trivially_copy_assignable_v<_Sent>)
1999	{
2000	_M_assign(__x);
2001	return *this;
2002	}
2003
2004	constexpr common_iterator&
2005	operator=(common_iterator&&) = default;
2006
2007	constexpr common_iterator&
2008	operator=(common_iterator&& __x)
2009	noexcept(is_nothrow_move_assignable_v<_It>
2010	&& is_nothrow_move_assignable_v<_Sent>
2011	&& is_nothrow_move_constructible_v<_It>
2012	&& is_nothrow_move_constructible_v<_Sent>)
2013	requires (!is_trivially_move_assignable_v<_It>
2014	\|\| !is_trivially_move_assignable_v<_Sent>)
2015	{
2016	_M_assign(std::move(__x));
2017	return *this;
2018	}
2019
2020	template<typename _It2, typename _Sent2>
2021	requires convertible_to<const _It2&, _It>
2022	&& convertible_to<const _Sent2&, _Sent>
2023	&& assignable_from<_It&, const _It2&>
2024	&& assignable_from<_Sent&, const _Sent2&>
2025	constexpr common_iterator&
2026	operator=(const common_iterator<_It2, _Sent2>& __x)
2027	noexcept(is_nothrow_constructible_v<_It, const _It2&>
2028	&& is_nothrow_constructible_v<_Sent, const _Sent2&>
2029	&& is_nothrow_assignable_v<_It&, const _It2&>
2030	&& is_nothrow_assignable_v<_Sent&, const _Sent2&>)
2031	{
2032	__glibcxx_assert(__x._M_has_value());
2033	_M_assign(__x);
2034	return *this;
2035	}
2036
2037	#if __cpp_concepts >= 202002L // Constrained special member functions
2038	~common_iterator() = default;
2039
2040	constexpr
2041	~common_iterator()
2042	requires (!is_trivially_destructible_v<_It>
2043	\|\| !is_trivially_destructible_v<_Sent>)
2044	#else
2045	constexpr
2046	~common_iterator()
2047	#endif
2048	{
2049	if (_M_index == `0`)
2050	_M_it.~_It();
2051	else if (_M_index == `1`)
2052	_M_sent.~_Sent();
2053	}
2054
2055	[[nodiscard]]
2056	constexpr decltype(auto)
2057	operator*()
2058	{
2059	__glibcxx_assert(_M_index == `0`);
2060	return *_M_it;
2061	}
2062
2063	[[nodiscard]]
2064	constexpr decltype(auto)
2065	operator() const* requires __detail::__dereferenceable<const _It>
2066	{
2067	__glibcxx_assert(_M_index == `0`);
2068	return *_M_it;
2069	}
2070
2071	[[nodiscard]]
2072	constexpr auto
2073	operator->() const requires __detail::__common_iter_has_arrow<_It>
2074	{
2075	__glibcxx_assert(_M_index == `0`);
2076	if constexpr (is_pointer_v<_It> \|\| requires { _M_it.operator->(); })
2077	return _M_it;
2078	else if constexpr (is_reference_v<iter_reference_t<_It>>)
2079	{
2080	auto&& __tmp = *_M_it;
2081	return std::__addressof(__tmp);
2082	}
2083	else
2084	return __arrow_proxy{*_M_it};
2085	}
2086
2087	constexpr common_iterator&
2088	operator++()
2089	{
2090	__glibcxx_assert(_M_index == `0`);
2091	++_M_it;
2092	return *this;
2093	}
2094
2095	constexpr decltype(auto)
2096	operator++(int)
2097	{
2098	__glibcxx_assert(_M_index == `0`);
2099	if constexpr (forward_iterator<_It>)
2100	{
2101	common_iterator __tmp = *this;
2102	++*this;
2103	return __tmp;
2104	}
2105	else if constexpr (!__detail::__common_iter_use_postfix_proxy<_It>)
2106	return _M_it++;
2107	else
2108	{
2109	__postfix_proxy __p(**this);
2110	++*this;
2111	return __p;
2112	}
2113	}
2114
2115	template<typename _It2, sentinel_for<_It> _Sent2>
2116	requires sentinel_for<_Sent, _It2>
2117	friend constexpr bool
2118	operator== [[nodiscard]] (const common_iterator& __x,
2119	const common_iterator<_It2, _Sent2>& __y)
2120	{
2121	switch(__x._M_index << `2` \| __y._M_index)
2122	{
2123	case `0b0000`:
2124	case `0b0101`:
2125	return true;
2126	case `0b0001`:
2127	return __x._M_it == __y._M_sent;
2128	case `0b0100`:
2129	return __x._M_sent == __y._M_it;
2130	default:
2131	__glibcxx_assert(__x._M_has_value());
2132	__glibcxx_assert(__y._M_has_value());
2133	__builtin_unreachable();
2134	}
2135	}
2136
2137	template<typename _It2, sentinel_for<_It> _Sent2>
2138	requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
2139	friend constexpr bool
2140	operator== [[nodiscard]] (const common_iterator& __x,
2141	const common_iterator<_It2, _Sent2>& __y)
2142	{
2143	switch(__x._M_index << `2` \| __y._M_index)
2144	{
2145	case `0b0101`:
2146	return true;
2147	case `0b0000`:
2148	return __x._M_it == __y._M_it;
2149	case `0b0001`:
2150	return __x._M_it == __y._M_sent;
2151	case `0b0100`:
2152	return __x._M_sent == __y._M_it;
2153	default:
2154	__glibcxx_assert(__x._M_has_value());
2155	__glibcxx_assert(__y._M_has_value());
2156	__builtin_unreachable();
2157	}
2158	}
2159
2160	template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
2161	requires sized_sentinel_for<_Sent, _It2>
2162	friend constexpr iter_difference_t<_It2>
2163	operator- [[nodiscard]] (const common_iterator& __x,
2164	const common_iterator<_It2, _Sent2>& __y)
2165	{
2166	switch(__x._M_index << `2` \| __y._M_index)
2167	{
2168	case `0b0101`:
2169	return `0`;
2170	case `0b0000`:
2171	return __x._M_it - __y._M_it;
2172	case `0b0001`:
2173	return __x._M_it - __y._M_sent;
2174	case `0b0100`:
2175	return __x._M_sent - __y._M_it;
2176	default:
2177	__glibcxx_assert(__x._M_has_value());
2178	__glibcxx_assert(__y._M_has_value());
2179	__builtin_unreachable();
2180	}
2181	}
2182
2183	[[nodiscard]]
2184	friend constexpr iter_rvalue_reference_t<_It>
2185	iter_move(const common_iterator& __i)
2186	noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
2187	requires input_iterator<_It>
2188	{
2189	__glibcxx_assert(__i._M_index == `0`);
2190	return ranges::iter_move(__i._M_it);
2191	}
2192
2193	template<indirectly_swappable<_It> _It2, typename _Sent2>
2194	friend constexpr void
2195	iter_swap(const common_iterator& __x,
2196	const common_iterator<_It2, _Sent2>& __y)
2197	noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
2198	std::declval<const _It2&>())))
2199	{
2200	__glibcxx_assert(__x._M_index == `0`);
2201	__glibcxx_assert(__y._M_index == `0`);
2202	return ranges::iter_swap(__x._M_it, __y._M_it);
2203	}
2204
2205	private:
2206	template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
2207	requires (!same_as<_It2, _Sent2>) && copyable<_It2>
2208	friend class common_iterator;
2209
2210	constexpr bool
2211	_M_has_value() const noexcept { return _M_index != _S_valueless; }
2212
2213	template<typename _CIt>
2214	constexpr void
2215	_M_assign(_CIt&& __x)
2216	{
2217	if (_M_index == __x._M_index)
2218	{
2219	if (_M_index == `0`)
2220	_M_it = std::forward<_CIt>(__x)._M_it;
2221	else if (_M_index == `1`)
2222	_M_sent = std::forward<_CIt>(__x)._M_sent;
2223	}
2224	else
2225	{
2226	if (_M_index == `0`)
2227	_M_it.~_It();
2228	else if (_M_index == `1`)
2229	_M_sent.~_Sent();
2230	_M_index = _S_valueless;
2231
2232	if (__x._M_index == `0`)
2233	std::construct_at(std::__addressof(_M_it),
2234	std::forward<_CIt>(__x)._M_it);
2235	else if (__x._M_index == `1`)
2236	std::construct_at(std::__addressof(_M_sent),
2237	std::forward<_CIt>(__x)._M_sent);
2238	_M_index = __x._M_index;
2239	}
2240	}
2241
2242	union
2243	{
2244	_It _M_it;
2245	_Sent _M_sent;
2246	unsigned char _M_valueless;
2247	};
2248	unsigned char _M_index; // 0 == _M_it, 1 == _M_sent, 2 == valueless
2249
2250	static constexpr unsigned char _S_valueless{`2`};
2251	};
2252
2253	template<typename _It, typename _Sent>
2254	struct incrementable_traits<common_iterator<_It, _Sent>>
2255	{
2256	using difference_type = iter_difference_t<_It>;
2257	};
2258
2259	template<input_iterator _It, typename _Sent>
2260	struct iterator_traits<common_iterator<_It, _Sent>>
2261	{
2262	private:
2263	template<typename _Iter>
2264	struct __ptr
2265	{
2266	using type = void;
2267	};
2268
2269	template<typename _Iter>
2270	requires __detail::__common_iter_has_arrow<_Iter>
2271	struct __ptr<_Iter>
2272	{
2273	using _CIter = common_iterator<_Iter, _Sent>;
2274	using type = decltype(std::declval<const _CIter&>().operator->());
2275	};
2276
2277	static auto
2278	_S_iter_cat()
2279	{
2280	if constexpr (requires { requires derived_from<__iter_category_t<_It>,
2281	forward_iterator_tag>; })
2282	return forward_iterator_tag{};
2283	else
2284	return input_iterator_tag{};
2285	}
2286
2287	public:
2288	using iterator_concept = __conditional_t<forward_iterator<_It>,
2289	forward_iterator_tag,
2290	input_iterator_tag>;
2291	using iterator_category = decltype(_S_iter_cat());
2292	using value_type = iter_value_t<_It>;
2293	using difference_type = iter_difference_t<_It>;
2294	using pointer = typename __ptr<_It>::type;
2295	using reference = iter_reference_t<_It>;
2296	};
2297
2298	// [iterators.counted] Counted iterators
2299
2300	namespace __detail
2301	{
2302	template<typename _It>
2303	struct __counted_iter_value_type
2304	{ };
2305
2306	template<indirectly_readable _It>
2307	struct __counted_iter_value_type<_It>
2308	{ using value_type = iter_value_t<_It>; };
2309
2310	template<typename _It>
2311	struct __counted_iter_concept
2312	{ };
2313
2314	template<typename _It>
2315	requires requires { typename _It::iterator_concept; }
2316	struct __counted_iter_concept<_It>
2317	{ using iterator_concept = typename _It::iterator_concept; };
2318
2319	template<typename _It>
2320	struct __counted_iter_cat
2321	{ };
2322
2323	template<typename _It>
2324	requires requires { typename _It::iterator_category; }
2325	struct __counted_iter_cat<_It>
2326	{ using iterator_category = typename _It::iterator_category; };
2327	}
2328
2329	/// An iterator adaptor that keeps track of the distance to the end.
2330	template<input_or_output_iterator _It>
2331	class counted_iterator
2332	: public __detail::__counted_iter_value_type<_It>,
2333	public __detail::__counted_iter_concept<_It>,
2334	public __detail::__counted_iter_cat<_It>
2335	{
2336	public:
2337	using iterator_type = _It;
2338	// value_type defined in __counted_iter_value_type
2339	using difference_type = iter_difference_t<_It>;
2340	// iterator_concept defined in __counted_iter_concept
2341	// iterator_category defined in __counted_iter_cat
2342
2343	constexpr counted_iterator() requires default_initializable<_It> = default;
2344
2345	constexpr
2346	counted_iterator(_It __i, iter_difference_t<_It> __n)
2347	: _M_current(std::move(__i)), _M_length(__n)
2348	{ __glibcxx_assert(__n >= `0`); }
2349
2350	template<typename _It2>
2351	requires convertible_to<const _It2&, _It>
2352	constexpr
2353	counted_iterator(const counted_iterator<_It2>& __x)
2354	: _M_current(__x._M_current), _M_length(__x._M_length)
2355	{ }
2356
2357	template<typename _It2>
2358	requires assignable_from<_It&, const _It2&>
2359	constexpr counted_iterator&
2360	operator=(const counted_iterator<_It2>& __x)
2361	{
2362	_M_current = __x._M_current;
2363	_M_length = __x._M_length;
2364	return *this;
2365	}
2366
2367	[[nodiscard]]
2368	constexpr const _It&
2369	base() const & noexcept
2370	{ return _M_current; }
2371
2372	[[nodiscard]]
2373	constexpr _It
2374	base() &&
2375	noexcept(is_nothrow_move_constructible_v<_It>)
2376	{ return std::move(_M_current); }
2377
2378	[[nodiscard]]
2379	constexpr iter_difference_t<_It>
2380	count() const noexcept { return _M_length; }
2381
2382	[[nodiscard]]
2383	constexpr decltype(auto)
2384	operator*()
2385	noexcept(noexcept(*_M_current))
2386	{
2387	__glibcxx_assert( _M_length > `0` );
2388	return *_M_current;
2389	}
2390
2391	[[nodiscard]]
2392	constexpr decltype(auto)
2393	operator() const*
2394	noexcept(noexcept(*_M_current))
2395	requires __detail::__dereferenceable<const _It>
2396	{
2397	__glibcxx_assert( _M_length > `0` );
2398	return *_M_current;
2399	}
2400
2401	[[nodiscard]]
2402	constexpr auto
2403	operator->() const noexcept
2404	requires contiguous_iterator<_It>
2405	{ return std::to_address(_M_current); }
2406
2407	constexpr counted_iterator&
2408	operator++()
2409	{
2410	__glibcxx_assert(_M_length > `0`);
2411	++_M_current;
2412	--_M_length;
2413	return *this;
2414	}
2415
2416	constexpr decltype(auto)
2417	operator++(int)
2418	{
2419	__glibcxx_assert(_M_length > `0`);
2420	--_M_length;
2421	__try
2422	{
2423	return _M_current++;
2424	} __catch(...) {
2425	++_M_length;
2426	__throw_exception_again;
2427	}
2428	}
2429
2430	constexpr counted_iterator
2431	operator++(int) requires forward_iterator<_It>
2432	{
2433	auto __tmp = *this;
2434	++*this;
2435	return __tmp;
2436	}
2437
2438	constexpr counted_iterator&
2439	operator--() requires bidirectional_iterator<_It>
2440	{
2441	--_M_current;
2442	++_M_length;
2443	return *this;
2444	}
2445
2446	constexpr counted_iterator
2447	operator--(int) requires bidirectional_iterator<_It>
2448	{
2449	auto __tmp = *this;
2450	--*this;
2451	return __tmp;
2452	}
2453
2454	[[nodiscard]]
2455	constexpr counted_iterator
2456	operator+(iter_difference_t<_It> __n) const
2457	requires random_access_iterator<_It>
2458	{ return counted_iterator(_M_current + __n, _M_length - __n); }
2459
2460	[[nodiscard]]
2461	friend constexpr counted_iterator
2462	operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
2463	requires random_access_iterator<_It>
2464	{ return __x + __n; }
2465
2466	constexpr counted_iterator&
2467	operator+=(iter_difference_t<_It> __n)
2468	requires random_access_iterator<_It>
2469	{
2470	__glibcxx_assert(__n <= _M_length);
2471	_M_current += __n;
2472	_M_length -= __n;
2473	return *this;
2474	}
2475
2476	[[nodiscard]]
2477	constexpr counted_iterator
2478	operator-(iter_difference_t<_It> __n) const
2479	requires random_access_iterator<_It>
2480	{ return counted_iterator(_M_current - __n, _M_length + __n); }
2481
2482	template<common_with<_It> _It2>
2483	[[nodiscard]]
2484	friend constexpr iter_difference_t<_It2>
2485	operator-(const counted_iterator& __x,
2486	const counted_iterator<_It2>& __y)
2487	{ return __y._M_length - __x._M_length; }
2488
2489	[[nodiscard]]
2490	friend constexpr iter_difference_t<_It>
2491	operator-(const counted_iterator& __x, default_sentinel_t)
2492	{ return -__x._M_length; }
2493
2494	[[nodiscard]]
2495	friend constexpr iter_difference_t<_It>
2496	operator-(default_sentinel_t, const counted_iterator& __y)
2497	{ return __y._M_length; }
2498
2499	constexpr counted_iterator&
2500	operator-=(iter_difference_t<_It> __n)
2501	requires random_access_iterator<_It>
2502	{
2503	__glibcxx_assert(-__n <= _M_length);
2504	_M_current -= __n;
2505	_M_length += __n;
2506	return *this;
2507	}
2508
2509	[[nodiscard]]
2510	constexpr decltype(auto)
2511	operator[](iter_difference_t<_It> __n) const
2512	noexcept(noexcept(_M_current[__n]))
2513	requires random_access_iterator<_It>
2514	{
2515	__glibcxx_assert(__n < _M_length);
2516	return _M_current[__n];
2517	}
2518
2519	template<common_with<_It> _It2>
2520	[[nodiscard]]
2521	friend constexpr bool
2522	operator==(const counted_iterator& __x,
2523	const counted_iterator<_It2>& __y)
2524	{ return __x._M_length == __y._M_length; }
2525
2526	[[nodiscard]]
2527	friend constexpr bool
2528	operator==(const counted_iterator& __x, default_sentinel_t)
2529	{ return __x._M_length == `0`; }
2530
2531	template<common_with<_It> _It2>
2532	[[nodiscard]]
2533	friend constexpr strong_ordering
2534	operator<=>(const counted_iterator& __x,
2535	const counted_iterator<_It2>& __y)
2536	{ return __y._M_length <=> __x._M_length; }
2537
2538	[[nodiscard]]
2539	friend constexpr iter_rvalue_reference_t<_It>
2540	iter_move(const counted_iterator& __i)
2541	noexcept(noexcept(ranges::iter_move(__i._M_current)))
2542	requires input_iterator<_It>
2543	{
2544	__glibcxx_assert( __i._M_length > `0` );
2545	return ranges::iter_move(__i._M_current);
2546	}
2547
2548	template<indirectly_swappable<_It> _It2>
2549	friend constexpr void
2550	iter_swap(const counted_iterator& __x,
2551	const counted_iterator<_It2>& __y)
2552	noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2553	{
2554	__glibcxx_assert( __x._M_length > `0` && __y._M_length > `0` );
2555	ranges::iter_swap(__x._M_current, __y._M_current);
2556	}
2557
2558	private:
2559	template<input_or_output_iterator _It2> friend class counted_iterator;
2560
2561	_It _M_current = _It();
2562	iter_difference_t<_It> _M_length = `0`;
2563	};
2564
2565	template<input_iterator _It>
2566	requires same_as<__detail::__iter_traits<_It>, iterator_traits<_It>>
2567	struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2568	{
2569	using pointer = __conditional_t<contiguous_iterator<_It>,
2570	add_pointer_t<iter_reference_t<_It>>,
2571	void>;
2572	};
2573
2574	#if __cplusplus > 202020L
2575	template<indirectly_readable _It>
2576	using iter_const_reference_t
2577	= common_reference_t<const iter_value_t<_It>&&, iter_reference_t<_It>>;
2578
2579	template<input_iterator _It> class basic_const_iterator;
2580
2581	namespace __detail
2582	{
2583	template<typename _It>
2584	concept __constant_iterator = input_iterator<_It>
2585	&& same_as<iter_const_reference_t<_It>, iter_reference_t<_It>>;
2586
2587	template<typename _Tp>
2588	inline constexpr bool __is_const_iterator = false;
2589
2590	template<typename _It>
2591	inline constexpr bool __is_const_iterator<basic_const_iterator<_It>> = true;
2592
2593	template<typename _Tp>
2594	concept __not_a_const_iterator = !__is_const_iterator<_Tp>;
2595
2596	template<indirectly_readable _It>
2597	using __iter_const_rvalue_reference_t
2598	= common_reference_t<const iter_value_t<_It>&&, iter_rvalue_reference_t<_It>>;
2599
2600	template<typename _It>
2601	struct __basic_const_iterator_iter_cat
2602	{ };
2603
2604	template<forward_iterator _It>
2605	struct __basic_const_iterator_iter_cat<_It>
2606	{ using iterator_category = __iter_category_t<_It>; };
2607	} // namespace detail
2608
2609	template<input_iterator _It>
2610	using const_iterator
2611	= __conditional_t<__detail::__constant_iterator<_It>, _It, basic_const_iterator<_It>>;
2612
2613	namespace __detail
2614	{
2615	template<typename _Sent>
2616	struct __const_sentinel
2617	{ using type = _Sent; };
2618
2619	template<input_iterator _Sent>
2620	struct __const_sentinel<_Sent>
2621	{ using type = const_iterator<_Sent>; };
2622	} // namespace __detail
2623
2624	template<semiregular _Sent>
2625	using const_sentinel = typename __detail::__const_sentinel<_Sent>::type;
2626
2627	template<input_iterator _It>
2628	class basic_const_iterator
2629	: public __detail::__basic_const_iterator_iter_cat<_It>
2630	{
2631	_It _M_current = _It();
2632	using __reference = iter_const_reference_t<_It>;
2633	using __rvalue_reference = __detail::__iter_const_rvalue_reference_t<_It>;
2634
2635	static auto
2636	_S_iter_concept()
2637	{
2638	if constexpr (contiguous_iterator<_It>)
2639	return contiguous_iterator_tag{};
2640	else if constexpr (random_access_iterator<_It>)
2641	return random_access_iterator_tag{};
2642	else if constexpr (bidirectional_iterator<_It>)
2643	return bidirectional_iterator_tag{};
2644	else if constexpr (forward_iterator<_It>)
2645	return forward_iterator_tag{};
2646	else
2647	return input_iterator_tag{};
2648	}
2649
2650	template<input_iterator _It2> friend class basic_const_iterator;
2651
2652	public:
2653	using iterator_concept = decltype(_S_iter_concept());
2654	using value_type = iter_value_t<_It>;
2655	using difference_type = iter_difference_t<_It>;
2656
2657	basic_const_iterator() requires default_initializable<_It> = default;
2658
2659	constexpr
2660	basic_const_iterator(_It __current)
2661	noexcept(is_nothrow_move_constructible_v<_It>)
2662	: _M_current(std::move(__current))
2663	{ }
2664
2665	template<convertible_to<_It> _It2>
2666	constexpr
2667	basic_const_iterator(basic_const_iterator<_It2> __current)
2668	noexcept(is_nothrow_constructible_v<_It, _It2>)
2669	: _M_current(std::move(__current._M_current))
2670	{ }
2671
2672	template<__detail::__different_from<basic_const_iterator> _Tp>
2673	requires convertible_to<_Tp, _It>
2674	constexpr
2675	basic_const_iterator(_Tp&& __current)
2676	noexcept(is_nothrow_constructible_v<_It, _Tp>)
2677	: _M_current(std::forward<_Tp>(__current))
2678	{ }
2679
2680	constexpr const _It&
2681	base() const & noexcept
2682	{ return _M_current; }
2683
2684	constexpr _It
2685	base() &&
2686	noexcept(is_nothrow_move_constructible_v<_It>)
2687	{ return std::move(_M_current); }
2688
2689	constexpr __reference
2690	operator() const*
2691	noexcept(noexcept(static_cast<__reference>(*_M_current)))
2692	{ return static_cast<__reference>(*_M_current); }
2693
2694	constexpr const auto*
2695	operator->() const
2696	noexcept(contiguous_iterator<_It> \|\| noexcept(*_M_current))
2697	requires is_lvalue_reference_v<iter_reference_t<_It>>
2698	&& same_as<remove_cvref_t<iter_reference_t<_It>>, value_type>
2699	{
2700	if constexpr (contiguous_iterator<_It>)
2701	return std::to_address(_M_current);
2702	else
2703	return std::__addressof(*_M_current);
2704	}
2705
2706	constexpr basic_const_iterator&
2707	operator++()
2708	noexcept(noexcept(++_M_current))
2709	{
2710	++_M_current;
2711	return *this;
2712	}
2713
2714	constexpr void
2715	operator++(int)
2716	noexcept(noexcept(++_M_current))
2717	{ ++_M_current; }
2718
2719	constexpr basic_const_iterator
2720	operator++(int)
2721	noexcept(noexcept(++*this) && is_nothrow_copy_constructible_v<basic_const_iterator>)
2722	requires forward_iterator<_It>
2723	{
2724	auto __tmp = *this;
2725	++*this;
2726	return __tmp;
2727	}
2728
2729	constexpr basic_const_iterator&
2730	operator--()
2731	noexcept(noexcept(--_M_current))
2732	requires bidirectional_iterator<_It>
2733	{
2734	--_M_current;
2735	return *this;
2736	}
2737
2738	constexpr basic_const_iterator
2739	operator--(int)
2740	noexcept(noexcept(--*this) && is_nothrow_copy_constructible_v<basic_const_iterator>)
2741	requires bidirectional_iterator<_It>
2742	{
2743	auto __tmp = *this;
2744	--*this;
2745	return __tmp;
2746	}
2747
2748	constexpr basic_const_iterator&
2749	operator+=(difference_type __n)
2750	noexcept(noexcept(_M_current += __n))
2751	requires random_access_iterator<_It>
2752	{
2753	_M_current += __n;
2754	return *this;
2755	}
2756
2757	constexpr basic_const_iterator&
2758	operator-=(difference_type __n)
2759	noexcept(noexcept(_M_current -= __n))
2760	requires random_access_iterator<_It>
2761	{
2762	_M_current -= __n;
2763	return *this;
2764	}
2765
2766	constexpr __reference
2767	operator[](difference_type __n) const
2768	noexcept(noexcept(static_cast<__reference>(_M_current[__n])))
2769	requires random_access_iterator<_It>
2770	{ return static_cast<__reference>(_M_current[__n]); }
2771
2772	template<sentinel_for<_It> _Sent>
2773	constexpr bool
2774	operator==(const _Sent& __s) const
2775	noexcept(noexcept(_M_current == __s))
2776	{ return _M_current == __s; }
2777
2778	template<__detail::__not_a_const_iterator _CIt>
2779	requires __detail::__constant_iterator<_CIt> && convertible_to<_It, _CIt>
2780	constexpr
2781	operator _CIt() const&
2782	{ return _M_current; }
2783
2784	template<__detail::__not_a_const_iterator _CIt>
2785	requires __detail::__constant_iterator<_CIt> && convertible_to<_It, _CIt>
2786	constexpr
2787	operator _CIt() &&
2788	{ return std::move(_M_current); }
2789
2790	constexpr bool
2791	operator<(const basic_const_iterator& __y) const
2792	noexcept(noexcept(_M_current < __y._M_current))
2793	requires random_access_iterator<_It>
2794	{ return _M_current < __y._M_current; }
2795
2796	constexpr bool
2797	operator>(const basic_const_iterator& __y) const
2798	noexcept(noexcept(_M_current > __y._M_current))
2799	requires random_access_iterator<_It>
2800	{ return _M_current > __y._M_current; }
2801
2802	constexpr bool
2803	operator<=(const basic_const_iterator& __y) const
2804	noexcept(noexcept(_M_current <= __y._M_current))
2805	requires random_access_iterator<_It>
2806	{ return _M_current <= __y._M_current; }
2807
2808	constexpr bool
2809	operator>=(const basic_const_iterator& __y) const
2810	noexcept(noexcept(_M_current >= __y._M_current))
2811	requires random_access_iterator<_It>
2812	{ return _M_current >= __y._M_current; }
2813
2814	constexpr auto
2815	operator<=>(const basic_const_iterator& __y) const
2816	noexcept(noexcept(_M_current <=> __y._M_current))
2817	requires random_access_iterator<_It> && three_way_comparable<_It>
2818	{ return _M_current <=> __y._M_current; }
2819
2820	template<__detail::__different_from<basic_const_iterator> _It2>
2821	constexpr bool
2822	operator<(const _It2& __y) const
2823	noexcept(noexcept(_M_current < __y))
2824	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2825	{ return _M_current < __y; }
2826
2827	template<__detail::__different_from<basic_const_iterator> _It2>
2828	constexpr bool
2829	operator>(const _It2& __y) const
2830	noexcept(noexcept(_M_current > __y))
2831	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2832	{ return _M_current > __y; }
2833
2834	template<__detail::__different_from<basic_const_iterator> _It2>
2835	constexpr bool
2836	operator<=(const _It2& __y) const
2837	noexcept(noexcept(_M_current <= __y))
2838	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2839	{ return _M_current <= __y; }
2840
2841	template<__detail::__different_from<basic_const_iterator> _It2>
2842	constexpr bool
2843	operator>=(const _It2& __y) const
2844	noexcept(noexcept(_M_current >= __y))
2845	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2846	{ return _M_current >= __y; }
2847
2848	template<__detail::__different_from<basic_const_iterator> _It2>
2849	constexpr auto
2850	operator<=>(const _It2& __y) const
2851	noexcept(noexcept(_M_current <=> __y))
2852	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2853	&& three_way_comparable_with<_It, _It2>
2854	{ return _M_current <=> __y; }
2855
2856	template<__detail::__not_a_const_iterator _It2>
2857	friend constexpr bool
2858	operator<(const _It2& __x, const basic_const_iterator& __y)
2859	noexcept(noexcept(__x < __y._M_current))
2860	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2861	{ return __x < __y._M_current; }
2862
2863	template<__detail::__not_a_const_iterator _It2>
2864	friend constexpr bool
2865	operator>(const _It2& __x, const basic_const_iterator& __y)
2866	noexcept(noexcept(__x > __y._M_current))
2867	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2868	{ return __x > __y._M_current; }
2869
2870	template<__detail::__not_a_const_iterator _It2>
2871	friend constexpr bool
2872	operator<=(const _It2& __x, const basic_const_iterator& __y)
2873	noexcept(noexcept(__x <= __y._M_current))
2874	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2875	{ return __x <= __y._M_current; }
2876
2877	template<__detail::__not_a_const_iterator _It2>
2878	friend constexpr bool
2879	operator>=(const _It2& __x, const basic_const_iterator& __y)
2880	noexcept(noexcept(__x >= __y._M_current))
2881	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2882	{ return __x >= __y._M_current; }
2883
2884	friend constexpr basic_const_iterator
2885	operator+(const basic_const_iterator& __i, difference_type __n)
2886	noexcept(noexcept(basic_const_iterator(__i._M_current + __n)))
2887	requires random_access_iterator<_It>
2888	{ return basic_const_iterator(__i._M_current + __n); }
2889
2890	friend constexpr basic_const_iterator
2891	operator+(difference_type __n, const basic_const_iterator& __i)
2892	noexcept(noexcept(basic_const_iterator(__i._M_current + __n)))
2893	requires random_access_iterator<_It>
2894	{ return basic_const_iterator(__i._M_current + __n); }
2895
2896	friend constexpr basic_const_iterator
2897	operator-(const basic_const_iterator& __i, difference_type __n)
2898	noexcept(noexcept(basic_const_iterator(__i._M_current - __n)))
2899	requires random_access_iterator<_It>
2900	{ return basic_const_iterator(__i._M_current - __n); }
2901
2902	template<sized_sentinel_for<_It> _Sent>
2903	constexpr difference_type
2904	operator-(const _Sent& __y) const
2905	noexcept(noexcept(_M_current - __y))
2906	{ return _M_current - __y; }
2907
2908	template<__detail::__not_a_const_iterator _Sent>
2909	requires sized_sentinel_for<_Sent, _It>
2910	friend constexpr difference_type
2911	operator-(const _Sent& __x, const basic_const_iterator& __y)
2912	noexcept(noexcept(__x - __y._M_current))
2913	{ return __x - __y._M_current; }
2914
2915	friend constexpr __rvalue_reference
2916	iter_move(const basic_const_iterator& __i)
2917	noexcept(noexcept(static_cast<__rvalue_reference>(ranges::iter_move(__i._M_current))))
2918	{ return static_cast<__rvalue_reference>(ranges::iter_move(__i._M_current)); }
2919	};
2920
2921	template<typename _Tp, common_with<_Tp> _Up>
2922	requires input_iterator<common_type_t<_Tp, _Up>>
2923	struct common_type<basic_const_iterator<_Tp>, _Up>
2924	{ using type = basic_const_iterator<common_type_t<_Tp, _Up>>; };
2925
2926	template<typename _Tp, common_with<_Tp> _Up>
2927	requires input_iterator<common_type_t<_Tp, _Up>>
2928	struct common_type<_Up, basic_const_iterator<_Tp>>
2929	{ using type = basic_const_iterator<common_type_t<_Tp, _Up>>; };
2930
2931	template<typename _Tp, common_with<_Tp> _Up>
2932	requires input_iterator<common_type_t<_Tp, _Up>>
2933	struct common_type<basic_const_iterator<_Tp>, basic_const_iterator<_Up>>
2934	{ using type = basic_const_iterator<common_type_t<_Tp, _Up>>; };
2935
2936	template<input_iterator _It>
2937	constexpr const_iterator<_It>
2938	make_const_iterator(_It __it)
2939	noexcept(is_nothrow_convertible_v<_It, const_iterator<_It>>)
2940	{ return __it; }
2941
2942	template<semiregular _Sent>
2943	constexpr const_sentinel<_Sent>
2944	make_const_sentinel(_Sent __s)
2945	noexcept(is_nothrow_convertible_v<_Sent, const_sentinel<_Sent>>)
2946	{ return __s; }
2947	#endif // C++23
2948	#endif // C++20
2949
2950	/// @} group iterators
2951
2952	template<typename _Iterator>
2953	_GLIBCXX20_CONSTEXPR
2954	auto
2955	__niter_base(move_iterator<_Iterator> __it)
2956	-> decltype(make_move_iterator(__niter_base(__it.base())))
2957	{ return make_move_iterator(__niter_base(__it.base())); }
2958
2959	template<typename _Iterator>
2960	struct __is_move_iterator<move_iterator<_Iterator> >
2961	{
2962	enum { __value = `1` };
2963	typedef __true_type __type;
2964	};
2965
2966	template<typename _Iterator>
2967	_GLIBCXX20_CONSTEXPR
2968	auto
2969	__miter_base(move_iterator<_Iterator> __it)
2970	-> decltype(__miter_base(__it.base()))
2971	{ return __miter_base(__it.base()); }
2972
2973	#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2974	#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2975	std::__make_move_if_noexcept_iterator(_Iter)
2976	#else
2977	#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2978	#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2979	#endif // C++11
2980
2981	#if __cpp_deduction_guides >= 201606
2982	// These helper traits are used for deduction guides
2983	// of associative containers.
2984	template<typename _InputIterator>
2985	using __iter_key_t = remove_const_t<
2986	#if __glibcxx_tuple_like // >= C++23
2987	tuple_element_t<`0`, typename iterator_traits<_InputIterator>::value_type>>;
2988	#else
2989	typename iterator_traits<_InputIterator>::value_type::first_type>;
2990	#endif
2991
2992	template<typename _InputIterator>
2993	using __iter_val_t
2994	#if __glibcxx_tuple_like // >= C++23
2995	= tuple_element_t<`1`, typename iterator_traits<_InputIterator>::value_type>;
2996	#else
2997	= typename iterator_traits<_InputIterator>::value_type::second_type;
2998	#endif
2999
3000	template<typename _T1, typename _T2>
3001	struct pair;
3002
3003	template<typename _InputIterator>
3004	using __iter_to_alloc_t
3005	= pair<const __iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>>;
3006	#endif // __cpp_deduction_guides
3007
3008	_GLIBCXX_END_NAMESPACE_VERSION
3009	} // namespace
3010
3011	#ifdef _GLIBCXX_DEBUG
3012	# include <debug/stl_iterator.h>
3013	#endif
3014
3015	#endif
3016

Browse the source code of include/c++/14.1.1/bits/stl_iterator.h