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