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; }
1041 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1042 _GLIBCXX20_CONSTEXPR
1044 operator==(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1045 const __normal_iterator<_IteratorR, _Container>& __rhs)
1047 {
return __lhs.base() == __rhs.base(); }
1049 template<
typename _Iterator,
typename _Container>
1050 _GLIBCXX20_CONSTEXPR
1052 operator==(
const __normal_iterator<_Iterator, _Container>& __lhs,
1053 const __normal_iterator<_Iterator, _Container>& __rhs)
1055 {
return __lhs.base() == __rhs.base(); }
1057 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1058 _GLIBCXX20_CONSTEXPR
1060 operator!=(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1061 const __normal_iterator<_IteratorR, _Container>& __rhs)
1063 {
return __lhs.base() != __rhs.base(); }
1065 template<
typename _Iterator,
typename _Container>
1066 _GLIBCXX20_CONSTEXPR
1068 operator!=(
const __normal_iterator<_Iterator, _Container>& __lhs,
1069 const __normal_iterator<_Iterator, _Container>& __rhs)
1071 {
return __lhs.base() != __rhs.base(); }
1074 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1075 #if __cplusplus > 201703L
1080 operator<(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1081 const __normal_iterator<_IteratorR, _Container>& __rhs)
1083 {
return __lhs.base() < __rhs.base(); }
1085 template<
typename _Iterator,
typename _Container>
1086 _GLIBCXX20_CONSTEXPR
1088 operator<(
const __normal_iterator<_Iterator, _Container>& __lhs,
1089 const __normal_iterator<_Iterator, _Container>& __rhs)
1091 {
return __lhs.base() < __rhs.base(); }
1093 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1094 #if __cplusplus > 201703L
1099 operator>(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1100 const __normal_iterator<_IteratorR, _Container>& __rhs)
1102 {
return __lhs.base() > __rhs.base(); }
1104 template<
typename _Iterator,
typename _Container>
1105 _GLIBCXX20_CONSTEXPR
1107 operator>(
const __normal_iterator<_Iterator, _Container>& __lhs,
1108 const __normal_iterator<_Iterator, _Container>& __rhs)
1110 {
return __lhs.base() > __rhs.base(); }
1112 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1113 #if __cplusplus > 201703L
1118 operator<=(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1119 const __normal_iterator<_IteratorR, _Container>& __rhs)
1121 {
return __lhs.base() <= __rhs.base(); }
1123 template<
typename _Iterator,
typename _Container>
1124 _GLIBCXX20_CONSTEXPR
1126 operator<=(
const __normal_iterator<_Iterator, _Container>& __lhs,
1127 const __normal_iterator<_Iterator, _Container>& __rhs)
1129 {
return __lhs.base() <= __rhs.base(); }
1131 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1132 #if __cplusplus > 201703L
1137 operator>=(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1138 const __normal_iterator<_IteratorR, _Container>& __rhs)
1140 {
return __lhs.base() >= __rhs.base(); }
1142 template<
typename _Iterator,
typename _Container>
1143 _GLIBCXX20_CONSTEXPR
1145 operator>=(
const __normal_iterator<_Iterator, _Container>& __lhs,
1146 const __normal_iterator<_Iterator, _Container>& __rhs)
1148 {
return __lhs.base() >= __rhs.base(); }
1154 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1155 #if __cplusplus >= 201103L
1157 _GLIBCXX20_CONSTEXPR
1159 operator-(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1160 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
1161 -> decltype(__lhs.base() - __rhs.base())
1163 inline typename __normal_iterator<_IteratorL, _Container>::difference_type
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
1171 inline typename __normal_iterator<_Iterator, _Container>::difference_type
1172 operator-(
const __normal_iterator<_Iterator, _Container>& __lhs,
1173 const __normal_iterator<_Iterator, _Container>& __rhs)
1175 {
return __lhs.base() - __rhs.base(); }
1177 template<
typename _Iterator,
typename _Container>
1178 _GLIBCXX20_CONSTEXPR
1179 inline __normal_iterator<_Iterator, _Container>
1180 operator+(
typename __normal_iterator<_Iterator, _Container>::difference_type
1181 __n,
const __normal_iterator<_Iterator, _Container>& __i)
1183 {
return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
1185 _GLIBCXX_END_NAMESPACE_VERSION
1188 namespace std _GLIBCXX_VISIBILITY(default)
1190 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1192 template<
typename _Iterator,
typename _Container>
1193 _GLIBCXX20_CONSTEXPR
1195 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
1197 {
return __it.base(); }
1199 #if __cplusplus >= 201103L
1205 #if __cplusplus > 201703L && __cpp_lib_concepts
1206 template<semiregular _Sent>
1212 noexcept(is_nothrow_default_constructible_v<_Sent>)
1216 move_sentinel(_Sent __s)
1217 noexcept(is_nothrow_move_constructible_v<_Sent>)
1220 template<
typename _S2> requires convertible_to<const _S2&, _Sent>
1222 move_sentinel(
const move_sentinel<_S2>& __s)
1223 noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
1224 : _M_last(__s.base())
1227 template<
typename _S2> requires assignable_from<_Sent&, const _S2&>
1228 constexpr move_sentinel&
1229 operator=(
const move_sentinel<_S2>& __s)
1230 noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
1232 _M_last = __s.base();
1238 noexcept(is_nothrow_copy_constructible_v<_Sent>)
1255 template<
typename _Iterator>
1258 _Iterator _M_current;
1261 #if __cplusplus > 201703L && __cpp_lib_concepts
1262 using __base_cat =
typename __traits_type::iterator_category;
1264 using __base_ref =
typename __traits_type::reference;
1268 using iterator_type = _Iterator;
1270 #if __cplusplus > 201703L && __cpp_lib_concepts
1272 using iterator_category
1273 = __detail::__clamp_iter_cat<__base_cat, random_access_iterator_tag>;
1274 using value_type = iter_value_t<_Iterator>;
1275 using difference_type = iter_difference_t<_Iterator>;
1276 using pointer = _Iterator;
1277 using reference = iter_rvalue_reference_t<_Iterator>;
1279 typedef typename __traits_type::iterator_category iterator_category;
1280 typedef typename __traits_type::value_type value_type;
1281 typedef typename __traits_type::difference_type difference_type;
1283 typedef _Iterator pointer;
1287 typename remove_reference<__base_ref>::type&&,
1288 __base_ref>::type reference;
1291 _GLIBCXX17_CONSTEXPR
1295 explicit _GLIBCXX17_CONSTEXPR
1299 template<
typename _Iter>
1300 _GLIBCXX17_CONSTEXPR
1302 : _M_current(__i.base()) { }
1304 #if __cplusplus <= 201703L
1305 _GLIBCXX17_CONSTEXPR iterator_type
1307 {
return _M_current; }
1309 constexpr iterator_type
1311 #if __cpp_lib_concepts
1312 requires copy_constructible<iterator_type>
1314 {
return _M_current; }
1316 constexpr iterator_type
1321 _GLIBCXX17_CONSTEXPR reference
1323 {
return static_cast<reference
>(*_M_current); }
1325 _GLIBCXX17_CONSTEXPR pointer
1327 {
return _M_current; }
1344 #if __cpp_lib_concepts
1346 operator++(
int) requires (!forward_iterator<_Iterator>)
1366 operator+(difference_type __n)
const
1370 operator+=(difference_type __n)
1377 operator-(difference_type __n)
const
1381 operator-=(difference_type __n)
1387 _GLIBCXX17_CONSTEXPR reference
1388 operator[](difference_type __n)
const
1391 #if __cplusplus > 201703L && __cpp_lib_concepts
1392 template<sentinel_for<_Iterator> _Sent>
1393 friend constexpr
bool
1394 operator==(
const move_iterator& __x,
const move_sentinel<_Sent>& __y)
1395 {
return __x.base() == __y.base(); }
1397 template<sized_sentinel_for<_Iterator> _Sent>
1398 friend constexpr iter_difference_t<_Iterator>
1399 operator-(
const move_sentinel<_Sent>& __x,
const move_iterator& __y)
1400 {
return __x.base() - __y.base(); }
1402 template<sized_sentinel_for<_Iterator> _Sent>
1403 friend constexpr iter_difference_t<_Iterator>
1404 operator-(
const move_iterator& __x,
const move_sentinel<_Sent>& __y)
1405 {
return __x.base() - __y.base(); }
1407 friend constexpr iter_rvalue_reference_t<_Iterator>
1409 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1410 {
return ranges::iter_move(__i._M_current); }
1412 template<indirectly_swappable<_Iterator> _Iter2>
1413 friend constexpr
void
1415 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1416 {
return ranges::iter_swap(__x._M_current, __y._M_current); }
1420 template<
typename _IteratorL,
typename _IteratorR>
1421 inline _GLIBCXX17_CONSTEXPR
bool
1424 #if __cplusplus > 201703L && __cpp_lib_concepts
1425 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1427 {
return __x.base() == __y.base(); }
1429 #if __cpp_lib_three_way_comparison
1430 template<
typename _IteratorL,
1431 three_way_comparable_with<_IteratorL> _IteratorR>
1432 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
1433 operator<=>(
const move_iterator<_IteratorL>& __x,
1434 const move_iterator<_IteratorR>& __y)
1435 {
return __x.base() <=> __y.base(); }
1437 template<
typename _IteratorL,
typename _IteratorR>
1438 inline _GLIBCXX17_CONSTEXPR
bool
1439 operator!=(
const move_iterator<_IteratorL>& __x,
1440 const move_iterator<_IteratorR>& __y)
1441 {
return !(__x == __y); }
1444 template<
typename _IteratorL,
typename _IteratorR>
1445 inline _GLIBCXX17_CONSTEXPR
bool
1446 operator<(
const move_iterator<_IteratorL>& __x,
1447 const move_iterator<_IteratorR>& __y)
1448 #if __cplusplus > 201703L && __cpp_lib_concepts
1449 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1451 {
return __x.base() < __y.base(); }
1453 template<
typename _IteratorL,
typename _IteratorR>
1454 inline _GLIBCXX17_CONSTEXPR
bool
1455 operator<=(
const move_iterator<_IteratorL>& __x,
1456 const move_iterator<_IteratorR>& __y)
1457 #if __cplusplus > 201703L && __cpp_lib_concepts
1458 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1460 {
return !(__y < __x); }
1462 template<
typename _IteratorL,
typename _IteratorR>
1463 inline _GLIBCXX17_CONSTEXPR
bool
1464 operator>(
const move_iterator<_IteratorL>& __x,
1465 const move_iterator<_IteratorR>& __y)
1466 #if __cplusplus > 201703L && __cpp_lib_concepts
1467 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1469 {
return __y < __x; }
1471 template<
typename _IteratorL,
typename _IteratorR>
1472 inline _GLIBCXX17_CONSTEXPR
bool
1473 operator>=(
const move_iterator<_IteratorL>& __x,
1474 const move_iterator<_IteratorR>& __y)
1475 #if __cplusplus > 201703L && __cpp_lib_concepts
1476 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1478 {
return !(__x < __y); }
1480 #if ! (__cplusplus > 201703L && __cpp_lib_concepts)
1488 template<
typename _Iterator>
1489 inline _GLIBCXX17_CONSTEXPR
bool
1490 operator==(
const move_iterator<_Iterator>& __x,
1491 const move_iterator<_Iterator>& __y)
1492 {
return __x.base() == __y.base(); }
1494 template<
typename _Iterator>
1495 inline _GLIBCXX17_CONSTEXPR
bool
1496 operator!=(
const move_iterator<_Iterator>& __x,
1497 const move_iterator<_Iterator>& __y)
1498 {
return !(__x == __y); }
1500 template<
typename _Iterator>
1501 inline _GLIBCXX17_CONSTEXPR
bool
1502 operator<(
const move_iterator<_Iterator>& __x,
1503 const move_iterator<_Iterator>& __y)
1504 {
return __x.base() < __y.base(); }
1506 template<
typename _Iterator>
1507 inline _GLIBCXX17_CONSTEXPR
bool
1508 operator<=(
const move_iterator<_Iterator>& __x,
1509 const move_iterator<_Iterator>& __y)
1510 {
return !(__y < __x); }
1512 template<
typename _Iterator>
1513 inline _GLIBCXX17_CONSTEXPR
bool
1514 operator>(
const move_iterator<_Iterator>& __x,
1515 const move_iterator<_Iterator>& __y)
1516 {
return __y < __x; }
1518 template<
typename _Iterator>
1519 inline _GLIBCXX17_CONSTEXPR
bool
1520 operator>=(
const move_iterator<_Iterator>& __x,
1521 const move_iterator<_Iterator>& __y)
1522 {
return !(__x < __y); }
1526 template<
typename _IteratorL,
typename _IteratorR>
1527 inline _GLIBCXX17_CONSTEXPR
auto
1528 operator-(
const move_iterator<_IteratorL>& __x,
1529 const move_iterator<_IteratorR>& __y)
1530 -> decltype(__x.base() - __y.base())
1531 {
return __x.base() - __y.base(); }
1533 template<
typename _Iterator>
1534 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1535 operator+(
typename move_iterator<_Iterator>::difference_type __n,
1536 const move_iterator<_Iterator>& __x)
1537 {
return __x + __n; }
1539 template<
typename _Iterator>
1540 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1541 make_move_iterator(_Iterator __i)
1542 {
return move_iterator<_Iterator>(
std::move(__i)); }
1544 template<
typename _Iterator,
typename _ReturnType
1545 =
typename conditional<__move_if_noexcept_cond
1546 <
typename iterator_traits<_Iterator>::value_type>::value,
1547 _Iterator, move_iterator<_Iterator>>::type>
1548 inline _GLIBCXX17_CONSTEXPR _ReturnType
1549 __make_move_if_noexcept_iterator(_Iterator __i)
1550 {
return _ReturnType(__i); }
1554 template<
typename _Tp,
typename _ReturnType
1555 =
typename conditional<__move_if_noexcept_cond<_Tp>::value,
1556 const _Tp*, move_iterator<_Tp*>>::type>
1557 inline _GLIBCXX17_CONSTEXPR _ReturnType
1558 __make_move_if_noexcept_iterator(_Tp* __i)
1559 {
return _ReturnType(__i); }
1561 #if __cplusplus > 201703L && __cpp_lib_concepts
1566 template<input_or_output_iterator _It>
1567 class _Common_iter_proxy
1569 iter_value_t<_It> _M_keep;
1571 _Common_iter_proxy(iter_reference_t<_It>&& __x)
1574 template<
typename _Iter,
typename _Sent>
1575 friend class common_iterator;
1578 const iter_value_t<_It>*
1583 template<
typename _It>
1584 concept __common_iter_has_arrow = indirectly_readable<const _It>
1585 && (requires(
const _It& __it) { __it.operator->(); }
1586 || is_reference_v<iter_reference_t<_It>>
1587 || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1592 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1593 requires (!same_as<_It, _Sent>) && copyable<_It>
1594 class common_iterator
1596 template<
typename _Tp,
typename _Up>
1597 static constexpr
bool
1600 if constexpr (is_trivially_default_constructible_v<_Tp>)
1601 return is_nothrow_assignable_v<_Tp, _Up>;
1603 return is_nothrow_constructible_v<_Tp, _Up>;
1606 template<
typename _It2,
typename _Sent2>
1607 static constexpr
bool
1609 {
return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1614 noexcept(is_nothrow_default_constructible_v<_It>)
1615 : _M_it(), _M_index(0)
1619 common_iterator(_It __i)
1620 noexcept(is_nothrow_move_constructible_v<_It>)
1621 : _M_it(
std::
move(__i)), _M_index(0)
1625 common_iterator(_Sent __s)
1626 noexcept(is_nothrow_move_constructible_v<_Sent>)
1627 : _M_sent(
std::
move(__s)), _M_index(1)
1630 template<
typename _It2,
typename _Sent2>
1631 requires convertible_to<const _It2&, _It>
1632 && convertible_to<const _Sent2&, _Sent>
1634 common_iterator(
const common_iterator<_It2, _Sent2>& __x)
1635 noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1636 : _M_valueless(), _M_index(__x._M_index)
1640 if constexpr (is_trivially_default_constructible_v<_It>)
1645 else if (_M_index == 1)
1647 if constexpr (is_trivially_default_constructible_v<_Sent>)
1655 common_iterator(
const common_iterator& __x)
1656 noexcept(_S_noexcept<const _It&, const _Sent&>())
1657 : _M_valueless(), _M_index(__x._M_index)
1661 if constexpr (is_trivially_default_constructible_v<_It>)
1666 else if (_M_index == 1)
1668 if constexpr (is_trivially_default_constructible_v<_Sent>)
1676 operator=(
const common_iterator& __x)
1677 noexcept(is_nothrow_copy_assignable_v<_It>
1678 && is_nothrow_copy_assignable_v<_Sent>
1679 && is_nothrow_copy_constructible_v<_It>
1680 && is_nothrow_copy_constructible_v<_Sent>)
1682 return this->
operator=<_It, _Sent>(__x);
1685 template<
typename _It2,
typename _Sent2>
1686 requires convertible_to<const _It2&, _It>
1687 && convertible_to<const _Sent2&, _Sent>
1688 && assignable_from<_It&, const _It2&>
1689 && assignable_from<_Sent&, const _Sent2&>
1691 operator=(
const common_iterator<_It2, _Sent2>& __x)
1692 noexcept(is_nothrow_constructible_v<_It, const _It2&>
1693 && is_nothrow_constructible_v<_Sent, const _Sent2&>
1694 && is_nothrow_assignable_v<_It, const _It2&>
1695 && is_nothrow_assignable_v<_Sent, const _Sent2&>)
1697 switch(_M_index << 2 | __x._M_index)
1703 _M_sent = __x._M_sent;
1722 __glibcxx_assert(__x._M_has_value());
1723 __builtin_unreachable();
1744 __glibcxx_assert(_M_index == 0);
1749 operator*() const requires __detail::__dereferenceable<const _It>
1751 __glibcxx_assert(_M_index == 0);
1756 operator->() const requires __detail::__common_iter_has_arrow<_It>
1758 __glibcxx_assert(_M_index == 0);
1759 if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
1761 else if constexpr (is_reference_v<iter_reference_t<_It>>)
1763 auto&& __tmp = *_M_it;
1767 return _Common_iter_proxy(*_M_it);
1773 __glibcxx_assert(_M_index == 0);
1781 __glibcxx_assert(_M_index == 0);
1782 if constexpr (forward_iterator<_It>)
1784 common_iterator __tmp = *
this;
1792 template<
typename _It2, sentinel_for<_It> _Sent2>
1793 requires sentinel_for<_Sent, _It2>
1795 operator==(
const common_iterator& __x,
1796 const common_iterator<_It2, _Sent2>& __y)
1798 switch(__x._M_index << 2 | __y._M_index)
1804 return __x._M_it == __y._M_sent;
1806 return __x._M_sent == __y._M_it;
1808 __glibcxx_assert(__x._M_has_value());
1809 __glibcxx_assert(__y._M_has_value());
1810 __builtin_unreachable();
1814 template<
typename _It2, sentinel_for<_It> _Sent2>
1815 requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
1817 operator==(
const common_iterator& __x,
1818 const common_iterator<_It2, _Sent2>& __y)
1820 switch(__x._M_index << 2 | __y._M_index)
1825 return __x._M_it == __y._M_it;
1827 return __x._M_it == __y._M_sent;
1829 return __x._M_sent == __y._M_it;
1831 __glibcxx_assert(__x._M_has_value());
1832 __glibcxx_assert(__y._M_has_value());
1833 __builtin_unreachable();
1837 template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
1838 requires sized_sentinel_for<_Sent, _It2>
1839 friend iter_difference_t<_It2>
1841 const common_iterator<_It2, _Sent2>& __y)
1843 switch(__x._M_index << 2 | __y._M_index)
1848 return __x._M_it - __y._M_it;
1850 return __x._M_it - __y._M_sent;
1852 return __x._M_sent - __y._M_it;
1854 __glibcxx_assert(__x._M_has_value());
1855 __glibcxx_assert(__y._M_has_value());
1856 __builtin_unreachable();
1860 friend iter_rvalue_reference_t<_It>
1861 iter_move(
const common_iterator& __i)
1862 noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
1863 requires input_iterator<_It>
1865 __glibcxx_assert(__i._M_index == 0);
1866 return ranges::iter_move(__i._M_it);
1869 template<indirectly_swappable<_It> _It2,
typename _Sent2>
1871 iter_swap(
const common_iterator& __x,
1872 const common_iterator<_It2, _Sent2>& __y)
1873 noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
1874 std::declval<const _It2&>())))
1876 __glibcxx_assert(__x._M_index == 0);
1877 __glibcxx_assert(__y._M_index == 0);
1878 return ranges::iter_swap(__x._M_it, __y._M_it);
1882 template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
1883 friend class common_iterator;
1885 bool _M_has_value() const noexcept {
return _M_index < 2; }
1891 unsigned char _M_valueless;
1893 unsigned char _M_index;
1896 template<
typename _It,
typename _Sent>
1897 struct incrementable_traits<common_iterator<_It, _Sent>>
1899 using difference_type = iter_difference_t<_It>;
1905 template<
typename _It,
typename _Sent>
1906 struct __common_iter_ptr
1911 template<
typename _It,
typename _Sent>
1912 requires __detail::__common_iter_has_arrow<_It>
1913 struct __common_iter_ptr<_It, _Sent>
1915 using common_iterator = std::common_iterator<_It, _Sent>;
1918 = decltype(std::declval<const common_iterator&>().operator->());
1922 template<input_iterator _It,
typename _Sent>
1923 struct iterator_traits<common_iterator<_It, _Sent>>
1925 using iterator_concept = conditional_t<forward_iterator<_It>,
1926 forward_iterator_tag, input_iterator_tag>;
1927 using iterator_category = __detail::__clamp_iter_cat<
1928 typename iterator_traits<_It>::iterator_category,
1929 forward_iterator_tag, input_iterator_tag>;
1930 using value_type = iter_value_t<_It>;
1931 using difference_type = iter_difference_t<_It>;
1932 using pointer =
typename __detail::__common_iter_ptr<_It, _Sent>::type;
1933 using reference = iter_reference_t<_It>;
1939 template<input_or_output_iterator _It>
1940 class counted_iterator
1943 using iterator_type = _It;
1945 constexpr counted_iterator() =
default;
1948 counted_iterator(_It __i, iter_difference_t<_It> __n)
1949 : _M_current(
std::
move(__i)), _M_length(__n)
1950 { __glibcxx_assert(__n >= 0); }
1952 template<
typename _It2>
1953 requires convertible_to<const _It2&, _It>
1955 counted_iterator(
const counted_iterator<_It2>& __x)
1956 : _M_current(__x._M_current), _M_length(__x._M_length)
1959 template<
typename _It2>
1960 requires assignable_from<_It&, const _It2&>
1961 constexpr counted_iterator&
1962 operator=(
const counted_iterator<_It2>& __x)
1964 _M_current = __x._M_current;
1965 _M_length = __x._M_length;
1971 noexcept(is_nothrow_copy_constructible_v<_It>)
1972 requires copy_constructible<_It>
1973 {
return _M_current; }
1977 noexcept(is_nothrow_move_constructible_v<_It>)
1980 constexpr iter_difference_t<_It>
1981 count() const noexcept {
return _M_length; }
1983 constexpr decltype(
auto)
1985 noexcept(noexcept(*_M_current))
1986 {
return *_M_current; }
1988 constexpr decltype(
auto)
1990 noexcept(noexcept(*_M_current))
1991 requires __detail::__dereferenceable<const _It>
1992 {
return *_M_current; }
1994 constexpr counted_iterator&
1997 __glibcxx_assert(_M_length > 0);
2006 __glibcxx_assert(_M_length > 0);
2010 return _M_current++;
2018 constexpr counted_iterator
2019 operator++(
int) requires forward_iterator<_It>
2026 constexpr counted_iterator&
2027 operator--() requires bidirectional_iterator<_It>
2034 constexpr counted_iterator
2035 operator--(
int) requires bidirectional_iterator<_It>
2042 constexpr counted_iterator
2043 operator+(iter_difference_t<_It> __n)
const
2044 requires random_access_iterator<_It>
2045 {
return counted_iterator(_M_current + __n, _M_length - __n); }
2047 friend constexpr counted_iterator
2048 operator+(iter_difference_t<_It> __n,
const counted_iterator& __x)
2049 requires random_access_iterator<_It>
2050 {
return __x + __n; }
2052 constexpr counted_iterator&
2053 operator+=(iter_difference_t<_It> __n)
2054 requires random_access_iterator<_It>
2056 __glibcxx_assert(__n <= _M_length);
2062 constexpr counted_iterator
2063 operator-(iter_difference_t<_It> __n)
const
2064 requires random_access_iterator<_It>
2065 {
return counted_iterator(_M_current - __n, _M_length + __n); }
2067 template<common_with<_It> _It2>
2068 friend constexpr iter_difference_t<_It2>
2070 const counted_iterator<_It2>& __y)
2071 {
return __y._M_length - __x._M_length; }
2073 friend constexpr iter_difference_t<_It>
2074 operator-(
const counted_iterator& __x, default_sentinel_t)
2075 {
return -__x._M_length; }
2077 friend constexpr iter_difference_t<_It>
2078 operator-(default_sentinel_t,
const counted_iterator& __y)
2079 {
return __y._M_length; }
2081 constexpr counted_iterator&
2082 operator-=(iter_difference_t<_It> __n)
2083 requires random_access_iterator<_It>
2085 __glibcxx_assert(-__n <= _M_length);
2091 constexpr decltype(
auto)
2092 operator[](iter_difference_t<_It> __n) const
2093 noexcept(noexcept(_M_current[__n]))
2094 requires random_access_iterator<_It>
2096 __glibcxx_assert(__n < _M_length);
2097 return _M_current[__n];
2100 template<common_with<_It> _It2>
2101 friend constexpr
bool
2102 operator==(
const counted_iterator& __x,
2103 const counted_iterator<_It2>& __y)
2104 {
return __x._M_length == __y._M_length; }
2106 friend constexpr
bool
2107 operator==(
const counted_iterator& __x, default_sentinel_t)
2108 {
return __x._M_length == 0; }
2110 template<common_with<_It> _It2>
2111 friend constexpr strong_ordering
2112 operator<=>(
const counted_iterator& __x,
2113 const counted_iterator<_It2>& __y)
2114 {
return __y._M_length <=> __x._M_length; }
2116 friend constexpr iter_rvalue_reference_t<_It>
2117 iter_move(
const counted_iterator& __i)
2118 noexcept(noexcept(ranges::iter_move(__i._M_current)))
2119 requires input_iterator<_It>
2120 {
return ranges::iter_move(__i._M_current); }
2122 template<indirectly_swappable<_It> _It2>
2123 friend constexpr
void
2124 iter_swap(
const counted_iterator& __x,
2125 const counted_iterator<_It2>& __y)
2126 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2127 { ranges::iter_swap(__x._M_current, __y._M_current); }
2130 template<input_or_output_iterator _It2>
friend class counted_iterator;
2132 _It _M_current = _It();
2133 iter_difference_t<_It> _M_length = 0;
2136 template<
typename _It>
2137 struct incrementable_traits<counted_iterator<_It>>
2139 using difference_type = iter_difference_t<_It>;
2142 template<input_iterator _It>
2143 struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2145 using pointer = void;
2151 template<
typename _Iterator>
2153 __niter_base(move_iterator<_Iterator> __it)
2154 -> decltype(make_move_iterator(__niter_base(__it.base())))
2155 {
return make_move_iterator(__niter_base(__it.base())); }
2157 template<
typename _Iterator>
2158 struct __is_move_iterator<move_iterator<_Iterator> >
2160 enum { __value = 1 };
2161 typedef __true_type __type;
2164 template<
typename _Iterator>
2166 __miter_base(move_iterator<_Iterator> __it)
2167 -> decltype(__miter_base(__it.base()))
2168 {
return __miter_base(__it.base()); }
2170 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2171 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2172 std::__make_move_if_noexcept_iterator(_Iter)
2174 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2175 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2178 #if __cpp_deduction_guides >= 201606
2181 template<
typename _InputIterator>
2183 typename iterator_traits<_InputIterator>::value_type::first_type>;
2185 template<
typename _InputIterator>
2186 using __iter_val_t =
2187 typename iterator_traits<_InputIterator>::value_type::second_type;
2189 template<
typename _T1,
typename _T2>
2192 template<
typename _InputIterator>
2193 using __iter_to_alloc_t =
2194 pair<add_const_t<__iter_key_t<_InputIterator>>,
2195 __iter_val_t<_InputIterator>>;
2196 #endif // __cpp_deduction_guides
2198 _GLIBCXX_END_NAMESPACE_VERSION
2201 #ifdef _GLIBCXX_DEBUG