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

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

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