60 #ifndef _STL_ITERATOR_H
61 #define _STL_ITERATOR_H 1
68 #if __cplusplus >= 201103L
72 #if __cplusplus > 201402L
73 # define __cpp_lib_array_constexpr 201803
76 #if __cplusplus > 201703L
82 namespace std _GLIBCXX_VISIBILITY(default)
84 _GLIBCXX_BEGIN_NAMESPACE_VERSION
91 #if __cplusplus > 201703L && __cpp_lib_concepts
96 template<
typename _Cat,
typename _Limit,
typename _Otherwise = _Cat>
97 using __clamp_iter_cat
98 = conditional_t<derived_from<_Cat, _Limit>, _Limit, _Otherwise>;
121 template<
typename _Iterator>
123 :
public iterator<typename iterator_traits<_Iterator>::iterator_category,
124 typename iterator_traits<_Iterator>::value_type,
125 typename iterator_traits<_Iterator>::difference_type,
126 typename iterator_traits<_Iterator>::pointer,
127 typename iterator_traits<_Iterator>::reference>
135 typedef _Iterator iterator_type;
136 typedef typename __traits_type::difference_type difference_type;
137 typedef typename __traits_type::pointer pointer;
138 typedef typename __traits_type::reference reference;
140 #if __cplusplus > 201703L && __cpp_lib_concepts
141 using iterator_concept
146 = __detail::__clamp_iter_cat<
typename __traits_type::iterator_category,
163 explicit _GLIBCXX17_CONSTEXPR
171 : current(__x.current) { }
173 #if __cplusplus >= 201103L
181 template<
typename _Iter>
184 : current(__x.
base()) { }
189 _GLIBCXX17_CONSTEXPR iterator_type
203 _GLIBCXX17_CONSTEXPR reference
206 _Iterator __tmp = current;
215 _GLIBCXX17_CONSTEXPR pointer
217 #if __cplusplus > 201703L && __cpp_concepts >= 201907L
218 requires is_pointer_v<_Iterator>
219 || requires(
const _Iterator __i) { __i.operator->(); }
224 _Iterator __tmp = current;
226 return _S_to_pointer(__tmp);
328 _GLIBCXX17_CONSTEXPR reference
330 {
return *(*
this + __n); }
333 template<
typename _Tp>
334 static _GLIBCXX17_CONSTEXPR _Tp*
335 _S_to_pointer(_Tp* __p)
338 template<
typename _Tp>
339 static _GLIBCXX17_CONSTEXPR pointer
340 _S_to_pointer(_Tp __t)
341 {
return __t.operator->(); }
354 #if __cplusplus <= 201703L || ! defined __cpp_lib_concepts
355 template<
typename _Iterator>
356 inline _GLIBCXX17_CONSTEXPR
bool
359 {
return __x.
base() == __y.
base(); }
361 template<
typename _Iterator>
362 inline _GLIBCXX17_CONSTEXPR
bool
363 operator<(
const reverse_iterator<_Iterator>& __x,
364 const reverse_iterator<_Iterator>& __y)
365 {
return __y.base() < __x.base(); }
367 template<
typename _Iterator>
368 inline _GLIBCXX17_CONSTEXPR
bool
369 operator!=(
const reverse_iterator<_Iterator>& __x,
370 const reverse_iterator<_Iterator>& __y)
371 {
return !(__x == __y); }
373 template<
typename _Iterator>
374 inline _GLIBCXX17_CONSTEXPR
bool
375 operator>(
const reverse_iterator<_Iterator>& __x,
376 const reverse_iterator<_Iterator>& __y)
377 {
return __y < __x; }
379 template<
typename _Iterator>
380 inline _GLIBCXX17_CONSTEXPR
bool
381 operator<=(
const reverse_iterator<_Iterator>& __x,
382 const reverse_iterator<_Iterator>& __y)
383 {
return !(__y < __x); }
385 template<
typename _Iterator>
386 inline _GLIBCXX17_CONSTEXPR
bool
387 operator>=(
const reverse_iterator<_Iterator>& __x,
388 const reverse_iterator<_Iterator>& __y)
389 {
return !(__x < __y); }
393 template<
typename _IteratorL,
typename _IteratorR>
394 inline _GLIBCXX17_CONSTEXPR
bool
395 operator==(
const reverse_iterator<_IteratorL>& __x,
396 const reverse_iterator<_IteratorR>& __y)
397 {
return __x.base() == __y.base(); }
399 template<
typename _IteratorL,
typename _IteratorR>
400 inline _GLIBCXX17_CONSTEXPR
bool
401 operator<(
const reverse_iterator<_IteratorL>& __x,
402 const reverse_iterator<_IteratorR>& __y)
403 {
return __y.base() < __x.base(); }
405 template<
typename _IteratorL,
typename _IteratorR>
406 inline _GLIBCXX17_CONSTEXPR
bool
407 operator!=(
const reverse_iterator<_IteratorL>& __x,
408 const reverse_iterator<_IteratorR>& __y)
409 {
return !(__x == __y); }
411 template<
typename _IteratorL,
typename _IteratorR>
412 inline _GLIBCXX17_CONSTEXPR
bool
413 operator>(
const reverse_iterator<_IteratorL>& __x,
414 const reverse_iterator<_IteratorR>& __y)
415 {
return __y < __x; }
417 template<
typename _IteratorL,
typename _IteratorR>
418 inline _GLIBCXX17_CONSTEXPR
bool
419 operator<=(
const reverse_iterator<_IteratorL>& __x,
420 const reverse_iterator<_IteratorR>& __y)
421 {
return !(__y < __x); }
423 template<
typename _IteratorL,
typename _IteratorR>
424 inline _GLIBCXX17_CONSTEXPR
bool
425 operator>=(
const reverse_iterator<_IteratorL>& __x,
426 const reverse_iterator<_IteratorR>& __y)
427 {
return !(__x < __y); }
429 template<
typename _IteratorL,
typename _IteratorR>
431 operator==(
const reverse_iterator<_IteratorL>& __x,
432 const reverse_iterator<_IteratorR>& __y)
433 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
434 {
return __x.base() == __y.base(); }
436 template<
typename _IteratorL,
typename _IteratorR>
438 operator!=(
const reverse_iterator<_IteratorL>& __x,
439 const reverse_iterator<_IteratorR>& __y)
440 requires requires { { __x.base() != __y.base() } -> convertible_to<bool>; }
441 {
return __x.base() != __y.base(); }
443 template<
typename _IteratorL,
typename _IteratorR>
445 operator<(
const reverse_iterator<_IteratorL>& __x,
446 const reverse_iterator<_IteratorR>& __y)
447 requires requires { { __x.base() > __y.base() } -> convertible_to<bool>; }
448 {
return __x.base() > __y.base(); }
450 template<
typename _IteratorL,
typename _IteratorR>
452 operator>(
const reverse_iterator<_IteratorL>& __x,
453 const reverse_iterator<_IteratorR>& __y)
454 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
455 {
return __x.base() < __y.base(); }
457 template<
typename _IteratorL,
typename _IteratorR>
459 operator<=(
const reverse_iterator<_IteratorL>& __x,
460 const reverse_iterator<_IteratorR>& __y)
461 requires requires { { __x.base() >= __y.base() } -> convertible_to<bool>; }
462 {
return __x.base() >= __y.base(); }
464 template<
typename _IteratorL,
typename _IteratorR>
466 operator>=(
const reverse_iterator<_IteratorL>& __x,
467 const reverse_iterator<_IteratorR>& __y)
468 requires requires { { __x.base() <= __y.base() } -> convertible_to<bool>; }
469 {
return __x.base() <= __y.base(); }
471 template<
typename _IteratorL,
472 three_way_comparable_with<_IteratorL> _IteratorR>
473 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
474 operator<=>(
const reverse_iterator<_IteratorL>& __x,
475 const reverse_iterator<_IteratorR>& __y)
476 {
return __y.base() <=> __x.base(); }
480 #if __cplusplus < 201103L
481 template<
typename _Iterator>
482 inline typename reverse_iterator<_Iterator>::difference_type
483 operator-(
const reverse_iterator<_Iterator>& __x,
484 const reverse_iterator<_Iterator>& __y)
485 {
return __y.base() - __x.base(); }
487 template<
typename _IteratorL,
typename _IteratorR>
488 inline typename reverse_iterator<_IteratorL>::difference_type
489 operator-(
const reverse_iterator<_IteratorL>& __x,
490 const reverse_iterator<_IteratorR>& __y)
491 {
return __y.base() - __x.base(); }
495 template<
typename _IteratorL,
typename _IteratorR>
496 inline _GLIBCXX17_CONSTEXPR
auto
497 operator-(
const reverse_iterator<_IteratorL>& __x,
498 const reverse_iterator<_IteratorR>& __y)
499 -> decltype(__y.base() - __x.base())
500 {
return __y.base() - __x.base(); }
503 template<
typename _Iterator>
504 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
505 operator+(
typename reverse_iterator<_Iterator>::difference_type __n,
506 const reverse_iterator<_Iterator>& __x)
507 {
return reverse_iterator<_Iterator>(__x.base() - __n); }
509 #if __cplusplus >= 201103L
511 template<
typename _Iterator>
512 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
513 __make_reverse_iterator(_Iterator __i)
514 {
return reverse_iterator<_Iterator>(__i); }
516 # if __cplusplus >= 201402L
517 # define __cpp_lib_make_reverse_iterator 201402
522 template<
typename _Iterator>
523 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
527 # if __cplusplus > 201703L && defined __cpp_lib_concepts
528 template<
typename _Iterator1,
typename _Iterator2>
529 requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
530 inline constexpr
bool
531 disable_sized_sentinel_for<reverse_iterator<_Iterator1>,
532 reverse_iterator<_Iterator2>> =
true;
536 template<
typename _Iterator>
539 __niter_base(reverse_iterator<_Iterator> __it)
540 -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
541 {
return __make_reverse_iterator(__niter_base(__it.base())); }
543 template<
typename _Iterator>
544 struct __is_move_iterator<reverse_iterator<_Iterator> >
545 : __is_move_iterator<_Iterator>
548 template<
typename _Iterator>
551 __miter_base(reverse_iterator<_Iterator> __it)
552 -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
553 {
return __make_reverse_iterator(__miter_base(__it.base())); }
567 template<
typename _Container>
569 :
public iterator<output_iterator_tag, void, void, void, void>
572 _Container* container;
577 #if __cplusplus > 201703L
584 explicit _GLIBCXX20_CONSTEXPR
599 #if __cplusplus < 201103L
601 operator=(
typename _Container::const_reference __value)
603 container->push_back(__value);
609 operator=(
const typename _Container::value_type& __value)
611 container->push_back(__value);
617 operator=(
typename _Container::value_type&& __value)
619 container->push_back(
std::move(__value));
654 template<
typename _Container>
656 inline back_insert_iterator<_Container>
670 template<
typename _Container>
672 :
public iterator<output_iterator_tag, void, void, void, void>
675 _Container* container;
680 #if __cplusplus > 201703L
687 explicit _GLIBCXX20_CONSTEXPR
702 #if __cplusplus < 201103L
704 operator=(
typename _Container::const_reference __value)
706 container->push_front(__value);
712 operator=(
const typename _Container::value_type& __value)
714 container->push_front(__value);
720 operator=(
typename _Container::value_type&& __value)
722 container->push_front(
std::move(__value));
757 template<
typename _Container>
759 inline front_insert_iterator<_Container>
777 template<
typename _Container>
779 :
public iterator<output_iterator_tag, void, void, void, void>
781 #if __cplusplus > 201703L && defined __cpp_lib_concepts
782 using _Iter = std::__detail::__range_iter_t<_Container>;
785 _Container* container =
nullptr;
786 _Iter iter = _Iter();
788 typedef typename _Container::iterator _Iter;
791 _Container* container;
799 #if __cplusplus > 201703L && defined __cpp_lib_concepts
836 #if __cplusplus < 201103L
838 operator=(
typename _Container::const_reference __value)
840 iter = container->insert(iter, __value);
847 operator=(
const typename _Container::value_type& __value)
849 iter = container->insert(iter, __value);
856 operator=(
typename _Container::value_type&& __value)
858 iter = container->insert(iter,
std::move(__value));
895 #if __cplusplus > 201703L && defined __cpp_lib_concepts
896 template<
typename _Container>
897 constexpr insert_iterator<_Container>
898 inserter(_Container& __x, std::__detail::__range_iter_t<_Container> __i)
899 {
return insert_iterator<_Container>(__x, __i); }
901 template<
typename _Container,
typename _Iterator>
902 inline insert_iterator<_Container>
906 typename _Container::iterator(__i));
912 _GLIBCXX_END_NAMESPACE_VERSION
915 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
917 _GLIBCXX_BEGIN_NAMESPACE_VERSION
926 template<
typename _Iterator,
typename _Container>
927 class __normal_iterator
930 _Iterator _M_current;
935 typedef _Iterator iterator_type;
936 typedef typename __traits_type::iterator_category iterator_category;
937 typedef typename __traits_type::value_type value_type;
938 typedef typename __traits_type::difference_type difference_type;
939 typedef typename __traits_type::reference reference;
940 typedef typename __traits_type::pointer pointer;
942 #if __cplusplus > 201703L && __cpp_lib_concepts
943 using iterator_concept = std::__detail::__iter_concept<_Iterator>;
946 _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
947 : _M_current(_Iterator()) { }
949 explicit _GLIBCXX20_CONSTEXPR
950 __normal_iterator(
const _Iterator& __i) _GLIBCXX_NOEXCEPT
951 : _M_current(__i) { }
954 template<
typename _Iter>
956 __normal_iterator(
const __normal_iterator<_Iter,
957 typename __enable_if<
958 (std::__are_same<_Iter, typename _Container::pointer>::__value),
959 _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
960 : _M_current(__i.base()) { }
966 {
return *_M_current; }
970 operator->() const _GLIBCXX_NOEXCEPT
971 {
return _M_current; }
975 operator++() _GLIBCXX_NOEXCEPT
983 operator++(
int) _GLIBCXX_NOEXCEPT
984 {
return __normal_iterator(_M_current++); }
989 operator--() _GLIBCXX_NOEXCEPT
997 operator--(
int) _GLIBCXX_NOEXCEPT
998 {
return __normal_iterator(_M_current--); }
1001 _GLIBCXX20_CONSTEXPR
1003 operator[](difference_type __n)
const _GLIBCXX_NOEXCEPT
1004 {
return _M_current[__n]; }
1006 _GLIBCXX20_CONSTEXPR
1008 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
1009 { _M_current += __n;
return *
this; }
1011 _GLIBCXX20_CONSTEXPR
1013 operator+(difference_type __n)
const _GLIBCXX_NOEXCEPT
1014 {
return __normal_iterator(_M_current + __n); }
1016 _GLIBCXX20_CONSTEXPR
1018 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
1019 { _M_current -= __n;
return *
this; }
1021 _GLIBCXX20_CONSTEXPR
1023 operator-(difference_type __n)
const _GLIBCXX_NOEXCEPT
1024 {
return __normal_iterator(_M_current - __n); }
1026 _GLIBCXX20_CONSTEXPR
1028 base() const _GLIBCXX_NOEXCEPT
1029 {
return _M_current; }
1040 #if __cpp_lib_three_way_comparison
1041 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1042 requires requires (_IteratorL __lhs, _IteratorR __rhs)
1043 { { __lhs == __rhs } -> std::convertible_to<bool>; }
1045 operator==(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1046 const __normal_iterator<_IteratorR, _Container>& __rhs)
1047 noexcept(noexcept(__lhs.base() == __rhs.base()))
1048 {
return __lhs.base() == __rhs.base(); }
1050 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1052 operator<=>(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1053 const __normal_iterator<_IteratorR, _Container>& __rhs)
1054 noexcept(noexcept(__lhs.base() <=> __rhs.base()))
1055 -> decltype(__lhs.base() <=> __rhs.base())
1056 {
return __lhs.base() <=> __rhs.base(); }
1059 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1060 _GLIBCXX20_CONSTEXPR
1062 operator==(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1063 const __normal_iterator<_IteratorR, _Container>& __rhs)
1065 {
return __lhs.base() == __rhs.base(); }
1067 template<
typename _Iterator,
typename _Container>
1068 _GLIBCXX20_CONSTEXPR
1070 operator==(
const __normal_iterator<_Iterator, _Container>& __lhs,
1071 const __normal_iterator<_Iterator, _Container>& __rhs)
1073 {
return __lhs.base() == __rhs.base(); }
1075 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1076 _GLIBCXX20_CONSTEXPR
1078 operator!=(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1079 const __normal_iterator<_IteratorR, _Container>& __rhs)
1081 {
return __lhs.base() != __rhs.base(); }
1083 template<
typename _Iterator,
typename _Container>
1084 _GLIBCXX20_CONSTEXPR
1086 operator!=(
const __normal_iterator<_Iterator, _Container>& __lhs,
1087 const __normal_iterator<_Iterator, _Container>& __rhs)
1089 {
return __lhs.base() != __rhs.base(); }
1092 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1094 operator<(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1095 const __normal_iterator<_IteratorR, _Container>& __rhs)
1097 {
return __lhs.base() < __rhs.base(); }
1099 template<
typename _Iterator,
typename _Container>
1100 _GLIBCXX20_CONSTEXPR
1102 operator<(
const __normal_iterator<_Iterator, _Container>& __lhs,
1103 const __normal_iterator<_Iterator, _Container>& __rhs)
1105 {
return __lhs.base() < __rhs.base(); }
1107 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1109 operator>(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1110 const __normal_iterator<_IteratorR, _Container>& __rhs)
1112 {
return __lhs.base() > __rhs.base(); }
1114 template<
typename _Iterator,
typename _Container>
1115 _GLIBCXX20_CONSTEXPR
1117 operator>(
const __normal_iterator<_Iterator, _Container>& __lhs,
1118 const __normal_iterator<_Iterator, _Container>& __rhs)
1120 {
return __lhs.base() > __rhs.base(); }
1122 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1124 operator<=(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1125 const __normal_iterator<_IteratorR, _Container>& __rhs)
1127 {
return __lhs.base() <= __rhs.base(); }
1129 template<
typename _Iterator,
typename _Container>
1130 _GLIBCXX20_CONSTEXPR
1132 operator<=(
const __normal_iterator<_Iterator, _Container>& __lhs,
1133 const __normal_iterator<_Iterator, _Container>& __rhs)
1135 {
return __lhs.base() <= __rhs.base(); }
1137 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1139 operator>=(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1140 const __normal_iterator<_IteratorR, _Container>& __rhs)
1142 {
return __lhs.base() >= __rhs.base(); }
1144 template<
typename _Iterator,
typename _Container>
1145 _GLIBCXX20_CONSTEXPR
1147 operator>=(
const __normal_iterator<_Iterator, _Container>& __lhs,
1148 const __normal_iterator<_Iterator, _Container>& __rhs)
1150 {
return __lhs.base() >= __rhs.base(); }
1151 #endif // three-way comparison
1157 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1158 #if __cplusplus >= 201103L
1160 _GLIBCXX20_CONSTEXPR
1162 operator-(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1163 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
1164 -> decltype(__lhs.base() - __rhs.base())
1166 inline typename __normal_iterator<_IteratorL, _Container>::difference_type
1167 operator-(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1168 const __normal_iterator<_IteratorR, _Container>& __rhs)
1170 {
return __lhs.base() - __rhs.base(); }
1172 template<
typename _Iterator,
typename _Container>
1173 _GLIBCXX20_CONSTEXPR
1174 inline typename __normal_iterator<_Iterator, _Container>::difference_type
1175 operator-(
const __normal_iterator<_Iterator, _Container>& __lhs,
1176 const __normal_iterator<_Iterator, _Container>& __rhs)
1178 {
return __lhs.base() - __rhs.base(); }
1180 template<
typename _Iterator,
typename _Container>
1181 _GLIBCXX20_CONSTEXPR
1182 inline __normal_iterator<_Iterator, _Container>
1183 operator+(
typename __normal_iterator<_Iterator, _Container>::difference_type
1184 __n,
const __normal_iterator<_Iterator, _Container>& __i)
1186 {
return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
1188 _GLIBCXX_END_NAMESPACE_VERSION
1191 namespace std _GLIBCXX_VISIBILITY(default)
1193 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1195 template<
typename _Iterator,
typename _Container>
1196 _GLIBCXX20_CONSTEXPR
1198 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
1200 {
return __it.base(); }
1202 #if __cplusplus >= 201103L
1208 #if __cplusplus > 201703L && __cpp_lib_concepts
1209 template<semiregular _Sent>
1215 noexcept(is_nothrow_default_constructible_v<_Sent>)
1219 move_sentinel(_Sent __s)
1220 noexcept(is_nothrow_move_constructible_v<_Sent>)
1223 template<
typename _S2> requires convertible_to<const _S2&, _Sent>
1225 move_sentinel(
const move_sentinel<_S2>& __s)
1226 noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
1227 : _M_last(__s.base())
1230 template<
typename _S2> requires assignable_from<_Sent&, const _S2&>
1231 constexpr move_sentinel&
1232 operator=(
const move_sentinel<_S2>& __s)
1233 noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
1235 _M_last = __s.base();
1241 noexcept(is_nothrow_copy_constructible_v<_Sent>)
1258 template<
typename _Iterator>
1261 _Iterator _M_current;
1264 #if __cplusplus > 201703L && __cpp_lib_concepts
1265 using __base_cat =
typename __traits_type::iterator_category;
1267 using __base_ref =
typename __traits_type::reference;
1271 using iterator_type = _Iterator;
1273 #if __cplusplus > 201703L && __cpp_lib_concepts
1275 using iterator_category
1276 = __detail::__clamp_iter_cat<__base_cat, random_access_iterator_tag>;
1277 using value_type = iter_value_t<_Iterator>;
1278 using difference_type = iter_difference_t<_Iterator>;
1279 using pointer = _Iterator;
1280 using reference = iter_rvalue_reference_t<_Iterator>;
1282 typedef typename __traits_type::iterator_category iterator_category;
1283 typedef typename __traits_type::value_type value_type;
1284 typedef typename __traits_type::difference_type difference_type;
1286 typedef _Iterator pointer;
1290 typename remove_reference<__base_ref>::type&&,
1291 __base_ref>::type reference;
1294 _GLIBCXX17_CONSTEXPR
1298 explicit _GLIBCXX17_CONSTEXPR
1302 template<
typename _Iter>
1303 _GLIBCXX17_CONSTEXPR
1305 : _M_current(__i.base()) { }
1307 #if __cplusplus <= 201703L
1308 _GLIBCXX17_CONSTEXPR iterator_type
1310 {
return _M_current; }
1312 constexpr iterator_type
1314 #if __cpp_lib_concepts
1315 requires copy_constructible<iterator_type>
1317 {
return _M_current; }
1319 constexpr iterator_type
1324 _GLIBCXX17_CONSTEXPR reference
1326 {
return static_cast<reference
>(*_M_current); }
1328 _GLIBCXX17_CONSTEXPR pointer
1330 {
return _M_current; }
1347 #if __cpp_lib_concepts
1349 operator++(
int) requires (!forward_iterator<_Iterator>)
1369 operator+(difference_type __n)
const
1373 operator+=(difference_type __n)
1380 operator-(difference_type __n)
const
1384 operator-=(difference_type __n)
1390 _GLIBCXX17_CONSTEXPR reference
1391 operator[](difference_type __n)
const
1394 #if __cplusplus > 201703L && __cpp_lib_concepts
1395 template<sentinel_for<_Iterator> _Sent>
1396 friend constexpr
bool
1397 operator==(
const move_iterator& __x,
const move_sentinel<_Sent>& __y)
1398 {
return __x.base() == __y.base(); }
1400 template<sized_sentinel_for<_Iterator> _Sent>
1401 friend constexpr iter_difference_t<_Iterator>
1402 operator-(
const move_sentinel<_Sent>& __x,
const move_iterator& __y)
1403 {
return __x.base() - __y.base(); }
1405 template<sized_sentinel_for<_Iterator> _Sent>
1406 friend constexpr iter_difference_t<_Iterator>
1407 operator-(
const move_iterator& __x,
const move_sentinel<_Sent>& __y)
1408 {
return __x.base() - __y.base(); }
1410 friend constexpr iter_rvalue_reference_t<_Iterator>
1412 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1413 {
return ranges::iter_move(__i._M_current); }
1415 template<indirectly_swappable<_Iterator> _Iter2>
1416 friend constexpr
void
1418 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1419 {
return ranges::iter_swap(__x._M_current, __y._M_current); }
1423 template<
typename _IteratorL,
typename _IteratorR>
1424 inline _GLIBCXX17_CONSTEXPR
bool
1427 #if __cplusplus > 201703L && __cpp_lib_concepts
1428 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1430 {
return __x.base() == __y.base(); }
1432 #if __cpp_lib_three_way_comparison
1433 template<
typename _IteratorL,
1434 three_way_comparable_with<_IteratorL> _IteratorR>
1435 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
1436 operator<=>(
const move_iterator<_IteratorL>& __x,
1437 const move_iterator<_IteratorR>& __y)
1438 {
return __x.base() <=> __y.base(); }
1440 template<
typename _IteratorL,
typename _IteratorR>
1441 inline _GLIBCXX17_CONSTEXPR
bool
1442 operator!=(
const move_iterator<_IteratorL>& __x,
1443 const move_iterator<_IteratorR>& __y)
1444 {
return !(__x == __y); }
1447 template<
typename _IteratorL,
typename _IteratorR>
1448 inline _GLIBCXX17_CONSTEXPR
bool
1449 operator<(
const move_iterator<_IteratorL>& __x,
1450 const move_iterator<_IteratorR>& __y)
1451 #if __cplusplus > 201703L && __cpp_lib_concepts
1452 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1454 {
return __x.base() < __y.base(); }
1456 template<
typename _IteratorL,
typename _IteratorR>
1457 inline _GLIBCXX17_CONSTEXPR
bool
1458 operator<=(
const move_iterator<_IteratorL>& __x,
1459 const move_iterator<_IteratorR>& __y)
1460 #if __cplusplus > 201703L && __cpp_lib_concepts
1461 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1463 {
return !(__y < __x); }
1465 template<
typename _IteratorL,
typename _IteratorR>
1466 inline _GLIBCXX17_CONSTEXPR
bool
1467 operator>(
const move_iterator<_IteratorL>& __x,
1468 const move_iterator<_IteratorR>& __y)
1469 #if __cplusplus > 201703L && __cpp_lib_concepts
1470 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1472 {
return __y < __x; }
1474 template<
typename _IteratorL,
typename _IteratorR>
1475 inline _GLIBCXX17_CONSTEXPR
bool
1476 operator>=(
const move_iterator<_IteratorL>& __x,
1477 const move_iterator<_IteratorR>& __y)
1478 #if __cplusplus > 201703L && __cpp_lib_concepts
1479 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1481 {
return !(__x < __y); }
1483 #if ! (__cplusplus > 201703L && __cpp_lib_concepts)
1491 template<
typename _Iterator>
1492 inline _GLIBCXX17_CONSTEXPR
bool
1493 operator==(
const move_iterator<_Iterator>& __x,
1494 const move_iterator<_Iterator>& __y)
1495 {
return __x.base() == __y.base(); }
1497 template<
typename _Iterator>
1498 inline _GLIBCXX17_CONSTEXPR
bool
1499 operator!=(
const move_iterator<_Iterator>& __x,
1500 const move_iterator<_Iterator>& __y)
1501 {
return !(__x == __y); }
1503 template<
typename _Iterator>
1504 inline _GLIBCXX17_CONSTEXPR
bool
1505 operator<(
const move_iterator<_Iterator>& __x,
1506 const move_iterator<_Iterator>& __y)
1507 {
return __x.base() < __y.base(); }
1509 template<
typename _Iterator>
1510 inline _GLIBCXX17_CONSTEXPR
bool
1511 operator<=(
const move_iterator<_Iterator>& __x,
1512 const move_iterator<_Iterator>& __y)
1513 {
return !(__y < __x); }
1515 template<
typename _Iterator>
1516 inline _GLIBCXX17_CONSTEXPR
bool
1517 operator>(
const move_iterator<_Iterator>& __x,
1518 const move_iterator<_Iterator>& __y)
1519 {
return __y < __x; }
1521 template<
typename _Iterator>
1522 inline _GLIBCXX17_CONSTEXPR
bool
1523 operator>=(
const move_iterator<_Iterator>& __x,
1524 const move_iterator<_Iterator>& __y)
1525 {
return !(__x < __y); }
1529 template<
typename _IteratorL,
typename _IteratorR>
1530 inline _GLIBCXX17_CONSTEXPR
auto
1531 operator-(
const move_iterator<_IteratorL>& __x,
1532 const move_iterator<_IteratorR>& __y)
1533 -> decltype(__x.base() - __y.base())
1534 {
return __x.base() - __y.base(); }
1536 template<
typename _Iterator>
1537 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1538 operator+(
typename move_iterator<_Iterator>::difference_type __n,
1539 const move_iterator<_Iterator>& __x)
1540 {
return __x + __n; }
1542 template<
typename _Iterator>
1543 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1544 make_move_iterator(_Iterator __i)
1545 {
return move_iterator<_Iterator>(
std::move(__i)); }
1547 template<
typename _Iterator,
typename _ReturnType
1548 =
typename conditional<__move_if_noexcept_cond
1549 <
typename iterator_traits<_Iterator>::value_type>::value,
1550 _Iterator, move_iterator<_Iterator>>::type>
1551 inline _GLIBCXX17_CONSTEXPR _ReturnType
1552 __make_move_if_noexcept_iterator(_Iterator __i)
1553 {
return _ReturnType(__i); }
1557 template<
typename _Tp,
typename _ReturnType
1558 =
typename conditional<__move_if_noexcept_cond<_Tp>::value,
1559 const _Tp*, move_iterator<_Tp*>>::type>
1560 inline _GLIBCXX17_CONSTEXPR _ReturnType
1561 __make_move_if_noexcept_iterator(_Tp* __i)
1562 {
return _ReturnType(__i); }
1564 #if __cplusplus > 201703L && __cpp_lib_concepts
1569 template<input_or_output_iterator _It>
1570 class _Common_iter_proxy
1572 iter_value_t<_It> _M_keep;
1574 _Common_iter_proxy(iter_reference_t<_It>&& __x)
1577 template<
typename _Iter,
typename _Sent>
1578 friend class common_iterator;
1581 const iter_value_t<_It>*
1586 template<
typename _It>
1587 concept __common_iter_has_arrow = indirectly_readable<const _It>
1588 && (requires(
const _It& __it) { __it.operator->(); }
1589 || is_reference_v<iter_reference_t<_It>>
1590 || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1595 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1596 requires (!same_as<_It, _Sent>) && copyable<_It>
1597 class common_iterator
1599 template<
typename _Tp,
typename _Up>
1600 static constexpr
bool
1603 if constexpr (is_trivially_default_constructible_v<_Tp>)
1604 return is_nothrow_assignable_v<_Tp, _Up>;
1606 return is_nothrow_constructible_v<_Tp, _Up>;
1609 template<
typename _It2,
typename _Sent2>
1610 static constexpr
bool
1612 {
return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1617 noexcept(is_nothrow_default_constructible_v<_It>)
1618 : _M_it(), _M_index(0)
1622 common_iterator(_It __i)
1623 noexcept(is_nothrow_move_constructible_v<_It>)
1624 : _M_it(
std::
move(__i)), _M_index(0)
1628 common_iterator(_Sent __s)
1629 noexcept(is_nothrow_move_constructible_v<_Sent>)
1630 : _M_sent(
std::
move(__s)), _M_index(1)
1633 template<
typename _It2,
typename _Sent2>
1634 requires convertible_to<const _It2&, _It>
1635 && convertible_to<const _Sent2&, _Sent>
1637 common_iterator(
const common_iterator<_It2, _Sent2>& __x)
1638 noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1639 : _M_valueless(), _M_index(__x._M_index)
1643 if constexpr (is_trivially_default_constructible_v<_It>)
1648 else if (_M_index == 1)
1650 if constexpr (is_trivially_default_constructible_v<_Sent>)
1658 common_iterator(
const common_iterator& __x)
1659 noexcept(_S_noexcept<const _It&, const _Sent&>())
1660 : _M_valueless(), _M_index(__x._M_index)
1664 if constexpr (is_trivially_default_constructible_v<_It>)
1669 else if (_M_index == 1)
1671 if constexpr (is_trivially_default_constructible_v<_Sent>)
1679 operator=(
const common_iterator& __x)
1680 noexcept(is_nothrow_copy_assignable_v<_It>
1681 && is_nothrow_copy_assignable_v<_Sent>
1682 && is_nothrow_copy_constructible_v<_It>
1683 && is_nothrow_copy_constructible_v<_Sent>)
1685 return this->
operator=<_It, _Sent>(__x);
1688 template<
typename _It2,
typename _Sent2>
1689 requires convertible_to<const _It2&, _It>
1690 && convertible_to<const _Sent2&, _Sent>
1691 && assignable_from<_It&, const _It2&>
1692 && assignable_from<_Sent&, const _Sent2&>
1694 operator=(
const common_iterator<_It2, _Sent2>& __x)
1695 noexcept(is_nothrow_constructible_v<_It, const _It2&>
1696 && is_nothrow_constructible_v<_Sent, const _Sent2&>
1697 && is_nothrow_assignable_v<_It, const _It2&>
1698 && is_nothrow_assignable_v<_Sent, const _Sent2&>)
1700 switch(_M_index << 2 | __x._M_index)
1706 _M_sent = __x._M_sent;
1725 __glibcxx_assert(__x._M_has_value());
1726 __builtin_unreachable();
1747 __glibcxx_assert(_M_index == 0);
1752 operator*() const requires __detail::__dereferenceable<const _It>
1754 __glibcxx_assert(_M_index == 0);
1759 operator->() const requires __detail::__common_iter_has_arrow<_It>
1761 __glibcxx_assert(_M_index == 0);
1762 if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
1764 else if constexpr (is_reference_v<iter_reference_t<_It>>)
1766 auto&& __tmp = *_M_it;
1770 return _Common_iter_proxy(*_M_it);
1776 __glibcxx_assert(_M_index == 0);
1784 __glibcxx_assert(_M_index == 0);
1785 if constexpr (forward_iterator<_It>)
1787 common_iterator __tmp = *
this;
1795 template<
typename _It2, sentinel_for<_It> _Sent2>
1796 requires sentinel_for<_Sent, _It2>
1798 operator==(
const common_iterator& __x,
1799 const common_iterator<_It2, _Sent2>& __y)
1801 switch(__x._M_index << 2 | __y._M_index)
1807 return __x._M_it == __y._M_sent;
1809 return __x._M_sent == __y._M_it;
1811 __glibcxx_assert(__x._M_has_value());
1812 __glibcxx_assert(__y._M_has_value());
1813 __builtin_unreachable();
1817 template<
typename _It2, sentinel_for<_It> _Sent2>
1818 requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
1820 operator==(
const common_iterator& __x,
1821 const common_iterator<_It2, _Sent2>& __y)
1823 switch(__x._M_index << 2 | __y._M_index)
1828 return __x._M_it == __y._M_it;
1830 return __x._M_it == __y._M_sent;
1832 return __x._M_sent == __y._M_it;
1834 __glibcxx_assert(__x._M_has_value());
1835 __glibcxx_assert(__y._M_has_value());
1836 __builtin_unreachable();
1840 template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
1841 requires sized_sentinel_for<_Sent, _It2>
1842 friend iter_difference_t<_It2>
1844 const common_iterator<_It2, _Sent2>& __y)
1846 switch(__x._M_index << 2 | __y._M_index)
1851 return __x._M_it - __y._M_it;
1853 return __x._M_it - __y._M_sent;
1855 return __x._M_sent - __y._M_it;
1857 __glibcxx_assert(__x._M_has_value());
1858 __glibcxx_assert(__y._M_has_value());
1859 __builtin_unreachable();
1863 friend iter_rvalue_reference_t<_It>
1864 iter_move(
const common_iterator& __i)
1865 noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
1866 requires input_iterator<_It>
1868 __glibcxx_assert(__i._M_index == 0);
1869 return ranges::iter_move(__i._M_it);
1872 template<indirectly_swappable<_It> _It2,
typename _Sent2>
1874 iter_swap(
const common_iterator& __x,
1875 const common_iterator<_It2, _Sent2>& __y)
1876 noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
1877 std::declval<const _It2&>())))
1879 __glibcxx_assert(__x._M_index == 0);
1880 __glibcxx_assert(__y._M_index == 0);
1881 return ranges::iter_swap(__x._M_it, __y._M_it);
1885 template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
1886 friend class common_iterator;
1888 bool _M_has_value() const noexcept {
return _M_index < 2; }
1894 unsigned char _M_valueless;
1896 unsigned char _M_index;
1899 template<
typename _It,
typename _Sent>
1900 struct incrementable_traits<common_iterator<_It, _Sent>>
1902 using difference_type = iter_difference_t<_It>;
1908 template<
typename _It,
typename _Sent>
1909 struct __common_iter_ptr
1914 template<
typename _It,
typename _Sent>
1915 requires __detail::__common_iter_has_arrow<_It>
1916 struct __common_iter_ptr<_It, _Sent>
1918 using common_iterator = std::common_iterator<_It, _Sent>;
1921 = decltype(std::declval<const common_iterator&>().operator->());
1925 template<input_iterator _It,
typename _Sent>
1926 struct iterator_traits<common_iterator<_It, _Sent>>
1928 using iterator_concept = conditional_t<forward_iterator<_It>,
1929 forward_iterator_tag, input_iterator_tag>;
1930 using iterator_category = __detail::__clamp_iter_cat<
1931 typename iterator_traits<_It>::iterator_category,
1932 forward_iterator_tag, input_iterator_tag>;
1933 using value_type = iter_value_t<_It>;
1934 using difference_type = iter_difference_t<_It>;
1935 using pointer =
typename __detail::__common_iter_ptr<_It, _Sent>::type;
1936 using reference = iter_reference_t<_It>;
1942 template<input_or_output_iterator _It>
1943 class counted_iterator
1946 using iterator_type = _It;
1948 constexpr counted_iterator() =
default;
1951 counted_iterator(_It __i, iter_difference_t<_It> __n)
1952 : _M_current(
std::
move(__i)), _M_length(__n)
1953 { __glibcxx_assert(__n >= 0); }
1955 template<
typename _It2>
1956 requires convertible_to<const _It2&, _It>
1958 counted_iterator(
const counted_iterator<_It2>& __x)
1959 : _M_current(__x._M_current), _M_length(__x._M_length)
1962 template<
typename _It2>
1963 requires assignable_from<_It&, const _It2&>
1964 constexpr counted_iterator&
1965 operator=(
const counted_iterator<_It2>& __x)
1967 _M_current = __x._M_current;
1968 _M_length = __x._M_length;
1974 noexcept(is_nothrow_copy_constructible_v<_It>)
1975 requires copy_constructible<_It>
1976 {
return _M_current; }
1980 noexcept(is_nothrow_move_constructible_v<_It>)
1983 constexpr iter_difference_t<_It>
1984 count() const noexcept {
return _M_length; }
1986 constexpr decltype(
auto)
1988 noexcept(noexcept(*_M_current))
1989 {
return *_M_current; }
1991 constexpr decltype(
auto)
1993 noexcept(noexcept(*_M_current))
1994 requires __detail::__dereferenceable<const _It>
1995 {
return *_M_current; }
1997 constexpr counted_iterator&
2000 __glibcxx_assert(_M_length > 0);
2009 __glibcxx_assert(_M_length > 0);
2013 return _M_current++;
2021 constexpr counted_iterator
2022 operator++(
int) requires forward_iterator<_It>
2029 constexpr counted_iterator&
2030 operator--() requires bidirectional_iterator<_It>
2037 constexpr counted_iterator
2038 operator--(
int) requires bidirectional_iterator<_It>
2045 constexpr counted_iterator
2046 operator+(iter_difference_t<_It> __n)
const
2047 requires random_access_iterator<_It>
2048 {
return counted_iterator(_M_current + __n, _M_length - __n); }
2050 friend constexpr counted_iterator
2051 operator+(iter_difference_t<_It> __n,
const counted_iterator& __x)
2052 requires random_access_iterator<_It>
2053 {
return __x + __n; }
2055 constexpr counted_iterator&
2056 operator+=(iter_difference_t<_It> __n)
2057 requires random_access_iterator<_It>
2059 __glibcxx_assert(__n <= _M_length);
2065 constexpr counted_iterator
2066 operator-(iter_difference_t<_It> __n)
const
2067 requires random_access_iterator<_It>
2068 {
return counted_iterator(_M_current - __n, _M_length + __n); }
2070 template<common_with<_It> _It2>
2071 friend constexpr iter_difference_t<_It2>
2073 const counted_iterator<_It2>& __y)
2074 {
return __y._M_length - __x._M_length; }
2076 friend constexpr iter_difference_t<_It>
2077 operator-(
const counted_iterator& __x, default_sentinel_t)
2078 {
return -__x._M_length; }
2080 friend constexpr iter_difference_t<_It>
2081 operator-(default_sentinel_t,
const counted_iterator& __y)
2082 {
return __y._M_length; }
2084 constexpr counted_iterator&
2085 operator-=(iter_difference_t<_It> __n)
2086 requires random_access_iterator<_It>
2088 __glibcxx_assert(-__n <= _M_length);
2094 constexpr decltype(
auto)
2095 operator[](iter_difference_t<_It> __n) const
2096 noexcept(noexcept(_M_current[__n]))
2097 requires random_access_iterator<_It>
2099 __glibcxx_assert(__n < _M_length);
2100 return _M_current[__n];
2103 template<common_with<_It> _It2>
2104 friend constexpr
bool
2105 operator==(
const counted_iterator& __x,
2106 const counted_iterator<_It2>& __y)
2107 {
return __x._M_length == __y._M_length; }
2109 friend constexpr
bool
2110 operator==(
const counted_iterator& __x, default_sentinel_t)
2111 {
return __x._M_length == 0; }
2113 template<common_with<_It> _It2>
2114 friend constexpr strong_ordering
2115 operator<=>(
const counted_iterator& __x,
2116 const counted_iterator<_It2>& __y)
2117 {
return __y._M_length <=> __x._M_length; }
2119 friend constexpr iter_rvalue_reference_t<_It>
2120 iter_move(
const counted_iterator& __i)
2121 noexcept(noexcept(ranges::iter_move(__i._M_current)))
2122 requires input_iterator<_It>
2123 {
return ranges::iter_move(__i._M_current); }
2125 template<indirectly_swappable<_It> _It2>
2126 friend constexpr
void
2127 iter_swap(
const counted_iterator& __x,
2128 const counted_iterator<_It2>& __y)
2129 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2130 { ranges::iter_swap(__x._M_current, __y._M_current); }
2133 template<input_or_output_iterator _It2>
friend class counted_iterator;
2135 _It _M_current = _It();
2136 iter_difference_t<_It> _M_length = 0;
2139 template<
typename _It>
2140 struct incrementable_traits<counted_iterator<_It>>
2142 using difference_type = iter_difference_t<_It>;
2145 template<input_iterator _It>
2146 struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2148 using pointer = void;
2154 template<
typename _Iterator>
2156 __niter_base(move_iterator<_Iterator> __it)
2157 -> decltype(make_move_iterator(__niter_base(__it.base())))
2158 {
return make_move_iterator(__niter_base(__it.base())); }
2160 template<
typename _Iterator>
2161 struct __is_move_iterator<move_iterator<_Iterator> >
2163 enum { __value = 1 };
2164 typedef __true_type __type;
2167 template<
typename _Iterator>
2169 __miter_base(move_iterator<_Iterator> __it)
2170 -> decltype(__miter_base(__it.base()))
2171 {
return __miter_base(__it.base()); }
2173 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2174 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2175 std::__make_move_if_noexcept_iterator(_Iter)
2177 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2178 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2181 #if __cpp_deduction_guides >= 201606
2184 template<
typename _InputIterator>
2186 typename iterator_traits<_InputIterator>::value_type::first_type>;
2188 template<
typename _InputIterator>
2189 using __iter_val_t =
2190 typename iterator_traits<_InputIterator>::value_type::second_type;
2192 template<
typename _T1,
typename _T2>
2195 template<
typename _InputIterator>
2196 using __iter_to_alloc_t =
2197 pair<add_const_t<__iter_key_t<_InputIterator>>,
2198 __iter_val_t<_InputIterator>>;
2199 #endif // __cpp_deduction_guides
2201 _GLIBCXX_END_NAMESPACE_VERSION
2204 #ifdef _GLIBCXX_DEBUG