30#ifndef _GLIBCXX_RANGES_BASE_H
31#define _GLIBCXX_RANGES_BASE_H 1
33#pragma GCC system_header
35#if __cplusplus > 201703L
41#ifdef __cpp_lib_concepts
42namespace std _GLIBCXX_VISIBILITY(default)
44_GLIBCXX_BEGIN_NAMESPACE_VERSION
48 inline constexpr bool disable_sized_range =
false;
50 template<
typename _Tp>
51 inline constexpr bool enable_borrowed_range =
false;
55 constexpr __max_size_type
56 __to_unsigned_like(__max_size_type __t)
noexcept
59 constexpr __max_size_type
60 __to_unsigned_like(__max_diff_type __t)
noexcept
61 {
return __max_size_type(__t); }
63 template<
integral _Tp>
65 __to_unsigned_like(_Tp __t)
noexcept
66 {
return static_cast<make_unsigned_t<_Tp>
>(__t); }
68#if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
69 constexpr unsigned __int128
70 __to_unsigned_like(__int128 __t)
noexcept
73 constexpr unsigned __int128
74 __to_unsigned_like(
unsigned __int128 __t)
noexcept
78 template<
typename _Tp>
79 using __make_unsigned_like_t
83 template<
typename _Tp>
84 concept __maybe_borrowed_range
85 = is_lvalue_reference_v<_Tp>
86 || enable_borrowed_range<remove_cvref_t<_Tp>>;
90 namespace __cust_access
92 using std::ranges::__detail::__maybe_borrowed_range;
93 using std::__detail::__range_iter_t;
98 template<
typename _Tp>
102 if constexpr (is_array_v<remove_reference_t<_Tp>>)
104 else if constexpr (__member_begin<_Tp>)
111 template<__maybe_borrowed_range _Tp>
112 requires is_array_v<remove_reference_t<_Tp>> || __member_begin<_Tp>
115 operator()[[nodiscard]](_Tp&& __t)
const noexcept(_S_noexcept<_Tp&>())
117 if constexpr (is_array_v<remove_reference_t<_Tp>>)
119 static_assert(is_lvalue_reference_v<_Tp>);
122 else if constexpr (__member_begin<_Tp>)
129 template<
typename _Tp>
130 concept __member_end =
requires(_Tp& __t)
132 { __decay_copy(__t.end()) } -> sentinel_for<__range_iter_t<_Tp>>;
136 void end(
auto&) =
delete;
137 void end(
const auto&) =
delete;
139 template<
typename _Tp>
140 concept __adl_end = __class_or_enum<remove_reference_t<_Tp>>
141 &&
requires(_Tp& __t)
143 { __decay_copy(end(__t)) } -> sentinel_for<__range_iter_t<_Tp>>;
149 template<
typename _Tp>
150 static constexpr bool
153 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
155 else if constexpr (__member_end<_Tp>)
162 template<__maybe_borrowed_range _Tp>
163 requires is_bounded_array_v<remove_reference_t<_Tp>>
164 || __member_end<_Tp> || __adl_end<_Tp>
166 operator()[[nodiscard]](_Tp&& __t)
const noexcept(_S_noexcept<_Tp&>())
168 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
170 static_assert(is_lvalue_reference_v<_Tp>);
171 return __t + extent_v<remove_reference_t<_Tp>>;
173 else if constexpr (__member_end<_Tp>)
180 template<
typename _Tp>
181 concept __member_rbegin =
requires(_Tp& __t)
183 { __decay_copy(__t.rbegin()) } -> input_or_output_iterator;
186 void rbegin(
auto&) =
delete;
187 void rbegin(
const auto&) =
delete;
189 template<
typename _Tp>
190 concept __adl_rbegin = __class_or_enum<remove_reference_t<_Tp>>
191 &&
requires(_Tp& __t)
193 { __decay_copy(rbegin(__t)) } -> input_or_output_iterator;
196 template<
typename _Tp>
197 concept __reversable =
requires(_Tp& __t)
199 { _Begin{}(__t) } -> bidirectional_iterator;
200 { _End{}(__t) } -> same_as<
decltype(_Begin{}(__t))>;
206 template<
typename _Tp>
207 static constexpr bool
210 if constexpr (__member_rbegin<_Tp>)
212 else if constexpr (__adl_rbegin<_Tp>)
220 return is_nothrow_copy_constructible_v<_It>;
228 template<__maybe_borrowed_range _Tp>
229 requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp>
231 operator()[[nodiscard]](_Tp&& __t)
const
232 noexcept(_S_noexcept<_Tp&>())
234 if constexpr (__member_rbegin<_Tp>)
236 else if constexpr (__adl_rbegin<_Tp>)
243 template<
typename _Tp>
244 concept __member_rend =
requires(_Tp& __t)
246 { __decay_copy(__t.rend()) }
250 void rend(
auto&) =
delete;
251 void rend(
const auto&) =
delete;
253 template<
typename _Tp>
254 concept __adl_rend = __class_or_enum<remove_reference_t<_Tp>>
255 &&
requires(_Tp& __t)
257 { __decay_copy(rend(__t)) }
264 template<
typename _Tp>
265 static constexpr bool
268 if constexpr (__member_rend<_Tp>)
270 else if constexpr (__adl_rend<_Tp>)
278 return is_nothrow_copy_constructible_v<_It>;
286 template<__maybe_borrowed_range _Tp>
287 requires __member_rend<_Tp> || __adl_rend<_Tp> || __reversable<_Tp>
289 operator()[[nodiscard]](_Tp&& __t)
const
290 noexcept(_S_noexcept<_Tp&>())
292 if constexpr (__member_rend<_Tp>)
294 else if constexpr (__adl_rend<_Tp>)
301 template<
typename _Tp>
302 concept __member_size = !disable_sized_range<remove_cvref_t<_Tp>>
303 &&
requires(_Tp& __t)
305 { __decay_copy(__t.size()) } -> __detail::__is_integer_like;
308 void size(
auto&) =
delete;
309 void size(
const auto&) =
delete;
311 template<
typename _Tp>
312 concept __adl_size = __class_or_enum<remove_reference_t<_Tp>>
313 && !disable_sized_range<remove_cvref_t<_Tp>>
314 &&
requires(_Tp& __t)
316 { __decay_copy(size(__t)) } -> __detail::__is_integer_like;
319 template<
typename _Tp>
320 concept __sentinel_size =
requires(_Tp& __t)
322 requires (!is_unbounded_array_v<remove_reference_t<_Tp>>);
324 { _Begin{}(__t) } -> forward_iterator;
326 { _End{}(__t) } -> sized_sentinel_for<
decltype(_Begin{}(__t))>;
328 __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
334 template<
typename _Tp>
335 static constexpr bool
338 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
340 else if constexpr (__member_size<_Tp>)
342 else if constexpr (__adl_size<_Tp>)
344 else if constexpr (__sentinel_size<_Tp>)
350 template<
typename _Tp>
351 requires is_bounded_array_v<remove_reference_t<_Tp>>
352 || __member_size<_Tp> || __adl_size<_Tp> || __sentinel_size<_Tp>
354 operator()[[nodiscard]](_Tp&& __t)
const noexcept(_S_noexcept<_Tp&>())
356 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
357 return extent_v<remove_reference_t<_Tp>>;
358 else if constexpr (__member_size<_Tp>)
360 else if constexpr (__adl_size<_Tp>)
362 else if constexpr (__sentinel_size<_Tp>)
363 return __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
371 template<
typename _Tp>
372 requires requires (_Tp& __t) { _Size{}(__t); }
374 operator()[[nodiscard]](_Tp&& __t)
const noexcept(
noexcept(_Size{}(__t)))
376 auto __size = _Size{}(__t);
377 using __size_type =
decltype(__size);
379 if constexpr (integral<__size_type>)
382 if constexpr (__int_traits<__size_type>::__digits
383 < __int_traits<ptrdiff_t>::__digits)
384 return static_cast<ptrdiff_t
>(__size);
386 return static_cast<make_signed_t<__size_type>
>(__size);
388#if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
390 else if constexpr (__detail::__is_int128<__size_type>)
391 return static_cast<__int128
>(__size);
394 return __detail::__max_diff_type(__size);
398 template<
typename _Tp>
399 concept __member_empty =
requires(_Tp& __t) { bool(__t.empty()); };
401 template<
typename _Tp>
402 concept __size0_empty =
requires(_Tp& __t) { _Size{}(__t) == 0; };
404 template<
typename _Tp>
405 concept __eq_iter_empty =
requires(_Tp& __t)
407 requires (!is_unbounded_array_v<remove_reference_t<_Tp>>);
409 { _Begin{}(__t) } -> forward_iterator;
411 bool(_Begin{}(__t) == _End{}(__t));
417 template<
typename _Tp>
418 static constexpr bool
421 if constexpr (__member_empty<_Tp>)
423 else if constexpr (__size0_empty<_Tp>)
431 template<
typename _Tp>
432 requires __member_empty<_Tp> || __size0_empty<_Tp>
433 || __eq_iter_empty<_Tp>
435 operator()[[nodiscard]](_Tp&& __t)
const noexcept(_S_noexcept<_Tp&>())
437 if constexpr (__member_empty<_Tp>)
438 return bool(__t.empty());
439 else if constexpr (__size0_empty<_Tp>)
440 return _Size{}(__t) == 0;
442 return bool(_Begin{}(__t) == _End{}(__t));
446 template<
typename _Tp>
447 concept __pointer_to_object = is_pointer_v<_Tp>
448 && is_object_v<remove_pointer_t<_Tp>>;
450 template<
typename _Tp>
451 concept __member_data =
requires(_Tp& __t)
453 { __decay_copy(__t.data()) } -> __pointer_to_object;
456 template<
typename _Tp>
457 concept __begin_data = contiguous_iterator<__range_iter_t<_Tp>>;
462 template<
typename _Tp>
463 static constexpr bool
466 if constexpr (__member_data<_Tp>)
473 template<__maybe_borrowed_range _Tp>
474 requires __member_data<_Tp> || __begin_data<_Tp>
476 operator()[[nodiscard]](_Tp&& __t)
const noexcept(_S_noexcept<_Tp>())
478 if constexpr (__member_data<_Tp>)
487 inline namespace __cust
489 inline constexpr __cust_access::_Begin begin{};
490 inline constexpr __cust_access::_End end{};
491 inline constexpr __cust_access::_RBegin rbegin{};
492 inline constexpr __cust_access::_REnd rend{};
493 inline constexpr __cust_access::_Size size{};
494 inline constexpr __cust_access::_SSize ssize{};
495 inline constexpr __cust_access::_Empty empty{};
496 inline constexpr __cust_access::_Data data{};
500 template<
typename _Tp>
508 template<
typename _Tp>
510 =
range<_Tp> && __detail::__maybe_borrowed_range<_Tp>;
512 template<
typename _Tp>
513 using iterator_t = std::__detail::__range_iter_t<_Tp>;
515 template<range _Range>
518#if __cplusplus > 202002L
519 template<range _Range>
520 using const_iterator_t = const_iterator<iterator_t<_Range>>;
522 template<range _Range>
523 using const_sentinel_t = const_sentinel<sentinel_t<_Range>>;
525 template<range _Range>
526 using range_const_reference_t = iter_const_reference_t<iterator_t<_Range>>;
529 template<range _Range>
530 using range_difference_t = iter_difference_t<iterator_t<_Range>>;
532 template<range _Range>
533 using range_value_t = iter_value_t<iterator_t<_Range>>;
535 template<range _Range>
536 using range_reference_t = iter_reference_t<iterator_t<_Range>>;
538 template<range _Range>
539 using range_rvalue_reference_t
540 = iter_rvalue_reference_t<iterator_t<_Range>>;
544 template<range _Range>
545 using range_common_reference_t
546 = iter_common_reference_t<iterator_t<_Range>>;
549 template<
typename _Tp>
551 &&
requires(_Tp& __t) { ranges::size(__t); };
553 template<sized_range _Range>
556 template<
typename _Derived>
562 template<
typename _Tp,
typename _Up>
564 void __is_derived_from_view_interface_fn(
const _Tp&,
569 template<
typename _Tp>
570 concept __is_derived_from_view_interface
571 =
requires (_Tp __t) { __is_derived_from_view_interface_fn(__t, __t); };
578 template<
typename _Tp>
580 || __detail::__is_derived_from_view_interface<_Tp>;
583 template<
typename _Tp>
585 =
range<_Tp> && movable<_Tp> && enable_view<_Tp>;
590 template<
typename _Range,
typename _Tp>
595 template<
typename _Tp>
599 template<
typename _Tp>
604 template<
typename _Tp>
609 template<
typename _Tp>
614 template<
typename _Tp>
617 &&
requires(_Tp& __t)
623 template<
typename _Tp>
627#if __cplusplus > 202002L
628 template<
typename _Tp>
629 concept constant_range
633 namespace __cust_access
635#if __cplusplus > 202020L
636 template<
typename _Range>
638 __possibly_const_range(_Range& __r)
noexcept
640 if constexpr (constant_range<const _Range> && !constant_range<_Range>)
641 return const_cast<const _Range&
>(__r);
647 template<
typename _To,
typename _Tp>
648 constexpr decltype(
auto)
649 __as_const(_Tp& __t)
noexcept
653 if constexpr (is_lvalue_reference_v<_To>)
654 return const_cast<const _Tp&
>(__t);
656 return static_cast<const _Tp&&
>(__t);
662#if __cplusplus > 202002L
663 template<__maybe_borrowed_range _Tp>
666 operator()(_Tp&& __t)
const
668 (ranges::begin(__cust_access::__possibly_const_range(__t)))))
670 (ranges::begin(__cust_access::__possibly_const_range(__t))); }
672 auto& __r = __cust_access::__possibly_const_range(__t);
673 return const_iterator_t<decltype(__r)>(ranges::begin(__r));
676 template<
typename _Tp>
679 operator()(_Tp&& __e)
const
680 noexcept(
noexcept(_Begin{}(__cust_access::__as_const<_Tp>(__e))))
681 requires requires { _Begin{}(__cust_access::__as_const<_Tp>(__e)); }
683 return _Begin{}(__cust_access::__as_const<_Tp>(__e));
690#if __cplusplus > 202002L
691 template<__maybe_borrowed_range _Tp>
694 operator()(_Tp&& __t)
const
696 (ranges::end(__cust_access::__possibly_const_range(__t)))))
698 (ranges::end(__cust_access::__possibly_const_range(__t))); }
700 auto& __r = __cust_access::__possibly_const_range(__t);
701 return const_sentinel_t<decltype(__r)>(ranges::end(__r));
704 template<
typename _Tp>
707 operator()(_Tp&& __e)
const
708 noexcept(
noexcept(_End{}(__cust_access::__as_const<_Tp>(__e))))
709 requires requires { _End{}(__cust_access::__as_const<_Tp>(__e)); }
711 return _End{}(__cust_access::__as_const<_Tp>(__e));
718#if __cplusplus > 202002L
719 template<__maybe_borrowed_range _Tp>
722 operator()(_Tp&& __t)
const
724 (ranges::rbegin(__cust_access::__possibly_const_range(__t)))))
726 (ranges::rbegin(__cust_access::__possibly_const_range(__t))); }
728 auto& __r = __cust_access::__possibly_const_range(__t);
729 return const_iterator<decltype(ranges::rbegin(__r))>(ranges::rbegin(__r));
732 template<
typename _Tp>
735 operator()(_Tp&& __e)
const
736 noexcept(
noexcept(_RBegin{}(__cust_access::__as_const<_Tp>(__e))))
737 requires requires { _RBegin{}(__cust_access::__as_const<_Tp>(__e)); }
739 return _RBegin{}(__cust_access::__as_const<_Tp>(__e));
746#if __cplusplus > 202002L
747 template<__maybe_borrowed_range _Tp>
750 operator()(_Tp&& __t)
const
752 (ranges::rend(__cust_access::__possibly_const_range(__t)))))
754 (ranges::rend(__cust_access::__possibly_const_range(__t))); }
756 auto& __r = __cust_access::__possibly_const_range(__t);
757 return const_sentinel<decltype(ranges::rend(__r))>(ranges::rend(__r));
760 template<
typename _Tp>
763 operator()(_Tp&& __e)
const
764 noexcept(
noexcept(_REnd{}(__cust_access::__as_const<_Tp>(__e))))
765 requires requires { _REnd{}(__cust_access::__as_const<_Tp>(__e)); }
767 return _REnd{}(__cust_access::__as_const<_Tp>(__e));
774#if __cplusplus > 202002L
775 template<__maybe_borrowed_range _Tp>
777 constexpr const auto*
778 operator()(_Tp&& __t)
const
779 noexcept(
noexcept(ranges::data(__cust_access::__possibly_const_range(__t))))
780 requires requires { ranges::data(__cust_access::__possibly_const_range(__t)); }
781 {
return ranges::data(__cust_access::__possibly_const_range(__t)); }
783 template<
typename _Tp>
786 operator()(_Tp&& __e)
const
787 noexcept(
noexcept(_Data{}(__cust_access::__as_const<_Tp>(__e))))
788 requires requires { _Data{}(__cust_access::__as_const<_Tp>(__e)); }
790 return _Data{}(__cust_access::__as_const<_Tp>(__e));
797 inline namespace __cust
799 inline constexpr __cust_access::_CBegin cbegin{};
800 inline constexpr __cust_access::_CEnd cend{};
801 inline constexpr __cust_access::_CRBegin crbegin{};
802 inline constexpr __cust_access::_CREnd crend{};
803 inline constexpr __cust_access::_CData cdata{};
808 template<
typename _Tp>
809 inline constexpr bool __is_initializer_list =
false;
811 template<
typename _Tp>
812 inline constexpr bool __is_initializer_list<initializer_list<_Tp>> =
true;
816 template<
typename _Tp>
819 || (!
view<remove_cvref_t<_Tp>>
820 && (is_lvalue_reference_v<_Tp>
821 || (movable<remove_reference_t<_Tp>>
822 && !__detail::__is_initializer_list<remove_cvref_t<_Tp>>))));
826 struct __advance_fn final
828 template<input_or_output_iterator _It>
830 operator()(_It& __it, iter_difference_t<_It> __n)
const
832 if constexpr (random_access_iterator<_It>)
834 else if constexpr (bidirectional_iterator<_It>)
856 __glibcxx_assert(__n >= 0);
862 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
864 operator()(_It& __it, _Sent __bound)
const
868 else if constexpr (sized_sentinel_for<_Sent, _It>)
869 (*
this)(__it, __bound - __it);
872 while (__it != __bound)
877 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
878 constexpr iter_difference_t<_It>
879 operator()(_It& __it, iter_difference_t<_It> __n, _Sent __bound)
const
881 if constexpr (sized_sentinel_for<_Sent, _It>)
883 const auto __diff = __bound - __it;
887 else if (__diff > 0 ? __n >= __diff : __n <= __diff)
889 (*this)(__it, __bound);
892 else if (__n != 0) [[likely]]
895 __glibcxx_assert((__n < 0) == (__diff < 0));
903 else if (__it == __bound || __n == 0)
907 iter_difference_t<_It> __m = 0;
913 while (__m != __n && __it != __bound);
918 iter_difference_t<_It> __m = 0;
924 while (__m != __n && __it != __bound);
930 __glibcxx_assert(__n >= 0);
938 inline constexpr __advance_fn advance{};
940 struct __distance_fn
final
944 template<
typename _It, sentinel_for<_It> _Sent>
947 operator()[[
nodiscard]](_It __first, _Sent __last)
const
950 while (__first != __last)
958 template<
typename _It, sized_sentinel_for<decay_t<_It>> _Sent>
960 constexpr iter_difference_t<decay_t<_It>>
961 operator()(_It&& __first, _Sent __last)
const
962 {
return __last -
static_cast<const decay_t<_It>&
>(__first); }
964 template<range _Range>
966 constexpr range_difference_t<_Range>
967 operator()(_Range&& __r)
const
969 if constexpr (sized_range<_Range>)
970 return static_cast<range_difference_t<_Range>
>(ranges::size(__r));
972 return (*
this)(ranges::begin(__r), ranges::end(__r));
978 inline constexpr __distance_fn distance{};
980 struct __next_fn final
982 template<input_or_output_iterator _It>
985 operator()(_It __x)
const
991 template<input_or_output_iterator _It>
994 operator()(_It __x, iter_difference_t<_It> __n)
const
996 ranges::advance(__x, __n);
1000 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1003 operator()(_It __x, _Sent __bound)
const
1005 ranges::advance(__x, __bound);
1009 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1012 operator()(_It __x, iter_difference_t<_It> __n, _Sent __bound)
const
1014 ranges::advance(__x, __n, __bound);
1021 inline constexpr __next_fn next{};
1023 struct __prev_fn final
1025 template<b
idirectional_iterator _It>
1028 operator()(_It __x)
const
1034 template<b
idirectional_iterator _It>
1037 operator()(_It __x, iter_difference_t<_It> __n)
const
1039 ranges::advance(__x, -__n);
1043 template<b
idirectional_iterator _It>
1046 operator()(_It __x, iter_difference_t<_It> __n, _It __bound)
const
1048 ranges::advance(__x, -__n, __bound);
1055 inline constexpr __prev_fn prev{};
1060 constexpr dangling()
noexcept =
default;
1061 template<
typename...
_Args>
1065 template<range _Range>
1071_GLIBCXX_END_NAMESPACE_VERSION
constexpr bool enable_view
[range.view] The ranges::enable_view boolean.
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
ISO C++ entities toplevel namespace is std.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
constexpr auto data(_Container &__cont) noexcept(noexcept(__cont.data())) -> decltype(__cont.data())
Return the data pointer of a container.
constexpr bitset< _Nb > operator&(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.
The ranges::view_interface class template.
[range.view] The ranges::view_base type.
Type returned by algorithms instead of a dangling iterator or subrange.
[concept.same], concept same_as
[concept.derived], concept derived_from
[concept.assignable], concept assignable_from
[concept.constructible], concept constructible_from
[range.range] The range concept.
[range.range] The borrowed_range concept.
[range.sized] The sized_range concept.
[range.view] The ranges::view concept.
A range for which ranges::begin returns an output iterator.
A range for which ranges::begin returns an input iterator.
A range for which ranges::begin returns a forward iterator.
A range for which ranges::begin returns a bidirectional iterator.
A range for which ranges::begin returns a random access iterator.
A range for which ranges::begin returns a contiguous iterator.
A range for which ranges::begin and ranges::end return the same type.
A range which can be safely converted to a view.