60 #ifndef _STL_ITERATOR_H
61 #define _STL_ITERATOR_H 1
68 #if __cplusplus >= 201103L
72 #if __cplusplus > 201703L
73 # define __cpp_lib_array_constexpr 201811L
74 #elif __cplusplus == 201703L
75 # define __cpp_lib_array_constexpr 201803L
78 #if __cplusplus > 201703L
84 namespace std _GLIBCXX_VISIBILITY(default)
86 _GLIBCXX_BEGIN_NAMESPACE_VERSION
93 #if __cplusplus > 201703L && __cpp_lib_concepts
98 template<
typename _Cat,
typename _Limit,
typename _Otherwise = _Cat>
99 using __clamp_iter_cat
100 = conditional_t<derived_from<_Cat, _Limit>, _Limit, _Otherwise>;
123 template<
typename _Iterator>
125 :
public iterator<typename iterator_traits<_Iterator>::iterator_category,
126 typename iterator_traits<_Iterator>::value_type,
127 typename iterator_traits<_Iterator>::difference_type,
128 typename iterator_traits<_Iterator>::pointer,
129 typename iterator_traits<_Iterator>::reference>
137 typedef _Iterator iterator_type;
138 typedef typename __traits_type::difference_type difference_type;
139 typedef typename __traits_type::pointer pointer;
140 typedef typename __traits_type::reference reference;
142 #if __cplusplus > 201703L && __cpp_lib_concepts
143 using iterator_concept
148 = __detail::__clamp_iter_cat<
typename __traits_type::iterator_category,
165 explicit _GLIBCXX17_CONSTEXPR
173 : current(__x.current) { }
175 #if __cplusplus >= 201103L
183 template<
typename _Iter>
186 : current(__x.
base()) { }
191 _GLIBCXX17_CONSTEXPR iterator_type
205 _GLIBCXX17_CONSTEXPR reference
208 _Iterator __tmp = current;
217 _GLIBCXX17_CONSTEXPR pointer
219 #if __cplusplus > 201703L && __cpp_concepts >= 201907L
220 requires is_pointer_v<_Iterator>
221 || requires(
const _Iterator __i) { __i.operator->(); }
226 _Iterator __tmp = current;
228 return _S_to_pointer(__tmp);
330 _GLIBCXX17_CONSTEXPR reference
332 {
return *(*
this + __n); }
335 template<
typename _Tp>
336 static _GLIBCXX17_CONSTEXPR _Tp*
337 _S_to_pointer(_Tp* __p)
340 template<
typename _Tp>
341 static _GLIBCXX17_CONSTEXPR pointer
342 _S_to_pointer(_Tp __t)
343 {
return __t.operator->(); }
356 #if __cplusplus <= 201703L || ! defined __cpp_lib_concepts
357 template<
typename _Iterator>
358 inline _GLIBCXX17_CONSTEXPR
bool
361 {
return __x.
base() == __y.
base(); }
363 template<
typename _Iterator>
364 inline _GLIBCXX17_CONSTEXPR
bool
365 operator<(
const reverse_iterator<_Iterator>& __x,
366 const reverse_iterator<_Iterator>& __y)
367 {
return __y.base() < __x.base(); }
369 template<
typename _Iterator>
370 inline _GLIBCXX17_CONSTEXPR
bool
371 operator!=(
const reverse_iterator<_Iterator>& __x,
372 const reverse_iterator<_Iterator>& __y)
373 {
return !(__x == __y); }
375 template<
typename _Iterator>
376 inline _GLIBCXX17_CONSTEXPR
bool
377 operator>(
const reverse_iterator<_Iterator>& __x,
378 const reverse_iterator<_Iterator>& __y)
379 {
return __y < __x; }
381 template<
typename _Iterator>
382 inline _GLIBCXX17_CONSTEXPR
bool
383 operator<=(
const reverse_iterator<_Iterator>& __x,
384 const reverse_iterator<_Iterator>& __y)
385 {
return !(__y < __x); }
387 template<
typename _Iterator>
388 inline _GLIBCXX17_CONSTEXPR
bool
389 operator>=(
const reverse_iterator<_Iterator>& __x,
390 const reverse_iterator<_Iterator>& __y)
391 {
return !(__x < __y); }
395 template<
typename _IteratorL,
typename _IteratorR>
396 inline _GLIBCXX17_CONSTEXPR
bool
397 operator==(
const reverse_iterator<_IteratorL>& __x,
398 const reverse_iterator<_IteratorR>& __y)
399 {
return __x.base() == __y.base(); }
401 template<
typename _IteratorL,
typename _IteratorR>
402 inline _GLIBCXX17_CONSTEXPR
bool
403 operator<(
const reverse_iterator<_IteratorL>& __x,
404 const reverse_iterator<_IteratorR>& __y)
405 {
return __y.base() < __x.base(); }
407 template<
typename _IteratorL,
typename _IteratorR>
408 inline _GLIBCXX17_CONSTEXPR
bool
409 operator!=(
const reverse_iterator<_IteratorL>& __x,
410 const reverse_iterator<_IteratorR>& __y)
411 {
return !(__x == __y); }
413 template<
typename _IteratorL,
typename _IteratorR>
414 inline _GLIBCXX17_CONSTEXPR
bool
415 operator>(
const reverse_iterator<_IteratorL>& __x,
416 const reverse_iterator<_IteratorR>& __y)
417 {
return __y < __x; }
419 template<
typename _IteratorL,
typename _IteratorR>
420 inline _GLIBCXX17_CONSTEXPR
bool
421 operator<=(
const reverse_iterator<_IteratorL>& __x,
422 const reverse_iterator<_IteratorR>& __y)
423 {
return !(__y < __x); }
425 template<
typename _IteratorL,
typename _IteratorR>
426 inline _GLIBCXX17_CONSTEXPR
bool
427 operator>=(
const reverse_iterator<_IteratorL>& __x,
428 const reverse_iterator<_IteratorR>& __y)
429 {
return !(__x < __y); }
431 template<
typename _IteratorL,
typename _IteratorR>
433 operator==(
const reverse_iterator<_IteratorL>& __x,
434 const reverse_iterator<_IteratorR>& __y)
435 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
436 {
return __x.base() == __y.base(); }
438 template<
typename _IteratorL,
typename _IteratorR>
440 operator!=(
const reverse_iterator<_IteratorL>& __x,
441 const reverse_iterator<_IteratorR>& __y)
442 requires requires { { __x.base() != __y.base() } -> convertible_to<bool>; }
443 {
return __x.base() != __y.base(); }
445 template<
typename _IteratorL,
typename _IteratorR>
447 operator<(
const reverse_iterator<_IteratorL>& __x,
448 const reverse_iterator<_IteratorR>& __y)
449 requires requires { { __x.base() > __y.base() } -> convertible_to<bool>; }
450 {
return __x.base() > __y.base(); }
452 template<
typename _IteratorL,
typename _IteratorR>
454 operator>(
const reverse_iterator<_IteratorL>& __x,
455 const reverse_iterator<_IteratorR>& __y)
456 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
457 {
return __x.base() < __y.base(); }
459 template<
typename _IteratorL,
typename _IteratorR>
461 operator<=(
const reverse_iterator<_IteratorL>& __x,
462 const reverse_iterator<_IteratorR>& __y)
463 requires requires { { __x.base() >= __y.base() } -> convertible_to<bool>; }
464 {
return __x.base() >= __y.base(); }
466 template<
typename _IteratorL,
typename _IteratorR>
468 operator>=(
const reverse_iterator<_IteratorL>& __x,
469 const reverse_iterator<_IteratorR>& __y)
470 requires requires { { __x.base() <= __y.base() } -> convertible_to<bool>; }
471 {
return __x.base() <= __y.base(); }
473 template<
typename _IteratorL,
474 three_way_comparable_with<_IteratorL> _IteratorR>
475 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
476 operator<=>(
const reverse_iterator<_IteratorL>& __x,
477 const reverse_iterator<_IteratorR>& __y)
478 {
return __y.base() <=> __x.base(); }
482 #if __cplusplus < 201103L
483 template<
typename _Iterator>
484 inline typename reverse_iterator<_Iterator>::difference_type
485 operator-(
const reverse_iterator<_Iterator>& __x,
486 const reverse_iterator<_Iterator>& __y)
487 {
return __y.base() - __x.base(); }
489 template<
typename _IteratorL,
typename _IteratorR>
490 inline typename reverse_iterator<_IteratorL>::difference_type
491 operator-(
const reverse_iterator<_IteratorL>& __x,
492 const reverse_iterator<_IteratorR>& __y)
493 {
return __y.base() - __x.base(); }
497 template<
typename _IteratorL,
typename _IteratorR>
498 inline _GLIBCXX17_CONSTEXPR
auto
499 operator-(
const reverse_iterator<_IteratorL>& __x,
500 const reverse_iterator<_IteratorR>& __y)
501 -> decltype(__y.base() - __x.base())
502 {
return __y.base() - __x.base(); }
505 template<
typename _Iterator>
506 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
507 operator+(
typename reverse_iterator<_Iterator>::difference_type __n,
508 const reverse_iterator<_Iterator>& __x)
509 {
return reverse_iterator<_Iterator>(__x.base() - __n); }
511 #if __cplusplus >= 201103L
513 template<
typename _Iterator>
514 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
515 __make_reverse_iterator(_Iterator __i)
516 {
return reverse_iterator<_Iterator>(__i); }
518 # if __cplusplus >= 201402L
519 # define __cpp_lib_make_reverse_iterator 201402
524 template<
typename _Iterator>
525 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
529 # if __cplusplus > 201703L && defined __cpp_lib_concepts
530 template<
typename _Iterator1,
typename _Iterator2>
531 requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
532 inline constexpr
bool
533 disable_sized_sentinel_for<reverse_iterator<_Iterator1>,
534 reverse_iterator<_Iterator2>> =
true;
538 template<
typename _Iterator>
541 __niter_base(reverse_iterator<_Iterator> __it)
542 -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
543 {
return __make_reverse_iterator(__niter_base(__it.base())); }
545 template<
typename _Iterator>
546 struct __is_move_iterator<reverse_iterator<_Iterator> >
547 : __is_move_iterator<_Iterator>
550 template<
typename _Iterator>
553 __miter_base(reverse_iterator<_Iterator> __it)
554 -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
555 {
return __make_reverse_iterator(__miter_base(__it.base())); }
569 template<
typename _Container>
571 :
public iterator<output_iterator_tag, void, void, void, void>
574 _Container* container;
579 #if __cplusplus > 201703L
586 explicit _GLIBCXX20_CONSTEXPR
601 #if __cplusplus < 201103L
603 operator=(
typename _Container::const_reference __value)
605 container->push_back(__value);
611 operator=(
const typename _Container::value_type& __value)
613 container->push_back(__value);
619 operator=(
typename _Container::value_type&& __value)
621 container->push_back(
std::move(__value));
656 template<
typename _Container>
658 inline back_insert_iterator<_Container>
672 template<
typename _Container>
674 :
public iterator<output_iterator_tag, void, void, void, void>
677 _Container* container;
682 #if __cplusplus > 201703L
689 explicit _GLIBCXX20_CONSTEXPR
704 #if __cplusplus < 201103L
706 operator=(
typename _Container::const_reference __value)
708 container->push_front(__value);
714 operator=(
const typename _Container::value_type& __value)
716 container->push_front(__value);
722 operator=(
typename _Container::value_type&& __value)
724 container->push_front(
std::move(__value));
759 template<
typename _Container>
761 inline front_insert_iterator<_Container>
779 template<
typename _Container>
781 :
public iterator<output_iterator_tag, void, void, void, void>
783 #if __cplusplus > 201703L && defined __cpp_lib_concepts
784 using _Iter = std::__detail::__range_iter_t<_Container>;
787 _Container* container =
nullptr;
788 _Iter iter = _Iter();
790 typedef typename _Container::iterator _Iter;
793 _Container* container;
801 #if __cplusplus > 201703L && defined __cpp_lib_concepts
838 #if __cplusplus < 201103L
840 operator=(
typename _Container::const_reference __value)
842 iter = container->insert(iter, __value);
849 operator=(
const typename _Container::value_type& __value)
851 iter = container->insert(iter, __value);
858 operator=(
typename _Container::value_type&& __value)
860 iter = container->insert(iter,
std::move(__value));
897 #if __cplusplus > 201703L && defined __cpp_lib_concepts
898 template<
typename _Container>
899 constexpr insert_iterator<_Container>
900 inserter(_Container& __x, std::__detail::__range_iter_t<_Container> __i)
901 {
return insert_iterator<_Container>(__x, __i); }
903 template<
typename _Container,
typename _Iterator>
904 inline insert_iterator<_Container>
908 typename _Container::iterator(__i));
914 _GLIBCXX_END_NAMESPACE_VERSION
917 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
919 _GLIBCXX_BEGIN_NAMESPACE_VERSION
928 template<
typename _Iterator,
typename _Container>
929 class __normal_iterator
932 _Iterator _M_current;
937 typedef _Iterator iterator_type;
938 typedef typename __traits_type::iterator_category iterator_category;
939 typedef typename __traits_type::value_type value_type;
940 typedef typename __traits_type::difference_type difference_type;
941 typedef typename __traits_type::reference reference;
942 typedef typename __traits_type::pointer pointer;
944 #if __cplusplus > 201703L && __cpp_lib_concepts
945 using iterator_concept = std::__detail::__iter_concept<_Iterator>;
948 _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
949 : _M_current(_Iterator()) { }
951 explicit _GLIBCXX20_CONSTEXPR
952 __normal_iterator(
const _Iterator& __i) _GLIBCXX_NOEXCEPT
953 : _M_current(__i) { }
956 template<
typename _Iter>
958 __normal_iterator(
const __normal_iterator<_Iter,
959 typename __enable_if<
960 (std::__are_same<_Iter, typename _Container::pointer>::__value),
961 _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
962 : _M_current(__i.base()) { }
968 {
return *_M_current; }
972 operator->() const _GLIBCXX_NOEXCEPT
973 {
return _M_current; }
977 operator++() _GLIBCXX_NOEXCEPT
985 operator++(
int) _GLIBCXX_NOEXCEPT
986 {
return __normal_iterator(_M_current++); }
991 operator--() _GLIBCXX_NOEXCEPT
999 operator--(
int) _GLIBCXX_NOEXCEPT
1000 {
return __normal_iterator(_M_current--); }
1003 _GLIBCXX20_CONSTEXPR
1005 operator[](difference_type __n)
const _GLIBCXX_NOEXCEPT
1006 {
return _M_current[__n]; }
1008 _GLIBCXX20_CONSTEXPR
1010 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
1011 { _M_current += __n;
return *
this; }
1013 _GLIBCXX20_CONSTEXPR
1015 operator+(difference_type __n)
const _GLIBCXX_NOEXCEPT
1016 {
return __normal_iterator(_M_current + __n); }
1018 _GLIBCXX20_CONSTEXPR
1020 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
1021 { _M_current -= __n;
return *
this; }
1023 _GLIBCXX20_CONSTEXPR
1025 operator-(difference_type __n)
const _GLIBCXX_NOEXCEPT
1026 {
return __normal_iterator(_M_current - __n); }
1028 _GLIBCXX20_CONSTEXPR
1030 base() const _GLIBCXX_NOEXCEPT
1031 {
return _M_current; }
1042 #if __cpp_lib_three_way_comparison
1043 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1044 requires requires (_IteratorL __lhs, _IteratorR __rhs)
1045 { { __lhs == __rhs } -> std::convertible_to<bool>; }
1047 operator==(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1048 const __normal_iterator<_IteratorR, _Container>& __rhs)
1049 noexcept(noexcept(__lhs.base() == __rhs.base()))
1050 {
return __lhs.base() == __rhs.base(); }
1052 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1053 constexpr std::__detail::__synth3way_t<_IteratorR, _IteratorL>
1054 operator<=>(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1055 const __normal_iterator<_IteratorR, _Container>& __rhs)
1056 noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base())))
1057 {
return std::__detail::__synth3way(__lhs.base(), __rhs.base()); }
1060 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1061 _GLIBCXX20_CONSTEXPR
1063 operator==(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1064 const __normal_iterator<_IteratorR, _Container>& __rhs)
1066 {
return __lhs.base() == __rhs.base(); }
1068 template<
typename _Iterator,
typename _Container>
1069 _GLIBCXX20_CONSTEXPR
1071 operator==(
const __normal_iterator<_Iterator, _Container>& __lhs,
1072 const __normal_iterator<_Iterator, _Container>& __rhs)
1074 {
return __lhs.base() == __rhs.base(); }
1076 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1077 _GLIBCXX20_CONSTEXPR
1079 operator!=(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1080 const __normal_iterator<_IteratorR, _Container>& __rhs)
1082 {
return __lhs.base() != __rhs.base(); }
1084 template<
typename _Iterator,
typename _Container>
1085 _GLIBCXX20_CONSTEXPR
1087 operator!=(
const __normal_iterator<_Iterator, _Container>& __lhs,
1088 const __normal_iterator<_Iterator, _Container>& __rhs)
1090 {
return __lhs.base() != __rhs.base(); }
1093 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1095 operator<(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1096 const __normal_iterator<_IteratorR, _Container>& __rhs)
1098 {
return __lhs.base() < __rhs.base(); }
1100 template<
typename _Iterator,
typename _Container>
1101 _GLIBCXX20_CONSTEXPR
1103 operator<(
const __normal_iterator<_Iterator, _Container>& __lhs,
1104 const __normal_iterator<_Iterator, _Container>& __rhs)
1106 {
return __lhs.base() < __rhs.base(); }
1108 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1110 operator>(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1111 const __normal_iterator<_IteratorR, _Container>& __rhs)
1113 {
return __lhs.base() > __rhs.base(); }
1115 template<
typename _Iterator,
typename _Container>
1116 _GLIBCXX20_CONSTEXPR
1118 operator>(
const __normal_iterator<_Iterator, _Container>& __lhs,
1119 const __normal_iterator<_Iterator, _Container>& __rhs)
1121 {
return __lhs.base() > __rhs.base(); }
1123 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1125 operator<=(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1126 const __normal_iterator<_IteratorR, _Container>& __rhs)
1128 {
return __lhs.base() <= __rhs.base(); }
1130 template<
typename _Iterator,
typename _Container>
1131 _GLIBCXX20_CONSTEXPR
1133 operator<=(
const __normal_iterator<_Iterator, _Container>& __lhs,
1134 const __normal_iterator<_Iterator, _Container>& __rhs)
1136 {
return __lhs.base() <= __rhs.base(); }
1138 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1140 operator>=(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1141 const __normal_iterator<_IteratorR, _Container>& __rhs)
1143 {
return __lhs.base() >= __rhs.base(); }
1145 template<
typename _Iterator,
typename _Container>
1146 _GLIBCXX20_CONSTEXPR
1148 operator>=(
const __normal_iterator<_Iterator, _Container>& __lhs,
1149 const __normal_iterator<_Iterator, _Container>& __rhs)
1151 {
return __lhs.base() >= __rhs.base(); }
1152 #endif // three-way comparison
1158 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1159 #if __cplusplus >= 201103L
1161 _GLIBCXX20_CONSTEXPR
1163 operator-(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1164 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
1165 -> decltype(__lhs.base() - __rhs.base())
1167 inline typename __normal_iterator<_IteratorL, _Container>::difference_type
1168 operator-(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1169 const __normal_iterator<_IteratorR, _Container>& __rhs)
1171 {
return __lhs.base() - __rhs.base(); }
1173 template<
typename _Iterator,
typename _Container>
1174 _GLIBCXX20_CONSTEXPR
1175 inline typename __normal_iterator<_Iterator, _Container>::difference_type
1176 operator-(
const __normal_iterator<_Iterator, _Container>& __lhs,
1177 const __normal_iterator<_Iterator, _Container>& __rhs)
1179 {
return __lhs.base() - __rhs.base(); }
1181 template<
typename _Iterator,
typename _Container>
1182 _GLIBCXX20_CONSTEXPR
1183 inline __normal_iterator<_Iterator, _Container>
1184 operator+(
typename __normal_iterator<_Iterator, _Container>::difference_type
1185 __n,
const __normal_iterator<_Iterator, _Container>& __i)
1187 {
return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
1189 _GLIBCXX_END_NAMESPACE_VERSION
1192 namespace std _GLIBCXX_VISIBILITY(default)
1194 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1196 template<
typename _Iterator,
typename _Container>
1197 _GLIBCXX20_CONSTEXPR
1199 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
1201 {
return __it.base(); }
1203 #if __cplusplus >= 201103L
1209 #if __cplusplus > 201703L && __cpp_lib_concepts
1210 template<semiregular _Sent>
1216 noexcept(is_nothrow_default_constructible_v<_Sent>)
1220 move_sentinel(_Sent __s)
1221 noexcept(is_nothrow_move_constructible_v<_Sent>)
1224 template<
typename _S2> requires convertible_to<const _S2&, _Sent>
1226 move_sentinel(
const move_sentinel<_S2>& __s)
1227 noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
1228 : _M_last(__s.base())
1231 template<
typename _S2> requires assignable_from<_Sent&, const _S2&>
1232 constexpr move_sentinel&
1233 operator=(
const move_sentinel<_S2>& __s)
1234 noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
1236 _M_last = __s.base();
1242 noexcept(is_nothrow_copy_constructible_v<_Sent>)
1259 template<
typename _Iterator>
1262 _Iterator _M_current;
1265 #if __cplusplus > 201703L && __cpp_lib_concepts
1266 using __base_cat =
typename __traits_type::iterator_category;
1268 using __base_ref =
typename __traits_type::reference;
1272 using iterator_type = _Iterator;
1274 #if __cplusplus > 201703L && __cpp_lib_concepts
1276 using iterator_category
1277 = __detail::__clamp_iter_cat<__base_cat, random_access_iterator_tag>;
1278 using value_type = iter_value_t<_Iterator>;
1279 using difference_type = iter_difference_t<_Iterator>;
1280 using pointer = _Iterator;
1281 using reference = iter_rvalue_reference_t<_Iterator>;
1283 typedef typename __traits_type::iterator_category iterator_category;
1284 typedef typename __traits_type::value_type value_type;
1285 typedef typename __traits_type::difference_type difference_type;
1287 typedef _Iterator pointer;
1291 typename remove_reference<__base_ref>::type&&,
1292 __base_ref>::type reference;
1295 _GLIBCXX17_CONSTEXPR
1299 explicit _GLIBCXX17_CONSTEXPR
1303 template<
typename _Iter>
1304 _GLIBCXX17_CONSTEXPR
1306 : _M_current(__i.base()) { }
1308 #if __cplusplus <= 201703L
1309 _GLIBCXX17_CONSTEXPR iterator_type
1311 {
return _M_current; }
1313 constexpr iterator_type
1315 #if __cpp_lib_concepts
1316 requires copy_constructible<iterator_type>
1318 {
return _M_current; }
1320 constexpr iterator_type
1325 _GLIBCXX17_CONSTEXPR reference
1327 {
return static_cast<reference
>(*_M_current); }
1329 _GLIBCXX17_CONSTEXPR pointer
1331 {
return _M_current; }
1348 #if __cpp_lib_concepts
1350 operator++(
int) requires (!forward_iterator<_Iterator>)
1370 operator+(difference_type __n)
const
1374 operator+=(difference_type __n)
1381 operator-(difference_type __n)
const
1385 operator-=(difference_type __n)
1391 _GLIBCXX17_CONSTEXPR reference
1392 operator[](difference_type __n)
const
1395 #if __cplusplus > 201703L && __cpp_lib_concepts
1396 template<sentinel_for<_Iterator> _Sent>
1397 friend constexpr
bool
1398 operator==(
const move_iterator& __x,
const move_sentinel<_Sent>& __y)
1399 {
return __x.base() == __y.base(); }
1401 template<sized_sentinel_for<_Iterator> _Sent>
1402 friend constexpr iter_difference_t<_Iterator>
1403 operator-(
const move_sentinel<_Sent>& __x,
const move_iterator& __y)
1404 {
return __x.base() - __y.base(); }
1406 template<sized_sentinel_for<_Iterator> _Sent>
1407 friend constexpr iter_difference_t<_Iterator>
1408 operator-(
const move_iterator& __x,
const move_sentinel<_Sent>& __y)
1409 {
return __x.base() - __y.base(); }
1411 friend constexpr iter_rvalue_reference_t<_Iterator>
1413 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1414 {
return ranges::iter_move(__i._M_current); }
1416 template<indirectly_swappable<_Iterator> _Iter2>
1417 friend constexpr
void
1419 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1420 {
return ranges::iter_swap(__x._M_current, __y._M_current); }
1424 template<
typename _IteratorL,
typename _IteratorR>
1425 inline _GLIBCXX17_CONSTEXPR
bool
1428 #if __cplusplus > 201703L && __cpp_lib_concepts
1429 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1431 {
return __x.base() == __y.base(); }
1433 #if __cpp_lib_three_way_comparison
1434 template<
typename _IteratorL,
1435 three_way_comparable_with<_IteratorL> _IteratorR>
1436 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
1437 operator<=>(
const move_iterator<_IteratorL>& __x,
1438 const move_iterator<_IteratorR>& __y)
1439 {
return __x.base() <=> __y.base(); }
1441 template<
typename _IteratorL,
typename _IteratorR>
1442 inline _GLIBCXX17_CONSTEXPR
bool
1443 operator!=(
const move_iterator<_IteratorL>& __x,
1444 const move_iterator<_IteratorR>& __y)
1445 {
return !(__x == __y); }
1448 template<
typename _IteratorL,
typename _IteratorR>
1449 inline _GLIBCXX17_CONSTEXPR
bool
1450 operator<(
const move_iterator<_IteratorL>& __x,
1451 const move_iterator<_IteratorR>& __y)
1452 #if __cplusplus > 201703L && __cpp_lib_concepts
1453 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1455 {
return __x.base() < __y.base(); }
1457 template<
typename _IteratorL,
typename _IteratorR>
1458 inline _GLIBCXX17_CONSTEXPR
bool
1459 operator<=(
const move_iterator<_IteratorL>& __x,
1460 const move_iterator<_IteratorR>& __y)
1461 #if __cplusplus > 201703L && __cpp_lib_concepts
1462 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1464 {
return !(__y < __x); }
1466 template<
typename _IteratorL,
typename _IteratorR>
1467 inline _GLIBCXX17_CONSTEXPR
bool
1468 operator>(
const move_iterator<_IteratorL>& __x,
1469 const move_iterator<_IteratorR>& __y)
1470 #if __cplusplus > 201703L && __cpp_lib_concepts
1471 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1473 {
return __y < __x; }
1475 template<
typename _IteratorL,
typename _IteratorR>
1476 inline _GLIBCXX17_CONSTEXPR
bool
1477 operator>=(
const move_iterator<_IteratorL>& __x,
1478 const move_iterator<_IteratorR>& __y)
1479 #if __cplusplus > 201703L && __cpp_lib_concepts
1480 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1482 {
return !(__x < __y); }
1484 #if ! (__cplusplus > 201703L && __cpp_lib_concepts)
1492 template<
typename _Iterator>
1493 inline _GLIBCXX17_CONSTEXPR
bool
1494 operator==(
const move_iterator<_Iterator>& __x,
1495 const move_iterator<_Iterator>& __y)
1496 {
return __x.base() == __y.base(); }
1498 template<
typename _Iterator>
1499 inline _GLIBCXX17_CONSTEXPR
bool
1500 operator!=(
const move_iterator<_Iterator>& __x,
1501 const move_iterator<_Iterator>& __y)
1502 {
return !(__x == __y); }
1504 template<
typename _Iterator>
1505 inline _GLIBCXX17_CONSTEXPR
bool
1506 operator<(
const move_iterator<_Iterator>& __x,
1507 const move_iterator<_Iterator>& __y)
1508 {
return __x.base() < __y.base(); }
1510 template<
typename _Iterator>
1511 inline _GLIBCXX17_CONSTEXPR
bool
1512 operator<=(
const move_iterator<_Iterator>& __x,
1513 const move_iterator<_Iterator>& __y)
1514 {
return !(__y < __x); }
1516 template<
typename _Iterator>
1517 inline _GLIBCXX17_CONSTEXPR
bool
1518 operator>(
const move_iterator<_Iterator>& __x,
1519 const move_iterator<_Iterator>& __y)
1520 {
return __y < __x; }
1522 template<
typename _Iterator>
1523 inline _GLIBCXX17_CONSTEXPR
bool
1524 operator>=(
const move_iterator<_Iterator>& __x,
1525 const move_iterator<_Iterator>& __y)
1526 {
return !(__x < __y); }
1530 template<
typename _IteratorL,
typename _IteratorR>
1531 inline _GLIBCXX17_CONSTEXPR
auto
1532 operator-(
const move_iterator<_IteratorL>& __x,
1533 const move_iterator<_IteratorR>& __y)
1534 -> decltype(__x.base() - __y.base())
1535 {
return __x.base() - __y.base(); }
1537 template<
typename _Iterator>
1538 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1539 operator+(
typename move_iterator<_Iterator>::difference_type __n,
1540 const move_iterator<_Iterator>& __x)
1541 {
return __x + __n; }
1543 template<
typename _Iterator>
1544 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1545 make_move_iterator(_Iterator __i)
1546 {
return move_iterator<_Iterator>(
std::move(__i)); }
1548 template<
typename _Iterator,
typename _ReturnType
1549 =
typename conditional<__move_if_noexcept_cond
1550 <
typename iterator_traits<_Iterator>::value_type>::value,
1551 _Iterator, move_iterator<_Iterator>>::type>
1552 inline _GLIBCXX17_CONSTEXPR _ReturnType
1553 __make_move_if_noexcept_iterator(_Iterator __i)
1554 {
return _ReturnType(__i); }
1558 template<
typename _Tp,
typename _ReturnType
1559 =
typename conditional<__move_if_noexcept_cond<_Tp>::value,
1560 const _Tp*, move_iterator<_Tp*>>::type>
1561 inline _GLIBCXX17_CONSTEXPR _ReturnType
1562 __make_move_if_noexcept_iterator(_Tp* __i)
1563 {
return _ReturnType(__i); }
1565 #if __cplusplus > 201703L && __cpp_lib_concepts
1570 template<input_or_output_iterator _It>
1571 class _Common_iter_proxy
1573 iter_value_t<_It> _M_keep;
1575 _Common_iter_proxy(iter_reference_t<_It>&& __x)
1578 template<
typename _Iter,
typename _Sent>
1579 friend class common_iterator;
1582 const iter_value_t<_It>*
1587 template<
typename _It>
1588 concept __common_iter_has_arrow = indirectly_readable<const _It>
1589 && (requires(
const _It& __it) { __it.operator->(); }
1590 || is_reference_v<iter_reference_t<_It>>
1591 || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1596 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1597 requires (!same_as<_It, _Sent>) && copyable<_It>
1598 class common_iterator
1600 template<
typename _Tp,
typename _Up>
1601 static constexpr
bool
1604 if constexpr (is_trivially_default_constructible_v<_Tp>)
1605 return is_nothrow_assignable_v<_Tp, _Up>;
1607 return is_nothrow_constructible_v<_Tp, _Up>;
1610 template<
typename _It2,
typename _Sent2>
1611 static constexpr
bool
1613 {
return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1618 noexcept(is_nothrow_default_constructible_v<_It>)
1619 : _M_it(), _M_index(0)
1623 common_iterator(_It __i)
1624 noexcept(is_nothrow_move_constructible_v<_It>)
1625 : _M_it(
std::
move(__i)), _M_index(0)
1629 common_iterator(_Sent __s)
1630 noexcept(is_nothrow_move_constructible_v<_Sent>)
1631 : _M_sent(
std::
move(__s)), _M_index(1)
1634 template<
typename _It2,
typename _Sent2>
1635 requires convertible_to<const _It2&, _It>
1636 && convertible_to<const _Sent2&, _Sent>
1638 common_iterator(
const common_iterator<_It2, _Sent2>& __x)
1639 noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1640 : _M_valueless(), _M_index(__x._M_index)
1644 if constexpr (is_trivially_default_constructible_v<_It>)
1649 else if (_M_index == 1)
1651 if constexpr (is_trivially_default_constructible_v<_Sent>)
1659 common_iterator(
const common_iterator& __x)
1660 noexcept(_S_noexcept<const _It&, const _Sent&>())
1661 : _M_valueless(), _M_index(__x._M_index)
1665 if constexpr (is_trivially_default_constructible_v<_It>)
1670 else if (_M_index == 1)
1672 if constexpr (is_trivially_default_constructible_v<_Sent>)
1680 operator=(
const common_iterator& __x)
1681 noexcept(is_nothrow_copy_assignable_v<_It>
1682 && is_nothrow_copy_assignable_v<_Sent>
1683 && is_nothrow_copy_constructible_v<_It>
1684 && is_nothrow_copy_constructible_v<_Sent>)
1686 return this->
operator=<_It, _Sent>(__x);
1689 template<
typename _It2,
typename _Sent2>
1690 requires convertible_to<const _It2&, _It>
1691 && convertible_to<const _Sent2&, _Sent>
1692 && assignable_from<_It&, const _It2&>
1693 && assignable_from<_Sent&, const _Sent2&>
1695 operator=(
const common_iterator<_It2, _Sent2>& __x)
1696 noexcept(is_nothrow_constructible_v<_It, const _It2&>
1697 && is_nothrow_constructible_v<_Sent, const _Sent2&>
1698 && is_nothrow_assignable_v<_It, const _It2&>
1699 && is_nothrow_assignable_v<_Sent, const _Sent2&>)
1701 switch(_M_index << 2 | __x._M_index)
1707 _M_sent = __x._M_sent;
1726 __glibcxx_assert(__x._M_has_value());
1727 __builtin_unreachable();
1748 __glibcxx_assert(_M_index == 0);
1753 operator*() const requires __detail::__dereferenceable<const _It>
1755 __glibcxx_assert(_M_index == 0);
1760 operator->() const requires __detail::__common_iter_has_arrow<_It>
1762 __glibcxx_assert(_M_index == 0);
1763 if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
1765 else if constexpr (is_reference_v<iter_reference_t<_It>>)
1767 auto&& __tmp = *_M_it;
1771 return _Common_iter_proxy(*_M_it);
1777 __glibcxx_assert(_M_index == 0);
1785 __glibcxx_assert(_M_index == 0);
1786 if constexpr (forward_iterator<_It>)
1788 common_iterator __tmp = *
this;
1796 template<
typename _It2, sentinel_for<_It> _Sent2>
1797 requires sentinel_for<_Sent, _It2>
1799 operator==(
const common_iterator& __x,
1800 const common_iterator<_It2, _Sent2>& __y)
1802 switch(__x._M_index << 2 | __y._M_index)
1808 return __x._M_it == __y._M_sent;
1810 return __x._M_sent == __y._M_it;
1812 __glibcxx_assert(__x._M_has_value());
1813 __glibcxx_assert(__y._M_has_value());
1814 __builtin_unreachable();
1818 template<
typename _It2, sentinel_for<_It> _Sent2>
1819 requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
1821 operator==(
const common_iterator& __x,
1822 const common_iterator<_It2, _Sent2>& __y)
1824 switch(__x._M_index << 2 | __y._M_index)
1829 return __x._M_it == __y._M_it;
1831 return __x._M_it == __y._M_sent;
1833 return __x._M_sent == __y._M_it;
1835 __glibcxx_assert(__x._M_has_value());
1836 __glibcxx_assert(__y._M_has_value());
1837 __builtin_unreachable();
1841 template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
1842 requires sized_sentinel_for<_Sent, _It2>
1843 friend iter_difference_t<_It2>
1845 const common_iterator<_It2, _Sent2>& __y)
1847 switch(__x._M_index << 2 | __y._M_index)
1852 return __x._M_it - __y._M_it;
1854 return __x._M_it - __y._M_sent;
1856 return __x._M_sent - __y._M_it;
1858 __glibcxx_assert(__x._M_has_value());
1859 __glibcxx_assert(__y._M_has_value());
1860 __builtin_unreachable();
1864 friend iter_rvalue_reference_t<_It>
1865 iter_move(
const common_iterator& __i)
1866 noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
1867 requires input_iterator<_It>
1869 __glibcxx_assert(__i._M_index == 0);
1870 return ranges::iter_move(__i._M_it);
1873 template<indirectly_swappable<_It> _It2,
typename _Sent2>
1875 iter_swap(
const common_iterator& __x,
1876 const common_iterator<_It2, _Sent2>& __y)
1877 noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
1878 std::declval<const _It2&>())))
1880 __glibcxx_assert(__x._M_index == 0);
1881 __glibcxx_assert(__y._M_index == 0);
1882 return ranges::iter_swap(__x._M_it, __y._M_it);
1886 template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
1887 friend class common_iterator;
1889 bool _M_has_value() const noexcept {
return _M_index < 2; }
1895 unsigned char _M_valueless;
1897 unsigned char _M_index;
1900 template<
typename _It,
typename _Sent>
1901 struct incrementable_traits<common_iterator<_It, _Sent>>
1903 using difference_type = iter_difference_t<_It>;
1909 template<
typename _It,
typename _Sent>
1910 struct __common_iter_ptr
1915 template<
typename _It,
typename _Sent>
1916 requires __detail::__common_iter_has_arrow<_It>
1917 struct __common_iter_ptr<_It, _Sent>
1919 using common_iterator = std::common_iterator<_It, _Sent>;
1922 = decltype(std::declval<const common_iterator&>().operator->());
1926 template<input_iterator _It,
typename _Sent>
1927 struct iterator_traits<common_iterator<_It, _Sent>>
1929 using iterator_concept = conditional_t<forward_iterator<_It>,
1930 forward_iterator_tag, input_iterator_tag>;
1931 using iterator_category = __detail::__clamp_iter_cat<
1932 typename iterator_traits<_It>::iterator_category,
1933 forward_iterator_tag, input_iterator_tag>;
1934 using value_type = iter_value_t<_It>;
1935 using difference_type = iter_difference_t<_It>;
1936 using pointer =
typename __detail::__common_iter_ptr<_It, _Sent>::type;
1937 using reference = iter_reference_t<_It>;
1943 template<input_or_output_iterator _It>
1944 class counted_iterator
1947 using iterator_type = _It;
1949 constexpr counted_iterator() =
default;
1952 counted_iterator(_It __i, iter_difference_t<_It> __n)
1953 : _M_current(
std::
move(__i)), _M_length(__n)
1954 { __glibcxx_assert(__n >= 0); }
1956 template<
typename _It2>
1957 requires convertible_to<const _It2&, _It>
1959 counted_iterator(
const counted_iterator<_It2>& __x)
1960 : _M_current(__x._M_current), _M_length(__x._M_length)
1963 template<
typename _It2>
1964 requires assignable_from<_It&, const _It2&>
1965 constexpr counted_iterator&
1966 operator=(
const counted_iterator<_It2>& __x)
1968 _M_current = __x._M_current;
1969 _M_length = __x._M_length;
1975 noexcept(is_nothrow_copy_constructible_v<_It>)
1976 requires copy_constructible<_It>
1977 {
return _M_current; }
1981 noexcept(is_nothrow_move_constructible_v<_It>)
1984 constexpr iter_difference_t<_It>
1985 count() const noexcept {
return _M_length; }
1987 constexpr decltype(
auto)
1989 noexcept(noexcept(*_M_current))
1990 {
return *_M_current; }
1992 constexpr decltype(
auto)
1994 noexcept(noexcept(*_M_current))
1995 requires __detail::__dereferenceable<const _It>
1996 {
return *_M_current; }
1998 constexpr counted_iterator&
2001 __glibcxx_assert(_M_length > 0);
2010 __glibcxx_assert(_M_length > 0);
2014 return _M_current++;
2022 constexpr counted_iterator
2023 operator++(
int) requires forward_iterator<_It>
2030 constexpr counted_iterator&
2031 operator--() requires bidirectional_iterator<_It>
2038 constexpr counted_iterator
2039 operator--(
int) requires bidirectional_iterator<_It>
2046 constexpr counted_iterator
2047 operator+(iter_difference_t<_It> __n)
const
2048 requires random_access_iterator<_It>
2049 {
return counted_iterator(_M_current + __n, _M_length - __n); }
2051 friend constexpr counted_iterator
2052 operator+(iter_difference_t<_It> __n,
const counted_iterator& __x)
2053 requires random_access_iterator<_It>
2054 {
return __x + __n; }
2056 constexpr counted_iterator&
2057 operator+=(iter_difference_t<_It> __n)
2058 requires random_access_iterator<_It>
2060 __glibcxx_assert(__n <= _M_length);
2066 constexpr counted_iterator
2067 operator-(iter_difference_t<_It> __n)
const
2068 requires random_access_iterator<_It>
2069 {
return counted_iterator(_M_current - __n, _M_length + __n); }
2071 template<common_with<_It> _It2>
2072 friend constexpr iter_difference_t<_It2>
2074 const counted_iterator<_It2>& __y)
2075 {
return __y._M_length - __x._M_length; }
2077 friend constexpr iter_difference_t<_It>
2078 operator-(
const counted_iterator& __x, default_sentinel_t)
2079 {
return -__x._M_length; }
2081 friend constexpr iter_difference_t<_It>
2082 operator-(default_sentinel_t,
const counted_iterator& __y)
2083 {
return __y._M_length; }
2085 constexpr counted_iterator&
2086 operator-=(iter_difference_t<_It> __n)
2087 requires random_access_iterator<_It>
2089 __glibcxx_assert(-__n <= _M_length);
2095 constexpr decltype(
auto)
2096 operator[](iter_difference_t<_It> __n) const
2097 noexcept(noexcept(_M_current[__n]))
2098 requires random_access_iterator<_It>
2100 __glibcxx_assert(__n < _M_length);
2101 return _M_current[__n];
2104 template<common_with<_It> _It2>
2105 friend constexpr
bool
2106 operator==(
const counted_iterator& __x,
2107 const counted_iterator<_It2>& __y)
2108 {
return __x._M_length == __y._M_length; }
2110 friend constexpr
bool
2111 operator==(
const counted_iterator& __x, default_sentinel_t)
2112 {
return __x._M_length == 0; }
2114 template<common_with<_It> _It2>
2115 friend constexpr strong_ordering
2116 operator<=>(
const counted_iterator& __x,
2117 const counted_iterator<_It2>& __y)
2118 {
return __y._M_length <=> __x._M_length; }
2120 friend constexpr iter_rvalue_reference_t<_It>
2121 iter_move(
const counted_iterator& __i)
2122 noexcept(noexcept(ranges::iter_move(__i._M_current)))
2123 requires input_iterator<_It>
2124 {
return ranges::iter_move(__i._M_current); }
2126 template<indirectly_swappable<_It> _It2>
2127 friend constexpr
void
2128 iter_swap(
const counted_iterator& __x,
2129 const counted_iterator<_It2>& __y)
2130 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2131 { ranges::iter_swap(__x._M_current, __y._M_current); }
2134 template<input_or_output_iterator _It2>
friend class counted_iterator;
2136 _It _M_current = _It();
2137 iter_difference_t<_It> _M_length = 0;
2140 template<
typename _It>
2141 struct incrementable_traits<counted_iterator<_It>>
2143 using difference_type = iter_difference_t<_It>;
2146 template<input_iterator _It>
2147 struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2149 using pointer = void;
2155 template<
typename _Iterator>
2157 __niter_base(move_iterator<_Iterator> __it)
2158 -> decltype(make_move_iterator(__niter_base(__it.base())))
2159 {
return make_move_iterator(__niter_base(__it.base())); }
2161 template<
typename _Iterator>
2162 struct __is_move_iterator<move_iterator<_Iterator> >
2164 enum { __value = 1 };
2165 typedef __true_type __type;
2168 template<
typename _Iterator>
2170 __miter_base(move_iterator<_Iterator> __it)
2171 -> decltype(__miter_base(__it.base()))
2172 {
return __miter_base(__it.base()); }
2174 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2175 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2176 std::__make_move_if_noexcept_iterator(_Iter)
2178 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2179 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2182 #if __cpp_deduction_guides >= 201606
2185 template<
typename _InputIterator>
2187 typename iterator_traits<_InputIterator>::value_type::first_type>;
2189 template<
typename _InputIterator>
2190 using __iter_val_t =
2191 typename iterator_traits<_InputIterator>::value_type::second_type;
2193 template<
typename _T1,
typename _T2>
2196 template<
typename _InputIterator>
2197 using __iter_to_alloc_t =
2198 pair<add_const_t<__iter_key_t<_InputIterator>>,
2199 __iter_val_t<_InputIterator>>;
2200 #endif // __cpp_deduction_guides
2202 _GLIBCXX_END_NAMESPACE_VERSION
2205 #ifdef _GLIBCXX_DEBUG