1 // Iterators -*- C++ -*-
3 // Copyright (C) 2001-2020 Free Software Foundation, Inc.
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)
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.
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.
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/>.
28 * Hewlett-Packard Company
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.
39 * Copyright (c) 1996-1998
40 * Silicon Graphics Computer Systems, Inc.
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.
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}
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.
60 #ifndef _STL_ITERATOR_H
61 #define _STL_ITERATOR_H 1
63 #include <bits/cpp_type_traits.h>
64 #include <ext/type_traits.h>
65 #include <bits/move.h>
66 #include <bits/ptr_traits.h>
68 #if __cplusplus >= 201103L
69 # include <type_traits>
72 #if __cplusplus > 201402L
73 # define __cpp_lib_array_constexpr 201803
76 #if __cplusplus > 201703L
81 namespace std
_GLIBCXX_VISIBILITY(default)
83 _GLIBCXX_BEGIN_NAMESPACE_VERSION
86 * @addtogroup iterators
90 // 24.4.1 Reverse iterators
92 * Bidirectional and random access iterators have corresponding reverse
93 * %iterator adaptors that iterate through the data structure in the
94 * opposite direction. They have the same signatures as the corresponding
95 * iterators. The fundamental relation between a reverse %iterator and its
96 * corresponding %iterator @c i is established by the identity:
98 * &*(reverse_iterator(i)) == &*(i - 1)
101 * <em>This mapping is dictated by the fact that while there is always a
102 * pointer past the end of an array, there might not be a valid pointer
103 * before the beginning of an array.</em> [24.4.1]/1,2
105 * Reverse iterators can be tricky and surprising at first. Their
106 * semantics make sense, however, and the trickiness is a side effect of
107 * the requirement that the iterators must be safe.
109 template<typename _Iterator
>
110 class reverse_iterator
111 : public iterator
<typename iterator_traits
<_Iterator
>::iterator_category
,
112 typename iterator_traits
<_Iterator
>::value_type
,
113 typename iterator_traits
<_Iterator
>::difference_type
,
114 typename iterator_traits
<_Iterator
>::pointer
,
115 typename iterator_traits
<_Iterator
>::reference
>
120 typedef iterator_traits
<_Iterator
> __traits_type
;
123 typedef _Iterator iterator_type
;
124 typedef typename
__traits_type::difference_type difference_type
;
125 typedef typename
__traits_type::pointer pointer
;
126 typedef typename
__traits_type::reference reference
;
129 * The default constructor value-initializes member @p current.
130 * If it is a pointer, that means it is zero-initialized.
132 // _GLIBCXX_RESOLVE_LIB_DEFECTS
133 // 235 No specification of default ctor for reverse_iterator
134 // 1012. reverse_iterator default ctor should value initialize
136 reverse_iterator() : current() { }
139 * This %iterator will move in the opposite direction that @p x does.
141 explicit _GLIBCXX17_CONSTEXPR
142 reverse_iterator(iterator_type __x
) : current(__x
) { }
145 * The copy constructor is normal.
148 reverse_iterator(const reverse_iterator
& __x
)
149 : current(__x
.current
) { }
151 #if __cplusplus >= 201103L
152 reverse_iterator
& operator=(const reverse_iterator
&) = default;
156 * A %reverse_iterator across other types can be copied if the
157 * underlying %iterator can be converted to the type of @c current.
159 template<typename _Iter
>
161 reverse_iterator(const reverse_iterator
<_Iter
>& __x
)
162 : current(__x
.base()) { }
165 * @return @c current, the %iterator used for underlying work.
167 _GLIBCXX17_CONSTEXPR iterator_type
172 * @return A reference to the value at @c --current
174 * This requires that @c --current is dereferenceable.
176 * @warning This implementation requires that for an iterator of the
177 * underlying iterator type, @c x, a reference obtained by
178 * @c *x remains valid after @c x has been modified or
179 * destroyed. This is a bug: http://gcc.gnu.org/PR51823
181 _GLIBCXX17_CONSTEXPR reference
184 _Iterator __tmp
= current
;
189 * @return A pointer to the value at @c --current
191 * This requires that @c --current is dereferenceable.
193 _GLIBCXX17_CONSTEXPR pointer
195 #if __cplusplus > 201703L && defined __cpp_concepts
196 requires is_pointer_v
<_Iterator
>
197 || requires(const _Iterator __i
) { __i
.operator->(); }
200 // _GLIBCXX_RESOLVE_LIB_DEFECTS
201 // 1052. operator-> should also support smart pointers
202 _Iterator __tmp
= current
;
204 return _S_to_pointer(__tmp
);
210 * Decrements the underlying iterator.
212 _GLIBCXX17_CONSTEXPR reverse_iterator
&
220 * @return The original value of @c *this
222 * Decrements the underlying iterator.
224 _GLIBCXX17_CONSTEXPR reverse_iterator
227 reverse_iterator __tmp
= *this;
235 * Increments the underlying iterator.
237 _GLIBCXX17_CONSTEXPR reverse_iterator
&
245 * @return A reverse_iterator with the previous value of @c *this
247 * Increments the underlying iterator.
249 _GLIBCXX17_CONSTEXPR reverse_iterator
252 reverse_iterator __tmp
= *this;
258 * @return A reverse_iterator that refers to @c current - @a __n
260 * The underlying iterator must be a Random Access Iterator.
262 _GLIBCXX17_CONSTEXPR reverse_iterator
263 operator+(difference_type __n
) const
264 { return reverse_iterator(current
- __n
); }
269 * Moves the underlying iterator backwards @a __n steps.
270 * The underlying iterator must be a Random Access Iterator.
272 _GLIBCXX17_CONSTEXPR reverse_iterator
&
273 operator+=(difference_type __n
)
280 * @return A reverse_iterator that refers to @c current - @a __n
282 * The underlying iterator must be a Random Access Iterator.
284 _GLIBCXX17_CONSTEXPR reverse_iterator
285 operator-(difference_type __n
) const
286 { return reverse_iterator(current
+ __n
); }
291 * Moves the underlying iterator forwards @a __n steps.
292 * The underlying iterator must be a Random Access Iterator.
294 _GLIBCXX17_CONSTEXPR reverse_iterator
&
295 operator-=(difference_type __n
)
302 * @return The value at @c current - @a __n - 1
304 * The underlying iterator must be a Random Access Iterator.
306 _GLIBCXX17_CONSTEXPR reference
307 operator[](difference_type __n
) const
308 { return *(*this + __n
); }
311 template<typename _Tp
>
312 static _GLIBCXX17_CONSTEXPR _Tp
*
313 _S_to_pointer(_Tp
* __p
)
316 template<typename _Tp
>
317 static _GLIBCXX17_CONSTEXPR pointer
318 _S_to_pointer(_Tp __t
)
319 { return __t
.operator->(); }
324 * @param __x A %reverse_iterator.
325 * @param __y A %reverse_iterator.
326 * @return A simple bool.
328 * Reverse iterators forward many operations to their underlying base()
329 * iterators. Others are implemented in terms of one another.
332 template<typename _Iterator
>
333 inline _GLIBCXX17_CONSTEXPR
bool
334 operator==(const reverse_iterator
<_Iterator
>& __x
,
335 const reverse_iterator
<_Iterator
>& __y
)
336 { return __x
.base() == __y
.base(); }
338 template<typename _Iterator
>
339 inline _GLIBCXX17_CONSTEXPR
bool
340 operator<(const reverse_iterator
<_Iterator
>& __x
,
341 const reverse_iterator
<_Iterator
>& __y
)
342 { return __y
.base() < __x
.base(); }
344 template<typename _Iterator
>
345 inline _GLIBCXX17_CONSTEXPR
bool
346 operator!=(const reverse_iterator
<_Iterator
>& __x
,
347 const reverse_iterator
<_Iterator
>& __y
)
348 { return !(__x
== __y
); }
350 template<typename _Iterator
>
351 inline _GLIBCXX17_CONSTEXPR
bool
352 operator>(const reverse_iterator
<_Iterator
>& __x
,
353 const reverse_iterator
<_Iterator
>& __y
)
354 { return __y
< __x
; }
356 template<typename _Iterator
>
357 inline _GLIBCXX17_CONSTEXPR
bool
358 operator<=(const reverse_iterator
<_Iterator
>& __x
,
359 const reverse_iterator
<_Iterator
>& __y
)
360 { return !(__y
< __x
); }
362 template<typename _Iterator
>
363 inline _GLIBCXX17_CONSTEXPR
bool
364 operator>=(const reverse_iterator
<_Iterator
>& __x
,
365 const reverse_iterator
<_Iterator
>& __y
)
366 { return !(__x
< __y
); }
368 // _GLIBCXX_RESOLVE_LIB_DEFECTS
369 // DR 280. Comparison of reverse_iterator to const reverse_iterator.
370 template<typename _IteratorL
, typename _IteratorR
>
371 inline _GLIBCXX17_CONSTEXPR
bool
372 operator==(const reverse_iterator
<_IteratorL
>& __x
,
373 const reverse_iterator
<_IteratorR
>& __y
)
374 { return __x
.base() == __y
.base(); }
376 template<typename _IteratorL
, typename _IteratorR
>
377 inline _GLIBCXX17_CONSTEXPR
bool
378 operator<(const reverse_iterator
<_IteratorL
>& __x
,
379 const reverse_iterator
<_IteratorR
>& __y
)
380 { return __y
.base() < __x
.base(); }
382 template<typename _IteratorL
, typename _IteratorR
>
383 inline _GLIBCXX17_CONSTEXPR
bool
384 operator!=(const reverse_iterator
<_IteratorL
>& __x
,
385 const reverse_iterator
<_IteratorR
>& __y
)
386 { return !(__x
== __y
); }
388 template<typename _IteratorL
, typename _IteratorR
>
389 inline _GLIBCXX17_CONSTEXPR
bool
390 operator>(const reverse_iterator
<_IteratorL
>& __x
,
391 const reverse_iterator
<_IteratorR
>& __y
)
392 { return __y
< __x
; }
394 template<typename _IteratorL
, typename _IteratorR
>
395 inline _GLIBCXX17_CONSTEXPR
bool
396 operator<=(const reverse_iterator
<_IteratorL
>& __x
,
397 const reverse_iterator
<_IteratorR
>& __y
)
398 { return !(__y
< __x
); }
400 template<typename _IteratorL
, typename _IteratorR
>
401 inline _GLIBCXX17_CONSTEXPR
bool
402 operator>=(const reverse_iterator
<_IteratorL
>& __x
,
403 const reverse_iterator
<_IteratorR
>& __y
)
404 { return !(__x
< __y
); }
407 #if __cplusplus < 201103L
408 template<typename _Iterator
>
409 inline typename reverse_iterator
<_Iterator
>::difference_type
410 operator-(const reverse_iterator
<_Iterator
>& __x
,
411 const reverse_iterator
<_Iterator
>& __y
)
412 { return __y
.base() - __x
.base(); }
414 template<typename _IteratorL
, typename _IteratorR
>
415 inline typename reverse_iterator
<_IteratorL
>::difference_type
416 operator-(const reverse_iterator
<_IteratorL
>& __x
,
417 const reverse_iterator
<_IteratorR
>& __y
)
418 { return __y
.base() - __x
.base(); }
420 // _GLIBCXX_RESOLVE_LIB_DEFECTS
421 // DR 685. reverse_iterator/move_iterator difference has invalid signatures
422 template<typename _IteratorL
, typename _IteratorR
>
423 inline _GLIBCXX17_CONSTEXPR
auto
424 operator-(const reverse_iterator
<_IteratorL
>& __x
,
425 const reverse_iterator
<_IteratorR
>& __y
)
426 -> decltype(__y
.base() - __x
.base())
427 { return __y
.base() - __x
.base(); }
430 template<typename _Iterator
>
431 inline _GLIBCXX17_CONSTEXPR reverse_iterator
<_Iterator
>
432 operator+(typename reverse_iterator
<_Iterator
>::difference_type __n
,
433 const reverse_iterator
<_Iterator
>& __x
)
434 { return reverse_iterator
<_Iterator
>(__x
.base() - __n
); }
436 #if __cplusplus >= 201103L
437 // Same as C++14 make_reverse_iterator but used in C++11 mode too.
438 template<typename _Iterator
>
439 inline _GLIBCXX17_CONSTEXPR reverse_iterator
<_Iterator
>
440 __make_reverse_iterator(_Iterator __i
)
441 { return reverse_iterator
<_Iterator
>(__i
); }
443 # if __cplusplus >= 201402L
444 # define __cpp_lib_make_reverse_iterator 201402
446 // _GLIBCXX_RESOLVE_LIB_DEFECTS
447 // DR 2285. make_reverse_iterator
448 /// Generator function for reverse_iterator.
449 template<typename _Iterator
>
450 inline _GLIBCXX17_CONSTEXPR reverse_iterator
<_Iterator
>
451 make_reverse_iterator(_Iterator __i
)
452 { return reverse_iterator
<_Iterator
>(__i
); }
454 # if __cplusplus > 201703L && defined __cpp_lib_concepts
455 template<typename _Iterator1
, typename _Iterator2
>
456 requires (!sized_sentinel_for
<_Iterator1
, _Iterator2
>)
457 inline constexpr bool
458 disable_sized_sentinel_for
<reverse_iterator
<_Iterator1
>,
459 reverse_iterator
<_Iterator2
>> = true;
463 template<typename _Iterator
>
466 __niter_base(reverse_iterator
<_Iterator
> __it
)
467 -> decltype(__make_reverse_iterator(__niter_base(__it
.base())))
468 { return __make_reverse_iterator(__niter_base(__it
.base())); }
470 template<typename _Iterator
>
471 struct __is_move_iterator
<reverse_iterator
<_Iterator
> >
472 : __is_move_iterator
<_Iterator
>
475 template<typename _Iterator
>
478 __miter_base(reverse_iterator
<_Iterator
> __it
)
479 -> decltype(__make_reverse_iterator(__miter_base(__it
.base())))
480 { return __make_reverse_iterator(__miter_base(__it
.base())); }
483 // 24.4.2.2.1 back_insert_iterator
485 * @brief Turns assignment into insertion.
487 * These are output iterators, constructed from a container-of-T.
488 * Assigning a T to the iterator appends it to the container using
491 * Tip: Using the back_inserter function to create these iterators can
494 template<typename _Container
>
495 class back_insert_iterator
496 : public iterator
<output_iterator_tag
, void, void, void, void>
499 _Container
* container
;
502 /// A nested typedef for the type of whatever container you used.
503 typedef _Container container_type
;
505 /// The only way to create this %iterator is with a container.
507 back_insert_iterator(_Container
& __x
)
508 : container(std::__addressof(__x
)) { }
511 * @param __value An instance of whatever type
512 * container_type::const_reference is; presumably a
513 * reference-to-const T for container<T>.
514 * @return This %iterator, for chained operations.
516 * This kind of %iterator doesn't really have a @a position in the
517 * container (you can think of the position as being permanently at
518 * the end, if you like). Assigning a value to the %iterator will
519 * always append the value to the end of the container.
521 #if __cplusplus < 201103L
522 back_insert_iterator
&
523 operator=(typename
_Container::const_reference __value
)
525 container
->push_back(__value
);
529 back_insert_iterator
&
530 operator=(const typename
_Container::value_type
& __value
)
532 container
->push_back(__value
);
536 back_insert_iterator
&
537 operator=(typename
_Container::value_type
&& __value
)
539 container
->push_back(std::move(__value
));
544 /// Simply returns *this.
545 back_insert_iterator
&
549 /// Simply returns *this. (This %iterator does not @a move.)
550 back_insert_iterator
&
554 /// Simply returns *this. (This %iterator does not @a move.)
561 * @param __x A container of arbitrary type.
562 * @return An instance of back_insert_iterator working on @p __x.
564 * This wrapper function helps in creating back_insert_iterator instances.
565 * Typing the name of the %iterator requires knowing the precise full
566 * type of the container, which can be tedious and impedes generic
567 * programming. Using this function lets you take advantage of automatic
568 * template parameter deduction, making the compiler match the correct
571 template<typename _Container
>
572 inline back_insert_iterator
<_Container
>
573 back_inserter(_Container
& __x
)
574 { return back_insert_iterator
<_Container
>(__x
); }
577 * @brief Turns assignment into insertion.
579 * These are output iterators, constructed from a container-of-T.
580 * Assigning a T to the iterator prepends it to the container using
583 * Tip: Using the front_inserter function to create these iterators can
586 template<typename _Container
>
587 class front_insert_iterator
588 : public iterator
<output_iterator_tag
, void, void, void, void>
591 _Container
* container
;
594 /// A nested typedef for the type of whatever container you used.
595 typedef _Container container_type
;
597 /// The only way to create this %iterator is with a container.
598 explicit front_insert_iterator(_Container
& __x
)
599 : container(std::__addressof(__x
)) { }
602 * @param __value An instance of whatever type
603 * container_type::const_reference is; presumably a
604 * reference-to-const T for container<T>.
605 * @return This %iterator, for chained operations.
607 * This kind of %iterator doesn't really have a @a position in the
608 * container (you can think of the position as being permanently at
609 * the front, if you like). Assigning a value to the %iterator will
610 * always prepend the value to the front of the container.
612 #if __cplusplus < 201103L
613 front_insert_iterator
&
614 operator=(typename
_Container::const_reference __value
)
616 container
->push_front(__value
);
620 front_insert_iterator
&
621 operator=(const typename
_Container::value_type
& __value
)
623 container
->push_front(__value
);
627 front_insert_iterator
&
628 operator=(typename
_Container::value_type
&& __value
)
630 container
->push_front(std::move(__value
));
635 /// Simply returns *this.
636 front_insert_iterator
&
640 /// Simply returns *this. (This %iterator does not @a move.)
641 front_insert_iterator
&
645 /// Simply returns *this. (This %iterator does not @a move.)
646 front_insert_iterator
652 * @param __x A container of arbitrary type.
653 * @return An instance of front_insert_iterator working on @p x.
655 * This wrapper function helps in creating front_insert_iterator instances.
656 * Typing the name of the %iterator requires knowing the precise full
657 * type of the container, which can be tedious and impedes generic
658 * programming. Using this function lets you take advantage of automatic
659 * template parameter deduction, making the compiler match the correct
662 template<typename _Container
>
663 inline front_insert_iterator
<_Container
>
664 front_inserter(_Container
& __x
)
665 { return front_insert_iterator
<_Container
>(__x
); }
668 * @brief Turns assignment into insertion.
670 * These are output iterators, constructed from a container-of-T.
671 * Assigning a T to the iterator inserts it in the container at the
672 * %iterator's position, rather than overwriting the value at that
675 * (Sequences will actually insert a @e copy of the value before the
676 * %iterator's position.)
678 * Tip: Using the inserter function to create these iterators can
681 template<typename _Container
>
682 class insert_iterator
683 : public iterator
<output_iterator_tag
, void, void, void, void>
686 _Container
* container
;
687 typename
_Container::iterator iter
;
690 /// A nested typedef for the type of whatever container you used.
691 typedef _Container container_type
;
694 * The only way to create this %iterator is with a container and an
695 * initial position (a normal %iterator into the container).
697 insert_iterator(_Container
& __x
, typename
_Container::iterator __i
)
698 : container(std::__addressof(__x
)), iter(__i
) {}
701 * @param __value An instance of whatever type
702 * container_type::const_reference is; presumably a
703 * reference-to-const T for container<T>.
704 * @return This %iterator, for chained operations.
706 * This kind of %iterator maintains its own position in the
707 * container. Assigning a value to the %iterator will insert the
708 * value into the container at the place before the %iterator.
710 * The position is maintained such that subsequent assignments will
711 * insert values immediately after one another. For example,
713 * // vector v contains A and Z
715 * insert_iterator i (v, ++v.begin());
720 * // vector v contains A, 1, 2, 3, and Z
723 #if __cplusplus < 201103L
725 operator=(typename
_Container::const_reference __value
)
727 iter
= container
->insert(iter
, __value
);
733 operator=(const typename
_Container::value_type
& __value
)
735 iter
= container
->insert(iter
, __value
);
741 operator=(typename
_Container::value_type
&& __value
)
743 iter
= container
->insert(iter
, std::move(__value
));
749 /// Simply returns *this.
754 /// Simply returns *this. (This %iterator does not @a move.)
759 /// Simply returns *this. (This %iterator does not @a move.)
766 * @param __x A container of arbitrary type.
767 * @param __i An iterator into the container.
768 * @return An instance of insert_iterator working on @p __x.
770 * This wrapper function helps in creating insert_iterator instances.
771 * Typing the name of the %iterator requires knowing the precise full
772 * type of the container, which can be tedious and impedes generic
773 * programming. Using this function lets you take advantage of automatic
774 * template parameter deduction, making the compiler match the correct
777 template<typename _Container
, typename _Iterator
>
778 inline insert_iterator
<_Container
>
779 inserter(_Container
& __x
, _Iterator __i
)
781 return insert_iterator
<_Container
>(__x
,
782 typename
_Container::iterator(__i
));
785 // @} group iterators
787 _GLIBCXX_END_NAMESPACE_VERSION
790 namespace __gnu_cxx
_GLIBCXX_VISIBILITY(default)
792 _GLIBCXX_BEGIN_NAMESPACE_VERSION
794 // This iterator adapter is @a normal in the sense that it does not
795 // change the semantics of any of the operators of its iterator
796 // parameter. Its primary purpose is to convert an iterator that is
797 // not a class, e.g. a pointer, into an iterator that is a class.
798 // The _Container parameter exists solely so that different containers
799 // using this template can instantiate different types, even if the
800 // _Iterator parameter is the same.
801 template<typename _Iterator
, typename _Container
>
802 class __normal_iterator
805 _Iterator _M_current
;
807 typedef std::iterator_traits
<_Iterator
> __traits_type
;
810 typedef _Iterator iterator_type
;
811 typedef typename
__traits_type::iterator_category iterator_category
;
812 typedef typename
__traits_type::value_type value_type
;
813 typedef typename
__traits_type::difference_type difference_type
;
814 typedef typename
__traits_type::reference reference
;
815 typedef typename
__traits_type::pointer pointer
;
817 #if __cplusplus > 201703L && __cpp_lib_concepts
818 using iterator_concept
= std::__detail::__iter_concept
<_Iterator
>;
821 _GLIBCXX_CONSTEXPR
__normal_iterator() _GLIBCXX_NOEXCEPT
822 : _M_current(_Iterator()) { }
824 explicit _GLIBCXX20_CONSTEXPR
825 __normal_iterator(const _Iterator
& __i
) _GLIBCXX_NOEXCEPT
826 : _M_current(__i
) { }
828 // Allow iterator to const_iterator conversion
829 template<typename _Iter
>
831 __normal_iterator(const __normal_iterator
<_Iter
,
832 typename __enable_if
<
833 (std::__are_same
<_Iter
, typename
_Container::pointer
>::__value
),
834 _Container
>::__type
>& __i
) _GLIBCXX_NOEXCEPT
835 : _M_current(__i
.base()) { }
837 // Forward iterator requirements
840 operator*() const _GLIBCXX_NOEXCEPT
841 { return *_M_current
; }
845 operator->() const _GLIBCXX_NOEXCEPT
846 { return _M_current
; }
850 operator++() _GLIBCXX_NOEXCEPT
858 operator++(int) _GLIBCXX_NOEXCEPT
859 { return __normal_iterator(_M_current
++); }
861 // Bidirectional iterator requirements
864 operator--() _GLIBCXX_NOEXCEPT
872 operator--(int) _GLIBCXX_NOEXCEPT
873 { return __normal_iterator(_M_current
--); }
875 // Random access iterator requirements
878 operator[](difference_type __n
) const _GLIBCXX_NOEXCEPT
879 { return _M_current
[__n
]; }
883 operator+=(difference_type __n
) _GLIBCXX_NOEXCEPT
884 { _M_current
+= __n
; return *this; }
888 operator+(difference_type __n
) const _GLIBCXX_NOEXCEPT
889 { return __normal_iterator(_M_current
+ __n
); }
893 operator-=(difference_type __n
) _GLIBCXX_NOEXCEPT
894 { _M_current
-= __n
; return *this; }
898 operator-(difference_type __n
) const _GLIBCXX_NOEXCEPT
899 { return __normal_iterator(_M_current
- __n
); }
903 base() const _GLIBCXX_NOEXCEPT
904 { return _M_current
; }
907 // Note: In what follows, the left- and right-hand-side iterators are
908 // allowed to vary in types (conceptually in cv-qualification) so that
909 // comparison between cv-qualified and non-cv-qualified iterators be
910 // valid. However, the greedy and unfriendly operators in std::rel_ops
911 // will make overload resolution ambiguous (when in scope) if we don't
912 // provide overloads whose operands are of the same type. Can someone
913 // remind me what generic programming is about? -- Gaby
915 // Forward iterator requirements
916 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
919 operator==(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
920 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
922 { return __lhs
.base() == __rhs
.base(); }
924 template<typename _Iterator
, typename _Container
>
927 operator==(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
928 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
930 { return __lhs
.base() == __rhs
.base(); }
932 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
935 operator!=(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
936 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
938 { return __lhs
.base() != __rhs
.base(); }
940 template<typename _Iterator
, typename _Container
>
943 operator!=(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
944 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
946 { return __lhs
.base() != __rhs
.base(); }
948 // Random access iterator requirements
949 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
952 operator<(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
953 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
955 { return __lhs
.base() < __rhs
.base(); }
957 template<typename _Iterator
, typename _Container
>
960 operator<(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
961 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
963 { return __lhs
.base() < __rhs
.base(); }
965 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
968 operator>(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
969 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
971 { return __lhs
.base() > __rhs
.base(); }
973 template<typename _Iterator
, typename _Container
>
976 operator>(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
977 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
979 { return __lhs
.base() > __rhs
.base(); }
981 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
984 operator<=(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
985 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
987 { return __lhs
.base() <= __rhs
.base(); }
989 template<typename _Iterator
, typename _Container
>
992 operator<=(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
993 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
995 { return __lhs
.base() <= __rhs
.base(); }
997 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
1000 operator>=(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
1001 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
1003 { return __lhs
.base() >= __rhs
.base(); }
1005 template<typename _Iterator
, typename _Container
>
1006 _GLIBCXX20_CONSTEXPR
1008 operator>=(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
1009 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
1011 { return __lhs
.base() >= __rhs
.base(); }
1013 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1014 // According to the resolution of DR179 not only the various comparison
1015 // operators but also operator- must accept mixed iterator/const_iterator
1017 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
1018 #if __cplusplus >= 201103L
1020 _GLIBCXX20_CONSTEXPR
1022 operator-(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
1023 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
) noexcept
1024 -> decltype(__lhs
.base() - __rhs
.base())
1026 inline typename __normal_iterator
<_IteratorL
, _Container
>::difference_type
1027 operator-(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
1028 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
1030 { return __lhs
.base() - __rhs
.base(); }
1032 template<typename _Iterator
, typename _Container
>
1033 _GLIBCXX20_CONSTEXPR
1034 inline typename __normal_iterator
<_Iterator
, _Container
>::difference_type
1035 operator-(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
1036 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
1038 { return __lhs
.base() - __rhs
.base(); }
1040 template<typename _Iterator
, typename _Container
>
1041 _GLIBCXX20_CONSTEXPR
1042 inline __normal_iterator
<_Iterator
, _Container
>
1043 operator+(typename __normal_iterator
<_Iterator
, _Container
>::difference_type
1044 __n
, const __normal_iterator
<_Iterator
, _Container
>& __i
)
1046 { return __normal_iterator
<_Iterator
, _Container
>(__i
.base() + __n
); }
1048 _GLIBCXX_END_NAMESPACE_VERSION
1051 namespace std
_GLIBCXX_VISIBILITY(default)
1053 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1055 template<typename _Iterator
, typename _Container
>
1056 _GLIBCXX20_CONSTEXPR
1058 __niter_base(__gnu_cxx::__normal_iterator
<_Iterator
, _Container
> __it
)
1059 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible
<_Iterator
>::value
)
1060 { return __it
.base(); }
1062 #if __cplusplus >= 201103L
1064 * @addtogroup iterators
1068 #if __cplusplus > 201703L && __cpp_lib_concepts
1069 template<semiregular _Sent
>
1075 noexcept(is_nothrow_default_constructible_v
<_Sent
>)
1079 move_sentinel(_Sent __s
)
1080 noexcept(is_nothrow_move_constructible_v
<_Sent
>)
1081 : _M_last(std::move(__s
)) { }
1083 template<typename _S2
> requires convertible_to
<const _S2
&, _Sent
>
1085 move_sentinel(const move_sentinel
<_S2
>& __s
)
1086 noexcept(is_nothrow_constructible_v
<_Sent
, const _S2
&>)
1087 : _M_last(__s
.base())
1090 template<typename _S2
> requires assignable_from
<_Sent
&, const _S2
&>
1091 constexpr move_sentinel
&
1092 operator=(const move_sentinel
<_S2
>& __s
)
1093 noexcept(is_nothrow_assignable_v
<_Sent
, const _S2
&>)
1095 _M_last
= __s
.base();
1101 noexcept(is_nothrow_copy_constructible_v
<_Sent
>)
1110 // Weaken iterator_category _Cat to _Limit if it is derived from that,
1111 // otherwise use _Otherwise.
1112 template<typename _Cat
, typename _Limit
, typename _Otherwise
= _Cat
>
1113 using __clamp_iter_cat
1114 = conditional_t
<derived_from
<_Cat
, _Limit
>, _Limit
, _Otherwise
>;
1118 // 24.4.3 Move iterators
1120 * Class template move_iterator is an iterator adapter with the same
1121 * behavior as the underlying iterator except that its dereference
1122 * operator implicitly converts the value returned by the underlying
1123 * iterator's dereference operator to an rvalue reference. Some
1124 * generic algorithms can be called with move iterators to replace
1125 * copying with moving.
1127 template<typename _Iterator
>
1130 _Iterator _M_current
;
1132 using __traits_type
= iterator_traits
<_Iterator
>;
1133 #if __cplusplus > 201703L && __cpp_lib_concepts
1134 using __base_cat
= typename
__traits_type::iterator_category
;
1136 using __base_ref
= typename
__traits_type::reference
;
1140 using iterator_type
= _Iterator
;
1142 #if __cplusplus > 201703L && __cpp_lib_concepts
1143 using iterator_concept
= input_iterator_tag
;
1144 using iterator_category
1145 = __detail::__clamp_iter_cat
<__base_cat
, random_access_iterator_tag
>;
1146 using value_type
= iter_value_t
<_Iterator
>;
1147 using difference_type
= iter_difference_t
<_Iterator
>;
1148 using pointer
= _Iterator
;
1149 using reference
= iter_rvalue_reference_t
<_Iterator
>;
1151 typedef typename
__traits_type::iterator_category iterator_category
;
1152 typedef typename
__traits_type::value_type value_type
;
1153 typedef typename
__traits_type::difference_type difference_type
;
1155 typedef _Iterator pointer
;
1156 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1157 // 2106. move_iterator wrapping iterators returning prvalues
1158 typedef typename conditional
<is_reference
<__base_ref
>::value
,
1159 typename remove_reference
<__base_ref
>::type
&&,
1160 __base_ref
>::type reference
;
1163 _GLIBCXX17_CONSTEXPR
1167 explicit _GLIBCXX17_CONSTEXPR
1168 move_iterator(iterator_type __i
)
1169 : _M_current(std::move(__i
)) { }
1171 template<typename _Iter
>
1172 _GLIBCXX17_CONSTEXPR
1173 move_iterator(const move_iterator
<_Iter
>& __i
)
1174 : _M_current(__i
.base()) { }
1176 #if __cplusplus <= 201703L
1177 _GLIBCXX17_CONSTEXPR iterator_type
1179 { return _M_current
; }
1181 constexpr iterator_type
1183 #if __cpp_lib_concepts
1184 requires copy_constructible
<iterator_type
>
1186 { return _M_current
; }
1188 constexpr iterator_type
1190 { return std::move(_M_current
); }
1193 _GLIBCXX17_CONSTEXPR reference
1195 { return static_cast<reference
>(*_M_current
); }
1197 _GLIBCXX17_CONSTEXPR pointer
1199 { return _M_current
; }
1201 _GLIBCXX17_CONSTEXPR move_iterator
&
1208 _GLIBCXX17_CONSTEXPR move_iterator
1211 move_iterator __tmp
= *this;
1216 _GLIBCXX17_CONSTEXPR move_iterator
&
1223 _GLIBCXX17_CONSTEXPR move_iterator
1226 move_iterator __tmp
= *this;
1231 _GLIBCXX17_CONSTEXPR move_iterator
1232 operator+(difference_type __n
) const
1233 { return move_iterator(_M_current
+ __n
); }
1235 _GLIBCXX17_CONSTEXPR move_iterator
&
1236 operator+=(difference_type __n
)
1242 _GLIBCXX17_CONSTEXPR move_iterator
1243 operator-(difference_type __n
) const
1244 { return move_iterator(_M_current
- __n
); }
1246 _GLIBCXX17_CONSTEXPR move_iterator
&
1247 operator-=(difference_type __n
)
1253 _GLIBCXX17_CONSTEXPR reference
1254 operator[](difference_type __n
) const
1255 { return std::move(_M_current
[__n
]); }
1257 #if __cplusplus > 201703L && __cpp_lib_concepts
1258 template<sentinel_for
<_Iterator
> _Sent
>
1259 friend constexpr bool
1260 operator==(const move_iterator
& __x
, const move_sentinel
<_Sent
>& __y
)
1261 { return __x
.base() == __y
.base(); }
1263 template<sized_sentinel_for
<_Iterator
> _Sent
>
1264 friend constexpr iter_difference_t
<_Iterator
>
1265 operator-(const move_sentinel
<_Sent
>& __x
, const move_iterator
& __y
)
1266 { return __x
.base() - __y
.base(); }
1268 template<sized_sentinel_for
<_Iterator
> _Sent
>
1269 friend constexpr iter_difference_t
<_Iterator
>
1270 operator-(const move_iterator
& __x
, const move_sentinel
<_Sent
>& __y
)
1271 { return __x
.base() - __y
.base(); }
1273 friend constexpr iter_rvalue_reference_t
<_Iterator
>
1274 iter_move(const move_iterator
& __i
)
1275 noexcept(noexcept(ranges::iter_move(__i
._M_current
)))
1276 { return ranges::iter_move(__i
._M_current
); }
1278 template<indirectly_swappable
<_Iterator
> _Iter2
>
1279 friend constexpr void
1280 iter_swap(const move_iterator
& __x
, const move_iterator
<_Iter2
>& __y
)
1281 noexcept(noexcept(ranges::iter_swap(__x
._M_current
, __y
._M_current
)))
1282 { return ranges::iter_swap(__x
._M_current
, __y
._M_current
); }
1286 // Note: See __normal_iterator operators note from Gaby to understand
1287 // why there are always 2 versions for most of the move_iterator
1289 template<typename _IteratorL
, typename _IteratorR
>
1290 inline _GLIBCXX17_CONSTEXPR
bool
1291 operator==(const move_iterator
<_IteratorL
>& __x
,
1292 const move_iterator
<_IteratorR
>& __y
)
1293 { return __x
.base() == __y
.base(); }
1295 template<typename _Iterator
>
1296 inline _GLIBCXX17_CONSTEXPR
bool
1297 operator==(const move_iterator
<_Iterator
>& __x
,
1298 const move_iterator
<_Iterator
>& __y
)
1299 { return __x
.base() == __y
.base(); }
1301 template<typename _IteratorL
, typename _IteratorR
>
1302 inline _GLIBCXX17_CONSTEXPR
bool
1303 operator!=(const move_iterator
<_IteratorL
>& __x
,
1304 const move_iterator
<_IteratorR
>& __y
)
1305 { return !(__x
== __y
); }
1307 template<typename _Iterator
>
1308 inline _GLIBCXX17_CONSTEXPR
bool
1309 operator!=(const move_iterator
<_Iterator
>& __x
,
1310 const move_iterator
<_Iterator
>& __y
)
1311 { return !(__x
== __y
); }
1313 template<typename _IteratorL
, typename _IteratorR
>
1314 inline _GLIBCXX17_CONSTEXPR
bool
1315 operator<(const move_iterator
<_IteratorL
>& __x
,
1316 const move_iterator
<_IteratorR
>& __y
)
1317 { return __x
.base() < __y
.base(); }
1319 template<typename _Iterator
>
1320 inline _GLIBCXX17_CONSTEXPR
bool
1321 operator<(const move_iterator
<_Iterator
>& __x
,
1322 const move_iterator
<_Iterator
>& __y
)
1323 { return __x
.base() < __y
.base(); }
1325 template<typename _IteratorL
, typename _IteratorR
>
1326 inline _GLIBCXX17_CONSTEXPR
bool
1327 operator<=(const move_iterator
<_IteratorL
>& __x
,
1328 const move_iterator
<_IteratorR
>& __y
)
1329 { return !(__y
< __x
); }
1331 template<typename _Iterator
>
1332 inline _GLIBCXX17_CONSTEXPR
bool
1333 operator<=(const move_iterator
<_Iterator
>& __x
,
1334 const move_iterator
<_Iterator
>& __y
)
1335 { return !(__y
< __x
); }
1337 template<typename _IteratorL
, typename _IteratorR
>
1338 inline _GLIBCXX17_CONSTEXPR
bool
1339 operator>(const move_iterator
<_IteratorL
>& __x
,
1340 const move_iterator
<_IteratorR
>& __y
)
1341 { return __y
< __x
; }
1343 template<typename _Iterator
>
1344 inline _GLIBCXX17_CONSTEXPR
bool
1345 operator>(const move_iterator
<_Iterator
>& __x
,
1346 const move_iterator
<_Iterator
>& __y
)
1347 { return __y
< __x
; }
1349 template<typename _IteratorL
, typename _IteratorR
>
1350 inline _GLIBCXX17_CONSTEXPR
bool
1351 operator>=(const move_iterator
<_IteratorL
>& __x
,
1352 const move_iterator
<_IteratorR
>& __y
)
1353 { return !(__x
< __y
); }
1355 template<typename _Iterator
>
1356 inline _GLIBCXX17_CONSTEXPR
bool
1357 operator>=(const move_iterator
<_Iterator
>& __x
,
1358 const move_iterator
<_Iterator
>& __y
)
1359 { return !(__x
< __y
); }
1362 template<typename _IteratorL
, typename _IteratorR
>
1363 inline _GLIBCXX17_CONSTEXPR
auto
1364 operator-(const move_iterator
<_IteratorL
>& __x
,
1365 const move_iterator
<_IteratorR
>& __y
)
1366 -> decltype(__x
.base() - __y
.base())
1367 { return __x
.base() - __y
.base(); }
1369 template<typename _Iterator
>
1370 inline _GLIBCXX17_CONSTEXPR move_iterator
<_Iterator
>
1371 operator+(typename move_iterator
<_Iterator
>::difference_type __n
,
1372 const move_iterator
<_Iterator
>& __x
)
1373 { return __x
+ __n
; }
1375 template<typename _Iterator
>
1376 inline _GLIBCXX17_CONSTEXPR move_iterator
<_Iterator
>
1377 make_move_iterator(_Iterator __i
)
1378 { return move_iterator
<_Iterator
>(std::move(__i
)); }
1380 template<typename _Iterator
, typename _ReturnType
1381 = typename conditional
<__move_if_noexcept_cond
1382 <typename iterator_traits
<_Iterator
>::value_type
>::value
,
1383 _Iterator
, move_iterator
<_Iterator
>>::type
>
1384 inline _GLIBCXX17_CONSTEXPR _ReturnType
1385 __make_move_if_noexcept_iterator(_Iterator __i
)
1386 { return _ReturnType(__i
); }
1388 // Overload for pointers that matches std::move_if_noexcept more closely,
1389 // returning a constant iterator when we don't want to move.
1390 template<typename _Tp
, typename _ReturnType
1391 = typename conditional
<__move_if_noexcept_cond
<_Tp
>::value
,
1392 const _Tp
*, move_iterator
<_Tp
*>>::type
>
1393 inline _GLIBCXX17_CONSTEXPR _ReturnType
1394 __make_move_if_noexcept_iterator(_Tp
* __i
)
1395 { return _ReturnType(__i
); }
1397 #if __cplusplus > 201703L && __cpp_lib_concepts
1398 // [iterators.common] Common iterators
1402 template<input_or_output_iterator _It
>
1403 class _Common_iter_proxy
1405 iter_value_t
<_It
> _M_keep
;
1407 _Common_iter_proxy(iter_reference_t
<_It
>&& __x
)
1408 : _M_keep(std::move(__x
)) { }
1410 template<typename _Iter
, typename _Sent
>
1411 friend class common_iterator
;
1414 const iter_value_t
<_It
>*
1416 { return std::__addressof(_M_keep
); }
1419 template<typename _It
>
1420 concept __common_iter_has_arrow
= indirectly_readable
<const _It
>
1421 && (requires(const _It
& __it
) { __it
.operator->(); }
1422 || is_reference_v
<iter_reference_t
<_It
>>
1423 || constructible_from
<iter_value_t
<_It
>, iter_reference_t
<_It
>>);
1425 } // namespace __detail
1427 /// An iterator/sentinel adaptor for representing a non-common range.
1428 template<input_or_output_iterator _It
, sentinel_for
<_It
> _Sent
>
1429 requires (!same_as
<_It
, _Sent
>)
1430 class common_iterator
1432 template<typename _Tp
, typename _Up
>
1433 static constexpr bool
1436 if constexpr (is_trivially_default_constructible_v
<_Tp
>)
1437 return is_nothrow_assignable_v
<_Tp
, _Up
>;
1439 return is_nothrow_constructible_v
<_Tp
, _Up
>;
1442 template<typename _It2
, typename _Sent2
>
1443 static constexpr bool
1445 { return _S_noexcept1
<_It
, _It2
>() && _S_noexcept1
<_Sent
, _Sent2
>(); }
1450 noexcept(is_nothrow_default_constructible_v
<_It
>)
1451 : _M_it(), _M_index(0)
1455 common_iterator(_It __i
)
1456 noexcept(is_nothrow_move_constructible_v
<_It
>)
1457 : _M_it(std::move(__i
)), _M_index(0)
1461 common_iterator(_Sent __s
)
1462 noexcept(is_nothrow_move_constructible_v
<_Sent
>)
1463 : _M_sent(std::move(__s
)), _M_index(1)
1466 template<typename _It2
, typename _Sent2
>
1467 requires convertible_to
<const _It2
&, _It
>
1468 && convertible_to
<const _Sent2
&, _Sent
>
1470 common_iterator(const common_iterator
<_It2
, _Sent2
>& __x
)
1471 noexcept(_S_noexcept
<const _It2
&, const _Sent2
&>())
1472 : _M_valueless(), _M_index(__x
._M_index
)
1476 if constexpr (is_trivially_default_constructible_v
<_It
>)
1477 _M_it
= std::move(__x
._M_it
);
1479 ::new((void*)std::__addressof(_M_it
)) _It(__x
._M_it
);
1481 else if (_M_index
== 1)
1483 if constexpr (is_trivially_default_constructible_v
<_Sent
>)
1484 _M_sent
= std::move(__x
._M_sent
);
1486 ::new((void*)std::__addressof(_M_sent
)) _Sent(__x
._M_sent
);
1491 common_iterator(const common_iterator
& __x
)
1492 noexcept(_S_noexcept
<const _It
&, const _Sent
&>())
1493 : _M_valueless(), _M_index(__x
._M_index
)
1497 if constexpr (is_trivially_default_constructible_v
<_It
>)
1498 _M_it
= std::move(__x
._M_it
);
1500 ::new((void*)std::__addressof(_M_it
)) _It(__x
._M_it
);
1502 else if (_M_index
== 1)
1504 if constexpr (is_trivially_default_constructible_v
<_Sent
>)
1505 _M_sent
= std::move(__x
._M_sent
);
1507 ::new((void*)std::__addressof(_M_sent
)) _Sent(__x
._M_sent
);
1512 operator=(const common_iterator
& __x
)
1513 noexcept(is_nothrow_copy_assignable_v
<_It
>
1514 && is_nothrow_copy_assignable_v
<_Sent
>
1515 && is_nothrow_copy_constructible_v
<_It
>
1516 && is_nothrow_copy_constructible_v
<_Sent
>)
1518 return this->operator=<_It
, _Sent
>(__x
);
1521 template<typename _It2
, typename _Sent2
>
1522 requires convertible_to
<const _It2
&, _It
>
1523 && convertible_to
<const _Sent2
&, _Sent
>
1524 && assignable_from
<_It
&, const _It2
&>
1525 && assignable_from
<_Sent
&, const _Sent2
&>
1527 operator=(const common_iterator
<_It2
, _Sent2
>& __x
)
1528 noexcept(is_nothrow_constructible_v
<_It
, const _It2
&>
1529 && is_nothrow_constructible_v
<_Sent
, const _Sent2
&>
1530 && is_nothrow_assignable_v
<_It
, const _It2
&>
1531 && is_nothrow_assignable_v
<_Sent
, const _Sent2
&>)
1533 switch(_M_index
<< 2 | __x
._M_index
)
1539 _M_sent
= __x
._M_sent
;
1546 ::new((void*)std::__addressof(_M_sent
)) _Sent(__x
._M_sent
);
1554 ::new((void*)std::__addressof(_M_it
)) _It(__x
._M_it
);
1558 __glibcxx_assert(__x
._M_has_value());
1559 __builtin_unreachable();
1580 __glibcxx_assert(_M_index
== 0);
1585 operator*() const requires
__detail::__dereferenceable
<const _It
>
1587 __glibcxx_assert(_M_index
== 0);
1592 operator->() const requires
__detail::__common_iter_has_arrow
<_It
>
1594 __glibcxx_assert(_M_index
== 0);
1595 if constexpr (is_pointer_v
<_It
> || requires
{ _M_it
.operator->(); })
1597 else if constexpr (is_reference_v
<iter_reference_t
<_It
>>)
1599 auto&& __tmp
= *_M_it
;
1600 return std::__addressof(__tmp
);
1603 return _Common_iter_proxy(*_M_it
);
1609 __glibcxx_assert(_M_index
== 0);
1617 __glibcxx_assert(_M_index
== 0);
1618 if constexpr (forward_iterator
<_It
>)
1620 common_iterator __tmp
= *this;
1628 template<typename _It2
, sentinel_for
<_It
> _Sent2
>
1629 requires sentinel_for
<_Sent
, _It2
>
1631 operator==(const common_iterator
& __x
,
1632 const common_iterator
<_It2
, _Sent2
>& __y
)
1634 switch(__x
._M_index
<< 2 | __y
._M_index
)
1640 return __x
._M_it
== __y
._M_sent
;
1642 return __x
._M_sent
== __y
._M_it
;
1644 __glibcxx_assert(__x
._M_has_value());
1645 __glibcxx_assert(__y
._M_has_value());
1646 __builtin_unreachable();
1650 template<typename _It2
, sentinel_for
<_It
> _Sent2
>
1651 requires sentinel_for
<_Sent
, _It2
> && equality_comparable_with
<_It
, _It2
>
1653 operator==(const common_iterator
& __x
,
1654 const common_iterator
<_It2
, _Sent2
>& __y
)
1656 switch(__x
._M_index
<< 2 | __y
._M_index
)
1661 return __x
._M_it
== __y
._M_it
;
1663 return __x
._M_it
== __y
._M_sent
;
1665 return __x
._M_sent
== __y
._M_it
;
1667 __glibcxx_assert(__x
._M_has_value());
1668 __glibcxx_assert(__y
._M_has_value());
1669 __builtin_unreachable();
1673 template<sized_sentinel_for
<_It
> _It2
, sized_sentinel_for
<_It
> _Sent2
>
1674 requires sized_sentinel_for
<_Sent
, _It2
>
1675 friend iter_difference_t
<_It2
>
1676 operator-(const common_iterator
& __x
,
1677 const common_iterator
<_It2
, _Sent2
>& __y
)
1679 switch(__x
._M_index
<< 2 | __y
._M_index
)
1684 return __x
._M_it
- __y
._M_it
;
1686 return __x
._M_it
- __y
._M_sent
;
1688 return __x
._M_sent
- __y
._M_it
;
1690 __glibcxx_assert(__x
._M_has_value());
1691 __glibcxx_assert(__y
._M_has_value());
1692 __builtin_unreachable();
1696 friend iter_rvalue_reference_t
<_It
>
1697 iter_move(const common_iterator
& __i
)
1698 noexcept(noexcept(ranges::iter_move(std::declval
<const _It
&>())))
1699 requires input_iterator
<_It
>
1701 __glibcxx_assert(__i
._M_index
== 0);
1702 return ranges::iter_move(__i
._M_it
);
1705 template<indirectly_swappable
<_It
> _It2
, typename _Sent2
>
1707 iter_swap(const common_iterator
& __x
,
1708 const common_iterator
<_It2
, _Sent2
>& __y
)
1709 noexcept(noexcept(ranges::iter_swap(std::declval
<const _It
&>(),
1710 std::declval
<const _It2
&>())))
1712 __glibcxx_assert(__x
._M_index
== 0);
1713 __glibcxx_assert(__y
._M_index
== 0);
1714 return ranges::iter_swap(__x
._M_it
, __y
._M_it
);
1718 template<input_or_output_iterator _It2
, sentinel_for
<_It2
> _Sent2
>
1719 friend class common_iterator
;
1721 bool _M_has_value() const noexcept
{ return _M_index
< 2; }
1727 unsigned char _M_valueless
;
1729 unsigned char _M_index
; // 0==_M_it, 1==_M_sent, 2==valueless
1732 template<typename _It
, typename _Sent
>
1733 struct incrementable_traits
<common_iterator
<_It
, _Sent
>>
1735 using difference_type
= iter_difference_t
<_It
>;
1740 // FIXME: This has to be at namespace-scope because of PR 92103.
1741 template<typename _It
, typename _Sent
>
1742 struct __common_iter_ptr
1747 template<typename _It
, typename _Sent
>
1748 requires
__detail::__common_iter_has_arrow
<_It
>
1749 struct __common_iter_ptr
<_It
, _Sent
>
1751 using common_iterator
= std::common_iterator
<_It
, _Sent
>;
1754 = decltype(std::declval
<const common_iterator
&>().operator->());
1756 } // namespace __detail
1758 template<input_iterator _It
, typename _Sent
>
1759 struct iterator_traits
<common_iterator
<_It
, _Sent
>>
1761 using iterator_concept
= conditional_t
<forward_iterator
<_It
>,
1762 forward_iterator_tag
, input_iterator_tag
>;
1763 using iterator_category
= __detail::__clamp_iter_cat
<
1764 typename iterator_traits
<_It
>::iterator_category
,
1765 forward_iterator_tag
, input_iterator_tag
>;
1766 using value_type
= iter_value_t
<_It
>;
1767 using difference_type
= iter_difference_t
<_It
>;
1768 using pointer
= typename
__detail::__common_iter_ptr
<_It
, _Sent
>::type
;
1769 using reference
= iter_reference_t
<_It
>;
1772 // [iterators.counted] Counted iterators
1774 /// An iterator adaptor that keeps track of the distance to the end.
1775 template<input_or_output_iterator _It
>
1776 class counted_iterator
1779 using iterator_type
= _It
;
1781 constexpr counted_iterator() = default;
1784 counted_iterator(_It __i
, iter_difference_t
<_It
> __n
)
1785 : _M_current(std::move(__i
)), _M_length(__n
)
1786 { __glibcxx_assert(__n
>= 0); }
1788 template<typename _It2
>
1789 requires convertible_to
<const _It2
&, _It
>
1791 counted_iterator(const counted_iterator
<_It2
>& __x
)
1792 : _M_current(__x
._M_current
), _M_length(__x
._M_length
)
1795 template<typename _It2
>
1796 requires assignable_from
<_It
&, const _It2
&>
1797 constexpr counted_iterator
&
1798 operator=(const counted_iterator
<_It2
>& __x
)
1800 _M_current
= __x
._M_current
;
1801 _M_length
= __x
._M_length
;
1807 noexcept(is_nothrow_copy_constructible_v
<_It
>)
1808 requires copy_constructible
<_It
>
1809 { return _M_current
; }
1813 noexcept(is_nothrow_move_constructible_v
<_It
>)
1814 { return std::move(_M_current
); }
1816 constexpr iter_difference_t
<_It
>
1817 count() const noexcept
{ return _M_length
; }
1819 constexpr decltype(auto)
1821 noexcept(noexcept(*_M_current
))
1822 { return *_M_current
; }
1824 constexpr decltype(auto)
1826 noexcept(noexcept(*_M_current
))
1827 requires
__detail::__dereferenceable
<const _It
>
1828 { return *_M_current
; }
1830 constexpr counted_iterator
&
1833 __glibcxx_assert(_M_length
> 0);
1842 __glibcxx_assert(_M_length
> 0);
1846 return _M_current
++;
1854 constexpr counted_iterator
1855 operator++(int) requires forward_iterator
<_It
>
1862 constexpr counted_iterator
&
1863 operator--() requires bidirectional_iterator
<_It
>
1870 constexpr counted_iterator
1871 operator--(int) requires bidirectional_iterator
<_It
>
1878 constexpr counted_iterator
1879 operator+(iter_difference_t
<_It
> __n
) const
1880 requires random_access_iterator
<_It
>
1881 { return counted_iterator(_M_current
+ __n
, _M_length
- __n
); }
1883 friend constexpr counted_iterator
1884 operator+(iter_difference_t
<_It
> __n
, const counted_iterator
& __x
)
1885 requires random_access_iterator
<_It
>
1886 { return __x
+ __n
; }
1888 constexpr counted_iterator
&
1889 operator+=(iter_difference_t
<_It
> __n
)
1890 requires random_access_iterator
<_It
>
1892 __glibcxx_assert(__n
<= _M_length
);
1898 constexpr counted_iterator
1899 operator-(iter_difference_t
<_It
> __n
) const
1900 requires random_access_iterator
<_It
>
1901 { return counted_iterator(_M_current
- __n
, _M_length
+ __n
); }
1903 template<common_with
<_It
> _It2
>
1904 friend constexpr iter_difference_t
<_It2
>
1905 operator-(const counted_iterator
& __x
,
1906 const counted_iterator
<_It2
>& __y
)
1907 { return __y
._M_length
- __x
._M_length
; }
1909 friend constexpr iter_difference_t
<_It
>
1910 operator-(const counted_iterator
& __x
, default_sentinel_t
)
1911 { return -__x
._M_length
; }
1913 friend constexpr iter_difference_t
<_It
>
1914 operator-(default_sentinel_t
, const counted_iterator
& __y
)
1915 { return __y
._M_length
; }
1917 constexpr counted_iterator
&
1918 operator-=(iter_difference_t
<_It
> __n
)
1919 requires random_access_iterator
<_It
>
1921 __glibcxx_assert(-__n
<= _M_length
);
1927 constexpr decltype(auto)
1928 operator[](iter_difference_t
<_It
> __n
) const
1929 noexcept(noexcept(_M_current
[__n
]))
1930 requires random_access_iterator
<_It
>
1932 __glibcxx_assert(__n
< _M_length
);
1933 return _M_current
[__n
];
1936 template<common_with
<_It
> _It2
>
1937 friend constexpr bool
1938 operator==(const counted_iterator
& __x
,
1939 const counted_iterator
<_It2
>& __y
)
1940 { return __x
._M_length
== __y
._M_length
; }
1942 friend constexpr bool
1943 operator==(const counted_iterator
& __x
, default_sentinel_t
)
1944 { return __x
._M_length
== 0; }
1946 template<common_with
<_It
> _It2
>
1947 friend constexpr strong_ordering
1948 operator<=>(const counted_iterator
& __x
,
1949 const counted_iterator
<_It2
>& __y
)
1950 { return __y
._M_length
<=> __x
._M_length
; }
1952 friend constexpr iter_rvalue_reference_t
<_It
>
1953 iter_move(const counted_iterator
& __i
)
1954 noexcept(noexcept(ranges::iter_move(__i
._M_current
)))
1955 requires input_iterator
<_It
>
1956 { return ranges::iter_move(__i
._M_current
); }
1958 template<indirectly_swappable
<_It
> _It2
>
1959 friend constexpr void
1960 iter_swap(const counted_iterator
& __x
,
1961 const counted_iterator
<_It2
>& __y
)
1962 noexcept(noexcept(ranges::iter_swap(__x
._M_current
, __y
._M_current
)))
1963 { ranges::iter_swap(__x
._M_current
, __y
._M_current
); }
1966 template<input_or_output_iterator _It2
> friend class counted_iterator
;
1968 _It _M_current
= _It();
1969 iter_difference_t
<_It
> _M_length
= 0;
1972 template<typename _It
>
1973 struct incrementable_traits
<counted_iterator
<_It
>>
1975 using difference_type
= iter_difference_t
<_It
>;
1978 template<input_iterator _It
>
1979 struct iterator_traits
<counted_iterator
<_It
>> : iterator_traits
<_It
>
1981 using pointer
= void;
1985 // @} group iterators
1987 template<typename _Iterator
>
1989 __niter_base(move_iterator
<_Iterator
> __it
)
1990 -> decltype(make_move_iterator(__niter_base(__it
.base())))
1991 { return make_move_iterator(__niter_base(__it
.base())); }
1993 template<typename _Iterator
>
1994 struct __is_move_iterator
<move_iterator
<_Iterator
> >
1996 enum { __value
= 1 };
1997 typedef __true_type __type
;
2000 template<typename _Iterator
>
2002 __miter_base(move_iterator
<_Iterator
> __it
)
2003 -> decltype(__miter_base(__it
.base()))
2004 { return __miter_base(__it
.base()); }
2006 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2007 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2008 std::__make_move_if_noexcept_iterator(_Iter)
2010 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2011 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2014 #if __cpp_deduction_guides >= 201606
2015 // These helper traits are used for deduction guides
2016 // of associative containers.
2017 template<typename _InputIterator
>
2018 using __iter_key_t
= remove_const_t
<
2019 typename iterator_traits
<_InputIterator
>::value_type::first_type
>;
2021 template<typename _InputIterator
>
2022 using __iter_val_t
=
2023 typename iterator_traits
<_InputIterator
>::value_type::second_type
;
2025 template<typename _T1
, typename _T2
>
2028 template<typename _InputIterator
>
2029 using __iter_to_alloc_t
=
2030 pair
<add_const_t
<__iter_key_t
<_InputIterator
>>,
2031 __iter_val_t
<_InputIterator
>>;
2032 #endif // __cpp_deduction_guides
2034 _GLIBCXX_END_NAMESPACE_VERSION
2037 #ifdef _GLIBCXX_DEBUG
2038 # include <debug/stl_iterator.h>