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