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