1 // Iterators -*- C++ -*-
3 // Copyright (C) 2001-2021 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 > 201703L
73 # define __cpp_lib_array_constexpr 201811L
74 # define __cpp_lib_constexpr_iterator 201811L
75 #elif __cplusplus == 201703L
76 # define __cpp_lib_array_constexpr 201803L
79 #if __cplusplus > 201703L
82 # include <bits/exception_defines.h>
83 # include <bits/iterator_concepts.h>
86 namespace std
_GLIBCXX_VISIBILITY(default)
88 _GLIBCXX_BEGIN_NAMESPACE_VERSION
91 * @addtogroup iterators
95 #if __cplusplus > 201703L && __cpp_lib_concepts
98 // Weaken iterator_category _Cat to _Limit if it is derived from that,
99 // otherwise use _Otherwise.
100 template<typename _Cat
, typename _Limit
, typename _Otherwise
= _Cat
>
101 using __clamp_iter_cat
102 = conditional_t
<derived_from
<_Cat
, _Limit
>, _Limit
, _Otherwise
>;
106 // 24.4.1 Reverse iterators
108 * Bidirectional and random access iterators have corresponding reverse
109 * %iterator adaptors that iterate through the data structure in the
110 * opposite direction. They have the same signatures as the corresponding
111 * iterators. The fundamental relation between a reverse %iterator and its
112 * corresponding %iterator @c i is established by the identity:
114 * &*(reverse_iterator(i)) == &*(i - 1)
117 * <em>This mapping is dictated by the fact that while there is always a
118 * pointer past the end of an array, there might not be a valid pointer
119 * before the beginning of an array.</em> [24.4.1]/1,2
121 * Reverse iterators can be tricky and surprising at first. Their
122 * semantics make sense, however, and the trickiness is a side effect of
123 * the requirement that the iterators must be safe.
125 template<typename _Iterator
>
126 class reverse_iterator
127 : public iterator
<typename iterator_traits
<_Iterator
>::iterator_category
,
128 typename iterator_traits
<_Iterator
>::value_type
,
129 typename iterator_traits
<_Iterator
>::difference_type
,
130 typename iterator_traits
<_Iterator
>::pointer
,
131 typename iterator_traits
<_Iterator
>::reference
>
133 template<typename _Iter
>
134 friend class reverse_iterator
;
136 #if __cpp_lib_concepts
137 // _GLIBCXX_RESOLVE_LIB_DEFECTS
138 // 3435. three_way_comparable_with<reverse_iterator<int*>, [...]>
139 template<typename _Iter
>
140 static constexpr bool __convertible
= !is_same_v
<_Iter
, _Iterator
>
141 && convertible_to
<const _Iter
&, _Iterator
>;
147 typedef iterator_traits
<_Iterator
> __traits_type
;
150 typedef _Iterator iterator_type
;
151 typedef typename
__traits_type::difference_type difference_type
;
152 typedef typename
__traits_type::pointer pointer
;
153 typedef typename
__traits_type::reference reference
;
155 #if __cplusplus > 201703L && __cpp_lib_concepts
156 using iterator_concept
157 = conditional_t
<random_access_iterator
<_Iterator
>,
158 random_access_iterator_tag
,
159 bidirectional_iterator_tag
>;
160 using iterator_category
161 = __detail::__clamp_iter_cat
<typename
__traits_type::iterator_category
,
162 random_access_iterator_tag
>;
166 * The default constructor value-initializes member @p current.
167 * If it is a pointer, that means it is zero-initialized.
169 // _GLIBCXX_RESOLVE_LIB_DEFECTS
170 // 235 No specification of default ctor for reverse_iterator
171 // 1012. reverse_iterator default ctor should value initialize
173 reverse_iterator() : current() { }
176 * This %iterator will move in the opposite direction that @p x does.
178 explicit _GLIBCXX17_CONSTEXPR
179 reverse_iterator(iterator_type __x
) : current(__x
) { }
182 * The copy constructor is normal.
185 reverse_iterator(const reverse_iterator
& __x
)
186 : current(__x
.current
) { }
188 #if __cplusplus >= 201103L
189 reverse_iterator
& operator=(const reverse_iterator
&) = default;
193 * A %reverse_iterator across other types can be copied if the
194 * underlying %iterator can be converted to the type of @c current.
196 template<typename _Iter
>
197 #if __cpp_lib_concepts
198 requires __convertible
<_Iter
>
201 reverse_iterator(const reverse_iterator
<_Iter
>& __x
)
202 : current(__x
.current
) { }
204 #if __cplusplus >= 201103L
205 template<typename _Iter
>
206 #if __cpp_lib_concepts
207 requires __convertible
<_Iter
>
208 && assignable_from
<_Iterator
&, const _Iter
&>
212 operator=(const reverse_iterator
<_Iter
>& __x
)
214 current
= __x
.current
;
220 * @return @c current, the %iterator used for underlying work.
222 _GLIBCXX17_CONSTEXPR iterator_type
227 * @return A reference to the value at @c --current
229 * This requires that @c --current is dereferenceable.
231 * @warning This implementation requires that for an iterator of the
232 * underlying iterator type, @c x, a reference obtained by
233 * @c *x remains valid after @c x has been modified or
234 * destroyed. This is a bug: http://gcc.gnu.org/PR51823
236 _GLIBCXX17_CONSTEXPR reference
239 _Iterator __tmp
= current
;
244 * @return A pointer to the value at @c --current
246 * This requires that @c --current is dereferenceable.
248 _GLIBCXX17_CONSTEXPR pointer
250 #if __cplusplus > 201703L && __cpp_concepts >= 201907L
251 requires is_pointer_v
<_Iterator
>
252 || requires(const _Iterator __i
) { __i
.operator->(); }
255 // _GLIBCXX_RESOLVE_LIB_DEFECTS
256 // 1052. operator-> should also support smart pointers
257 _Iterator __tmp
= current
;
259 return _S_to_pointer(__tmp
);
265 * Decrements the underlying iterator.
267 _GLIBCXX17_CONSTEXPR reverse_iterator
&
275 * @return The original value of @c *this
277 * Decrements the underlying iterator.
279 _GLIBCXX17_CONSTEXPR reverse_iterator
282 reverse_iterator __tmp
= *this;
290 * Increments the underlying iterator.
292 _GLIBCXX17_CONSTEXPR reverse_iterator
&
300 * @return A reverse_iterator with the previous value of @c *this
302 * Increments the underlying iterator.
304 _GLIBCXX17_CONSTEXPR reverse_iterator
307 reverse_iterator __tmp
= *this;
313 * @return A reverse_iterator that refers to @c current - @a __n
315 * The underlying iterator must be a Random Access Iterator.
317 _GLIBCXX17_CONSTEXPR reverse_iterator
318 operator+(difference_type __n
) const
319 { return reverse_iterator(current
- __n
); }
324 * Moves the underlying iterator backwards @a __n steps.
325 * The underlying iterator must be a Random Access Iterator.
327 _GLIBCXX17_CONSTEXPR reverse_iterator
&
328 operator+=(difference_type __n
)
335 * @return A reverse_iterator that refers to @c current - @a __n
337 * The underlying iterator must be a Random Access Iterator.
339 _GLIBCXX17_CONSTEXPR reverse_iterator
340 operator-(difference_type __n
) const
341 { return reverse_iterator(current
+ __n
); }
346 * Moves the underlying iterator forwards @a __n steps.
347 * The underlying iterator must be a Random Access Iterator.
349 _GLIBCXX17_CONSTEXPR reverse_iterator
&
350 operator-=(difference_type __n
)
357 * @return The value at @c current - @a __n - 1
359 * The underlying iterator must be a Random Access Iterator.
361 _GLIBCXX17_CONSTEXPR reference
362 operator[](difference_type __n
) const
363 { return *(*this + __n
); }
365 #if __cplusplus > 201703L && __cpp_lib_concepts
366 friend constexpr iter_rvalue_reference_t
<_Iterator
>
367 iter_move(const reverse_iterator
& __i
)
368 noexcept(is_nothrow_copy_constructible_v
<_Iterator
>
369 && noexcept(ranges::iter_move(--std::declval
<_Iterator
&>())))
371 auto __tmp
= __i
.base();
372 return ranges::iter_move(--__tmp
);
375 template<indirectly_swappable
<_Iterator
> _Iter2
>
376 friend constexpr void
377 iter_swap(const reverse_iterator
& __x
,
378 const reverse_iterator
<_Iter2
>& __y
)
379 noexcept(is_nothrow_copy_constructible_v
<_Iterator
>
380 && is_nothrow_copy_constructible_v
<_Iter2
>
381 && noexcept(ranges::iter_swap(--std::declval
<_Iterator
&>(),
382 --std::declval
<_Iter2
&>())))
384 auto __xtmp
= __x
.base();
385 auto __ytmp
= __y
.base();
386 ranges::iter_swap(--__xtmp
, --__ytmp
);
391 template<typename _Tp
>
392 static _GLIBCXX17_CONSTEXPR _Tp
*
393 _S_to_pointer(_Tp
* __p
)
396 template<typename _Tp
>
397 static _GLIBCXX17_CONSTEXPR pointer
398 _S_to_pointer(_Tp __t
)
399 { return __t
.operator->(); }
404 * @param __x A %reverse_iterator.
405 * @param __y A %reverse_iterator.
406 * @return A simple bool.
408 * Reverse iterators forward comparisons to their underlying base()
412 #if __cplusplus <= 201703L || ! defined __cpp_lib_concepts
413 template<typename _Iterator
>
414 inline _GLIBCXX17_CONSTEXPR
bool
415 operator==(const reverse_iterator
<_Iterator
>& __x
,
416 const reverse_iterator
<_Iterator
>& __y
)
417 { return __x
.base() == __y
.base(); }
419 template<typename _Iterator
>
420 inline _GLIBCXX17_CONSTEXPR
bool
421 operator<(const reverse_iterator
<_Iterator
>& __x
,
422 const reverse_iterator
<_Iterator
>& __y
)
423 { return __y
.base() < __x
.base(); }
425 template<typename _Iterator
>
426 inline _GLIBCXX17_CONSTEXPR
bool
427 operator!=(const reverse_iterator
<_Iterator
>& __x
,
428 const reverse_iterator
<_Iterator
>& __y
)
429 { return !(__x
== __y
); }
431 template<typename _Iterator
>
432 inline _GLIBCXX17_CONSTEXPR
bool
433 operator>(const reverse_iterator
<_Iterator
>& __x
,
434 const reverse_iterator
<_Iterator
>& __y
)
435 { return __y
< __x
; }
437 template<typename _Iterator
>
438 inline _GLIBCXX17_CONSTEXPR
bool
439 operator<=(const reverse_iterator
<_Iterator
>& __x
,
440 const reverse_iterator
<_Iterator
>& __y
)
441 { return !(__y
< __x
); }
443 template<typename _Iterator
>
444 inline _GLIBCXX17_CONSTEXPR
bool
445 operator>=(const reverse_iterator
<_Iterator
>& __x
,
446 const reverse_iterator
<_Iterator
>& __y
)
447 { return !(__x
< __y
); }
449 // _GLIBCXX_RESOLVE_LIB_DEFECTS
450 // DR 280. Comparison of reverse_iterator to const reverse_iterator.
452 template<typename _IteratorL
, typename _IteratorR
>
453 inline _GLIBCXX17_CONSTEXPR
bool
454 operator==(const reverse_iterator
<_IteratorL
>& __x
,
455 const reverse_iterator
<_IteratorR
>& __y
)
456 { return __x
.base() == __y
.base(); }
458 template<typename _IteratorL
, typename _IteratorR
>
459 inline _GLIBCXX17_CONSTEXPR
bool
460 operator<(const reverse_iterator
<_IteratorL
>& __x
,
461 const reverse_iterator
<_IteratorR
>& __y
)
462 { return __x
.base() > __y
.base(); }
464 template<typename _IteratorL
, typename _IteratorR
>
465 inline _GLIBCXX17_CONSTEXPR
bool
466 operator!=(const reverse_iterator
<_IteratorL
>& __x
,
467 const reverse_iterator
<_IteratorR
>& __y
)
468 { return __x
.base() != __y
.base(); }
470 template<typename _IteratorL
, typename _IteratorR
>
471 inline _GLIBCXX17_CONSTEXPR
bool
472 operator>(const reverse_iterator
<_IteratorL
>& __x
,
473 const reverse_iterator
<_IteratorR
>& __y
)
474 { return __x
.base() < __y
.base(); }
476 template<typename _IteratorL
, typename _IteratorR
>
477 inline _GLIBCXX17_CONSTEXPR
bool
478 operator<=(const reverse_iterator
<_IteratorL
>& __x
,
479 const reverse_iterator
<_IteratorR
>& __y
)
480 { return __x
.base() >= __y
.base(); }
482 template<typename _IteratorL
, typename _IteratorR
>
483 inline _GLIBCXX17_CONSTEXPR
bool
484 operator>=(const reverse_iterator
<_IteratorL
>& __x
,
485 const reverse_iterator
<_IteratorR
>& __y
)
486 { return __x
.base() <= __y
.base(); }
488 template<typename _IteratorL
, typename _IteratorR
>
490 operator==(const reverse_iterator
<_IteratorL
>& __x
,
491 const reverse_iterator
<_IteratorR
>& __y
)
492 requires requires
{ { __x
.base() == __y
.base() } -> convertible_to
<bool>; }
493 { return __x
.base() == __y
.base(); }
495 template<typename _IteratorL
, typename _IteratorR
>
497 operator!=(const reverse_iterator
<_IteratorL
>& __x
,
498 const reverse_iterator
<_IteratorR
>& __y
)
499 requires requires
{ { __x
.base() != __y
.base() } -> convertible_to
<bool>; }
500 { return __x
.base() != __y
.base(); }
502 template<typename _IteratorL
, typename _IteratorR
>
504 operator<(const reverse_iterator
<_IteratorL
>& __x
,
505 const reverse_iterator
<_IteratorR
>& __y
)
506 requires requires
{ { __x
.base() > __y
.base() } -> convertible_to
<bool>; }
507 { return __x
.base() > __y
.base(); }
509 template<typename _IteratorL
, typename _IteratorR
>
511 operator>(const reverse_iterator
<_IteratorL
>& __x
,
512 const reverse_iterator
<_IteratorR
>& __y
)
513 requires requires
{ { __x
.base() < __y
.base() } -> convertible_to
<bool>; }
514 { return __x
.base() < __y
.base(); }
516 template<typename _IteratorL
, typename _IteratorR
>
518 operator<=(const reverse_iterator
<_IteratorL
>& __x
,
519 const reverse_iterator
<_IteratorR
>& __y
)
520 requires requires
{ { __x
.base() >= __y
.base() } -> convertible_to
<bool>; }
521 { return __x
.base() >= __y
.base(); }
523 template<typename _IteratorL
, typename _IteratorR
>
525 operator>=(const reverse_iterator
<_IteratorL
>& __x
,
526 const reverse_iterator
<_IteratorR
>& __y
)
527 requires requires
{ { __x
.base() <= __y
.base() } -> convertible_to
<bool>; }
528 { return __x
.base() <= __y
.base(); }
530 template<typename _IteratorL
,
531 three_way_comparable_with
<_IteratorL
> _IteratorR
>
532 constexpr compare_three_way_result_t
<_IteratorL
, _IteratorR
>
533 operator<=>(const reverse_iterator
<_IteratorL
>& __x
,
534 const reverse_iterator
<_IteratorR
>& __y
)
535 { return __y
.base() <=> __x
.base(); }
539 #if __cplusplus < 201103L
540 template<typename _Iterator
>
541 inline typename reverse_iterator
<_Iterator
>::difference_type
542 operator-(const reverse_iterator
<_Iterator
>& __x
,
543 const reverse_iterator
<_Iterator
>& __y
)
544 { return __y
.base() - __x
.base(); }
546 template<typename _IteratorL
, typename _IteratorR
>
547 inline typename reverse_iterator
<_IteratorL
>::difference_type
548 operator-(const reverse_iterator
<_IteratorL
>& __x
,
549 const reverse_iterator
<_IteratorR
>& __y
)
550 { return __y
.base() - __x
.base(); }
552 // _GLIBCXX_RESOLVE_LIB_DEFECTS
553 // DR 685. reverse_iterator/move_iterator difference has invalid signatures
554 template<typename _IteratorL
, typename _IteratorR
>
555 inline _GLIBCXX17_CONSTEXPR
auto
556 operator-(const reverse_iterator
<_IteratorL
>& __x
,
557 const reverse_iterator
<_IteratorR
>& __y
)
558 -> decltype(__y
.base() - __x
.base())
559 { return __y
.base() - __x
.base(); }
562 template<typename _Iterator
>
563 inline _GLIBCXX17_CONSTEXPR reverse_iterator
<_Iterator
>
564 operator+(typename reverse_iterator
<_Iterator
>::difference_type __n
,
565 const reverse_iterator
<_Iterator
>& __x
)
566 { return reverse_iterator
<_Iterator
>(__x
.base() - __n
); }
568 #if __cplusplus >= 201103L
569 // Same as C++14 make_reverse_iterator but used in C++11 mode too.
570 template<typename _Iterator
>
571 inline _GLIBCXX17_CONSTEXPR reverse_iterator
<_Iterator
>
572 __make_reverse_iterator(_Iterator __i
)
573 { return reverse_iterator
<_Iterator
>(__i
); }
575 # if __cplusplus >= 201402L
576 # define __cpp_lib_make_reverse_iterator 201402
578 // _GLIBCXX_RESOLVE_LIB_DEFECTS
579 // DR 2285. make_reverse_iterator
580 /// Generator function for reverse_iterator.
581 template<typename _Iterator
>
582 inline _GLIBCXX17_CONSTEXPR reverse_iterator
<_Iterator
>
583 make_reverse_iterator(_Iterator __i
)
584 { return reverse_iterator
<_Iterator
>(__i
); }
586 # if __cplusplus > 201703L && defined __cpp_lib_concepts
587 template<typename _Iterator1
, typename _Iterator2
>
588 requires (!sized_sentinel_for
<_Iterator1
, _Iterator2
>)
589 inline constexpr bool
590 disable_sized_sentinel_for
<reverse_iterator
<_Iterator1
>,
591 reverse_iterator
<_Iterator2
>> = true;
595 template<typename _Iterator
>
598 __niter_base(reverse_iterator
<_Iterator
> __it
)
599 -> decltype(__make_reverse_iterator(__niter_base(__it
.base())))
600 { return __make_reverse_iterator(__niter_base(__it
.base())); }
602 template<typename _Iterator
>
603 struct __is_move_iterator
<reverse_iterator
<_Iterator
> >
604 : __is_move_iterator
<_Iterator
>
607 template<typename _Iterator
>
610 __miter_base(reverse_iterator
<_Iterator
> __it
)
611 -> decltype(__make_reverse_iterator(__miter_base(__it
.base())))
612 { return __make_reverse_iterator(__miter_base(__it
.base())); }
615 // 24.4.2.2.1 back_insert_iterator
617 * @brief Turns assignment into insertion.
619 * These are output iterators, constructed from a container-of-T.
620 * Assigning a T to the iterator appends it to the container using
623 * Tip: Using the back_inserter function to create these iterators can
626 template<typename _Container
>
627 class back_insert_iterator
628 : public iterator
<output_iterator_tag
, void, void, void, void>
631 _Container
* container
;
634 /// A nested typedef for the type of whatever container you used.
635 typedef _Container container_type
;
636 #if __cplusplus > 201703L
637 using difference_type
= ptrdiff_t;
639 constexpr back_insert_iterator() noexcept
: container(nullptr) { }
642 /// The only way to create this %iterator is with a container.
643 explicit _GLIBCXX20_CONSTEXPR
644 back_insert_iterator(_Container
& __x
)
645 : container(std::__addressof(__x
)) { }
648 * @param __value An instance of whatever type
649 * container_type::const_reference is; presumably a
650 * reference-to-const T for container<T>.
651 * @return This %iterator, for chained operations.
653 * This kind of %iterator doesn't really have a @a position in the
654 * container (you can think of the position as being permanently at
655 * the end, if you like). Assigning a value to the %iterator will
656 * always append the value to the end of the container.
658 #if __cplusplus < 201103L
659 back_insert_iterator
&
660 operator=(typename
_Container::const_reference __value
)
662 container
->push_back(__value
);
667 back_insert_iterator
&
668 operator=(const typename
_Container::value_type
& __value
)
670 container
->push_back(__value
);
675 back_insert_iterator
&
676 operator=(typename
_Container::value_type
&& __value
)
678 container
->push_back(std::move(__value
));
683 /// Simply returns *this.
685 back_insert_iterator
&
689 /// Simply returns *this. (This %iterator does not @a move.)
691 back_insert_iterator
&
695 /// Simply returns *this. (This %iterator does not @a move.)
703 * @param __x A container of arbitrary type.
704 * @return An instance of back_insert_iterator working on @p __x.
706 * This wrapper function helps in creating back_insert_iterator instances.
707 * Typing the name of the %iterator requires knowing the precise full
708 * type of the container, which can be tedious and impedes generic
709 * programming. Using this function lets you take advantage of automatic
710 * template parameter deduction, making the compiler match the correct
713 template<typename _Container
>
715 inline back_insert_iterator
<_Container
>
716 back_inserter(_Container
& __x
)
717 { return back_insert_iterator
<_Container
>(__x
); }
720 * @brief Turns assignment into insertion.
722 * These are output iterators, constructed from a container-of-T.
723 * Assigning a T to the iterator prepends it to the container using
726 * Tip: Using the front_inserter function to create these iterators can
729 template<typename _Container
>
730 class front_insert_iterator
731 : public iterator
<output_iterator_tag
, void, void, void, void>
734 _Container
* container
;
737 /// A nested typedef for the type of whatever container you used.
738 typedef _Container container_type
;
739 #if __cplusplus > 201703L
740 using difference_type
= ptrdiff_t;
742 constexpr front_insert_iterator() noexcept
: container(nullptr) { }
745 /// The only way to create this %iterator is with a container.
746 explicit _GLIBCXX20_CONSTEXPR
747 front_insert_iterator(_Container
& __x
)
748 : container(std::__addressof(__x
)) { }
751 * @param __value An instance of whatever type
752 * container_type::const_reference is; presumably a
753 * reference-to-const T for container<T>.
754 * @return This %iterator, for chained operations.
756 * This kind of %iterator doesn't really have a @a position in the
757 * container (you can think of the position as being permanently at
758 * the front, if you like). Assigning a value to the %iterator will
759 * always prepend the value to the front of the container.
761 #if __cplusplus < 201103L
762 front_insert_iterator
&
763 operator=(typename
_Container::const_reference __value
)
765 container
->push_front(__value
);
770 front_insert_iterator
&
771 operator=(const typename
_Container::value_type
& __value
)
773 container
->push_front(__value
);
778 front_insert_iterator
&
779 operator=(typename
_Container::value_type
&& __value
)
781 container
->push_front(std::move(__value
));
786 /// Simply returns *this.
788 front_insert_iterator
&
792 /// Simply returns *this. (This %iterator does not @a move.)
794 front_insert_iterator
&
798 /// Simply returns *this. (This %iterator does not @a move.)
800 front_insert_iterator
806 * @param __x A container of arbitrary type.
807 * @return An instance of front_insert_iterator working on @p x.
809 * This wrapper function helps in creating front_insert_iterator instances.
810 * Typing the name of the %iterator requires knowing the precise full
811 * type of the container, which can be tedious and impedes generic
812 * programming. Using this function lets you take advantage of automatic
813 * template parameter deduction, making the compiler match the correct
816 template<typename _Container
>
818 inline front_insert_iterator
<_Container
>
819 front_inserter(_Container
& __x
)
820 { return front_insert_iterator
<_Container
>(__x
); }
823 * @brief Turns assignment into insertion.
825 * These are output iterators, constructed from a container-of-T.
826 * Assigning a T to the iterator inserts it in the container at the
827 * %iterator's position, rather than overwriting the value at that
830 * (Sequences will actually insert a @e copy of the value before the
831 * %iterator's position.)
833 * Tip: Using the inserter function to create these iterators can
836 template<typename _Container
>
837 class insert_iterator
838 : public iterator
<output_iterator_tag
, void, void, void, void>
840 #if __cplusplus > 201703L && defined __cpp_lib_concepts
841 using _Iter
= std::__detail::__range_iter_t
<_Container
>;
844 _Container
* container
= nullptr;
845 _Iter iter
= _Iter();
847 typedef typename
_Container::iterator _Iter
;
850 _Container
* container
;
855 /// A nested typedef for the type of whatever container you used.
856 typedef _Container container_type
;
858 #if __cplusplus > 201703L && defined __cpp_lib_concepts
859 using difference_type
= ptrdiff_t;
861 insert_iterator() = default;
865 * The only way to create this %iterator is with a container and an
866 * initial position (a normal %iterator into the container).
869 insert_iterator(_Container
& __x
, _Iter __i
)
870 : container(std::__addressof(__x
)), iter(__i
) {}
873 * @param __value An instance of whatever type
874 * container_type::const_reference is; presumably a
875 * reference-to-const T for container<T>.
876 * @return This %iterator, for chained operations.
878 * This kind of %iterator maintains its own position in the
879 * container. Assigning a value to the %iterator will insert the
880 * value into the container at the place before the %iterator.
882 * The position is maintained such that subsequent assignments will
883 * insert values immediately after one another. For example,
885 * // vector v contains A and Z
887 * insert_iterator i (v, ++v.begin());
892 * // vector v contains A, 1, 2, 3, and Z
895 #if __cplusplus < 201103L
897 operator=(typename
_Container::const_reference __value
)
899 iter
= container
->insert(iter
, __value
);
906 operator=(const typename
_Container::value_type
& __value
)
908 iter
= container
->insert(iter
, __value
);
915 operator=(typename
_Container::value_type
&& __value
)
917 iter
= container
->insert(iter
, std::move(__value
));
923 /// Simply returns *this.
929 /// Simply returns *this. (This %iterator does not @a move.)
935 /// Simply returns *this. (This %iterator does not @a move.)
943 * @param __x A container of arbitrary type.
944 * @param __i An iterator into the container.
945 * @return An instance of insert_iterator working on @p __x.
947 * This wrapper function helps in creating insert_iterator instances.
948 * Typing the name of the %iterator requires knowing the precise full
949 * type of the container, which can be tedious and impedes generic
950 * programming. Using this function lets you take advantage of automatic
951 * template parameter deduction, making the compiler match the correct
954 #if __cplusplus > 201703L && defined __cpp_lib_concepts
955 template<typename _Container
>
956 constexpr insert_iterator
<_Container
>
957 inserter(_Container
& __x
, std::__detail::__range_iter_t
<_Container
> __i
)
958 { return insert_iterator
<_Container
>(__x
, __i
); }
960 template<typename _Container
>
961 inline insert_iterator
<_Container
>
962 inserter(_Container
& __x
, typename
_Container::iterator __i
)
963 { return insert_iterator
<_Container
>(__x
, __i
); }
966 // @} group iterators
968 _GLIBCXX_END_NAMESPACE_VERSION
971 namespace __gnu_cxx
_GLIBCXX_VISIBILITY(default)
973 _GLIBCXX_BEGIN_NAMESPACE_VERSION
975 // This iterator adapter is @a normal in the sense that it does not
976 // change the semantics of any of the operators of its iterator
977 // parameter. Its primary purpose is to convert an iterator that is
978 // not a class, e.g. a pointer, into an iterator that is a class.
979 // The _Container parameter exists solely so that different containers
980 // using this template can instantiate different types, even if the
981 // _Iterator parameter is the same.
982 template<typename _Iterator
, typename _Container
>
983 class __normal_iterator
986 _Iterator _M_current
;
988 typedef std::iterator_traits
<_Iterator
> __traits_type
;
991 typedef _Iterator iterator_type
;
992 typedef typename
__traits_type::iterator_category iterator_category
;
993 typedef typename
__traits_type::value_type value_type
;
994 typedef typename
__traits_type::difference_type difference_type
;
995 typedef typename
__traits_type::reference reference
;
996 typedef typename
__traits_type::pointer pointer
;
998 #if __cplusplus > 201703L && __cpp_lib_concepts
999 using iterator_concept
= std::__detail::__iter_concept
<_Iterator
>;
1002 _GLIBCXX_CONSTEXPR
__normal_iterator() _GLIBCXX_NOEXCEPT
1003 : _M_current(_Iterator()) { }
1005 explicit _GLIBCXX20_CONSTEXPR
1006 __normal_iterator(const _Iterator
& __i
) _GLIBCXX_NOEXCEPT
1007 : _M_current(__i
) { }
1009 // Allow iterator to const_iterator conversion
1010 template<typename _Iter
>
1011 _GLIBCXX20_CONSTEXPR
1012 __normal_iterator(const __normal_iterator
<_Iter
,
1013 typename __enable_if
<
1014 (std::__are_same
<_Iter
, typename
_Container::pointer
>::__value
),
1015 _Container
>::__type
>& __i
) _GLIBCXX_NOEXCEPT
1016 : _M_current(__i
.base()) { }
1018 // Forward iterator requirements
1019 _GLIBCXX20_CONSTEXPR
1021 operator*() const _GLIBCXX_NOEXCEPT
1022 { return *_M_current
; }
1024 _GLIBCXX20_CONSTEXPR
1026 operator->() const _GLIBCXX_NOEXCEPT
1027 { return _M_current
; }
1029 _GLIBCXX20_CONSTEXPR
1031 operator++() _GLIBCXX_NOEXCEPT
1037 _GLIBCXX20_CONSTEXPR
1039 operator++(int) _GLIBCXX_NOEXCEPT
1040 { return __normal_iterator(_M_current
++); }
1042 // Bidirectional iterator requirements
1043 _GLIBCXX20_CONSTEXPR
1045 operator--() _GLIBCXX_NOEXCEPT
1051 _GLIBCXX20_CONSTEXPR
1053 operator--(int) _GLIBCXX_NOEXCEPT
1054 { return __normal_iterator(_M_current
--); }
1056 // Random access iterator requirements
1057 _GLIBCXX20_CONSTEXPR
1059 operator[](difference_type __n
) const _GLIBCXX_NOEXCEPT
1060 { return _M_current
[__n
]; }
1062 _GLIBCXX20_CONSTEXPR
1064 operator+=(difference_type __n
) _GLIBCXX_NOEXCEPT
1065 { _M_current
+= __n
; return *this; }
1067 _GLIBCXX20_CONSTEXPR
1069 operator+(difference_type __n
) const _GLIBCXX_NOEXCEPT
1070 { return __normal_iterator(_M_current
+ __n
); }
1072 _GLIBCXX20_CONSTEXPR
1074 operator-=(difference_type __n
) _GLIBCXX_NOEXCEPT
1075 { _M_current
-= __n
; return *this; }
1077 _GLIBCXX20_CONSTEXPR
1079 operator-(difference_type __n
) const _GLIBCXX_NOEXCEPT
1080 { return __normal_iterator(_M_current
- __n
); }
1082 _GLIBCXX20_CONSTEXPR
1084 base() const _GLIBCXX_NOEXCEPT
1085 { return _M_current
; }
1088 // Note: In what follows, the left- and right-hand-side iterators are
1089 // allowed to vary in types (conceptually in cv-qualification) so that
1090 // comparison between cv-qualified and non-cv-qualified iterators be
1091 // valid. However, the greedy and unfriendly operators in std::rel_ops
1092 // will make overload resolution ambiguous (when in scope) if we don't
1093 // provide overloads whose operands are of the same type. Can someone
1094 // remind me what generic programming is about? -- Gaby
1096 #if __cpp_lib_three_way_comparison
1097 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
1098 requires
requires (_IteratorL __lhs
, _IteratorR __rhs
)
1099 { { __lhs
== __rhs
} -> std::convertible_to
<bool>; }
1101 operator==(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
1102 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
1103 noexcept(noexcept(__lhs
.base() == __rhs
.base()))
1104 { return __lhs
.base() == __rhs
.base(); }
1106 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
1107 constexpr std::__detail::__synth3way_t
<_IteratorR
, _IteratorL
>
1108 operator<=>(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
1109 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
1110 noexcept(noexcept(std::__detail::__synth3way(__lhs
.base(), __rhs
.base())))
1111 { return std::__detail::__synth3way(__lhs
.base(), __rhs
.base()); }
1113 // Forward iterator requirements
1114 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
1115 _GLIBCXX20_CONSTEXPR
1117 operator==(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
1118 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
1120 { return __lhs
.base() == __rhs
.base(); }
1122 template<typename _Iterator
, typename _Container
>
1123 _GLIBCXX20_CONSTEXPR
1125 operator==(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
1126 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
1128 { return __lhs
.base() == __rhs
.base(); }
1130 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
1131 _GLIBCXX20_CONSTEXPR
1133 operator!=(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
1134 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
1136 { return __lhs
.base() != __rhs
.base(); }
1138 template<typename _Iterator
, typename _Container
>
1139 _GLIBCXX20_CONSTEXPR
1141 operator!=(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
1142 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
1144 { return __lhs
.base() != __rhs
.base(); }
1146 // Random access iterator requirements
1147 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
1149 operator<(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
1150 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
1152 { return __lhs
.base() < __rhs
.base(); }
1154 template<typename _Iterator
, typename _Container
>
1155 _GLIBCXX20_CONSTEXPR
1157 operator<(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
1158 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
1160 { return __lhs
.base() < __rhs
.base(); }
1162 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
1164 operator>(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
1165 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
1167 { return __lhs
.base() > __rhs
.base(); }
1169 template<typename _Iterator
, typename _Container
>
1170 _GLIBCXX20_CONSTEXPR
1172 operator>(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
1173 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
1175 { return __lhs
.base() > __rhs
.base(); }
1177 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
1179 operator<=(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
1180 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
1182 { return __lhs
.base() <= __rhs
.base(); }
1184 template<typename _Iterator
, typename _Container
>
1185 _GLIBCXX20_CONSTEXPR
1187 operator<=(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
1188 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
1190 { return __lhs
.base() <= __rhs
.base(); }
1192 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
1194 operator>=(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
1195 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
1197 { return __lhs
.base() >= __rhs
.base(); }
1199 template<typename _Iterator
, typename _Container
>
1200 _GLIBCXX20_CONSTEXPR
1202 operator>=(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
1203 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
1205 { return __lhs
.base() >= __rhs
.base(); }
1206 #endif // three-way comparison
1208 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1209 // According to the resolution of DR179 not only the various comparison
1210 // operators but also operator- must accept mixed iterator/const_iterator
1212 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
1213 #if __cplusplus >= 201103L
1215 _GLIBCXX20_CONSTEXPR
1217 operator-(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
1218 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
) noexcept
1219 -> decltype(__lhs
.base() - __rhs
.base())
1221 inline typename __normal_iterator
<_IteratorL
, _Container
>::difference_type
1222 operator-(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
1223 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
1225 { return __lhs
.base() - __rhs
.base(); }
1227 template<typename _Iterator
, typename _Container
>
1228 _GLIBCXX20_CONSTEXPR
1229 inline typename __normal_iterator
<_Iterator
, _Container
>::difference_type
1230 operator-(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
1231 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
1233 { return __lhs
.base() - __rhs
.base(); }
1235 template<typename _Iterator
, typename _Container
>
1236 _GLIBCXX20_CONSTEXPR
1237 inline __normal_iterator
<_Iterator
, _Container
>
1238 operator+(typename __normal_iterator
<_Iterator
, _Container
>::difference_type
1239 __n
, const __normal_iterator
<_Iterator
, _Container
>& __i
)
1241 { return __normal_iterator
<_Iterator
, _Container
>(__i
.base() + __n
); }
1243 _GLIBCXX_END_NAMESPACE_VERSION
1246 namespace std
_GLIBCXX_VISIBILITY(default)
1248 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1250 template<typename _Iterator
, typename _Container
>
1251 _GLIBCXX20_CONSTEXPR
1253 __niter_base(__gnu_cxx::__normal_iterator
<_Iterator
, _Container
> __it
)
1254 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible
<_Iterator
>::value
)
1255 { return __it
.base(); }
1257 #if __cplusplus >= 201103L
1259 * @addtogroup iterators
1263 #if __cplusplus > 201703L && __cpp_lib_concepts
1264 template<semiregular _Sent
>
1270 noexcept(is_nothrow_default_constructible_v
<_Sent
>)
1274 move_sentinel(_Sent __s
)
1275 noexcept(is_nothrow_move_constructible_v
<_Sent
>)
1276 : _M_last(std::move(__s
)) { }
1278 template<typename _S2
> requires convertible_to
<const _S2
&, _Sent
>
1280 move_sentinel(const move_sentinel
<_S2
>& __s
)
1281 noexcept(is_nothrow_constructible_v
<_Sent
, const _S2
&>)
1282 : _M_last(__s
.base())
1285 template<typename _S2
> requires assignable_from
<_Sent
&, const _S2
&>
1286 constexpr move_sentinel
&
1287 operator=(const move_sentinel
<_S2
>& __s
)
1288 noexcept(is_nothrow_assignable_v
<_Sent
, const _S2
&>)
1290 _M_last
= __s
.base();
1296 noexcept(is_nothrow_copy_constructible_v
<_Sent
>)
1304 // 24.4.3 Move iterators
1306 * Class template move_iterator is an iterator adapter with the same
1307 * behavior as the underlying iterator except that its dereference
1308 * operator implicitly converts the value returned by the underlying
1309 * iterator's dereference operator to an rvalue reference. Some
1310 * generic algorithms can be called with move iterators to replace
1311 * copying with moving.
1313 template<typename _Iterator
>
1316 _Iterator _M_current
;
1318 using __traits_type
= iterator_traits
<_Iterator
>;
1319 #if __cplusplus > 201703L && __cpp_lib_concepts
1320 using __base_cat
= typename
__traits_type::iterator_category
;
1322 using __base_ref
= typename
__traits_type::reference
;
1325 template<typename _Iter2
>
1326 friend class move_iterator
;
1328 #if __cpp_lib_concepts
1329 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1330 // 3435. three_way_comparable_with<reverse_iterator<int*>, [...]>
1331 template<typename _Iter2
>
1332 static constexpr bool __convertible
= !is_same_v
<_Iter2
, _Iterator
>
1333 && convertible_to
<const _Iter2
&, _Iterator
>;
1337 using iterator_type
= _Iterator
;
1339 #if __cplusplus > 201703L && __cpp_lib_concepts
1340 using iterator_concept
= input_iterator_tag
;
1341 using iterator_category
1342 = __detail::__clamp_iter_cat
<__base_cat
, random_access_iterator_tag
>;
1343 using value_type
= iter_value_t
<_Iterator
>;
1344 using difference_type
= iter_difference_t
<_Iterator
>;
1345 using pointer
= _Iterator
;
1346 using reference
= iter_rvalue_reference_t
<_Iterator
>;
1348 typedef typename
__traits_type::iterator_category iterator_category
;
1349 typedef typename
__traits_type::value_type value_type
;
1350 typedef typename
__traits_type::difference_type difference_type
;
1352 typedef _Iterator pointer
;
1353 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1354 // 2106. move_iterator wrapping iterators returning prvalues
1355 typedef typename conditional
<is_reference
<__base_ref
>::value
,
1356 typename remove_reference
<__base_ref
>::type
&&,
1357 __base_ref
>::type reference
;
1360 _GLIBCXX17_CONSTEXPR
1364 explicit _GLIBCXX17_CONSTEXPR
1365 move_iterator(iterator_type __i
)
1366 : _M_current(std::move(__i
)) { }
1368 template<typename _Iter
>
1369 #if __cpp_lib_concepts
1370 requires __convertible
<_Iter
>
1372 _GLIBCXX17_CONSTEXPR
1373 move_iterator(const move_iterator
<_Iter
>& __i
)
1374 : _M_current(__i
._M_current
) { }
1376 template<typename _Iter
>
1377 #if __cpp_lib_concepts
1378 requires __convertible
<_Iter
>
1379 && assignable_from
<_Iterator
&, const _Iter
&>
1381 _GLIBCXX17_CONSTEXPR
1382 move_iterator
& operator=(const move_iterator
<_Iter
>& __i
)
1384 _M_current
= __i
._M_current
;
1388 #if __cplusplus <= 201703L
1389 _GLIBCXX17_CONSTEXPR iterator_type
1391 { return _M_current
; }
1393 constexpr iterator_type
1395 #if __cpp_lib_concepts
1396 requires copy_constructible
<iterator_type
>
1398 { return _M_current
; }
1400 constexpr iterator_type
1402 { return std::move(_M_current
); }
1405 _GLIBCXX17_CONSTEXPR reference
1407 #if __cplusplus > 201703L && __cpp_lib_concepts
1408 { return ranges::iter_move(_M_current
); }
1410 { return static_cast<reference
>(*_M_current
); }
1413 _GLIBCXX17_CONSTEXPR pointer
1415 { return _M_current
; }
1417 _GLIBCXX17_CONSTEXPR move_iterator
&
1424 _GLIBCXX17_CONSTEXPR move_iterator
1427 move_iterator __tmp
= *this;
1432 #if __cpp_lib_concepts
1434 operator++(int) requires (!forward_iterator
<_Iterator
>)
1438 _GLIBCXX17_CONSTEXPR move_iterator
&
1445 _GLIBCXX17_CONSTEXPR move_iterator
1448 move_iterator __tmp
= *this;
1453 _GLIBCXX17_CONSTEXPR move_iterator
1454 operator+(difference_type __n
) const
1455 { return move_iterator(_M_current
+ __n
); }
1457 _GLIBCXX17_CONSTEXPR move_iterator
&
1458 operator+=(difference_type __n
)
1464 _GLIBCXX17_CONSTEXPR move_iterator
1465 operator-(difference_type __n
) const
1466 { return move_iterator(_M_current
- __n
); }
1468 _GLIBCXX17_CONSTEXPR move_iterator
&
1469 operator-=(difference_type __n
)
1475 _GLIBCXX17_CONSTEXPR reference
1476 operator[](difference_type __n
) const
1477 #if __cplusplus > 201703L && __cpp_lib_concepts
1478 { return ranges::iter_move(_M_current
+ __n
); }
1480 { return std::move(_M_current
[__n
]); }
1483 #if __cplusplus > 201703L && __cpp_lib_concepts
1484 template<sentinel_for
<_Iterator
> _Sent
>
1485 friend constexpr bool
1486 operator==(const move_iterator
& __x
, const move_sentinel
<_Sent
>& __y
)
1487 { return __x
.base() == __y
.base(); }
1489 template<sized_sentinel_for
<_Iterator
> _Sent
>
1490 friend constexpr iter_difference_t
<_Iterator
>
1491 operator-(const move_sentinel
<_Sent
>& __x
, const move_iterator
& __y
)
1492 { return __x
.base() - __y
.base(); }
1494 template<sized_sentinel_for
<_Iterator
> _Sent
>
1495 friend constexpr iter_difference_t
<_Iterator
>
1496 operator-(const move_iterator
& __x
, const move_sentinel
<_Sent
>& __y
)
1497 { return __x
.base() - __y
.base(); }
1499 friend constexpr iter_rvalue_reference_t
<_Iterator
>
1500 iter_move(const move_iterator
& __i
)
1501 noexcept(noexcept(ranges::iter_move(__i
._M_current
)))
1502 { return ranges::iter_move(__i
._M_current
); }
1504 template<indirectly_swappable
<_Iterator
> _Iter2
>
1505 friend constexpr void
1506 iter_swap(const move_iterator
& __x
, const move_iterator
<_Iter2
>& __y
)
1507 noexcept(noexcept(ranges::iter_swap(__x
._M_current
, __y
._M_current
)))
1508 { return ranges::iter_swap(__x
._M_current
, __y
._M_current
); }
1512 template<typename _IteratorL
, typename _IteratorR
>
1513 inline _GLIBCXX17_CONSTEXPR
bool
1514 operator==(const move_iterator
<_IteratorL
>& __x
,
1515 const move_iterator
<_IteratorR
>& __y
)
1516 #if __cplusplus > 201703L && __cpp_lib_concepts
1517 requires requires
{ { __x
.base() == __y
.base() } -> convertible_to
<bool>; }
1519 { return __x
.base() == __y
.base(); }
1521 #if __cpp_lib_three_way_comparison
1522 template<typename _IteratorL
,
1523 three_way_comparable_with
<_IteratorL
> _IteratorR
>
1524 constexpr compare_three_way_result_t
<_IteratorL
, _IteratorR
>
1525 operator<=>(const move_iterator
<_IteratorL
>& __x
,
1526 const move_iterator
<_IteratorR
>& __y
)
1527 { return __x
.base() <=> __y
.base(); }
1529 template<typename _IteratorL
, typename _IteratorR
>
1530 inline _GLIBCXX17_CONSTEXPR
bool
1531 operator!=(const move_iterator
<_IteratorL
>& __x
,
1532 const move_iterator
<_IteratorR
>& __y
)
1533 { return !(__x
== __y
); }
1536 template<typename _IteratorL
, typename _IteratorR
>
1537 inline _GLIBCXX17_CONSTEXPR
bool
1538 operator<(const move_iterator
<_IteratorL
>& __x
,
1539 const move_iterator
<_IteratorR
>& __y
)
1540 #if __cplusplus > 201703L && __cpp_lib_concepts
1541 requires requires
{ { __x
.base() < __y
.base() } -> convertible_to
<bool>; }
1543 { return __x
.base() < __y
.base(); }
1545 template<typename _IteratorL
, typename _IteratorR
>
1546 inline _GLIBCXX17_CONSTEXPR
bool
1547 operator<=(const move_iterator
<_IteratorL
>& __x
,
1548 const move_iterator
<_IteratorR
>& __y
)
1549 #if __cplusplus > 201703L && __cpp_lib_concepts
1550 requires requires
{ { __y
.base() < __x
.base() } -> convertible_to
<bool>; }
1552 { return !(__y
< __x
); }
1554 template<typename _IteratorL
, typename _IteratorR
>
1555 inline _GLIBCXX17_CONSTEXPR
bool
1556 operator>(const move_iterator
<_IteratorL
>& __x
,
1557 const move_iterator
<_IteratorR
>& __y
)
1558 #if __cplusplus > 201703L && __cpp_lib_concepts
1559 requires requires
{ { __y
.base() < __x
.base() } -> convertible_to
<bool>; }
1561 { return __y
< __x
; }
1563 template<typename _IteratorL
, typename _IteratorR
>
1564 inline _GLIBCXX17_CONSTEXPR
bool
1565 operator>=(const move_iterator
<_IteratorL
>& __x
,
1566 const move_iterator
<_IteratorR
>& __y
)
1567 #if __cplusplus > 201703L && __cpp_lib_concepts
1568 requires requires
{ { __x
.base() < __y
.base() } -> convertible_to
<bool>; }
1570 { return !(__x
< __y
); }
1572 #if ! (__cplusplus > 201703L && __cpp_lib_concepts)
1573 // Note: See __normal_iterator operators note from Gaby to understand
1574 // why we have these extra overloads for some move_iterator operators.
1576 // These extra overloads are not needed in C++20, because the ones above
1577 // are constrained with a requires-clause and so overload resolution will
1578 // prefer them to greedy unconstrained function templates.
1580 template<typename _Iterator
>
1581 inline _GLIBCXX17_CONSTEXPR
bool
1582 operator==(const move_iterator
<_Iterator
>& __x
,
1583 const move_iterator
<_Iterator
>& __y
)
1584 { return __x
.base() == __y
.base(); }
1586 template<typename _Iterator
>
1587 inline _GLIBCXX17_CONSTEXPR
bool
1588 operator!=(const move_iterator
<_Iterator
>& __x
,
1589 const move_iterator
<_Iterator
>& __y
)
1590 { return !(__x
== __y
); }
1592 template<typename _Iterator
>
1593 inline _GLIBCXX17_CONSTEXPR
bool
1594 operator<(const move_iterator
<_Iterator
>& __x
,
1595 const move_iterator
<_Iterator
>& __y
)
1596 { return __x
.base() < __y
.base(); }
1598 template<typename _Iterator
>
1599 inline _GLIBCXX17_CONSTEXPR
bool
1600 operator<=(const move_iterator
<_Iterator
>& __x
,
1601 const move_iterator
<_Iterator
>& __y
)
1602 { return !(__y
< __x
); }
1604 template<typename _Iterator
>
1605 inline _GLIBCXX17_CONSTEXPR
bool
1606 operator>(const move_iterator
<_Iterator
>& __x
,
1607 const move_iterator
<_Iterator
>& __y
)
1608 { return __y
< __x
; }
1610 template<typename _Iterator
>
1611 inline _GLIBCXX17_CONSTEXPR
bool
1612 operator>=(const move_iterator
<_Iterator
>& __x
,
1613 const move_iterator
<_Iterator
>& __y
)
1614 { return !(__x
< __y
); }
1618 template<typename _IteratorL
, typename _IteratorR
>
1619 inline _GLIBCXX17_CONSTEXPR
auto
1620 operator-(const move_iterator
<_IteratorL
>& __x
,
1621 const move_iterator
<_IteratorR
>& __y
)
1622 -> decltype(__x
.base() - __y
.base())
1623 { return __x
.base() - __y
.base(); }
1625 template<typename _Iterator
>
1626 inline _GLIBCXX17_CONSTEXPR move_iterator
<_Iterator
>
1627 operator+(typename move_iterator
<_Iterator
>::difference_type __n
,
1628 const move_iterator
<_Iterator
>& __x
)
1629 { return __x
+ __n
; }
1631 template<typename _Iterator
>
1632 inline _GLIBCXX17_CONSTEXPR move_iterator
<_Iterator
>
1633 make_move_iterator(_Iterator __i
)
1634 { return move_iterator
<_Iterator
>(std::move(__i
)); }
1636 template<typename _Iterator
, typename _ReturnType
1637 = typename conditional
<__move_if_noexcept_cond
1638 <typename iterator_traits
<_Iterator
>::value_type
>::value
,
1639 _Iterator
, move_iterator
<_Iterator
>>::type
>
1640 inline _GLIBCXX17_CONSTEXPR _ReturnType
1641 __make_move_if_noexcept_iterator(_Iterator __i
)
1642 { return _ReturnType(__i
); }
1644 // Overload for pointers that matches std::move_if_noexcept more closely,
1645 // returning a constant iterator when we don't want to move.
1646 template<typename _Tp
, typename _ReturnType
1647 = typename conditional
<__move_if_noexcept_cond
<_Tp
>::value
,
1648 const _Tp
*, move_iterator
<_Tp
*>>::type
>
1649 inline _GLIBCXX17_CONSTEXPR _ReturnType
1650 __make_move_if_noexcept_iterator(_Tp
* __i
)
1651 { return _ReturnType(__i
); }
1653 #if __cplusplus > 201703L && __cpp_lib_concepts
1654 // [iterators.common] Common iterators
1658 template<typename _It
>
1659 concept __common_iter_has_arrow
= indirectly_readable
<const _It
>
1660 && (requires(const _It
& __it
) { __it
.operator->(); }
1661 || is_reference_v
<iter_reference_t
<_It
>>
1662 || constructible_from
<iter_value_t
<_It
>, iter_reference_t
<_It
>>);
1664 } // namespace __detail
1666 /// An iterator/sentinel adaptor for representing a non-common range.
1667 template<input_or_output_iterator _It
, sentinel_for
<_It
> _Sent
>
1668 requires (!same_as
<_It
, _Sent
>) && copyable
<_It
>
1669 class common_iterator
1671 template<typename _Tp
, typename _Up
>
1672 static constexpr bool
1675 if constexpr (is_trivially_default_constructible_v
<_Tp
>)
1676 return is_nothrow_assignable_v
<_Tp
, _Up
>;
1678 return is_nothrow_constructible_v
<_Tp
, _Up
>;
1681 template<typename _It2
, typename _Sent2
>
1682 static constexpr bool
1684 { return _S_noexcept1
<_It
, _It2
>() && _S_noexcept1
<_Sent
, _Sent2
>(); }
1688 iter_value_t
<_It
> _M_keep
;
1690 _Proxy(iter_reference_t
<_It
>&& __x
)
1691 : _M_keep(std::move(__x
)) { }
1693 friend class common_iterator
;
1696 const iter_value_t
<_It
>*
1698 { return std::__addressof(_M_keep
); }
1704 noexcept(is_nothrow_default_constructible_v
<_It
>)
1705 : _M_it(), _M_index(0)
1709 common_iterator(_It __i
)
1710 noexcept(is_nothrow_move_constructible_v
<_It
>)
1711 : _M_it(std::move(__i
)), _M_index(0)
1715 common_iterator(_Sent __s
)
1716 noexcept(is_nothrow_move_constructible_v
<_Sent
>)
1717 : _M_sent(std::move(__s
)), _M_index(1)
1720 template<typename _It2
, typename _Sent2
>
1721 requires convertible_to
<const _It2
&, _It
>
1722 && convertible_to
<const _Sent2
&, _Sent
>
1724 common_iterator(const common_iterator
<_It2
, _Sent2
>& __x
)
1725 noexcept(_S_noexcept
<const _It2
&, const _Sent2
&>())
1726 : _M_valueless(), _M_index(__x
._M_index
)
1730 if constexpr (is_trivially_default_constructible_v
<_It
>)
1731 _M_it
= std::move(__x
._M_it
);
1733 ::new((void*)std::__addressof(_M_it
)) _It(__x
._M_it
);
1735 else if (_M_index
== 1)
1737 if constexpr (is_trivially_default_constructible_v
<_Sent
>)
1738 _M_sent
= std::move(__x
._M_sent
);
1740 ::new((void*)std::__addressof(_M_sent
)) _Sent(__x
._M_sent
);
1745 common_iterator(const common_iterator
& __x
)
1746 noexcept(_S_noexcept
<const _It
&, const _Sent
&>())
1747 : _M_valueless(), _M_index(__x
._M_index
)
1751 if constexpr (is_trivially_default_constructible_v
<_It
>)
1752 _M_it
= std::move(__x
._M_it
);
1754 ::new((void*)std::__addressof(_M_it
)) _It(__x
._M_it
);
1756 else if (_M_index
== 1)
1758 if constexpr (is_trivially_default_constructible_v
<_Sent
>)
1759 _M_sent
= std::move(__x
._M_sent
);
1761 ::new((void*)std::__addressof(_M_sent
)) _Sent(__x
._M_sent
);
1766 operator=(const common_iterator
& __x
)
1767 noexcept(is_nothrow_copy_assignable_v
<_It
>
1768 && is_nothrow_copy_assignable_v
<_Sent
>
1769 && is_nothrow_copy_constructible_v
<_It
>
1770 && is_nothrow_copy_constructible_v
<_Sent
>)
1772 return this->operator=<_It
, _Sent
>(__x
);
1775 template<typename _It2
, typename _Sent2
>
1776 requires convertible_to
<const _It2
&, _It
>
1777 && convertible_to
<const _Sent2
&, _Sent
>
1778 && assignable_from
<_It
&, const _It2
&>
1779 && assignable_from
<_Sent
&, const _Sent2
&>
1781 operator=(const common_iterator
<_It2
, _Sent2
>& __x
)
1782 noexcept(is_nothrow_constructible_v
<_It
, const _It2
&>
1783 && is_nothrow_constructible_v
<_Sent
, const _Sent2
&>
1784 && is_nothrow_assignable_v
<_It
, const _It2
&>
1785 && is_nothrow_assignable_v
<_Sent
, const _Sent2
&>)
1787 switch(_M_index
<< 2 | __x
._M_index
)
1793 _M_sent
= __x
._M_sent
;
1800 ::new((void*)std::__addressof(_M_sent
)) _Sent(__x
._M_sent
);
1808 ::new((void*)std::__addressof(_M_it
)) _It(__x
._M_it
);
1812 __glibcxx_assert(__x
._M_has_value());
1813 __builtin_unreachable();
1834 __glibcxx_assert(_M_index
== 0);
1839 operator*() const requires
__detail::__dereferenceable
<const _It
>
1841 __glibcxx_assert(_M_index
== 0);
1846 operator->() const requires
__detail::__common_iter_has_arrow
<_It
>
1848 __glibcxx_assert(_M_index
== 0);
1849 if constexpr (is_pointer_v
<_It
> || requires
{ _M_it
.operator->(); })
1851 else if constexpr (is_reference_v
<iter_reference_t
<_It
>>)
1853 auto&& __tmp
= *_M_it
;
1854 return std::__addressof(__tmp
);
1857 return _Proxy
{*_M_it
};
1863 __glibcxx_assert(_M_index
== 0);
1871 __glibcxx_assert(_M_index
== 0);
1872 if constexpr (forward_iterator
<_It
>)
1874 common_iterator __tmp
= *this;
1882 template<typename _It2
, sentinel_for
<_It
> _Sent2
>
1883 requires sentinel_for
<_Sent
, _It2
>
1885 operator==(const common_iterator
& __x
,
1886 const common_iterator
<_It2
, _Sent2
>& __y
)
1888 switch(__x
._M_index
<< 2 | __y
._M_index
)
1894 return __x
._M_it
== __y
._M_sent
;
1896 return __x
._M_sent
== __y
._M_it
;
1898 __glibcxx_assert(__x
._M_has_value());
1899 __glibcxx_assert(__y
._M_has_value());
1900 __builtin_unreachable();
1904 template<typename _It2
, sentinel_for
<_It
> _Sent2
>
1905 requires sentinel_for
<_Sent
, _It2
> && equality_comparable_with
<_It
, _It2
>
1907 operator==(const common_iterator
& __x
,
1908 const common_iterator
<_It2
, _Sent2
>& __y
)
1910 switch(__x
._M_index
<< 2 | __y
._M_index
)
1915 return __x
._M_it
== __y
._M_it
;
1917 return __x
._M_it
== __y
._M_sent
;
1919 return __x
._M_sent
== __y
._M_it
;
1921 __glibcxx_assert(__x
._M_has_value());
1922 __glibcxx_assert(__y
._M_has_value());
1923 __builtin_unreachable();
1927 template<sized_sentinel_for
<_It
> _It2
, sized_sentinel_for
<_It
> _Sent2
>
1928 requires sized_sentinel_for
<_Sent
, _It2
>
1929 friend iter_difference_t
<_It2
>
1930 operator-(const common_iterator
& __x
,
1931 const common_iterator
<_It2
, _Sent2
>& __y
)
1933 switch(__x
._M_index
<< 2 | __y
._M_index
)
1938 return __x
._M_it
- __y
._M_it
;
1940 return __x
._M_it
- __y
._M_sent
;
1942 return __x
._M_sent
- __y
._M_it
;
1944 __glibcxx_assert(__x
._M_has_value());
1945 __glibcxx_assert(__y
._M_has_value());
1946 __builtin_unreachable();
1950 friend iter_rvalue_reference_t
<_It
>
1951 iter_move(const common_iterator
& __i
)
1952 noexcept(noexcept(ranges::iter_move(std::declval
<const _It
&>())))
1953 requires input_iterator
<_It
>
1955 __glibcxx_assert(__i
._M_index
== 0);
1956 return ranges::iter_move(__i
._M_it
);
1959 template<indirectly_swappable
<_It
> _It2
, typename _Sent2
>
1961 iter_swap(const common_iterator
& __x
,
1962 const common_iterator
<_It2
, _Sent2
>& __y
)
1963 noexcept(noexcept(ranges::iter_swap(std::declval
<const _It
&>(),
1964 std::declval
<const _It2
&>())))
1966 __glibcxx_assert(__x
._M_index
== 0);
1967 __glibcxx_assert(__y
._M_index
== 0);
1968 return ranges::iter_swap(__x
._M_it
, __y
._M_it
);
1972 template<input_or_output_iterator _It2
, sentinel_for
<_It2
> _Sent2
>
1973 friend class common_iterator
;
1975 bool _M_has_value() const noexcept
{ return _M_index
< 2; }
1981 unsigned char _M_valueless
;
1983 unsigned char _M_index
; // 0==_M_it, 1==_M_sent, 2==valueless
1986 template<typename _It
, typename _Sent
>
1987 struct incrementable_traits
<common_iterator
<_It
, _Sent
>>
1989 using difference_type
= iter_difference_t
<_It
>;
1992 template<input_iterator _It
, typename _Sent
>
1993 struct iterator_traits
<common_iterator
<_It
, _Sent
>>
1996 template<typename _Iter
>
2002 template<typename _Iter
>
2003 requires
__detail::__common_iter_has_arrow
<_Iter
>
2006 using _CIter
= common_iterator
<_Iter
, _Sent
>;
2007 using type
= decltype(std::declval
<const _CIter
&>().operator->());
2011 using iterator_concept
= conditional_t
<forward_iterator
<_It
>,
2012 forward_iterator_tag
, input_iterator_tag
>;
2013 using iterator_category
= __detail::__clamp_iter_cat
<
2014 typename iterator_traits
<_It
>::iterator_category
,
2015 forward_iterator_tag
, input_iterator_tag
>;
2016 using value_type
= iter_value_t
<_It
>;
2017 using difference_type
= iter_difference_t
<_It
>;
2018 using pointer
= typename __ptr
<_It
>::type
;
2019 using reference
= iter_reference_t
<_It
>;
2022 // [iterators.counted] Counted iterators
2024 /// An iterator adaptor that keeps track of the distance to the end.
2025 template<input_or_output_iterator _It
>
2026 class counted_iterator
2029 using iterator_type
= _It
;
2031 constexpr counted_iterator() = default;
2034 counted_iterator(_It __i
, iter_difference_t
<_It
> __n
)
2035 : _M_current(std::move(__i
)), _M_length(__n
)
2036 { __glibcxx_assert(__n
>= 0); }
2038 template<typename _It2
>
2039 requires convertible_to
<const _It2
&, _It
>
2041 counted_iterator(const counted_iterator
<_It2
>& __x
)
2042 : _M_current(__x
._M_current
), _M_length(__x
._M_length
)
2045 template<typename _It2
>
2046 requires assignable_from
<_It
&, const _It2
&>
2047 constexpr counted_iterator
&
2048 operator=(const counted_iterator
<_It2
>& __x
)
2050 _M_current
= __x
._M_current
;
2051 _M_length
= __x
._M_length
;
2057 noexcept(is_nothrow_copy_constructible_v
<_It
>)
2058 requires copy_constructible
<_It
>
2059 { return _M_current
; }
2063 noexcept(is_nothrow_move_constructible_v
<_It
>)
2064 { return std::move(_M_current
); }
2066 constexpr iter_difference_t
<_It
>
2067 count() const noexcept
{ return _M_length
; }
2069 constexpr decltype(auto)
2071 noexcept(noexcept(*_M_current
))
2073 __glibcxx_assert( _M_length
> 0 );
2077 constexpr decltype(auto)
2079 noexcept(noexcept(*_M_current
))
2080 requires
__detail::__dereferenceable
<const _It
>
2082 __glibcxx_assert( _M_length
> 0 );
2086 constexpr counted_iterator
&
2089 __glibcxx_assert(_M_length
> 0);
2098 __glibcxx_assert(_M_length
> 0);
2102 return _M_current
++;
2105 __throw_exception_again
;
2110 constexpr counted_iterator
2111 operator++(int) requires forward_iterator
<_It
>
2118 constexpr counted_iterator
&
2119 operator--() requires bidirectional_iterator
<_It
>
2126 constexpr counted_iterator
2127 operator--(int) requires bidirectional_iterator
<_It
>
2134 constexpr counted_iterator
2135 operator+(iter_difference_t
<_It
> __n
) const
2136 requires random_access_iterator
<_It
>
2137 { return counted_iterator(_M_current
+ __n
, _M_length
- __n
); }
2139 friend constexpr counted_iterator
2140 operator+(iter_difference_t
<_It
> __n
, const counted_iterator
& __x
)
2141 requires random_access_iterator
<_It
>
2142 { return __x
+ __n
; }
2144 constexpr counted_iterator
&
2145 operator+=(iter_difference_t
<_It
> __n
)
2146 requires random_access_iterator
<_It
>
2148 __glibcxx_assert(__n
<= _M_length
);
2154 constexpr counted_iterator
2155 operator-(iter_difference_t
<_It
> __n
) const
2156 requires random_access_iterator
<_It
>
2157 { return counted_iterator(_M_current
- __n
, _M_length
+ __n
); }
2159 template<common_with
<_It
> _It2
>
2160 friend constexpr iter_difference_t
<_It2
>
2161 operator-(const counted_iterator
& __x
,
2162 const counted_iterator
<_It2
>& __y
)
2163 { return __y
._M_length
- __x
._M_length
; }
2165 friend constexpr iter_difference_t
<_It
>
2166 operator-(const counted_iterator
& __x
, default_sentinel_t
)
2167 { return -__x
._M_length
; }
2169 friend constexpr iter_difference_t
<_It
>
2170 operator-(default_sentinel_t
, const counted_iterator
& __y
)
2171 { return __y
._M_length
; }
2173 constexpr counted_iterator
&
2174 operator-=(iter_difference_t
<_It
> __n
)
2175 requires random_access_iterator
<_It
>
2177 __glibcxx_assert(-__n
<= _M_length
);
2183 constexpr decltype(auto)
2184 operator[](iter_difference_t
<_It
> __n
) const
2185 noexcept(noexcept(_M_current
[__n
]))
2186 requires random_access_iterator
<_It
>
2188 __glibcxx_assert(__n
< _M_length
);
2189 return _M_current
[__n
];
2192 template<common_with
<_It
> _It2
>
2193 friend constexpr bool
2194 operator==(const counted_iterator
& __x
,
2195 const counted_iterator
<_It2
>& __y
)
2196 { return __x
._M_length
== __y
._M_length
; }
2198 friend constexpr bool
2199 operator==(const counted_iterator
& __x
, default_sentinel_t
)
2200 { return __x
._M_length
== 0; }
2202 template<common_with
<_It
> _It2
>
2203 friend constexpr strong_ordering
2204 operator<=>(const counted_iterator
& __x
,
2205 const counted_iterator
<_It2
>& __y
)
2206 { return __y
._M_length
<=> __x
._M_length
; }
2208 friend constexpr iter_rvalue_reference_t
<_It
>
2209 iter_move(const counted_iterator
& __i
)
2210 noexcept(noexcept(ranges::iter_move(__i
._M_current
)))
2211 requires input_iterator
<_It
>
2213 __glibcxx_assert( __i
._M_length
> 0 );
2214 return ranges::iter_move(__i
._M_current
);
2217 template<indirectly_swappable
<_It
> _It2
>
2218 friend constexpr void
2219 iter_swap(const counted_iterator
& __x
,
2220 const counted_iterator
<_It2
>& __y
)
2221 noexcept(noexcept(ranges::iter_swap(__x
._M_current
, __y
._M_current
)))
2223 __glibcxx_assert( __x
._M_length
> 0 && __y
._M_length
> 0 );
2224 ranges::iter_swap(__x
._M_current
, __y
._M_current
);
2228 template<input_or_output_iterator _It2
> friend class counted_iterator
;
2230 _It _M_current
= _It();
2231 iter_difference_t
<_It
> _M_length
= 0;
2234 template<typename _It
>
2235 struct incrementable_traits
<counted_iterator
<_It
>>
2237 using difference_type
= iter_difference_t
<_It
>;
2240 template<input_iterator _It
>
2241 struct iterator_traits
<counted_iterator
<_It
>> : iterator_traits
<_It
>
2243 using pointer
= void;
2247 // @} group iterators
2249 template<typename _Iterator
>
2251 __niter_base(move_iterator
<_Iterator
> __it
)
2252 -> decltype(make_move_iterator(__niter_base(__it
.base())))
2253 { return make_move_iterator(__niter_base(__it
.base())); }
2255 template<typename _Iterator
>
2256 struct __is_move_iterator
<move_iterator
<_Iterator
> >
2258 enum { __value
= 1 };
2259 typedef __true_type __type
;
2262 template<typename _Iterator
>
2264 __miter_base(move_iterator
<_Iterator
> __it
)
2265 -> decltype(__miter_base(__it
.base()))
2266 { return __miter_base(__it
.base()); }
2268 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2269 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2270 std::__make_move_if_noexcept_iterator(_Iter)
2272 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2273 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2276 #if __cpp_deduction_guides >= 201606
2277 // These helper traits are used for deduction guides
2278 // of associative containers.
2279 template<typename _InputIterator
>
2280 using __iter_key_t
= remove_const_t
<
2281 typename iterator_traits
<_InputIterator
>::value_type::first_type
>;
2283 template<typename _InputIterator
>
2284 using __iter_val_t
=
2285 typename iterator_traits
<_InputIterator
>::value_type::second_type
;
2287 template<typename _T1
, typename _T2
>
2290 template<typename _InputIterator
>
2291 using __iter_to_alloc_t
=
2292 pair
<add_const_t
<__iter_key_t
<_InputIterator
>>,
2293 __iter_val_t
<_InputIterator
>>;
2294 #endif // __cpp_deduction_guides
2296 _GLIBCXX_END_NAMESPACE_VERSION
2299 #ifdef _GLIBCXX_DEBUG
2300 # include <debug/stl_iterator.h>