stl_iterator.h source code [include/c++/14/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	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1826	// 3736. move_iterator missing disable_sized_sentinel_for specialization
1827	template<typename _Iterator1, typename _Iterator2>
1828	requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
1829	inline constexpr bool
1830	disable_sized_sentinel_for<move_iterator<_Iterator1>,
1831	move_iterator<_Iterator2>> = true;
1832
1833	// [iterators.common] Common iterators
1834
1835	namespace __detail
1836	{
1837	template<typename _It>
1838	concept __common_iter_has_arrow = indirectly_readable<const _It>
1839	&& (requires(const _It& __it) { __it.operator->(); }
1840	\|\| is_reference_v<iter_reference_t<_It>>
1841	\|\| constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1842
1843	template<typename _It>
1844	concept __common_iter_use_postfix_proxy
1845	= (!requires (_It& __i) { { *__i++ } -> __can_reference; })
1846	&& constructible_from<iter_value_t<_It>, iter_reference_t<_It>>
1847	&& move_constructible<iter_value_t<_It>>;
1848	} // namespace __detail
1849
1850	/// An iterator/sentinel adaptor for representing a non-common range.
1851	template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1852	requires (!same_as<_It, _Sent>) && copyable<_It>
1853	class common_iterator
1854	{
1855	template<typename _Tp, typename _Up>
1856	static constexpr bool
1857	_S_noexcept1()
1858	{
1859	if constexpr (is_trivially_default_constructible_v<_Tp>)
1860	return is_nothrow_assignable_v<_Tp&, _Up>;
1861	else
1862	return is_nothrow_constructible_v<_Tp, _Up>;
1863	}
1864
1865	template<typename _It2, typename _Sent2>
1866	static constexpr bool
1867	_S_noexcept()
1868	{ return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1869
1870	class __arrow_proxy
1871	{
1872	iter_value_t<_It> _M_keep;
1873
1874	constexpr
1875	__arrow_proxy(iter_reference_t<_It>&& __x)
1876	: _M_keep(std::move(__x)) { }
1877
1878	friend class common_iterator;
1879
1880	public:
1881	constexpr const iter_value_t<_It>*
1882	operator->() const noexcept
1883	{ return std::__addressof(_M_keep); }
1884	};
1885
1886	class __postfix_proxy
1887	{
1888	iter_value_t<_It> _M_keep;
1889
1890	constexpr
1891	__postfix_proxy(iter_reference_t<_It>&& __x)
1892	: _M_keep(std::forward<iter_reference_t<_It>>(__x)) { }
1893
1894	friend class common_iterator;
1895
1896	public:
1897	constexpr const iter_value_t<_It>&
1898	operator() const* noexcept
1899	{ return _M_keep; }
1900	};
1901
1902	public:
1903	constexpr
1904	common_iterator()
1905	noexcept(is_nothrow_default_constructible_v<_It>)
1906	requires default_initializable<_It>
1907	: _M_it(), _M_index(`0`)
1908	{ }
1909
1910	constexpr
1911	common_iterator(_It __i)
1912	noexcept(is_nothrow_move_constructible_v<_It>)
1913	: _M_it(std::move(__i)), _M_index(`0`)
1914	{ }
1915
1916	constexpr
1917	common_iterator(_Sent __s)
1918	noexcept(is_nothrow_move_constructible_v<_Sent>)
1919	: _M_sent(std::move(__s)), _M_index(`1`)
1920	{ }
1921
1922	template<typename _It2, typename _Sent2>
1923	requires convertible_to<const _It2&, _It>
1924	&& convertible_to<const _Sent2&, _Sent>
1925	constexpr
1926	common_iterator(const common_iterator<_It2, _Sent2>& __x)
1927	noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1928	: _M_valueless(), _M_index(__x._M_index)
1929	{
1930	__glibcxx_assert(__x._M_has_value());
1931	if (_M_index == `0`)
1932	{
1933	if constexpr (is_trivially_default_constructible_v<_It>)
1934	_M_it = std::move(__x._M_it);
1935	else
1936	std::construct_at(std::__addressof(_M_it), __x._M_it);
1937	}
1938	else if (_M_index == `1`)
1939	{
1940	if constexpr (is_trivially_default_constructible_v<_Sent>)
1941	_M_sent = std::move(__x._M_sent);
1942	else
1943	std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1944	}
1945	}
1946
1947	common_iterator(const common_iterator&) = default;
1948
1949	constexpr
1950	common_iterator(const common_iterator& __x)
1951	noexcept(_S_noexcept<const _It&, const _Sent&>())
1952	requires (!is_trivially_copyable_v<_It> \|\| !is_trivially_copyable_v<_Sent>)
1953	: _M_valueless(), _M_index(__x._M_index)
1954	{
1955	if (_M_index == `0`)
1956	{
1957	if constexpr (is_trivially_default_constructible_v<_It>)
1958	_M_it = __x._M_it;
1959	else
1960	std::construct_at(std::__addressof(_M_it), __x._M_it);
1961	}
1962	else if (_M_index == `1`)
1963	{
1964	if constexpr (is_trivially_default_constructible_v<_Sent>)
1965	_M_sent = __x._M_sent;
1966	else
1967	std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1968	}
1969	}
1970
1971	common_iterator(common_iterator&&) = default;
1972
1973	constexpr
1974	common_iterator(common_iterator&& __x)
1975	noexcept(_S_noexcept<_It, _Sent>())
1976	requires (!is_trivially_copyable_v<_It> \|\| !is_trivially_copyable_v<_Sent>)
1977	: _M_valueless(), _M_index(__x._M_index)
1978	{
1979	if (_M_index == `0`)
1980	{
1981	if constexpr (is_trivially_default_constructible_v<_It>)
1982	_M_it = std::move(__x._M_it);
1983	else
1984	std::construct_at(std::__addressof(_M_it), std::move(__x._M_it));
1985	}
1986	else if (_M_index == `1`)
1987	{
1988	if constexpr (is_trivially_default_constructible_v<_Sent>)
1989	_M_sent = std::move(__x._M_sent);
1990	else
1991	std::construct_at(std::__addressof(_M_sent),
1992	std::move(__x._M_sent));
1993	}
1994	}
1995
1996	constexpr common_iterator&
1997	operator=(const common_iterator&) = default;
1998
1999	constexpr common_iterator&
2000	operator=(const common_iterator& __x)
2001	noexcept(is_nothrow_copy_assignable_v<_It>
2002	&& is_nothrow_copy_assignable_v<_Sent>
2003	&& is_nothrow_copy_constructible_v<_It>
2004	&& is_nothrow_copy_constructible_v<_Sent>)
2005	requires (!is_trivially_copy_assignable_v<_It>
2006	\|\| !is_trivially_copy_assignable_v<_Sent>)
2007	{
2008	_M_assign(__x);
2009	return *this;
2010	}
2011
2012	constexpr common_iterator&
2013	operator=(common_iterator&&) = default;
2014
2015	constexpr common_iterator&
2016	operator=(common_iterator&& __x)
2017	noexcept(is_nothrow_move_assignable_v<_It>
2018	&& is_nothrow_move_assignable_v<_Sent>
2019	&& is_nothrow_move_constructible_v<_It>
2020	&& is_nothrow_move_constructible_v<_Sent>)
2021	requires (!is_trivially_move_assignable_v<_It>
2022	\|\| !is_trivially_move_assignable_v<_Sent>)
2023	{
2024	_M_assign(std::move(__x));
2025	return *this;
2026	}
2027
2028	template<typename _It2, typename _Sent2>
2029	requires convertible_to<const _It2&, _It>
2030	&& convertible_to<const _Sent2&, _Sent>
2031	&& assignable_from<_It&, const _It2&>
2032	&& assignable_from<_Sent&, const _Sent2&>
2033	constexpr common_iterator&
2034	operator=(const common_iterator<_It2, _Sent2>& __x)
2035	noexcept(is_nothrow_constructible_v<_It, const _It2&>
2036	&& is_nothrow_constructible_v<_Sent, const _Sent2&>
2037	&& is_nothrow_assignable_v<_It&, const _It2&>
2038	&& is_nothrow_assignable_v<_Sent&, const _Sent2&>)
2039	{
2040	__glibcxx_assert(__x._M_has_value());
2041	_M_assign(__x);
2042	return *this;
2043	}
2044
2045	#if __cpp_concepts >= 202002L // Constrained special member functions
2046	~common_iterator() = default;
2047
2048	constexpr
2049	~common_iterator()
2050	requires (!is_trivially_destructible_v<_It>
2051	\|\| !is_trivially_destructible_v<_Sent>)
2052	#else
2053	constexpr
2054	~common_iterator()
2055	#endif
2056	{
2057	if (_M_index == `0`)
2058	_M_it.~_It();
2059	else if (_M_index == `1`)
2060	_M_sent.~_Sent();
2061	}
2062
2063	[[nodiscard]]
2064	constexpr decltype(auto)
2065	operator*()
2066	{
2067	__glibcxx_assert(_M_index == `0`);
2068	return *_M_it;
2069	}
2070
2071	[[nodiscard]]
2072	constexpr decltype(auto)
2073	operator() const* requires __detail::__dereferenceable<const _It>
2074	{
2075	__glibcxx_assert(_M_index == `0`);
2076	return *_M_it;
2077	}
2078
2079	[[nodiscard]]
2080	constexpr auto
2081	operator->() const requires __detail::__common_iter_has_arrow<_It>
2082	{
2083	__glibcxx_assert(_M_index == `0`);
2084	if constexpr (is_pointer_v<_It> \|\| requires { _M_it.operator->(); })
2085	return _M_it;
2086	else if constexpr (is_reference_v<iter_reference_t<_It>>)
2087	{
2088	auto&& __tmp = *_M_it;
2089	return std::__addressof(__tmp);
2090	}
2091	else
2092	return __arrow_proxy{*_M_it};
2093	}
2094
2095	constexpr common_iterator&
2096	operator++()
2097	{
2098	__glibcxx_assert(_M_index == `0`);
2099	++_M_it;
2100	return *this;
2101	}
2102
2103	constexpr decltype(auto)
2104	operator++(int)
2105	{
2106	__glibcxx_assert(_M_index == `0`);
2107	if constexpr (forward_iterator<_It>)
2108	{
2109	common_iterator __tmp = *this;
2110	++*this;
2111	return __tmp;
2112	}
2113	else if constexpr (!__detail::__common_iter_use_postfix_proxy<_It>)
2114	return _M_it++;
2115	else
2116	{
2117	__postfix_proxy __p(**this);
2118	++*this;
2119	return __p;
2120	}
2121	}
2122
2123	template<typename _It2, sentinel_for<_It> _Sent2>
2124	requires sentinel_for<_Sent, _It2>
2125	friend constexpr bool
2126	operator== [[nodiscard]] (const common_iterator& __x,
2127	const common_iterator<_It2, _Sent2>& __y)
2128	{
2129	switch(__x._M_index << `2` \| __y._M_index)
2130	{
2131	case `0b0000`:
2132	case `0b0101`:
2133	return true;
2134	case `0b0001`:
2135	return __x._M_it == __y._M_sent;
2136	case `0b0100`:
2137	return __x._M_sent == __y._M_it;
2138	default:
2139	__glibcxx_assert(__x._M_has_value());
2140	__glibcxx_assert(__y._M_has_value());
2141	__builtin_unreachable();
2142	}
2143	}
2144
2145	template<typename _It2, sentinel_for<_It> _Sent2>
2146	requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
2147	friend constexpr bool
2148	operator== [[nodiscard]] (const common_iterator& __x,
2149	const common_iterator<_It2, _Sent2>& __y)
2150	{
2151	switch(__x._M_index << `2` \| __y._M_index)
2152	{
2153	case `0b0101`:
2154	return true;
2155	case `0b0000`:
2156	return __x._M_it == __y._M_it;
2157	case `0b0001`:
2158	return __x._M_it == __y._M_sent;
2159	case `0b0100`:
2160	return __x._M_sent == __y._M_it;
2161	default:
2162	__glibcxx_assert(__x._M_has_value());
2163	__glibcxx_assert(__y._M_has_value());
2164	__builtin_unreachable();
2165	}
2166	}
2167
2168	template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
2169	requires sized_sentinel_for<_Sent, _It2>
2170	friend constexpr iter_difference_t<_It2>
2171	operator- [[nodiscard]] (const common_iterator& __x,
2172	const common_iterator<_It2, _Sent2>& __y)
2173	{
2174	switch(__x._M_index << `2` \| __y._M_index)
2175	{
2176	case `0b0101`:
2177	return `0`;
2178	case `0b0000`:
2179	return __x._M_it - __y._M_it;
2180	case `0b0001`:
2181	return __x._M_it - __y._M_sent;
2182	case `0b0100`:
2183	return __x._M_sent - __y._M_it;
2184	default:
2185	__glibcxx_assert(__x._M_has_value());
2186	__glibcxx_assert(__y._M_has_value());
2187	__builtin_unreachable();
2188	}
2189	}
2190
2191	[[nodiscard]]
2192	friend constexpr iter_rvalue_reference_t<_It>
2193	iter_move(const common_iterator& __i)
2194	noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
2195	requires input_iterator<_It>
2196	{
2197	__glibcxx_assert(__i._M_index == `0`);
2198	return ranges::iter_move(__i._M_it);
2199	}
2200
2201	template<indirectly_swappable<_It> _It2, typename _Sent2>
2202	friend constexpr void
2203	iter_swap(const common_iterator& __x,
2204	const common_iterator<_It2, _Sent2>& __y)
2205	noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
2206	std::declval<const _It2&>())))
2207	{
2208	__glibcxx_assert(__x._M_index == `0`);
2209	__glibcxx_assert(__y._M_index == `0`);
2210	return ranges::iter_swap(__x._M_it, __y._M_it);
2211	}
2212
2213	private:
2214	template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
2215	requires (!same_as<_It2, _Sent2>) && copyable<_It2>
2216	friend class common_iterator;
2217
2218	constexpr bool
2219	_M_has_value() const noexcept { return _M_index != _S_valueless; }
2220
2221	template<typename _CIt>
2222	constexpr void
2223	_M_assign(_CIt&& __x)
2224	{
2225	if (_M_index == __x._M_index)
2226	{
2227	if (_M_index == `0`)
2228	_M_it = std::forward<_CIt>(__x)._M_it;
2229	else if (_M_index == `1`)
2230	_M_sent = std::forward<_CIt>(__x)._M_sent;
2231	}
2232	else
2233	{
2234	if (_M_index == `0`)
2235	_M_it.~_It();
2236	else if (_M_index == `1`)
2237	_M_sent.~_Sent();
2238	_M_index = _S_valueless;
2239
2240	if (__x._M_index == `0`)
2241	std::construct_at(std::__addressof(_M_it),
2242	std::forward<_CIt>(__x)._M_it);
2243	else if (__x._M_index == `1`)
2244	std::construct_at(std::__addressof(_M_sent),
2245	std::forward<_CIt>(__x)._M_sent);
2246	_M_index = __x._M_index;
2247	}
2248	}
2249
2250	union
2251	{
2252	_It _M_it;
2253	_Sent _M_sent;
2254	unsigned char _M_valueless;
2255	};
2256	unsigned char _M_index; // 0 == _M_it, 1 == _M_sent, 2 == valueless
2257
2258	static constexpr unsigned char _S_valueless{`2`};
2259	};
2260
2261	template<typename _It, typename _Sent>
2262	struct incrementable_traits<common_iterator<_It, _Sent>>
2263	{
2264	using difference_type = iter_difference_t<_It>;
2265	};
2266
2267	template<input_iterator _It, typename _Sent>
2268	struct iterator_traits<common_iterator<_It, _Sent>>
2269	{
2270	private:
2271	template<typename _Iter>
2272	struct __ptr
2273	{
2274	using type = void;
2275	};
2276
2277	template<typename _Iter>
2278	requires __detail::__common_iter_has_arrow<_Iter>
2279	struct __ptr<_Iter>
2280	{
2281	using _CIter = common_iterator<_Iter, _Sent>;
2282	using type = decltype(std::declval<const _CIter&>().operator->());
2283	};
2284
2285	static auto
2286	_S_iter_cat()
2287	{
2288	if constexpr (requires { requires derived_from<__iter_category_t<_It>,
2289	forward_iterator_tag>; })
2290	return forward_iterator_tag{};
2291	else
2292	return input_iterator_tag{};
2293	}
2294
2295	public:
2296	using iterator_concept = __conditional_t<forward_iterator<_It>,
2297	forward_iterator_tag,
2298	input_iterator_tag>;
2299	using iterator_category = decltype(_S_iter_cat());
2300	using value_type = iter_value_t<_It>;
2301	using difference_type = iter_difference_t<_It>;
2302	using pointer = typename __ptr<_It>::type;
2303	using reference = iter_reference_t<_It>;
2304	};
2305
2306	// [iterators.counted] Counted iterators
2307
2308	namespace __detail
2309	{
2310	template<typename _It>
2311	struct __counted_iter_value_type
2312	{ };
2313
2314	template<indirectly_readable _It>
2315	struct __counted_iter_value_type<_It>
2316	{ using value_type = iter_value_t<_It>; };
2317
2318	template<typename _It>
2319	struct __counted_iter_concept
2320	{ };
2321
2322	template<typename _It>
2323	requires requires { typename _It::iterator_concept; }
2324	struct __counted_iter_concept<_It>
2325	{ using iterator_concept = typename _It::iterator_concept; };
2326
2327	template<typename _It>
2328	struct __counted_iter_cat
2329	{ };
2330
2331	template<typename _It>
2332	requires requires { typename _It::iterator_category; }
2333	struct __counted_iter_cat<_It>
2334	{ using iterator_category = typename _It::iterator_category; };
2335	}
2336
2337	/// An iterator adaptor that keeps track of the distance to the end.
2338	template<input_or_output_iterator _It>
2339	class counted_iterator
2340	: public __detail::__counted_iter_value_type<_It>,
2341	public __detail::__counted_iter_concept<_It>,
2342	public __detail::__counted_iter_cat<_It>
2343	{
2344	public:
2345	using iterator_type = _It;
2346	// value_type defined in __counted_iter_value_type
2347	using difference_type = iter_difference_t<_It>;
2348	// iterator_concept defined in __counted_iter_concept
2349	// iterator_category defined in __counted_iter_cat
2350
2351	constexpr counted_iterator() requires default_initializable<_It> = default;
2352
2353	constexpr
2354	counted_iterator(_It __i, iter_difference_t<_It> __n)
2355	: _M_current(std::move(__i)), _M_length(__n)
2356	{ __glibcxx_assert(__n >= `0`); }
2357
2358	template<typename _It2>
2359	requires convertible_to<const _It2&, _It>
2360	constexpr
2361	counted_iterator(const counted_iterator<_It2>& __x)
2362	: _M_current(__x._M_current), _M_length(__x._M_length)
2363	{ }
2364
2365	template<typename _It2>
2366	requires assignable_from<_It&, const _It2&>
2367	constexpr counted_iterator&
2368	operator=(const counted_iterator<_It2>& __x)
2369	{
2370	_M_current = __x._M_current;
2371	_M_length = __x._M_length;
2372	return *this;
2373	}
2374
2375	[[nodiscard]]
2376	constexpr const _It&
2377	base() const & noexcept
2378	{ return _M_current; }
2379
2380	[[nodiscard]]
2381	constexpr _It
2382	base() &&
2383	noexcept(is_nothrow_move_constructible_v<_It>)
2384	{ return std::move(_M_current); }
2385
2386	[[nodiscard]]
2387	constexpr iter_difference_t<_It>
2388	count() const noexcept { return _M_length; }
2389
2390	[[nodiscard]]
2391	constexpr decltype(auto)
2392	operator*()
2393	noexcept(noexcept(*_M_current))
2394	{
2395	__glibcxx_assert( _M_length > `0` );
2396	return *_M_current;
2397	}
2398
2399	[[nodiscard]]
2400	constexpr decltype(auto)
2401	operator() const*
2402	noexcept(noexcept(*_M_current))
2403	requires __detail::__dereferenceable<const _It>
2404	{
2405	__glibcxx_assert( _M_length > `0` );
2406	return *_M_current;
2407	}
2408
2409	[[nodiscard]]
2410	constexpr auto
2411	operator->() const noexcept
2412	requires contiguous_iterator<_It>
2413	{ return std::to_address(_M_current); }
2414
2415	constexpr counted_iterator&
2416	operator++()
2417	{
2418	__glibcxx_assert(_M_length > `0`);
2419	++_M_current;
2420	--_M_length;
2421	return *this;
2422	}
2423
2424	constexpr decltype(auto)
2425	operator++(int)
2426	{
2427	__glibcxx_assert(_M_length > `0`);
2428	--_M_length;
2429	__try
2430	{
2431	return _M_current++;
2432	} __catch(...) {
2433	++_M_length;
2434	__throw_exception_again;
2435	}
2436	}
2437
2438	constexpr counted_iterator
2439	operator++(int) requires forward_iterator<_It>
2440	{
2441	auto __tmp = *this;
2442	++*this;
2443	return __tmp;
2444	}
2445
2446	constexpr counted_iterator&
2447	operator--() requires bidirectional_iterator<_It>
2448	{
2449	--_M_current;
2450	++_M_length;
2451	return *this;
2452	}
2453
2454	constexpr counted_iterator
2455	operator--(int) requires bidirectional_iterator<_It>
2456	{
2457	auto __tmp = *this;
2458	--*this;
2459	return __tmp;
2460	}
2461
2462	[[nodiscard]]
2463	constexpr counted_iterator
2464	operator+(iter_difference_t<_It> __n) const
2465	requires random_access_iterator<_It>
2466	{ return counted_iterator(_M_current + __n, _M_length - __n); }
2467
2468	[[nodiscard]]
2469	friend constexpr counted_iterator
2470	operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
2471	requires random_access_iterator<_It>
2472	{ return __x + __n; }
2473
2474	constexpr counted_iterator&
2475	operator+=(iter_difference_t<_It> __n)
2476	requires random_access_iterator<_It>
2477	{
2478	__glibcxx_assert(__n <= _M_length);
2479	_M_current += __n;
2480	_M_length -= __n;
2481	return *this;
2482	}
2483
2484	[[nodiscard]]
2485	constexpr counted_iterator
2486	operator-(iter_difference_t<_It> __n) const
2487	requires random_access_iterator<_It>
2488	{ return counted_iterator(_M_current - __n, _M_length + __n); }
2489
2490	template<common_with<_It> _It2>
2491	[[nodiscard]]
2492	friend constexpr iter_difference_t<_It2>
2493	operator-(const counted_iterator& __x,
2494	const counted_iterator<_It2>& __y)
2495	{ return __y._M_length - __x._M_length; }
2496
2497	[[nodiscard]]
2498	friend constexpr iter_difference_t<_It>
2499	operator-(const counted_iterator& __x, default_sentinel_t)
2500	{ return -__x._M_length; }
2501
2502	[[nodiscard]]
2503	friend constexpr iter_difference_t<_It>
2504	operator-(default_sentinel_t, const counted_iterator& __y)
2505	{ return __y._M_length; }
2506
2507	constexpr counted_iterator&
2508	operator-=(iter_difference_t<_It> __n)
2509	requires random_access_iterator<_It>
2510	{
2511	__glibcxx_assert(-__n <= _M_length);
2512	_M_current -= __n;
2513	_M_length += __n;
2514	return *this;
2515	}
2516
2517	[[nodiscard]]
2518	constexpr decltype(auto)
2519	operator[](iter_difference_t<_It> __n) const
2520	noexcept(noexcept(_M_current[__n]))
2521	requires random_access_iterator<_It>
2522	{
2523	__glibcxx_assert(__n < _M_length);
2524	return _M_current[__n];
2525	}
2526
2527	template<common_with<_It> _It2>
2528	[[nodiscard]]
2529	friend constexpr bool
2530	operator==(const counted_iterator& __x,
2531	const counted_iterator<_It2>& __y)
2532	{ return __x._M_length == __y._M_length; }
2533
2534	[[nodiscard]]
2535	friend constexpr bool
2536	operator==(const counted_iterator& __x, default_sentinel_t)
2537	{ return __x._M_length == `0`; }
2538
2539	template<common_with<_It> _It2>
2540	[[nodiscard]]
2541	friend constexpr strong_ordering
2542	operator<=>(const counted_iterator& __x,
2543	const counted_iterator<_It2>& __y)
2544	{ return __y._M_length <=> __x._M_length; }
2545
2546	[[nodiscard]]
2547	friend constexpr iter_rvalue_reference_t<_It>
2548	iter_move(const counted_iterator& __i)
2549	noexcept(noexcept(ranges::iter_move(__i._M_current)))
2550	requires input_iterator<_It>
2551	{
2552	__glibcxx_assert( __i._M_length > `0` );
2553	return ranges::iter_move(__i._M_current);
2554	}
2555
2556	template<indirectly_swappable<_It> _It2>
2557	friend constexpr void
2558	iter_swap(const counted_iterator& __x,
2559	const counted_iterator<_It2>& __y)
2560	noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2561	{
2562	__glibcxx_assert( __x._M_length > `0` && __y._M_length > `0` );
2563	ranges::iter_swap(__x._M_current, __y._M_current);
2564	}
2565
2566	private:
2567	template<input_or_output_iterator _It2> friend class counted_iterator;
2568
2569	_It _M_current = _It();
2570	iter_difference_t<_It> _M_length = `0`;
2571	};
2572
2573	template<input_iterator _It>
2574	requires same_as<__detail::__iter_traits<_It>, iterator_traits<_It>>
2575	struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2576	{
2577	using pointer = __conditional_t<contiguous_iterator<_It>,
2578	add_pointer_t<iter_reference_t<_It>>,
2579	void>;
2580	};
2581
2582	#if __glibcxx_ranges_as_const // >= C++23
2583	template<indirectly_readable _It>
2584	using iter_const_reference_t
2585	= common_reference_t<const iter_value_t<_It>&&, iter_reference_t<_It>>;
2586
2587	template<input_iterator _It> class basic_const_iterator;
2588
2589	namespace __detail
2590	{
2591	template<typename _It>
2592	concept __constant_iterator = input_iterator<_It>
2593	&& same_as<iter_const_reference_t<_It>, iter_reference_t<_It>>;
2594
2595	template<typename _Tp>
2596	inline constexpr bool __is_const_iterator = false;
2597
2598	template<typename _It>
2599	inline constexpr bool __is_const_iterator<basic_const_iterator<_It>> = true;
2600
2601	template<typename _Tp>
2602	concept __not_a_const_iterator = !__is_const_iterator<_Tp>;
2603
2604	template<indirectly_readable _It>
2605	using __iter_const_rvalue_reference_t
2606	= common_reference_t<const iter_value_t<_It>&&, iter_rvalue_reference_t<_It>>;
2607
2608	template<typename _It>
2609	struct __basic_const_iterator_iter_cat
2610	{ };
2611
2612	template<forward_iterator _It>
2613	struct __basic_const_iterator_iter_cat<_It>
2614	{ using iterator_category = __iter_category_t<_It>; };
2615	} // namespace detail
2616
2617	template<input_iterator _It>
2618	using const_iterator
2619	= __conditional_t<__detail::__constant_iterator<_It>, _It, basic_const_iterator<_It>>;
2620
2621	namespace __detail
2622	{
2623	template<typename _Sent>
2624	struct __const_sentinel
2625	{ using type = _Sent; };
2626
2627	template<input_iterator _Sent>
2628	struct __const_sentinel<_Sent>
2629	{ using type = const_iterator<_Sent>; };
2630	} // namespace __detail
2631
2632	template<semiregular _Sent>
2633	using const_sentinel = typename __detail::__const_sentinel<_Sent>::type;
2634
2635	template<input_iterator _It>
2636	class basic_const_iterator
2637	: public __detail::__basic_const_iterator_iter_cat<_It>
2638	{
2639	_It _M_current = _It();
2640	using __reference = iter_const_reference_t<_It>;
2641	using __rvalue_reference = __detail::__iter_const_rvalue_reference_t<_It>;
2642
2643	static auto
2644	_S_iter_concept()
2645	{
2646	if constexpr (contiguous_iterator<_It>)
2647	return contiguous_iterator_tag{};
2648	else if constexpr (random_access_iterator<_It>)
2649	return random_access_iterator_tag{};
2650	else if constexpr (bidirectional_iterator<_It>)
2651	return bidirectional_iterator_tag{};
2652	else if constexpr (forward_iterator<_It>)
2653	return forward_iterator_tag{};
2654	else
2655	return input_iterator_tag{};
2656	}
2657
2658	template<input_iterator _It2> friend class basic_const_iterator;
2659
2660	public:
2661	using iterator_concept = decltype(_S_iter_concept());
2662	using value_type = iter_value_t<_It>;
2663	using difference_type = iter_difference_t<_It>;
2664
2665	basic_const_iterator() requires default_initializable<_It> = default;
2666
2667	constexpr
2668	basic_const_iterator(_It __current)
2669	noexcept(is_nothrow_move_constructible_v<_It>)
2670	: _M_current(std::move(__current))
2671	{ }
2672
2673	template<convertible_to<_It> _It2>
2674	constexpr
2675	basic_const_iterator(basic_const_iterator<_It2> __current)
2676	noexcept(is_nothrow_constructible_v<_It, _It2>)
2677	: _M_current(std::move(__current._M_current))
2678	{ }
2679
2680	template<__detail::__different_from<basic_const_iterator> _Tp>
2681	requires convertible_to<_Tp, _It>
2682	constexpr
2683	basic_const_iterator(_Tp&& __current)
2684	noexcept(is_nothrow_constructible_v<_It, _Tp>)
2685	: _M_current(std::forward<_Tp>(__current))
2686	{ }
2687
2688	constexpr const _It&
2689	base() const & noexcept
2690	{ return _M_current; }
2691
2692	constexpr _It
2693	base() &&
2694	noexcept(is_nothrow_move_constructible_v<_It>)
2695	{ return std::move(_M_current); }
2696
2697	constexpr __reference
2698	operator() const*
2699	noexcept(noexcept(static_cast<__reference>(*_M_current)))
2700	{ return static_cast<__reference>(*_M_current); }
2701
2702	constexpr const auto*
2703	operator->() const
2704	noexcept(contiguous_iterator<_It> \|\| noexcept(*_M_current))
2705	requires is_lvalue_reference_v<iter_reference_t<_It>>
2706	&& same_as<remove_cvref_t<iter_reference_t<_It>>, value_type>
2707	{
2708	if constexpr (contiguous_iterator<_It>)
2709	return std::to_address(_M_current);
2710	else
2711	return std::__addressof(*_M_current);
2712	}
2713
2714	constexpr basic_const_iterator&
2715	operator++()
2716	noexcept(noexcept(++_M_current))
2717	{
2718	++_M_current;
2719	return *this;
2720	}
2721
2722	constexpr void
2723	operator++(int)
2724	noexcept(noexcept(++_M_current))
2725	{ ++_M_current; }
2726
2727	constexpr basic_const_iterator
2728	operator++(int)
2729	noexcept(noexcept(++*this) && is_nothrow_copy_constructible_v<basic_const_iterator>)
2730	requires forward_iterator<_It>
2731	{
2732	auto __tmp = *this;
2733	++*this;
2734	return __tmp;
2735	}
2736
2737	constexpr basic_const_iterator&
2738	operator--()
2739	noexcept(noexcept(--_M_current))
2740	requires bidirectional_iterator<_It>
2741	{
2742	--_M_current;
2743	return *this;
2744	}
2745
2746	constexpr basic_const_iterator
2747	operator--(int)
2748	noexcept(noexcept(--*this) && is_nothrow_copy_constructible_v<basic_const_iterator>)
2749	requires bidirectional_iterator<_It>
2750	{
2751	auto __tmp = *this;
2752	--*this;
2753	return __tmp;
2754	}
2755
2756	constexpr basic_const_iterator&
2757	operator+=(difference_type __n)
2758	noexcept(noexcept(_M_current += __n))
2759	requires random_access_iterator<_It>
2760	{
2761	_M_current += __n;
2762	return *this;
2763	}
2764
2765	constexpr basic_const_iterator&
2766	operator-=(difference_type __n)
2767	noexcept(noexcept(_M_current -= __n))
2768	requires random_access_iterator<_It>
2769	{
2770	_M_current -= __n;
2771	return *this;
2772	}
2773
2774	constexpr __reference
2775	operator[](difference_type __n) const
2776	noexcept(noexcept(static_cast<__reference>(_M_current[__n])))
2777	requires random_access_iterator<_It>
2778	{ return static_cast<__reference>(_M_current[__n]); }
2779
2780	template<sentinel_for<_It> _Sent>
2781	constexpr bool
2782	operator==(const _Sent& __s) const
2783	noexcept(noexcept(_M_current == __s))
2784	{ return _M_current == __s; }
2785
2786	template<__detail::__not_a_const_iterator _CIt>
2787	requires __detail::__constant_iterator<_CIt> && convertible_to<_It, _CIt>
2788	constexpr
2789	operator _CIt() const&
2790	{ return _M_current; }
2791
2792	template<__detail::__not_a_const_iterator _CIt>
2793	requires __detail::__constant_iterator<_CIt> && convertible_to<_It, _CIt>
2794	constexpr
2795	operator _CIt() &&
2796	{ return std::move(_M_current); }
2797
2798	constexpr bool
2799	operator<(const basic_const_iterator& __y) const
2800	noexcept(noexcept(_M_current < __y._M_current))
2801	requires random_access_iterator<_It>
2802	{ return _M_current < __y._M_current; }
2803
2804	constexpr bool
2805	operator>(const basic_const_iterator& __y) const
2806	noexcept(noexcept(_M_current > __y._M_current))
2807	requires random_access_iterator<_It>
2808	{ return _M_current > __y._M_current; }
2809
2810	constexpr bool
2811	operator<=(const basic_const_iterator& __y) const
2812	noexcept(noexcept(_M_current <= __y._M_current))
2813	requires random_access_iterator<_It>
2814	{ return _M_current <= __y._M_current; }
2815
2816	constexpr bool
2817	operator>=(const basic_const_iterator& __y) const
2818	noexcept(noexcept(_M_current >= __y._M_current))
2819	requires random_access_iterator<_It>
2820	{ return _M_current >= __y._M_current; }
2821
2822	constexpr auto
2823	operator<=>(const basic_const_iterator& __y) const
2824	noexcept(noexcept(_M_current <=> __y._M_current))
2825	requires random_access_iterator<_It> && three_way_comparable<_It>
2826	{ return _M_current <=> __y._M_current; }
2827
2828	template<__detail::__different_from<basic_const_iterator> _It2>
2829	constexpr bool
2830	operator<(const _It2& __y) const
2831	noexcept(noexcept(_M_current < __y))
2832	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2833	{ return _M_current < __y; }
2834
2835	template<__detail::__different_from<basic_const_iterator> _It2>
2836	constexpr bool
2837	operator>(const _It2& __y) const
2838	noexcept(noexcept(_M_current > __y))
2839	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2840	{ return _M_current > __y; }
2841
2842	template<__detail::__different_from<basic_const_iterator> _It2>
2843	constexpr bool
2844	operator<=(const _It2& __y) const
2845	noexcept(noexcept(_M_current <= __y))
2846	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2847	{ return _M_current <= __y; }
2848
2849	template<__detail::__different_from<basic_const_iterator> _It2>
2850	constexpr bool
2851	operator>=(const _It2& __y) const
2852	noexcept(noexcept(_M_current >= __y))
2853	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2854	{ return _M_current >= __y; }
2855
2856	template<__detail::__different_from<basic_const_iterator> _It2>
2857	constexpr auto
2858	operator<=>(const _It2& __y) const
2859	noexcept(noexcept(_M_current <=> __y))
2860	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2861	&& three_way_comparable_with<_It, _It2>
2862	{ return _M_current <=> __y; }
2863
2864	template<__detail::__not_a_const_iterator _It2>
2865	friend constexpr bool
2866	operator<(const _It2& __x, const basic_const_iterator& __y)
2867	noexcept(noexcept(__x < __y._M_current))
2868	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2869	{ return __x < __y._M_current; }
2870
2871	template<__detail::__not_a_const_iterator _It2>
2872	friend constexpr bool
2873	operator>(const _It2& __x, const basic_const_iterator& __y)
2874	noexcept(noexcept(__x > __y._M_current))
2875	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2876	{ return __x > __y._M_current; }
2877
2878	template<__detail::__not_a_const_iterator _It2>
2879	friend constexpr bool
2880	operator<=(const _It2& __x, const basic_const_iterator& __y)
2881	noexcept(noexcept(__x <= __y._M_current))
2882	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2883	{ return __x <= __y._M_current; }
2884
2885	template<__detail::__not_a_const_iterator _It2>
2886	friend constexpr bool
2887	operator>=(const _It2& __x, const basic_const_iterator& __y)
2888	noexcept(noexcept(__x >= __y._M_current))
2889	requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2890	{ return __x >= __y._M_current; }
2891
2892	friend constexpr basic_const_iterator
2893	operator+(const basic_const_iterator& __i, difference_type __n)
2894	noexcept(noexcept(basic_const_iterator(__i._M_current + __n)))
2895	requires random_access_iterator<_It>
2896	{ return basic_const_iterator(__i._M_current + __n); }
2897
2898	friend constexpr basic_const_iterator
2899	operator+(difference_type __n, const basic_const_iterator& __i)
2900	noexcept(noexcept(basic_const_iterator(__i._M_current + __n)))
2901	requires random_access_iterator<_It>
2902	{ return basic_const_iterator(__i._M_current + __n); }
2903
2904	friend constexpr basic_const_iterator
2905	operator-(const basic_const_iterator& __i, difference_type __n)
2906	noexcept(noexcept(basic_const_iterator(__i._M_current - __n)))
2907	requires random_access_iterator<_It>
2908	{ return basic_const_iterator(__i._M_current - __n); }
2909
2910	template<sized_sentinel_for<_It> _Sent>
2911	constexpr difference_type
2912	operator-(const _Sent& __y) const
2913	noexcept(noexcept(_M_current - __y))
2914	{ return _M_current - __y; }
2915
2916	template<__detail::__not_a_const_iterator _Sent>
2917	requires sized_sentinel_for<_Sent, _It>
2918	friend constexpr difference_type
2919	operator-(const _Sent& __x, const basic_const_iterator& __y)
2920	noexcept(noexcept(__x - __y._M_current))
2921	{ return __x - __y._M_current; }
2922
2923	friend constexpr __rvalue_reference
2924	iter_move(const basic_const_iterator& __i)
2925	noexcept(noexcept(static_cast<__rvalue_reference>(ranges::iter_move(__i._M_current))))
2926	{ return static_cast<__rvalue_reference>(ranges::iter_move(__i._M_current)); }
2927	};
2928
2929	template<typename _Tp, common_with<_Tp> _Up>
2930	requires input_iterator<common_type_t<_Tp, _Up>>
2931	struct common_type<basic_const_iterator<_Tp>, _Up>
2932	{ using type = basic_const_iterator<common_type_t<_Tp, _Up>>; };
2933
2934	template<typename _Tp, common_with<_Tp> _Up>
2935	requires input_iterator<common_type_t<_Tp, _Up>>
2936	struct common_type<_Up, basic_const_iterator<_Tp>>
2937	{ using type = basic_const_iterator<common_type_t<_Tp, _Up>>; };
2938
2939	template<typename _Tp, common_with<_Tp> _Up>
2940	requires input_iterator<common_type_t<_Tp, _Up>>
2941	struct common_type<basic_const_iterator<_Tp>, basic_const_iterator<_Up>>
2942	{ using type = basic_const_iterator<common_type_t<_Tp, _Up>>; };
2943
2944	template<input_iterator _It>
2945	constexpr const_iterator<_It>
2946	make_const_iterator(_It __it)
2947	noexcept(is_nothrow_convertible_v<_It, const_iterator<_It>>)
2948	{ return __it; }
2949
2950	template<semiregular _Sent>
2951	constexpr const_sentinel<_Sent>
2952	make_const_sentinel(_Sent __s)
2953	noexcept(is_nothrow_convertible_v<_Sent, const_sentinel<_Sent>>)
2954	{ return __s; }
2955	#endif // C++23
2956	#endif // C++20
2957
2958	/// @} group iterators
2959
2960	template<typename _Iterator>
2961	_GLIBCXX20_CONSTEXPR
2962	auto
2963	__niter_base(move_iterator<_Iterator> __it)
2964	-> decltype(make_move_iterator(__niter_base(__it.base())))
2965	{ return make_move_iterator(__niter_base(__it.base())); }
2966
2967	template<typename _Iterator>
2968	struct __is_move_iterator<move_iterator<_Iterator> >
2969	{
2970	enum { __value = `1` };
2971	typedef __true_type __type;
2972	};
2973
2974	template<typename _Iterator>
2975	_GLIBCXX20_CONSTEXPR
2976	auto
2977	__miter_base(move_iterator<_Iterator> __it)
2978	-> decltype(__miter_base(__it.base()))
2979	{ return __miter_base(__it.base()); }
2980
2981	#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2982	#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2983	std::__make_move_if_noexcept_iterator(_Iter)
2984	#else
2985	#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2986	#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2987	#endif // C++11
2988
2989	#if __cpp_deduction_guides >= 201606
2990	// These helper traits are used for deduction guides
2991	// of associative containers.
2992	template<typename _InputIterator>
2993	using __iter_key_t = remove_const_t<
2994	#if __glibcxx_tuple_like // >= C++23
2995	tuple_element_t<`0`, typename iterator_traits<_InputIterator>::value_type>>;
2996	#else
2997	typename iterator_traits<_InputIterator>::value_type::first_type>;
2998	#endif
2999
3000	template<typename _InputIterator>
3001	using __iter_val_t
3002	#if __glibcxx_tuple_like // >= C++23
3003	= tuple_element_t<`1`, typename iterator_traits<_InputIterator>::value_type>;
3004	#else
3005	= typename iterator_traits<_InputIterator>::value_type::second_type;
3006	#endif
3007
3008	template<typename _T1, typename _T2>
3009	struct pair;
3010
3011	template<typename _InputIterator>
3012	using __iter_to_alloc_t
3013	= pair<const __iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>>;
3014	#endif // __cpp_deduction_guides
3015
3016	_GLIBCXX_END_NAMESPACE_VERSION
3017	} // namespace
3018
3019	#ifdef _GLIBCXX_DEBUG
3020	# include <debug/stl_iterator.h>
3021	#endif
3022
3023	#endif
3024

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