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
81 namespace std _GLIBCXX_VISIBILITY(default)
83 _GLIBCXX_BEGIN_NAMESPACE_VERSION
109 template<
typename _Iterator>
111 :
public iterator<typename iterator_traits<_Iterator>::iterator_category,
112 typename iterator_traits<_Iterator>::value_type,
113 typename iterator_traits<_Iterator>::difference_type,
114 typename iterator_traits<_Iterator>::pointer,
115 typename iterator_traits<_Iterator>::reference>
123 typedef _Iterator iterator_type;
124 typedef typename __traits_type::difference_type difference_type;
125 typedef typename __traits_type::pointer pointer;
126 typedef typename __traits_type::reference reference;
141 explicit _GLIBCXX17_CONSTEXPR
149 : current(__x.current) { }
151 #if __cplusplus >= 201103L
159 template<
typename _Iter>
162 : current(__x.
base()) { }
167 _GLIBCXX17_CONSTEXPR iterator_type
181 _GLIBCXX17_CONSTEXPR reference
184 _Iterator __tmp = current;
193 _GLIBCXX17_CONSTEXPR pointer
195 #if __cplusplus > 201703L && defined __cpp_concepts
196 requires is_pointer_v<_Iterator>
197 || requires(
const _Iterator __i) { __i.operator->(); }
202 _Iterator __tmp = current;
204 return _S_to_pointer(__tmp);
306 _GLIBCXX17_CONSTEXPR reference
308 {
return *(*
this + __n); }
311 template<
typename _Tp>
312 static _GLIBCXX17_CONSTEXPR _Tp*
313 _S_to_pointer(_Tp* __p)
316 template<
typename _Tp>
317 static _GLIBCXX17_CONSTEXPR pointer
318 _S_to_pointer(_Tp __t)
319 {
return __t.operator->(); }
332 template<
typename _Iterator>
333 inline _GLIBCXX17_CONSTEXPR
bool
336 {
return __x.
base() == __y.
base(); }
338 template<
typename _Iterator>
339 inline _GLIBCXX17_CONSTEXPR
bool
340 operator<(
const reverse_iterator<_Iterator>& __x,
341 const reverse_iterator<_Iterator>& __y)
342 {
return __y.base() < __x.base(); }
344 template<
typename _Iterator>
345 inline _GLIBCXX17_CONSTEXPR
bool
346 operator!=(
const reverse_iterator<_Iterator>& __x,
347 const reverse_iterator<_Iterator>& __y)
348 {
return !(__x == __y); }
350 template<
typename _Iterator>
351 inline _GLIBCXX17_CONSTEXPR
bool
352 operator>(
const reverse_iterator<_Iterator>& __x,
353 const reverse_iterator<_Iterator>& __y)
354 {
return __y < __x; }
356 template<
typename _Iterator>
357 inline _GLIBCXX17_CONSTEXPR
bool
358 operator<=(
const reverse_iterator<_Iterator>& __x,
359 const reverse_iterator<_Iterator>& __y)
360 {
return !(__y < __x); }
362 template<
typename _Iterator>
363 inline _GLIBCXX17_CONSTEXPR
bool
364 operator>=(
const reverse_iterator<_Iterator>& __x,
365 const reverse_iterator<_Iterator>& __y)
366 {
return !(__x < __y); }
370 template<
typename _IteratorL,
typename _IteratorR>
371 inline _GLIBCXX17_CONSTEXPR
bool
372 operator==(
const reverse_iterator<_IteratorL>& __x,
373 const reverse_iterator<_IteratorR>& __y)
374 {
return __x.base() == __y.base(); }
376 template<
typename _IteratorL,
typename _IteratorR>
377 inline _GLIBCXX17_CONSTEXPR
bool
378 operator<(
const reverse_iterator<_IteratorL>& __x,
379 const reverse_iterator<_IteratorR>& __y)
380 {
return __y.base() < __x.base(); }
382 template<
typename _IteratorL,
typename _IteratorR>
383 inline _GLIBCXX17_CONSTEXPR
bool
384 operator!=(
const reverse_iterator<_IteratorL>& __x,
385 const reverse_iterator<_IteratorR>& __y)
386 {
return !(__x == __y); }
388 template<
typename _IteratorL,
typename _IteratorR>
389 inline _GLIBCXX17_CONSTEXPR
bool
390 operator>(
const reverse_iterator<_IteratorL>& __x,
391 const reverse_iterator<_IteratorR>& __y)
392 {
return __y < __x; }
394 template<
typename _IteratorL,
typename _IteratorR>
395 inline _GLIBCXX17_CONSTEXPR
bool
396 operator<=(
const reverse_iterator<_IteratorL>& __x,
397 const reverse_iterator<_IteratorR>& __y)
398 {
return !(__y < __x); }
400 template<
typename _IteratorL,
typename _IteratorR>
401 inline _GLIBCXX17_CONSTEXPR
bool
402 operator>=(
const reverse_iterator<_IteratorL>& __x,
403 const reverse_iterator<_IteratorR>& __y)
404 {
return !(__x < __y); }
407 #if __cplusplus < 201103L
408 template<
typename _Iterator>
409 inline typename reverse_iterator<_Iterator>::difference_type
410 operator-(
const reverse_iterator<_Iterator>& __x,
411 const reverse_iterator<_Iterator>& __y)
412 {
return __y.base() - __x.base(); }
414 template<
typename _IteratorL,
typename _IteratorR>
415 inline typename reverse_iterator<_IteratorL>::difference_type
416 operator-(
const reverse_iterator<_IteratorL>& __x,
417 const reverse_iterator<_IteratorR>& __y)
418 {
return __y.base() - __x.base(); }
422 template<
typename _IteratorL,
typename _IteratorR>
423 inline _GLIBCXX17_CONSTEXPR
auto
424 operator-(
const reverse_iterator<_IteratorL>& __x,
425 const reverse_iterator<_IteratorR>& __y)
426 -> decltype(__y.base() - __x.base())
427 {
return __y.base() - __x.base(); }
430 template<
typename _Iterator>
431 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
432 operator+(
typename reverse_iterator<_Iterator>::difference_type __n,
433 const reverse_iterator<_Iterator>& __x)
434 {
return reverse_iterator<_Iterator>(__x.base() - __n); }
436 #if __cplusplus >= 201103L
438 template<
typename _Iterator>
439 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
440 __make_reverse_iterator(_Iterator __i)
441 {
return reverse_iterator<_Iterator>(__i); }
443 # if __cplusplus >= 201402L
444 # define __cpp_lib_make_reverse_iterator 201402
449 template<
typename _Iterator>
450 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
454 # if __cplusplus > 201703L && defined __cpp_lib_concepts
455 template<
typename _Iterator1,
typename _Iterator2>
456 requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
457 inline constexpr
bool
458 disable_sized_sentinel_for<reverse_iterator<_Iterator1>,
459 reverse_iterator<_Iterator2>> =
true;
463 template<
typename _Iterator>
466 __niter_base(reverse_iterator<_Iterator> __it)
467 -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
468 {
return __make_reverse_iterator(__niter_base(__it.base())); }
470 template<
typename _Iterator>
471 struct __is_move_iterator<reverse_iterator<_Iterator> >
472 : __is_move_iterator<_Iterator>
475 template<
typename _Iterator>
478 __miter_base(reverse_iterator<_Iterator> __it)
479 -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
480 {
return __make_reverse_iterator(__miter_base(__it.base())); }
494 template<
typename _Container>
496 :
public iterator<output_iterator_tag, void, void, void, void>
499 _Container* container;
521 #if __cplusplus < 201103L
523 operator=(
typename _Container::const_reference __value)
525 container->push_back(__value);
530 operator=(
const typename _Container::value_type& __value)
532 container->push_back(__value);
537 operator=(
typename _Container::value_type&& __value)
539 container->push_back(
std::move(__value));
571 template<
typename _Container>
572 inline back_insert_iterator<_Container>
586 template<
typename _Container>
588 :
public iterator<output_iterator_tag, void, void, void, void>
591 _Container* container;
612 #if __cplusplus < 201103L
614 operator=(
typename _Container::const_reference __value)
616 container->push_front(__value);
621 operator=(
const typename _Container::value_type& __value)
623 container->push_front(__value);
628 operator=(
typename _Container::value_type&& __value)
630 container->push_front(
std::move(__value));
662 template<
typename _Container>
663 inline front_insert_iterator<_Container>
681 template<
typename _Container>
683 :
public iterator<output_iterator_tag, void, void, void, void>
686 _Container* container;
687 typename _Container::iterator iter;
723 #if __cplusplus < 201103L
725 operator=(
typename _Container::const_reference __value)
727 iter = container->insert(iter, __value);
733 operator=(
const typename _Container::value_type& __value)
735 iter = container->insert(iter, __value);
741 operator=(
typename _Container::value_type&& __value)
743 iter = container->insert(iter,
std::move(__value));
777 template<
typename _Container,
typename _Iterator>
778 inline insert_iterator<_Container>
782 typename _Container::iterator(__i));
787 _GLIBCXX_END_NAMESPACE_VERSION
790 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
792 _GLIBCXX_BEGIN_NAMESPACE_VERSION
801 template<
typename _Iterator,
typename _Container>
802 class __normal_iterator
805 _Iterator _M_current;
810 typedef _Iterator iterator_type;
811 typedef typename __traits_type::iterator_category iterator_category;
812 typedef typename __traits_type::value_type value_type;
813 typedef typename __traits_type::difference_type difference_type;
814 typedef typename __traits_type::reference reference;
815 typedef typename __traits_type::pointer pointer;
817 #if __cplusplus > 201703L && __cpp_lib_concepts
818 using iterator_concept = std::__detail::__iter_concept<_Iterator>;
821 _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
822 : _M_current(_Iterator()) { }
824 explicit _GLIBCXX20_CONSTEXPR
825 __normal_iterator(
const _Iterator& __i) _GLIBCXX_NOEXCEPT
826 : _M_current(__i) { }
829 template<
typename _Iter>
831 __normal_iterator(
const __normal_iterator<_Iter,
832 typename __enable_if<
833 (std::__are_same<_Iter, typename _Container::pointer>::__value),
834 _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
835 : _M_current(__i.base()) { }
841 {
return *_M_current; }
845 operator->() const _GLIBCXX_NOEXCEPT
846 {
return _M_current; }
850 operator++() _GLIBCXX_NOEXCEPT
858 operator++(
int) _GLIBCXX_NOEXCEPT
859 {
return __normal_iterator(_M_current++); }
864 operator--() _GLIBCXX_NOEXCEPT
872 operator--(
int) _GLIBCXX_NOEXCEPT
873 {
return __normal_iterator(_M_current--); }
878 operator[](difference_type __n)
const _GLIBCXX_NOEXCEPT
879 {
return _M_current[__n]; }
883 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
884 { _M_current += __n;
return *
this; }
888 operator+(difference_type __n)
const _GLIBCXX_NOEXCEPT
889 {
return __normal_iterator(_M_current + __n); }
893 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
894 { _M_current -= __n;
return *
this; }
898 operator-(difference_type __n)
const _GLIBCXX_NOEXCEPT
899 {
return __normal_iterator(_M_current - __n); }
903 base() const _GLIBCXX_NOEXCEPT
904 {
return _M_current; }
916 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
919 operator==(
const __normal_iterator<_IteratorL, _Container>& __lhs,
920 const __normal_iterator<_IteratorR, _Container>& __rhs)
922 {
return __lhs.base() == __rhs.base(); }
924 template<
typename _Iterator,
typename _Container>
927 operator==(
const __normal_iterator<_Iterator, _Container>& __lhs,
928 const __normal_iterator<_Iterator, _Container>& __rhs)
930 {
return __lhs.base() == __rhs.base(); }
932 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
935 operator!=(
const __normal_iterator<_IteratorL, _Container>& __lhs,
936 const __normal_iterator<_IteratorR, _Container>& __rhs)
938 {
return __lhs.base() != __rhs.base(); }
940 template<
typename _Iterator,
typename _Container>
943 operator!=(
const __normal_iterator<_Iterator, _Container>& __lhs,
944 const __normal_iterator<_Iterator, _Container>& __rhs)
946 {
return __lhs.base() != __rhs.base(); }
949 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
952 operator<(
const __normal_iterator<_IteratorL, _Container>& __lhs,
953 const __normal_iterator<_IteratorR, _Container>& __rhs)
955 {
return __lhs.base() < __rhs.base(); }
957 template<
typename _Iterator,
typename _Container>
960 operator<(
const __normal_iterator<_Iterator, _Container>& __lhs,
961 const __normal_iterator<_Iterator, _Container>& __rhs)
963 {
return __lhs.base() < __rhs.base(); }
965 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
968 operator>(
const __normal_iterator<_IteratorL, _Container>& __lhs,
969 const __normal_iterator<_IteratorR, _Container>& __rhs)
971 {
return __lhs.base() > __rhs.base(); }
973 template<
typename _Iterator,
typename _Container>
976 operator>(
const __normal_iterator<_Iterator, _Container>& __lhs,
977 const __normal_iterator<_Iterator, _Container>& __rhs)
979 {
return __lhs.base() > __rhs.base(); }
981 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
984 operator<=(
const __normal_iterator<_IteratorL, _Container>& __lhs,
985 const __normal_iterator<_IteratorR, _Container>& __rhs)
987 {
return __lhs.base() <= __rhs.base(); }
989 template<
typename _Iterator,
typename _Container>
992 operator<=(
const __normal_iterator<_Iterator, _Container>& __lhs,
993 const __normal_iterator<_Iterator, _Container>& __rhs)
995 {
return __lhs.base() <= __rhs.base(); }
997 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1000 operator>=(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1001 const __normal_iterator<_IteratorR, _Container>& __rhs)
1003 {
return __lhs.base() >= __rhs.base(); }
1005 template<
typename _Iterator,
typename _Container>
1006 _GLIBCXX20_CONSTEXPR
1008 operator>=(
const __normal_iterator<_Iterator, _Container>& __lhs,
1009 const __normal_iterator<_Iterator, _Container>& __rhs)
1011 {
return __lhs.base() >= __rhs.base(); }
1017 template<
typename _IteratorL,
typename _IteratorR,
typename _Container>
1018 #if __cplusplus >= 201103L
1020 _GLIBCXX20_CONSTEXPR
1022 operator-(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1023 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
1024 -> decltype(__lhs.base() - __rhs.base())
1026 inline typename __normal_iterator<_IteratorL, _Container>::difference_type
1027 operator-(
const __normal_iterator<_IteratorL, _Container>& __lhs,
1028 const __normal_iterator<_IteratorR, _Container>& __rhs)
1030 {
return __lhs.base() - __rhs.base(); }
1032 template<
typename _Iterator,
typename _Container>
1033 _GLIBCXX20_CONSTEXPR
1034 inline typename __normal_iterator<_Iterator, _Container>::difference_type
1035 operator-(
const __normal_iterator<_Iterator, _Container>& __lhs,
1036 const __normal_iterator<_Iterator, _Container>& __rhs)
1038 {
return __lhs.base() - __rhs.base(); }
1040 template<
typename _Iterator,
typename _Container>
1041 _GLIBCXX20_CONSTEXPR
1042 inline __normal_iterator<_Iterator, _Container>
1043 operator+(
typename __normal_iterator<_Iterator, _Container>::difference_type
1044 __n,
const __normal_iterator<_Iterator, _Container>& __i)
1046 {
return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
1048 _GLIBCXX_END_NAMESPACE_VERSION
1051 namespace std _GLIBCXX_VISIBILITY(default)
1053 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1055 template<
typename _Iterator,
typename _Container>
1056 _GLIBCXX20_CONSTEXPR
1058 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
1060 {
return __it.base(); }
1062 #if __cplusplus >= 201103L
1068 #if __cplusplus > 201703L && __cpp_lib_concepts
1069 template<semiregular _Sent>
1075 noexcept(is_nothrow_default_constructible_v<_Sent>)
1079 move_sentinel(_Sent __s)
1080 noexcept(is_nothrow_move_constructible_v<_Sent>)
1083 template<
typename _S2> requires convertible_to<const _S2&, _Sent>
1085 move_sentinel(
const move_sentinel<_S2>& __s)
1086 noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
1087 : _M_last(__s.base())
1090 template<
typename _S2> requires assignable_from<_Sent&, const _S2&>
1091 constexpr move_sentinel&
1092 operator=(
const move_sentinel<_S2>& __s)
1093 noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
1095 _M_last = __s.base();
1101 noexcept(is_nothrow_copy_constructible_v<_Sent>)
1112 template<
typename _Cat,
typename _Limit,
typename _Otherwise = _Cat>
1113 using __clamp_iter_cat
1114 = conditional_t<derived_from<_Cat, _Limit>, _Limit, _Otherwise>;
1127 template<
typename _Iterator>
1130 _Iterator _M_current;
1133 #if __cplusplus > 201703L && __cpp_lib_concepts
1134 using __base_cat =
typename __traits_type::iterator_category;
1136 using __base_ref =
typename __traits_type::reference;
1140 using iterator_type = _Iterator;
1142 #if __cplusplus > 201703L && __cpp_lib_concepts
1144 using iterator_category
1145 = __detail::__clamp_iter_cat<__base_cat, random_access_iterator_tag>;
1146 using value_type = iter_value_t<_Iterator>;
1147 using difference_type = iter_difference_t<_Iterator>;
1148 using pointer = _Iterator;
1149 using reference = iter_rvalue_reference_t<_Iterator>;
1151 typedef typename __traits_type::iterator_category iterator_category;
1152 typedef typename __traits_type::value_type value_type;
1153 typedef typename __traits_type::difference_type difference_type;
1155 typedef _Iterator pointer;
1159 typename remove_reference<__base_ref>::type&&,
1160 __base_ref>::type reference;
1163 _GLIBCXX17_CONSTEXPR
1167 explicit _GLIBCXX17_CONSTEXPR
1169 : _M_current(__i) { }
1171 template<
typename _Iter>
1172 _GLIBCXX17_CONSTEXPR
1174 : _M_current(__i.base()) { }
1176 _GLIBCXX17_CONSTEXPR iterator_type
1178 {
return _M_current; }
1180 _GLIBCXX17_CONSTEXPR reference
1182 {
return static_cast<reference
>(*_M_current); }
1184 _GLIBCXX17_CONSTEXPR pointer
1186 {
return _M_current; }
1219 operator+(difference_type __n)
const
1223 operator+=(difference_type __n)
1230 operator-(difference_type __n)
const
1234 operator-=(difference_type __n)
1240 _GLIBCXX17_CONSTEXPR reference
1241 operator[](difference_type __n)
const
1244 #if __cplusplus > 201703L && __cpp_lib_concepts
1245 template<sentinel_for<_Iterator> _Sent>
1246 friend constexpr
bool
1247 operator==(
const move_iterator& __x,
const move_sentinel<_Sent>& __y)
1248 {
return __x.base() == __y.base(); }
1250 template<sized_sentinel_for<_Iterator> _Sent>
1251 friend constexpr iter_difference_t<_Iterator>
1252 operator-(
const move_sentinel<_Sent>& __x,
const move_iterator& __y)
1253 {
return __x.base() - __y.base(); }
1255 template<sized_sentinel_for<_Iterator> _Sent>
1256 friend constexpr iter_difference_t<_Iterator>
1257 operator-(
const move_iterator& __x,
const move_sentinel<_Sent>& __y)
1258 {
return __x.base() - __y.base(); }
1260 friend constexpr iter_rvalue_reference_t<_Iterator>
1262 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1263 {
return ranges::iter_move(__i._M_current); }
1265 template<indirectly_swappable<_Iterator> _Iter2>
1266 friend constexpr
void
1268 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1269 {
return ranges::iter_swap(__x._M_current, __y._M_current); }
1276 template<
typename _IteratorL,
typename _IteratorR>
1277 inline _GLIBCXX17_CONSTEXPR
bool
1280 {
return __x.base() == __y.base(); }
1282 template<
typename _Iterator>
1283 inline _GLIBCXX17_CONSTEXPR
bool
1284 operator==(
const move_iterator<_Iterator>& __x,
1285 const move_iterator<_Iterator>& __y)
1286 {
return __x.base() == __y.base(); }
1288 template<
typename _IteratorL,
typename _IteratorR>
1289 inline _GLIBCXX17_CONSTEXPR
bool
1290 operator!=(
const move_iterator<_IteratorL>& __x,
1291 const move_iterator<_IteratorR>& __y)
1292 {
return !(__x == __y); }
1294 template<
typename _Iterator>
1295 inline _GLIBCXX17_CONSTEXPR
bool
1296 operator!=(
const move_iterator<_Iterator>& __x,
1297 const move_iterator<_Iterator>& __y)
1298 {
return !(__x == __y); }
1300 template<
typename _IteratorL,
typename _IteratorR>
1301 inline _GLIBCXX17_CONSTEXPR
bool
1302 operator<(
const move_iterator<_IteratorL>& __x,
1303 const move_iterator<_IteratorR>& __y)
1304 {
return __x.base() < __y.base(); }
1306 template<
typename _Iterator>
1307 inline _GLIBCXX17_CONSTEXPR
bool
1308 operator<(
const move_iterator<_Iterator>& __x,
1309 const move_iterator<_Iterator>& __y)
1310 {
return __x.base() < __y.base(); }
1312 template<
typename _IteratorL,
typename _IteratorR>
1313 inline _GLIBCXX17_CONSTEXPR
bool
1314 operator<=(
const move_iterator<_IteratorL>& __x,
1315 const move_iterator<_IteratorR>& __y)
1316 {
return !(__y < __x); }
1318 template<
typename _Iterator>
1319 inline _GLIBCXX17_CONSTEXPR
bool
1320 operator<=(
const move_iterator<_Iterator>& __x,
1321 const move_iterator<_Iterator>& __y)
1322 {
return !(__y < __x); }
1324 template<
typename _IteratorL,
typename _IteratorR>
1325 inline _GLIBCXX17_CONSTEXPR
bool
1326 operator>(
const move_iterator<_IteratorL>& __x,
1327 const move_iterator<_IteratorR>& __y)
1328 {
return __y < __x; }
1330 template<
typename _Iterator>
1331 inline _GLIBCXX17_CONSTEXPR
bool
1332 operator>(
const move_iterator<_Iterator>& __x,
1333 const move_iterator<_Iterator>& __y)
1334 {
return __y < __x; }
1336 template<
typename _IteratorL,
typename _IteratorR>
1337 inline _GLIBCXX17_CONSTEXPR
bool
1338 operator>=(
const move_iterator<_IteratorL>& __x,
1339 const move_iterator<_IteratorR>& __y)
1340 {
return !(__x < __y); }
1342 template<
typename _Iterator>
1343 inline _GLIBCXX17_CONSTEXPR
bool
1344 operator>=(
const move_iterator<_Iterator>& __x,
1345 const move_iterator<_Iterator>& __y)
1346 {
return !(__x < __y); }
1349 template<
typename _IteratorL,
typename _IteratorR>
1350 inline _GLIBCXX17_CONSTEXPR
auto
1351 operator-(
const move_iterator<_IteratorL>& __x,
1352 const move_iterator<_IteratorR>& __y)
1353 -> decltype(__x.base() - __y.base())
1354 {
return __x.base() - __y.base(); }
1356 template<
typename _Iterator>
1357 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1358 operator+(
typename move_iterator<_Iterator>::difference_type __n,
1359 const move_iterator<_Iterator>& __x)
1360 {
return __x + __n; }
1362 template<
typename _Iterator>
1363 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1364 make_move_iterator(_Iterator __i)
1365 {
return move_iterator<_Iterator>(__i); }
1367 template<
typename _Iterator,
typename _ReturnType
1368 =
typename conditional<__move_if_noexcept_cond
1369 <
typename iterator_traits<_Iterator>::value_type>::value,
1370 _Iterator, move_iterator<_Iterator>>::type>
1371 inline _GLIBCXX17_CONSTEXPR _ReturnType
1372 __make_move_if_noexcept_iterator(_Iterator __i)
1373 {
return _ReturnType(__i); }
1377 template<
typename _Tp,
typename _ReturnType
1378 =
typename conditional<__move_if_noexcept_cond<_Tp>::value,
1379 const _Tp*, move_iterator<_Tp*>>::type>
1380 inline _GLIBCXX17_CONSTEXPR _ReturnType
1381 __make_move_if_noexcept_iterator(_Tp* __i)
1382 {
return _ReturnType(__i); }
1384 #if __cplusplus > 201703L && __cpp_lib_concepts
1389 template<input_or_output_iterator _It>
1390 class _Common_iter_proxy
1392 iter_value_t<_It> _M_keep;
1394 _Common_iter_proxy(iter_reference_t<_It>&& __x)
1397 template<
typename _Iter,
typename _Sent>
1398 friend class common_iterator;
1401 const iter_value_t<_It>*
1406 template<
typename _It>
1407 concept __common_iter_has_arrow = readable<const _It>
1408 && (requires(
const _It& __it) { __it.operator->(); }
1409 || is_reference_v<iter_reference_t<_It>>
1410 || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1415 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1416 requires (!same_as<_It, _Sent>)
1417 class common_iterator
1419 template<
typename _Tp,
typename _Up>
1420 static constexpr
bool
1423 if constexpr (is_trivially_default_constructible_v<_Tp>)
1424 return is_nothrow_assignable_v<_Tp, _Up>;
1426 return is_nothrow_constructible_v<_Tp, _Up>;
1429 template<
typename _It2,
typename _Sent2>
1430 static constexpr
bool
1432 {
return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1437 noexcept(is_nothrow_default_constructible_v<_It>)
1438 : _M_it(), _M_index(0)
1442 common_iterator(_It __i)
1443 noexcept(is_nothrow_move_constructible_v<_It>)
1444 : _M_it(
std::
move(__i)), _M_index(0)
1448 common_iterator(_Sent __s)
1449 noexcept(is_nothrow_move_constructible_v<_Sent>)
1450 : _M_sent(
std::
move(__s)), _M_index(1)
1453 template<
typename _It2,
typename _Sent2>
1454 requires convertible_to<const _It2&, _It>
1455 && convertible_to<const _Sent2&, _Sent>
1457 common_iterator(
const common_iterator<_It2, _Sent2>& __x)
1458 noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1459 : _M_valueless(), _M_index(__x._M_index)
1463 if constexpr (is_trivially_default_constructible_v<_It>)
1468 else if (_M_index == 1)
1470 if constexpr (is_trivially_default_constructible_v<_Sent>)
1478 common_iterator(
const common_iterator& __x)
1479 noexcept(_S_noexcept<const _It&, const _Sent&>())
1480 : _M_valueless(), _M_index(__x._M_index)
1484 if constexpr (is_trivially_default_constructible_v<_It>)
1489 else if (_M_index == 1)
1491 if constexpr (is_trivially_default_constructible_v<_Sent>)
1499 operator=(
const common_iterator& __x)
1500 noexcept(is_nothrow_copy_assignable_v<_It>
1501 && is_nothrow_copy_assignable_v<_Sent>
1502 && is_nothrow_copy_constructible_v<_It>
1503 && is_nothrow_copy_constructible_v<_Sent>)
1505 return this->
operator=<_It, _Sent>(__x);
1508 template<
typename _It2,
typename _Sent2>
1509 requires convertible_to<const _It2&, _It>
1510 && convertible_to<const _Sent2&, _Sent>
1511 && assignable_from<_It&, const _It2&>
1512 && assignable_from<_Sent&, const _Sent2&>
1514 operator=(
const common_iterator<_It2, _Sent2>& __x)
1515 noexcept(is_nothrow_constructible_v<_It, const _It2&>
1516 && is_nothrow_constructible_v<_Sent, const _Sent2&>
1517 && is_nothrow_assignable_v<_It, const _It2&>
1518 && is_nothrow_assignable_v<_Sent, const _Sent2&>)
1520 switch(_M_index << 2 | __x._M_index)
1526 _M_sent = __x._M_sent;
1545 __glibcxx_assert(__x._M_has_value());
1546 __builtin_unreachable();
1567 __glibcxx_assert(_M_index == 0);
1572 operator*() const requires __detail::__dereferenceable<const _It>
1574 __glibcxx_assert(_M_index == 0);
1579 operator->() const requires __detail::__common_iter_has_arrow<_It>
1581 __glibcxx_assert(_M_index == 0);
1582 if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
1584 else if constexpr (is_reference_v<iter_reference_t<_It>>)
1586 auto&& __tmp = *_M_it;
1590 return _Common_iter_proxy(*_M_it);
1596 __glibcxx_assert(_M_index == 0);
1604 __glibcxx_assert(_M_index == 0);
1605 if constexpr (forward_iterator<_It>)
1607 common_iterator __tmp = *
this;
1615 template<
typename _It2, sentinel_for<_It> _Sent2>
1616 requires sentinel_for<_Sent, _It2>
1618 operator==(
const common_iterator& __x,
1619 const common_iterator<_It2, _Sent2>& __y)
1621 switch(__x._M_index << 2 | __y._M_index)
1627 return __x._M_it == __y._M_sent;
1629 return __x._M_sent == __y._M_it;
1631 __glibcxx_assert(__x._M_has_value());
1632 __glibcxx_assert(__y._M_has_value());
1633 __builtin_unreachable();
1637 template<
typename _It2, sentinel_for<_It> _Sent2>
1638 requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
1640 operator==(
const common_iterator& __x,
1641 const common_iterator<_It2, _Sent2>& __y)
1643 switch(__x._M_index << 2 | __y._M_index)
1648 return __x._M_it == __y._M_it;
1650 return __x._M_it == __y._M_sent;
1652 return __x._M_sent == __y._M_it;
1654 __glibcxx_assert(__x._M_has_value());
1655 __glibcxx_assert(__y._M_has_value());
1656 __builtin_unreachable();
1660 template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
1661 requires sized_sentinel_for<_Sent, _It2>
1662 friend iter_difference_t<_It2>
1664 const common_iterator<_It2, _Sent2>& __y)
1666 switch(__x._M_index << 2 | __y._M_index)
1671 return __x._M_it - __y._M_it;
1673 return __x._M_it - __y._M_sent;
1675 return __x._M_sent - __y._M_it;
1677 __glibcxx_assert(__x._M_has_value());
1678 __glibcxx_assert(__y._M_has_value());
1679 __builtin_unreachable();
1683 friend iter_rvalue_reference_t<_It>
1684 iter_move(
const common_iterator& __i)
1685 noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
1686 requires input_iterator<_It>
1688 __glibcxx_assert(__i._M_index == 0);
1689 return ranges::iter_move(__i._M_it);
1692 template<indirectly_swappable<_It> _It2,
typename _Sent2>
1694 iter_swap(
const common_iterator& __x,
1695 const common_iterator<_It2, _Sent2>& __y)
1696 noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
1697 std::declval<const _It2&>())))
1699 __glibcxx_assert(__x._M_index == 0);
1700 __glibcxx_assert(__y._M_index == 0);
1701 return ranges::iter_swap(__x._M_it, __y._M_it);
1705 template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
1706 friend class common_iterator;
1708 bool _M_has_value() const noexcept {
return _M_index < 2; }
1714 unsigned char _M_valueless;
1716 unsigned char _M_index;
1719 template<
typename _It,
typename _Sent>
1720 struct incrementable_traits<common_iterator<_It, _Sent>>
1722 using difference_type = iter_difference_t<_It>;
1728 template<
typename _Iter>
1729 struct __common_iter_ptr
1734 template<
typename _Iter>
1735 requires __detail::__common_iter_has_arrow<_Iter>
1736 struct __common_iter_ptr<_Iter>
1738 using type = decltype(std::declval<const _Iter&>().operator->());
1742 template<input_iterator _It,
typename _Sent>
1743 struct iterator_traits<common_iterator<_It, _Sent>>
1745 using iterator_concept = conditional_t<forward_iterator<_It>,
1746 forward_iterator_tag, input_iterator_tag>;
1747 using iterator_category = __detail::__clamp_iter_cat<
1748 typename iterator_traits<_It>::iterator_category,
1749 forward_iterator_tag, input_iterator_tag>;
1750 using value_type = iter_value_t<_It>;
1751 using difference_type = iter_difference_t<_It>;
1752 using pointer =
typename
1753 __detail::__common_iter_ptr<common_iterator<_It, _Sent>>::type;
1754 using reference = iter_reference_t<_It>;
1760 template<input_or_output_iterator _It>
1761 class counted_iterator
1764 using iterator_type = _It;
1766 constexpr counted_iterator() =
default;
1769 counted_iterator(_It __i, iter_difference_t<_It> __n)
1770 : _M_current(__i), _M_length(__n)
1771 { __glibcxx_assert(__n >= 0); }
1773 template<
typename _It2>
1774 requires convertible_to<const _It2&, _It>
1776 counted_iterator(
const counted_iterator<_It2>& __x)
1777 : _M_current(__x._M_current), _M_length(__x._M_length)
1780 template<
typename _It2>
1781 requires assignable_from<_It&, const _It2&>
1782 constexpr counted_iterator&
1783 operator=(
const counted_iterator<_It2>& __x)
1785 _M_current = __x._M_current;
1786 _M_length = __x._M_length;
1792 noexcept(is_nothrow_copy_constructible_v<_It>)
1793 requires copy_constructible<_It>
1794 {
return _M_current; }
1798 noexcept(is_nothrow_move_constructible_v<_It>)
1801 constexpr iter_difference_t<_It>
1802 count() const noexcept {
return _M_length; }
1804 constexpr decltype(
auto)
1806 noexcept(noexcept(*_M_current))
1807 {
return *_M_current; }
1809 constexpr decltype(
auto)
1811 noexcept(noexcept(*_M_current))
1812 requires __detail::__dereferenceable<const _It>
1813 {
return *_M_current; }
1815 constexpr counted_iterator&
1818 __glibcxx_assert(_M_length > 0);
1827 __glibcxx_assert(_M_length > 0);
1831 return _M_current++;
1839 constexpr counted_iterator
1840 operator++(
int) requires forward_iterator<_It>
1847 constexpr counted_iterator&
1848 operator--() requires bidirectional_iterator<_It>
1855 constexpr counted_iterator
1856 operator--(
int) requires bidirectional_iterator<_It>
1863 constexpr counted_iterator
1864 operator+(iter_difference_t<_It> __n)
const
1865 requires random_access_iterator<_It>
1866 {
return counted_iterator(_M_current + __n, _M_length - __n); }
1868 friend constexpr counted_iterator
1869 operator+(iter_difference_t<_It> __n,
const counted_iterator& __x)
1870 requires random_access_iterator<_It>
1871 {
return __x + __n; }
1873 constexpr counted_iterator&
1874 operator+=(iter_difference_t<_It> __n)
1875 requires random_access_iterator<_It>
1877 __glibcxx_assert(__n <= _M_length);
1883 constexpr counted_iterator
1884 operator-(iter_difference_t<_It> __n)
const
1885 requires random_access_iterator<_It>
1886 {
return counted_iterator(_M_current - __n, _M_length + __n); }
1888 template<common_with<_It> _It2>
1889 friend constexpr iter_difference_t<_It2>
1891 const counted_iterator<_It2>& __y)
1892 {
return __y._M_length - __x._M_length; }
1894 friend constexpr iter_difference_t<_It>
1895 operator-(
const counted_iterator& __x, default_sentinel_t)
1896 {
return -__x._M_length; }
1898 friend constexpr iter_difference_t<_It>
1899 operator-(default_sentinel_t,
const counted_iterator& __y)
1900 {
return __y._M_length; }
1902 constexpr counted_iterator&
1903 operator-=(iter_difference_t<_It> __n)
1904 requires random_access_iterator<_It>
1906 __glibcxx_assert(-__n <= _M_length);
1912 constexpr decltype(
auto)
1913 operator[](iter_difference_t<_It> __n) const
1914 noexcept(noexcept(_M_current[__n]))
1915 requires random_access_iterator<_It>
1917 __glibcxx_assert(__n < _M_length);
1918 return _M_current[__n];
1921 template<common_with<_It> _It2>
1922 friend constexpr
bool
1923 operator==(
const counted_iterator& __x,
1924 const counted_iterator<_It2>& __y)
1925 {
return __x._M_length == __y._M_length; }
1927 friend constexpr
bool
1928 operator==(
const counted_iterator& __x, default_sentinel_t)
1929 {
return __x._M_length == 0; }
1931 template<common_with<_It> _It2>
1932 friend constexpr strong_ordering
1933 operator<=>(
const counted_iterator& __x,
1934 const counted_iterator<_It2>& __y)
1935 {
return __y._M_length <=> __x._M_length; }
1937 friend constexpr iter_rvalue_reference_t<_It>
1938 iter_move(
const counted_iterator& __i)
1939 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1940 requires input_iterator<_It>
1941 {
return ranges::iter_move(__i._M_current); }
1943 template<indirectly_swappable<_It> _It2>
1944 friend constexpr
void
1945 iter_swap(
const counted_iterator& __x,
1946 const counted_iterator<_It2>& __y)
1947 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1948 { ranges::iter_swap(__x._M_current, __y._M_current); }
1951 template<input_or_output_iterator _It2>
friend class counted_iterator;
1953 _It _M_current = _It();
1954 iter_difference_t<_It> _M_length = 0;
1957 template<
typename _It>
1958 struct incrementable_traits<counted_iterator<_It>>
1960 using difference_type = iter_difference_t<_It>;
1963 template<input_iterator _It>
1964 struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
1966 using pointer = void;
1972 template<
typename _Iterator>
1974 __niter_base(move_iterator<_Iterator> __it)
1975 -> decltype(make_move_iterator(__niter_base(__it.base())))
1976 {
return make_move_iterator(__niter_base(__it.base())); }
1978 template<
typename _Iterator>
1979 struct __is_move_iterator<move_iterator<_Iterator> >
1981 enum { __value = 1 };
1982 typedef __true_type __type;
1985 template<
typename _Iterator>
1987 __miter_base(move_iterator<_Iterator> __it)
1988 -> decltype(__miter_base(__it.base()))
1989 {
return __miter_base(__it.base()); }
1991 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
1992 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
1993 std::__make_move_if_noexcept_iterator(_Iter)
1995 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
1996 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
1999 #if __cpp_deduction_guides >= 201606
2002 template<
typename _InputIterator>
2004 typename iterator_traits<_InputIterator>::value_type::first_type>;
2006 template<
typename _InputIterator>
2007 using __iter_val_t =
2008 typename iterator_traits<_InputIterator>::value_type::second_type;
2010 template<
typename _T1,
typename _T2>
2013 template<
typename _InputIterator>
2014 using __iter_to_alloc_t =
2015 pair<add_const_t<__iter_key_t<_InputIterator>>,
2016 __iter_val_t<_InputIterator>>;
2017 #endif // __cpp_deduction_guides
2019 _GLIBCXX_END_NAMESPACE_VERSION
2022 #ifdef _GLIBCXX_DEBUG