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->(); }
345 namespace __detail {
bool __convbool(
bool); }
357 #if __cplusplus <= 201703L
358 template<
typename _Iterator>
359 inline _GLIBCXX17_CONSTEXPR
bool
362 {
return __x.
base() == __y.
base(); }
364 template<
typename _Iterator>
365 inline _GLIBCXX17_CONSTEXPR
bool
366 operator<(
const reverse_iterator<_Iterator>& __x,
367 const reverse_iterator<_Iterator>& __y)
368 {
return __y.base() < __x.base(); }
370 template<
typename _Iterator>
371 inline _GLIBCXX17_CONSTEXPR
bool
372 operator!=(
const reverse_iterator<_Iterator>& __x,
373 const reverse_iterator<_Iterator>& __y)
374 {
return !(__x == __y); }
376 template<
typename _Iterator>
377 inline _GLIBCXX17_CONSTEXPR
bool
378 operator>(
const reverse_iterator<_Iterator>& __x,
379 const reverse_iterator<_Iterator>& __y)
380 {
return __y < __x; }
382 template<
typename _Iterator>
383 inline _GLIBCXX17_CONSTEXPR
bool
384 operator<=(
const reverse_iterator<_Iterator>& __x,
385 const reverse_iterator<_Iterator>& __y)
386 {
return !(__y < __x); }
388 template<
typename _Iterator>
389 inline _GLIBCXX17_CONSTEXPR
bool
390 operator>=(
const reverse_iterator<_Iterator>& __x,
391 const reverse_iterator<_Iterator>& __y)
392 {
return !(__x < __y); }
396 template<
typename _IteratorL,
typename _IteratorR>
397 inline _GLIBCXX17_CONSTEXPR
bool
398 operator==(
const reverse_iterator<_IteratorL>& __x,
399 const reverse_iterator<_IteratorR>& __y)
400 {
return __x.base() == __y.base(); }
402 template<
typename _IteratorL,
typename _IteratorR>
403 inline _GLIBCXX17_CONSTEXPR
bool
404 operator<(
const reverse_iterator<_IteratorL>& __x,
405 const reverse_iterator<_IteratorR>& __y)
406 {
return __y.base() < __x.base(); }
408 template<
typename _IteratorL,
typename _IteratorR>
409 inline _GLIBCXX17_CONSTEXPR
bool
410 operator!=(
const reverse_iterator<_IteratorL>& __x,
411 const reverse_iterator<_IteratorR>& __y)
412 {
return !(__x == __y); }
414 template<
typename _IteratorL,
typename _IteratorR>
415 inline _GLIBCXX17_CONSTEXPR
bool
416 operator>(
const reverse_iterator<_IteratorL>& __x,
417 const reverse_iterator<_IteratorR>& __y)
418 {
return __y < __x; }
420 template<
typename _IteratorL,
typename _IteratorR>
421 inline _GLIBCXX17_CONSTEXPR
bool
422 operator<=(
const reverse_iterator<_IteratorL>& __x,
423 const reverse_iterator<_IteratorR>& __y)
424 {
return !(__y < __x); }
426 template<
typename _IteratorL,
typename _IteratorR>
427 inline _GLIBCXX17_CONSTEXPR
bool
428 operator>=(
const reverse_iterator<_IteratorL>& __x,
429 const reverse_iterator<_IteratorR>& __y)
430 {
return !(__x < __y); }
432 template<
typename _IteratorL,
typename _IteratorR>
434 operator==(
const reverse_iterator<_IteratorL>& __x,
435 const reverse_iterator<_IteratorR>& __y)
436 -> decltype(__detail::__convbool(__x.base() == __y.base()))
437 {
return __x.base() == __y.base(); }
439 template<
typename _IteratorL,
typename _IteratorR>
441 operator!=(
const reverse_iterator<_IteratorL>& __x,
442 const reverse_iterator<_IteratorR>& __y)
443 -> decltype(__detail::__convbool(__x.base() != __y.base()))
444 {
return __x.base() != __y.base(); }
446 template<
typename _IteratorL,
typename _IteratorR>
448 operator<(
const reverse_iterator<_IteratorL>& __x,
449 const reverse_iterator<_IteratorR>& __y)
450 -> decltype(__detail::__convbool(__x.base() < __y.base()))
451 {
return __x.base() < __y.base(); }
453 template<
typename _IteratorL,
typename _IteratorR>
455 operator>(
const reverse_iterator<_IteratorL>& __x,
456 const reverse_iterator<_IteratorR>& __y)
457 -> decltype(__detail::__convbool(__x.base() > __y.base()))
458 {
return __x.base() > __y.base(); }
460 template<
typename _IteratorL,
typename _IteratorR>
462 operator<=(
const reverse_iterator<_IteratorL>& __x,
463 const reverse_iterator<_IteratorR>& __y)
464 -> decltype(__detail::__convbool(__x.base() <= __y.base()))
465 {
return __x.base() <= __y.base(); }
467 template<
typename _IteratorL,
typename _IteratorR>
469 operator>=(
const reverse_iterator<_IteratorL>& __x,
470 const reverse_iterator<_IteratorR>& __y)
471 -> decltype(__detail::__convbool(__x.base() >= __y.base()))
472 {
return __x.base() >= __y.base(); }
476 #if __cplusplus < 201103L
477 template<
typename _Iterator>
478 inline typename reverse_iterator<_Iterator>::difference_type
479 operator-(
const reverse_iterator<_Iterator>& __x,
480 const reverse_iterator<_Iterator>& __y)
481 {
return __y.base() - __x.base(); }
483 template<
typename _IteratorL,
typename _IteratorR>
484 inline typename reverse_iterator<_IteratorL>::difference_type
485 operator-(
const reverse_iterator<_IteratorL>& __x,
486 const reverse_iterator<_IteratorR>& __y)
487 {
return __y.base() - __x.base(); }
491 template<
typename _IteratorL,
typename _IteratorR>
492 inline _GLIBCXX17_CONSTEXPR
auto
493 operator-(
const reverse_iterator<_IteratorL>& __x,
494 const reverse_iterator<_IteratorR>& __y)
495 -> decltype(__y.base() - __x.base())
496 {
return __y.base() - __x.base(); }
499 template<
typename _Iterator>
500 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
501 operator+(
typename reverse_iterator<_Iterator>::difference_type __n,
502 const reverse_iterator<_Iterator>& __x)
503 {
return reverse_iterator<_Iterator>(__x.base() - __n); }
505 #if __cplusplus >= 201103L
507 template<
typename _Iterator>
508 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
509 __make_reverse_iterator(_Iterator __i)
510 {
return reverse_iterator<_Iterator>(__i); }
512 # if __cplusplus >= 201402L
513 # define __cpp_lib_make_reverse_iterator 201402
518 template<
typename _Iterator>
519 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
523 # if __cplusplus > 201703L && defined __cpp_lib_concepts
524 template<
typename _Iterator1,
typename _Iterator2>
525 requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
526 inline constexpr
bool
527 disable_sized_sentinel_for<reverse_iterator<_Iterator1>,
528 reverse_iterator<_Iterator2>> =
true;
532 template<
typename _Iterator>
535 __niter_base(reverse_iterator<_Iterator> __it)
536 -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
537 {
return __make_reverse_iterator(__niter_base(__it.base())); }
539 template<
typename _Iterator>
540 struct __is_move_iterator<reverse_iterator<_Iterator> >
541 : __is_move_iterator<_Iterator>
544 template<
typename _Iterator>
547 __miter_base(reverse_iterator<_Iterator> __it)
548 -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
549 {
return __make_reverse_iterator(__miter_base(__it.base())); }
563 template<
typename _Container>
565 :
public iterator<output_iterator_tag, void, void, void, void>
568 _Container* container;
573 #if __cplusplus > 201703L
580 explicit _GLIBCXX20_CONSTEXPR
595 #if __cplusplus < 201103L
597 operator=(
typename _Container::const_reference __value)
599 container->push_back(__value);
605 operator=(
const typename _Container::value_type& __value)
607 container->push_back(__value);
613 operator=(
typename _Container::value_type&& __value)
615 container->push_back(
std::move(__value));
650 template<
typename _Container>
652 inline back_insert_iterator<_Container>
666 template<
typename _Container>
668 :
public iterator<output_iterator_tag, void, void, void, void>
671 _Container* container;
676 #if __cplusplus > 201703L
683 explicit _GLIBCXX20_CONSTEXPR
698 #if __cplusplus < 201103L
700 operator=(
typename _Container::const_reference __value)
702 container->push_front(__value);
708 operator=(
const typename _Container::value_type& __value)
710 container->push_front(__value);
716 operator=(
typename _Container::value_type&& __value)
718 container->push_front(
std::move(__value));
753 template<
typename _Container>
755 inline front_insert_iterator<_Container>
773 template<
typename _Container>
775 :
public iterator<output_iterator_tag, void, void, void, void>
777 #if __cplusplus > 201703L && defined __cpp_lib_concepts
778 using _Iter = std::__detail::__range_iter_t<_Container>;
781 _Container* container =
nullptr;
782 _Iter iter = _Iter();
784 typedef typename _Container::iterator _Iter;
787 _Container* container;
795 #if __cplusplus > 201703L && defined __cpp_lib_concepts
832 #if __cplusplus < 201103L
834 operator=(
typename _Container::const_reference __value)
836 iter = container->insert(iter, __value);
843 operator=(
const typename _Container::value_type& __value)
845 iter = container->insert(iter, __value);
852 operator=(
typename _Container::value_type&& __value)
854 iter = container->insert(iter,
std::move(__value));
891 #if __cplusplus > 201703L && defined __cpp_lib_concepts
892 template<
typename _Container>
893 constexpr insert_iterator<_Container>
894 inserter(_Container& __x, std::__detail::__range_iter_t<_Container> __i)
895 {
return insert_iterator<_Container>(__x, __i); }
897 template<
typename _Container,
typename _Iterator>
898 inline insert_iterator<_Container>
902 typename _Container::iterator(__i));
908 _GLIBCXX_END_NAMESPACE_VERSION
911 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
913 _GLIBCXX_BEGIN_NAMESPACE_VERSION
922 template<
typename _Iterator,
typename _Container>
923 class __normal_iterator
926 _Iterator _M_current;
931 typedef _Iterator iterator_type;
932 typedef typename __traits_type::iterator_category iterator_category;
933 typedef typename __traits_type::value_type value_type;
934 typedef typename __traits_type::difference_type difference_type;
935 typedef typename __traits_type::reference reference;
936 typedef typename __traits_type::pointer pointer;
938 #if __cplusplus > 201703L && __cpp_lib_concepts
939 using iterator_concept = std::__detail::__iter_concept<_Iterator>;
942 _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
943 : _M_current(_Iterator()) { }
945 explicit _GLIBCXX20_CONSTEXPR
946 __normal_iterator(
const _Iterator& __i) _GLIBCXX_NOEXCEPT
947 : _M_current(__i) { }
950 template<
typename _Iter>
952 __normal_iterator(
const __normal_iterator<_Iter,
953 typename __enable_if<
954 (std::__are_same<_Iter, typename _Container::pointer>::__value),
955 _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
956 : _M_current(__i.base()) { }
962 {
return *_M_current; }
966 operator->() const _GLIBCXX_NOEXCEPT
967 {
return _M_current; }
971 operator++() _GLIBCXX_NOEXCEPT
979 operator++(
int) _GLIBCXX_NOEXCEPT
980 {
return __normal_iterator(_M_current++); }
985 operator--() _GLIBCXX_NOEXCEPT
993 operator--(
int) _GLIBCXX_NOEXCEPT
994 {
return __normal_iterator(_M_current--); }
999 operator[](difference_type __n)
const _GLIBCXX_NOEXCEPT
1000 {
return _M_current[__n]; }
1002 _GLIBCXX20_CONSTEXPR
1004 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
1005 { _M_current += __n;
return *
this; }
1007 _GLIBCXX20_CONSTEXPR
1009 operator+(difference_type __n)
const _GLIBCXX_NOEXCEPT
1010 {
return __normal_iterator(_M_current + __n); }
1012 _GLIBCXX20_CONSTEXPR
1014 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
1015 { _M_current -= __n;
return *
this; }
1017 _GLIBCXX20_CONSTEXPR
1019 operator-(difference_type __n)
const _GLIBCXX_NOEXCEPT
1020 {
return __normal_iterator(_M_current - __n); }
1022 _GLIBCXX20_CONSTEXPR
1024 base() const _GLIBCXX_NOEXCEPT
1025 {
return _M_current; }
1037 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1038 _GLIBCXX20_CONSTEXPR
1040 operator==(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1041 const __normal_iterator<_IteratorR, _Container>& __rhs)
1043 {
return __lhs.base() == __rhs.base(); }
1045 template<
typename _Iterator,
typename _Container>
1046 _GLIBCXX20_CONSTEXPR
1048 operator==(
const __normal_iterator<_Iterator, _Container>& __lhs,
1049 const __normal_iterator<_Iterator, _Container>& __rhs)
1051 {
return __lhs.base() == __rhs.base(); }
1053 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1054 _GLIBCXX20_CONSTEXPR
1056 operator!=(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1057 const __normal_iterator<_IteratorR, _Container>& __rhs)
1059 {
return __lhs.base() != __rhs.base(); }
1061 template<
typename _Iterator,
typename _Container>
1062 _GLIBCXX20_CONSTEXPR
1064 operator!=(
const __normal_iterator<_Iterator, _Container>& __lhs,
1065 const __normal_iterator<_Iterator, _Container>& __rhs)
1067 {
return __lhs.base() != __rhs.base(); }
1070 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1071 #if __cplusplus > 201703L
1076 operator<(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1077 const __normal_iterator<_IteratorR, _Container>& __rhs)
1079 {
return __lhs.base() < __rhs.base(); }
1081 template<
typename _Iterator,
typename _Container>
1082 _GLIBCXX20_CONSTEXPR
1084 operator<(
const __normal_iterator<_Iterator, _Container>& __lhs,
1085 const __normal_iterator<_Iterator, _Container>& __rhs)
1087 {
return __lhs.base() < __rhs.base(); }
1089 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1090 #if __cplusplus > 201703L
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>
1109 #if __cplusplus > 201703L
1114 operator<=(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1115 const __normal_iterator<_IteratorR, _Container>& __rhs)
1117 {
return __lhs.base() <= __rhs.base(); }
1119 template<
typename _Iterator,
typename _Container>
1120 _GLIBCXX20_CONSTEXPR
1122 operator<=(
const __normal_iterator<_Iterator, _Container>& __lhs,
1123 const __normal_iterator<_Iterator, _Container>& __rhs)
1125 {
return __lhs.base() <= __rhs.base(); }
1127 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1128 #if __cplusplus > 201703L
1133 operator>=(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1134 const __normal_iterator<_IteratorR, _Container>& __rhs)
1136 {
return __lhs.base() >= __rhs.base(); }
1138 template<
typename _Iterator,
typename _Container>
1139 _GLIBCXX20_CONSTEXPR
1141 operator>=(
const __normal_iterator<_Iterator, _Container>& __lhs,
1142 const __normal_iterator<_Iterator, _Container>& __rhs)
1144 {
return __lhs.base() >= __rhs.base(); }
1150 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1151 #if __cplusplus >= 201103L
1153 _GLIBCXX20_CONSTEXPR
1155 operator-(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1156 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
1157 -> decltype(__lhs.base() - __rhs.base())
1159 inline typename __normal_iterator<_IteratorL, _Container>::difference_type
1160 operator-(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1161 const __normal_iterator<_IteratorR, _Container>& __rhs)
1163 {
return __lhs.base() - __rhs.base(); }
1165 template<
typename _Iterator,
typename _Container>
1166 _GLIBCXX20_CONSTEXPR
1167 inline typename __normal_iterator<_Iterator, _Container>::difference_type
1168 operator-(
const __normal_iterator<_Iterator, _Container>& __lhs,
1169 const __normal_iterator<_Iterator, _Container>& __rhs)
1171 {
return __lhs.base() - __rhs.base(); }
1173 template<
typename _Iterator,
typename _Container>
1174 _GLIBCXX20_CONSTEXPR
1175 inline __normal_iterator<_Iterator, _Container>
1176 operator+(
typename __normal_iterator<_Iterator, _Container>::difference_type
1177 __n,
const __normal_iterator<_Iterator, _Container>& __i)
1179 {
return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
1181 _GLIBCXX_END_NAMESPACE_VERSION
1184 namespace std _GLIBCXX_VISIBILITY(default)
1186 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1188 template<
typename _Iterator,
typename _Container>
1189 _GLIBCXX20_CONSTEXPR
1191 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
1193 {
return __it.base(); }
1195 #if __cplusplus >= 201103L
1201 #if __cplusplus > 201703L && __cpp_lib_concepts
1202 template<semiregular _Sent>
1208 noexcept(is_nothrow_default_constructible_v<_Sent>)
1212 move_sentinel(_Sent __s)
1213 noexcept(is_nothrow_move_constructible_v<_Sent>)
1216 template<
typename _S2> requires convertible_to<const _S2&, _Sent>
1218 move_sentinel(
const move_sentinel<_S2>& __s)
1219 noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
1220 : _M_last(__s.base())
1223 template<
typename _S2> requires assignable_from<_Sent&, const _S2&>
1224 constexpr move_sentinel&
1225 operator=(
const move_sentinel<_S2>& __s)
1226 noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
1228 _M_last = __s.base();
1234 noexcept(is_nothrow_copy_constructible_v<_Sent>)
1251 template<
typename _Iterator>
1254 _Iterator _M_current;
1257 #if __cplusplus > 201703L && __cpp_lib_concepts
1258 using __base_cat =
typename __traits_type::iterator_category;
1260 using __base_ref =
typename __traits_type::reference;
1264 using iterator_type = _Iterator;
1266 #if __cplusplus > 201703L && __cpp_lib_concepts
1268 using iterator_category
1269 = __detail::__clamp_iter_cat<__base_cat, random_access_iterator_tag>;
1270 using value_type = iter_value_t<_Iterator>;
1271 using difference_type = iter_difference_t<_Iterator>;
1272 using pointer = _Iterator;
1273 using reference = iter_rvalue_reference_t<_Iterator>;
1275 typedef typename __traits_type::iterator_category iterator_category;
1276 typedef typename __traits_type::value_type value_type;
1277 typedef typename __traits_type::difference_type difference_type;
1279 typedef _Iterator pointer;
1283 typename remove_reference<__base_ref>::type&&,
1284 __base_ref>::type reference;
1287 _GLIBCXX17_CONSTEXPR
1291 explicit _GLIBCXX17_CONSTEXPR
1295 template<
typename _Iter>
1296 _GLIBCXX17_CONSTEXPR
1298 : _M_current(__i.base()) { }
1300 #if __cplusplus <= 201703L
1301 _GLIBCXX17_CONSTEXPR iterator_type
1303 {
return _M_current; }
1305 constexpr iterator_type
1307 #if __cpp_lib_concepts
1308 requires copy_constructible<iterator_type>
1310 {
return _M_current; }
1312 constexpr iterator_type
1317 _GLIBCXX17_CONSTEXPR reference
1319 {
return static_cast<reference
>(*_M_current); }
1321 _GLIBCXX17_CONSTEXPR pointer
1323 {
return _M_current; }
1340 #if __cpp_lib_concepts
1342 operator++(
int) requires (!forward_iterator<_Iterator>)
1362 operator+(difference_type __n)
const
1366 operator+=(difference_type __n)
1373 operator-(difference_type __n)
const
1377 operator-=(difference_type __n)
1383 _GLIBCXX17_CONSTEXPR reference
1384 operator[](difference_type __n)
const
1387 #if __cplusplus > 201703L && __cpp_lib_concepts
1388 template<sentinel_for<_Iterator> _Sent>
1389 friend constexpr
bool
1390 operator==(
const move_iterator& __x,
const move_sentinel<_Sent>& __y)
1391 {
return __x.base() == __y.base(); }
1393 template<sized_sentinel_for<_Iterator> _Sent>
1394 friend constexpr iter_difference_t<_Iterator>
1395 operator-(
const move_sentinel<_Sent>& __x,
const move_iterator& __y)
1396 {
return __x.base() - __y.base(); }
1398 template<sized_sentinel_for<_Iterator> _Sent>
1399 friend constexpr iter_difference_t<_Iterator>
1400 operator-(
const move_iterator& __x,
const move_sentinel<_Sent>& __y)
1401 {
return __x.base() - __y.base(); }
1403 friend constexpr iter_rvalue_reference_t<_Iterator>
1405 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1406 {
return ranges::iter_move(__i._M_current); }
1408 template<indirectly_swappable<_Iterator> _Iter2>
1409 friend constexpr
void
1411 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1412 {
return ranges::iter_swap(__x._M_current, __y._M_current); }
1419 template<
typename _IteratorL,
typename _IteratorR>
1420 inline _GLIBCXX17_CONSTEXPR
bool
1423 #if __cplusplus > 201703L && __cpp_lib_concepts
1424 requires requires { __detail::__convbool(__x.base() == __y.base()); }
1426 {
return __x.base() == __y.base(); }
1428 template<
typename _Iterator>
1429 inline _GLIBCXX17_CONSTEXPR
bool
1430 operator==(
const move_iterator<_Iterator>& __x,
1431 const move_iterator<_Iterator>& __y)
1432 {
return __x.base() == __y.base(); }
1434 #if __cpp_lib_three_way_comparison
1435 template<
typename _IteratorL,
1436 three_way_comparable_with<_IteratorL> _IteratorR>
1437 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
1438 operator<=>(
const move_iterator<_IteratorL>& __x,
1439 const move_iterator<_IteratorR>& __y)
1440 {
return __x.base() <=> __y.base(); }
1442 template<
typename _IteratorL,
typename _IteratorR>
1443 inline _GLIBCXX17_CONSTEXPR
bool
1444 operator!=(
const move_iterator<_IteratorL>& __x,
1445 const move_iterator<_IteratorR>& __y)
1446 {
return !(__x == __y); }
1448 template<
typename _Iterator>
1449 inline _GLIBCXX17_CONSTEXPR
bool
1450 operator!=(
const move_iterator<_Iterator>& __x,
1451 const move_iterator<_Iterator>& __y)
1452 {
return !(__x == __y); }
1455 template<
typename _IteratorL,
typename _IteratorR>
1456 inline _GLIBCXX17_CONSTEXPR
bool
1457 operator<(
const move_iterator<_IteratorL>& __x,
1458 const move_iterator<_IteratorR>& __y)
1459 #if __cplusplus > 201703L && __cpp_lib_concepts
1460 requires requires { __detail::__convbool(__x.base() < __y.base()); }
1462 {
return __x.base() < __y.base(); }
1464 template<
typename _Iterator>
1465 inline _GLIBCXX17_CONSTEXPR
bool
1466 operator<(
const move_iterator<_Iterator>& __x,
1467 const move_iterator<_Iterator>& __y)
1468 {
return __x.base() < __y.base(); }
1470 template<
typename _IteratorL,
typename _IteratorR>
1471 inline _GLIBCXX17_CONSTEXPR
bool
1472 operator<=(
const move_iterator<_IteratorL>& __x,
1473 const move_iterator<_IteratorR>& __y)
1474 #if __cplusplus > 201703L && __cpp_lib_concepts
1475 requires requires { __detail::__convbool(__y.base() < __x.base()); }
1477 {
return !(__y < __x); }
1479 template<
typename _Iterator>
1480 inline _GLIBCXX17_CONSTEXPR
bool
1481 operator<=(
const move_iterator<_Iterator>& __x,
1482 const move_iterator<_Iterator>& __y)
1483 {
return !(__y < __x); }
1485 template<
typename _IteratorL,
typename _IteratorR>
1486 inline _GLIBCXX17_CONSTEXPR
bool
1487 operator>(
const move_iterator<_IteratorL>& __x,
1488 const move_iterator<_IteratorR>& __y)
1489 #if __cplusplus > 201703L && __cpp_lib_concepts
1490 requires requires { __detail::__convbool(__y.base() < __x.base()); }
1492 {
return __y < __x; }
1494 template<
typename _Iterator>
1495 inline _GLIBCXX17_CONSTEXPR
bool
1496 operator>(
const move_iterator<_Iterator>& __x,
1497 const move_iterator<_Iterator>& __y)
1498 {
return __y < __x; }
1500 template<
typename _IteratorL,
typename _IteratorR>
1501 inline _GLIBCXX17_CONSTEXPR
bool
1502 operator>=(
const move_iterator<_IteratorL>& __x,
1503 const move_iterator<_IteratorR>& __y)
1504 #if __cplusplus > 201703L && __cpp_lib_concepts
1505 requires requires { __detail::__convbool(__x.base() < __y.base()); }
1507 {
return !(__x < __y); }
1509 template<
typename _Iterator>
1510 inline _GLIBCXX17_CONSTEXPR
bool
1511 operator>=(
const move_iterator<_Iterator>& __x,
1512 const move_iterator<_Iterator>& __y)
1513 {
return !(__x < __y); }
1516 template<
typename _IteratorL,
typename _IteratorR>
1517 inline _GLIBCXX17_CONSTEXPR
auto
1518 operator-(
const move_iterator<_IteratorL>& __x,
1519 const move_iterator<_IteratorR>& __y)
1520 -> decltype(__x.base() - __y.base())
1521 {
return __x.base() - __y.base(); }
1523 template<
typename _Iterator>
1524 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1525 operator+(
typename move_iterator<_Iterator>::difference_type __n,
1526 const move_iterator<_Iterator>& __x)
1527 {
return __x + __n; }
1529 template<
typename _Iterator>
1530 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1531 make_move_iterator(_Iterator __i)
1532 {
return move_iterator<_Iterator>(
std::move(__i)); }
1534 template<
typename _Iterator,
typename _ReturnType
1535 =
typename conditional<__move_if_noexcept_cond
1536 <
typename iterator_traits<_Iterator>::value_type>::value,
1537 _Iterator, move_iterator<_Iterator>>::type>
1538 inline _GLIBCXX17_CONSTEXPR _ReturnType
1539 __make_move_if_noexcept_iterator(_Iterator __i)
1540 {
return _ReturnType(__i); }
1544 template<
typename _Tp,
typename _ReturnType
1545 =
typename conditional<__move_if_noexcept_cond<_Tp>::value,
1546 const _Tp*, move_iterator<_Tp*>>::type>
1547 inline _GLIBCXX17_CONSTEXPR _ReturnType
1548 __make_move_if_noexcept_iterator(_Tp* __i)
1549 {
return _ReturnType(__i); }
1551 #if __cplusplus > 201703L && __cpp_lib_concepts
1556 template<input_or_output_iterator _It>
1557 class _Common_iter_proxy
1559 iter_value_t<_It> _M_keep;
1561 _Common_iter_proxy(iter_reference_t<_It>&& __x)
1564 template<
typename _Iter,
typename _Sent>
1565 friend class common_iterator;
1568 const iter_value_t<_It>*
1573 template<
typename _It>
1574 concept __common_iter_has_arrow = indirectly_readable<const _It>
1575 && (requires(
const _It& __it) { __it.operator->(); }
1576 || is_reference_v<iter_reference_t<_It>>
1577 || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1582 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1583 requires (!same_as<_It, _Sent>) && copyable<_It>
1584 class common_iterator
1586 template<
typename _Tp,
typename _Up>
1587 static constexpr
bool
1590 if constexpr (is_trivially_default_constructible_v<_Tp>)
1591 return is_nothrow_assignable_v<_Tp, _Up>;
1593 return is_nothrow_constructible_v<_Tp, _Up>;
1596 template<
typename _It2,
typename _Sent2>
1597 static constexpr
bool
1599 {
return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1604 noexcept(is_nothrow_default_constructible_v<_It>)
1605 : _M_it(), _M_index(0)
1609 common_iterator(_It __i)
1610 noexcept(is_nothrow_move_constructible_v<_It>)
1611 : _M_it(
std::
move(__i)), _M_index(0)
1615 common_iterator(_Sent __s)
1616 noexcept(is_nothrow_move_constructible_v<_Sent>)
1617 : _M_sent(
std::
move(__s)), _M_index(1)
1620 template<
typename _It2,
typename _Sent2>
1621 requires convertible_to<const _It2&, _It>
1622 && convertible_to<const _Sent2&, _Sent>
1624 common_iterator(
const common_iterator<_It2, _Sent2>& __x)
1625 noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1626 : _M_valueless(), _M_index(__x._M_index)
1630 if constexpr (is_trivially_default_constructible_v<_It>)
1635 else if (_M_index == 1)
1637 if constexpr (is_trivially_default_constructible_v<_Sent>)
1645 common_iterator(
const common_iterator& __x)
1646 noexcept(_S_noexcept<const _It&, const _Sent&>())
1647 : _M_valueless(), _M_index(__x._M_index)
1651 if constexpr (is_trivially_default_constructible_v<_It>)
1656 else if (_M_index == 1)
1658 if constexpr (is_trivially_default_constructible_v<_Sent>)
1666 operator=(
const common_iterator& __x)
1667 noexcept(is_nothrow_copy_assignable_v<_It>
1668 && is_nothrow_copy_assignable_v<_Sent>
1669 && is_nothrow_copy_constructible_v<_It>
1670 && is_nothrow_copy_constructible_v<_Sent>)
1672 return this->
operator=<_It, _Sent>(__x);
1675 template<
typename _It2,
typename _Sent2>
1676 requires convertible_to<const _It2&, _It>
1677 && convertible_to<const _Sent2&, _Sent>
1678 && assignable_from<_It&, const _It2&>
1679 && assignable_from<_Sent&, const _Sent2&>
1681 operator=(
const common_iterator<_It2, _Sent2>& __x)
1682 noexcept(is_nothrow_constructible_v<_It, const _It2&>
1683 && is_nothrow_constructible_v<_Sent, const _Sent2&>
1684 && is_nothrow_assignable_v<_It, const _It2&>
1685 && is_nothrow_assignable_v<_Sent, const _Sent2&>)
1687 switch(_M_index << 2 | __x._M_index)
1693 _M_sent = __x._M_sent;
1712 __glibcxx_assert(__x._M_has_value());
1713 __builtin_unreachable();
1734 __glibcxx_assert(_M_index == 0);
1739 operator*() const requires __detail::__dereferenceable<const _It>
1741 __glibcxx_assert(_M_index == 0);
1746 operator->() const requires __detail::__common_iter_has_arrow<_It>
1748 __glibcxx_assert(_M_index == 0);
1749 if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
1751 else if constexpr (is_reference_v<iter_reference_t<_It>>)
1753 auto&& __tmp = *_M_it;
1757 return _Common_iter_proxy(*_M_it);
1763 __glibcxx_assert(_M_index == 0);
1771 __glibcxx_assert(_M_index == 0);
1772 if constexpr (forward_iterator<_It>)
1774 common_iterator __tmp = *
this;
1782 template<
typename _It2, sentinel_for<_It> _Sent2>
1783 requires sentinel_for<_Sent, _It2>
1785 operator==(
const common_iterator& __x,
1786 const common_iterator<_It2, _Sent2>& __y)
1788 switch(__x._M_index << 2 | __y._M_index)
1794 return __x._M_it == __y._M_sent;
1796 return __x._M_sent == __y._M_it;
1798 __glibcxx_assert(__x._M_has_value());
1799 __glibcxx_assert(__y._M_has_value());
1800 __builtin_unreachable();
1804 template<
typename _It2, sentinel_for<_It> _Sent2>
1805 requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
1807 operator==(
const common_iterator& __x,
1808 const common_iterator<_It2, _Sent2>& __y)
1810 switch(__x._M_index << 2 | __y._M_index)
1815 return __x._M_it == __y._M_it;
1817 return __x._M_it == __y._M_sent;
1819 return __x._M_sent == __y._M_it;
1821 __glibcxx_assert(__x._M_has_value());
1822 __glibcxx_assert(__y._M_has_value());
1823 __builtin_unreachable();
1827 template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
1828 requires sized_sentinel_for<_Sent, _It2>
1829 friend iter_difference_t<_It2>
1831 const common_iterator<_It2, _Sent2>& __y)
1833 switch(__x._M_index << 2 | __y._M_index)
1838 return __x._M_it - __y._M_it;
1840 return __x._M_it - __y._M_sent;
1842 return __x._M_sent - __y._M_it;
1844 __glibcxx_assert(__x._M_has_value());
1845 __glibcxx_assert(__y._M_has_value());
1846 __builtin_unreachable();
1850 friend iter_rvalue_reference_t<_It>
1851 iter_move(
const common_iterator& __i)
1852 noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
1853 requires input_iterator<_It>
1855 __glibcxx_assert(__i._M_index == 0);
1856 return ranges::iter_move(__i._M_it);
1859 template<indirectly_swappable<_It> _It2,
typename _Sent2>
1861 iter_swap(
const common_iterator& __x,
1862 const common_iterator<_It2, _Sent2>& __y)
1863 noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
1864 std::declval<const _It2&>())))
1866 __glibcxx_assert(__x._M_index == 0);
1867 __glibcxx_assert(__y._M_index == 0);
1868 return ranges::iter_swap(__x._M_it, __y._M_it);
1872 template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
1873 friend class common_iterator;
1875 bool _M_has_value() const noexcept {
return _M_index < 2; }
1881 unsigned char _M_valueless;
1883 unsigned char _M_index;
1886 template<
typename _It,
typename _Sent>
1887 struct incrementable_traits<common_iterator<_It, _Sent>>
1889 using difference_type = iter_difference_t<_It>;
1895 template<
typename _It,
typename _Sent>
1896 struct __common_iter_ptr
1901 template<
typename _It,
typename _Sent>
1902 requires __detail::__common_iter_has_arrow<_It>
1903 struct __common_iter_ptr<_It, _Sent>
1905 using common_iterator = std::common_iterator<_It, _Sent>;
1908 = decltype(std::declval<const common_iterator&>().operator->());
1912 template<input_iterator _It,
typename _Sent>
1913 struct iterator_traits<common_iterator<_It, _Sent>>
1915 using iterator_concept = conditional_t<forward_iterator<_It>,
1916 forward_iterator_tag, input_iterator_tag>;
1917 using iterator_category = __detail::__clamp_iter_cat<
1918 typename iterator_traits<_It>::iterator_category,
1919 forward_iterator_tag, input_iterator_tag>;
1920 using value_type = iter_value_t<_It>;
1921 using difference_type = iter_difference_t<_It>;
1922 using pointer =
typename __detail::__common_iter_ptr<_It, _Sent>::type;
1923 using reference = iter_reference_t<_It>;
1929 template<input_or_output_iterator _It>
1930 class counted_iterator
1933 using iterator_type = _It;
1935 constexpr counted_iterator() =
default;
1938 counted_iterator(_It __i, iter_difference_t<_It> __n)
1939 : _M_current(
std::
move(__i)), _M_length(__n)
1940 { __glibcxx_assert(__n >= 0); }
1942 template<
typename _It2>
1943 requires convertible_to<const _It2&, _It>
1945 counted_iterator(
const counted_iterator<_It2>& __x)
1946 : _M_current(__x._M_current), _M_length(__x._M_length)
1949 template<
typename _It2>
1950 requires assignable_from<_It&, const _It2&>
1951 constexpr counted_iterator&
1952 operator=(
const counted_iterator<_It2>& __x)
1954 _M_current = __x._M_current;
1955 _M_length = __x._M_length;
1961 noexcept(is_nothrow_copy_constructible_v<_It>)
1962 requires copy_constructible<_It>
1963 {
return _M_current; }
1967 noexcept(is_nothrow_move_constructible_v<_It>)
1970 constexpr iter_difference_t<_It>
1971 count() const noexcept {
return _M_length; }
1973 constexpr decltype(
auto)
1975 noexcept(noexcept(*_M_current))
1976 {
return *_M_current; }
1978 constexpr decltype(
auto)
1980 noexcept(noexcept(*_M_current))
1981 requires __detail::__dereferenceable<const _It>
1982 {
return *_M_current; }
1984 constexpr counted_iterator&
1987 __glibcxx_assert(_M_length > 0);
1996 __glibcxx_assert(_M_length > 0);
2000 return _M_current++;
2008 constexpr counted_iterator
2009 operator++(
int) requires forward_iterator<_It>
2016 constexpr counted_iterator&
2017 operator--() requires bidirectional_iterator<_It>
2024 constexpr counted_iterator
2025 operator--(
int) requires bidirectional_iterator<_It>
2032 constexpr counted_iterator
2033 operator+(iter_difference_t<_It> __n)
const
2034 requires random_access_iterator<_It>
2035 {
return counted_iterator(_M_current + __n, _M_length - __n); }
2037 friend constexpr counted_iterator
2038 operator+(iter_difference_t<_It> __n,
const counted_iterator& __x)
2039 requires random_access_iterator<_It>
2040 {
return __x + __n; }
2042 constexpr counted_iterator&
2043 operator+=(iter_difference_t<_It> __n)
2044 requires random_access_iterator<_It>
2046 __glibcxx_assert(__n <= _M_length);
2052 constexpr counted_iterator
2053 operator-(iter_difference_t<_It> __n)
const
2054 requires random_access_iterator<_It>
2055 {
return counted_iterator(_M_current - __n, _M_length + __n); }
2057 template<common_with<_It> _It2>
2058 friend constexpr iter_difference_t<_It2>
2060 const counted_iterator<_It2>& __y)
2061 {
return __y._M_length - __x._M_length; }
2063 friend constexpr iter_difference_t<_It>
2064 operator-(
const counted_iterator& __x, default_sentinel_t)
2065 {
return -__x._M_length; }
2067 friend constexpr iter_difference_t<_It>
2068 operator-(default_sentinel_t,
const counted_iterator& __y)
2069 {
return __y._M_length; }
2071 constexpr counted_iterator&
2072 operator-=(iter_difference_t<_It> __n)
2073 requires random_access_iterator<_It>
2075 __glibcxx_assert(-__n <= _M_length);
2081 constexpr decltype(
auto)
2082 operator[](iter_difference_t<_It> __n) const
2083 noexcept(noexcept(_M_current[__n]))
2084 requires random_access_iterator<_It>
2086 __glibcxx_assert(__n < _M_length);
2087 return _M_current[__n];
2090 template<common_with<_It> _It2>
2091 friend constexpr
bool
2092 operator==(
const counted_iterator& __x,
2093 const counted_iterator<_It2>& __y)
2094 {
return __x._M_length == __y._M_length; }
2096 friend constexpr
bool
2097 operator==(
const counted_iterator& __x, default_sentinel_t)
2098 {
return __x._M_length == 0; }
2100 template<common_with<_It> _It2>
2101 friend constexpr strong_ordering
2102 operator<=>(
const counted_iterator& __x,
2103 const counted_iterator<_It2>& __y)
2104 {
return __y._M_length <=> __x._M_length; }
2106 friend constexpr iter_rvalue_reference_t<_It>
2107 iter_move(
const counted_iterator& __i)
2108 noexcept(noexcept(ranges::iter_move(__i._M_current)))
2109 requires input_iterator<_It>
2110 {
return ranges::iter_move(__i._M_current); }
2112 template<indirectly_swappable<_It> _It2>
2113 friend constexpr
void
2114 iter_swap(
const counted_iterator& __x,
2115 const counted_iterator<_It2>& __y)
2116 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2117 { ranges::iter_swap(__x._M_current, __y._M_current); }
2120 template<input_or_output_iterator _It2>
friend class counted_iterator;
2122 _It _M_current = _It();
2123 iter_difference_t<_It> _M_length = 0;
2126 template<
typename _It>
2127 struct incrementable_traits<counted_iterator<_It>>
2129 using difference_type = iter_difference_t<_It>;
2132 template<input_iterator _It>
2133 struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2135 using pointer = void;
2141 template<
typename _Iterator>
2143 __niter_base(move_iterator<_Iterator> __it)
2144 -> decltype(make_move_iterator(__niter_base(__it.base())))
2145 {
return make_move_iterator(__niter_base(__it.base())); }
2147 template<
typename _Iterator>
2148 struct __is_move_iterator<move_iterator<_Iterator> >
2150 enum { __value = 1 };
2151 typedef __true_type __type;
2154 template<
typename _Iterator>
2156 __miter_base(move_iterator<_Iterator> __it)
2157 -> decltype(__miter_base(__it.base()))
2158 {
return __miter_base(__it.base()); }
2160 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2161 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2162 std::__make_move_if_noexcept_iterator(_Iter)
2164 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2165 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2168 #if __cpp_deduction_guides >= 201606
2171 template<
typename _InputIterator>
2173 typename iterator_traits<_InputIterator>::value_type::first_type>;
2175 template<
typename _InputIterator>
2176 using __iter_val_t =
2177 typename iterator_traits<_InputIterator>::value_type::second_type;
2179 template<
typename _T1,
typename _T2>
2182 template<
typename _InputIterator>
2183 using __iter_to_alloc_t =
2184 pair<add_const_t<__iter_key_t<_InputIterator>>,
2185 __iter_val_t<_InputIterator>>;
2186 #endif // __cpp_deduction_guides
2188 _GLIBCXX_END_NAMESPACE_VERSION
2191 #ifdef _GLIBCXX_DEBUG