30 #ifndef _GLIBCXX_RANGES_BASE_H
31 #define _GLIBCXX_RANGES_BASE_H 1
33 #pragma GCC system_header
35 #if __cplusplus > 201703L
40 #ifdef __cpp_lib_concepts
41 namespace std _GLIBCXX_VISIBILITY(default)
43 _GLIBCXX_BEGIN_NAMESPACE_VERSION
47 inline constexpr
bool disable_sized_range =
false;
49 template<
typename _Tp>
50 inline constexpr
bool enable_borrowed_range =
false;
54 constexpr __max_size_type
55 __to_unsigned_like(__max_size_type __t) noexcept
58 constexpr __max_size_type
59 __to_unsigned_like(__max_diff_type __t) noexcept
60 {
return __max_size_type(__t); }
62 template<
integral _Tp>
64 __to_unsigned_like(_Tp __t) noexcept
65 {
return static_cast<make_unsigned_t<_Tp>
>(__t); }
67 #if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
68 constexpr
unsigned __int128
69 __to_unsigned_like(__int128 __t) noexcept
72 constexpr
unsigned __int128
73 __to_unsigned_like(
unsigned __int128 __t) noexcept
77 template<
typename _Tp>
78 using __make_unsigned_like_t
79 = decltype(__detail::__to_unsigned_like(std::declval<_Tp>()));
82 template<
typename _Tp>
83 concept __maybe_borrowed_range
84 = is_lvalue_reference_v<_Tp>
85 || enable_borrowed_range<remove_cvref_t<_Tp>>;
89 namespace __cust_access
91 using std::ranges::__detail::__maybe_borrowed_range;
92 using std::__detail::__class_or_enum;
93 using std::__detail::__decay_copy;
94 using std::__detail::__member_begin;
95 using std::__detail::__adl_begin;
100 template<
typename _Tp>
101 static constexpr
bool
104 if constexpr (is_array_v<remove_reference_t<_Tp>>)
106 else if constexpr (__member_begin<_Tp>)
107 return noexcept(__decay_copy(
std::declval<_Tp&>().
begin()));
109 return noexcept(__decay_copy(
begin(
std::declval<_Tp&>())));
113 template<__maybe_borrowed_range _Tp>
117 operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>())
119 if constexpr (is_array_v<remove_reference_t<_Tp>>)
121 static_assert(is_lvalue_reference_v<_Tp>);
122 using _Up = remove_all_extents_t<remove_reference_t<_Tp>>;
123 static_assert(
sizeof(_Up) != 0,
"not array of incomplete type");
126 else if constexpr (__member_begin<_Tp>)
133 template<
typename _Tp>
134 concept __member_end = requires(_Tp& __t)
136 { __decay_copy(__t.end()) }
137 -> sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__t)))>;
140 void end(
auto&) =
delete;
141 void end(
const auto&) =
delete;
143 template<
typename _Tp>
144 concept __adl_end = __class_or_enum<remove_reference_t<_Tp>>
145 && requires(_Tp& __t)
147 { __decay_copy(
end(__t)) }
148 -> sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__t)))>;
154 template<
typename _Tp>
155 static constexpr
bool
158 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
160 else if constexpr (__member_end<_Tp>)
161 return noexcept(__decay_copy(
std::declval<_Tp&>().
end()));
163 return noexcept(__decay_copy(
end(
std::declval<_Tp&>())));
167 template<__maybe_borrowed_range _Tp>
171 operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>())
173 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
175 static_assert(is_lvalue_reference_v<_Tp>);
176 return __t + extent_v<remove_reference_t<_Tp>>;
178 else if constexpr (__member_end<_Tp>)
185 template<
typename _Tp>
186 constexpr decltype(
auto)
187 __as_const(_Tp&& __t) noexcept
189 if constexpr (is_lvalue_reference_v<_Tp>)
190 return static_cast<const remove_reference_t<_Tp>&
>(__t);
192 return static_cast<const _Tp&&
>(__t);
197 template<
typename _Tp>
199 operator()(_Tp&& __e)
const
200 noexcept(noexcept(_Begin{}(__cust_access::__as_const((_Tp&&)__e))))
201 requires requires { _Begin{}(__cust_access::__as_const((_Tp&&)__e)); }
203 return _Begin{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
209 template<
typename _Tp>
211 operator()(_Tp&& __e)
const
212 noexcept(noexcept(_End{}(__cust_access::__as_const((_Tp&&)__e))))
213 requires requires { _End{}(__cust_access::__as_const((_Tp&&)__e)); }
215 return _End{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
219 template<
typename _Tp>
220 concept __member_rbegin = requires(_Tp& __t)
222 { __decay_copy(__t.rbegin()) } -> input_or_output_iterator;
225 void rbegin(
auto&) =
delete;
226 void rbegin(
const auto&) =
delete;
228 template<
typename _Tp>
229 concept __adl_rbegin = __class_or_enum<remove_reference_t<_Tp>>
230 && requires(_Tp& __t)
232 { __decay_copy(
rbegin(__t)) } -> input_or_output_iterator;
235 template<
typename _Tp>
236 concept __reversable = requires(_Tp& __t)
238 { _Begin{}(__t) } -> bidirectional_iterator;
239 { _End{}(__t) } -> same_as<decltype(_Begin{}(__t))>;
245 template<
typename _Tp>
246 static constexpr
bool
249 if constexpr (__member_rbegin<_Tp>)
250 return noexcept(__decay_copy(std::declval<_Tp&>().
rbegin()));
251 else if constexpr (__adl_rbegin<_Tp>)
252 return noexcept(__decay_copy(
rbegin(std::declval<_Tp&>())));
255 if constexpr (noexcept(_End{}(std::declval<_Tp&>())))
257 using _It = decltype(_End{}(std::declval<_Tp&>()));
259 return is_nothrow_copy_constructible_v<_It>;
267 template<__maybe_borrowed_range _Tp>
268 requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp>
270 operator()(_Tp&& __t)
const
271 noexcept(_S_noexcept<_Tp>())
273 if constexpr (__member_rbegin<_Tp>)
275 else if constexpr (__adl_rbegin<_Tp>)
282 template<
typename _Tp>
283 concept __member_rend = requires(_Tp& __t)
285 { __decay_copy(__t.rend()) }
286 -> sentinel_for<decltype(_RBegin{}(__t))>;
289 void rend(
auto&) =
delete;
290 void rend(
const auto&) =
delete;
292 template<
typename _Tp>
293 concept __adl_rend = __class_or_enum<remove_reference_t<_Tp>>
294 && requires(_Tp& __t)
296 { __decay_copy(
rend(__t)) }
297 -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>;
303 template<
typename _Tp>
304 static constexpr
bool
307 if constexpr (__member_rend<_Tp>)
308 return noexcept(__decay_copy(std::declval<_Tp&>().
rend()));
309 else if constexpr (__adl_rend<_Tp>)
310 return noexcept(__decay_copy(
rend(std::declval<_Tp&>())));
313 if constexpr (noexcept(_Begin{}(std::declval<_Tp&>())))
315 using _It = decltype(_Begin{}(std::declval<_Tp&>()));
317 return is_nothrow_copy_constructible_v<_It>;
325 template<__maybe_borrowed_range _Tp>
326 requires __member_rend<_Tp> || __adl_rend<_Tp> || __reversable<_Tp>
328 operator()(_Tp&& __t)
const
329 noexcept(_S_noexcept<_Tp>())
331 if constexpr (__member_rend<_Tp>)
333 else if constexpr (__adl_rend<_Tp>)
342 template<
typename _Tp>
344 operator()(_Tp&& __e)
const
345 noexcept(noexcept(_RBegin{}(__cust_access::__as_const((_Tp&&)__e))))
346 requires requires { _RBegin{}(__cust_access::__as_const((_Tp&&)__e)); }
348 return _RBegin{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
354 template<
typename _Tp>
356 operator()(_Tp&& __e)
const
357 noexcept(noexcept(_REnd{}(__cust_access::__as_const((_Tp&&)__e))))
358 requires requires { _REnd{}(__cust_access::__as_const((_Tp&&)__e)); }
360 return _REnd{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
364 template<
typename _Tp>
365 concept __member_size = !disable_sized_range<remove_cvref_t<_Tp>>
366 && requires(_Tp&& __t)
368 { __decay_copy(std::forward<_Tp>(__t).
size()) }
369 -> __detail::__is_integer_like;
372 void size(
auto&) =
delete;
373 void size(
const auto&) =
delete;
375 template<
typename _Tp>
376 concept __adl_size = __class_or_enum<remove_reference_t<_Tp>>
377 && !disable_sized_range<remove_cvref_t<_Tp>>
378 && requires(_Tp&& __t)
380 { __decay_copy(
size(std::forward<_Tp>(__t))) }
381 -> __detail::__is_integer_like;
384 template<
typename _Tp>
385 concept __sentinel_size = requires(_Tp&& __t)
387 { _Begin{}(std::forward<_Tp>(__t)) } -> forward_iterator;
389 { _End{}(std::forward<_Tp>(__t)) }
390 -> sized_sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__t)))>;
396 template<
typename _Tp>
397 static constexpr
bool
400 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
402 else if constexpr (__member_size<_Tp>)
403 return noexcept(__decay_copy(
std::declval<_Tp>().
size()));
404 else if constexpr (__adl_size<_Tp>)
405 return noexcept(__decay_copy(
size(
std::declval<_Tp>())));
406 else if constexpr (__sentinel_size<_Tp>)
407 return noexcept(_End{}(std::declval<_Tp>())
408 - _Begin{}(std::declval<_Tp>()));
412 template<
typename _Tp>
413 requires is_bounded_array_v<remove_reference_t<_Tp>>
414 || __member_size<_Tp> || __adl_size<_Tp> || __sentinel_size<_Tp>
416 operator()(_Tp&& __e)
const noexcept(_S_noexcept<_Tp>())
418 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
420 return extent_v<remove_reference_t<_Tp>>;
422 else if constexpr (__member_size<_Tp>)
423 return std::forward<_Tp>(__e).size();
424 else if constexpr (__adl_size<_Tp>)
425 return size(std::forward<_Tp>(__e));
426 else if constexpr (__sentinel_size<_Tp>)
427 return __detail::__to_unsigned_like(
428 _End{}(std::forward<_Tp>(__e))
429 - _Begin{}(std::forward<_Tp>(__e)));
435 template<
typename _Tp>
436 requires requires (_Tp&& __e)
438 _Begin{}(std::forward<_Tp>(__e));
439 _Size{}(std::forward<_Tp>(__e));
442 operator()(_Tp&& __e)
const
443 noexcept(noexcept(_Size{}(std::forward<_Tp>(__e))))
445 using __iter_type = decltype(_Begin{}(std::forward<_Tp>(__e)));
446 using __diff_type = iter_difference_t<__iter_type>;
448 auto __size = _Size{}(std::forward<_Tp>(__e));
449 if constexpr (integral<__diff_type>)
451 if constexpr (__int_traits<__diff_type>::__digits
452 < __int_traits<ptrdiff_t>::__digits)
453 return static_cast<ptrdiff_t
>(__size);
455 return static_cast<__diff_type
>(__size);
459 template<
typename _Tp>
460 concept __member_empty = requires(_Tp&& __t)
461 { bool(std::forward<_Tp>(__t).
empty()); };
463 template<
typename _Tp>
464 concept __size0_empty = requires(_Tp&& __t)
465 { _Size{}(std::forward<_Tp>(__t)) == 0; };
467 template<
typename _Tp>
468 concept __eq_iter_empty = requires(_Tp&& __t)
470 { _Begin{}(std::forward<_Tp>(__t)) } -> forward_iterator;
471 bool(_Begin{}(std::forward<_Tp>(__t))
472 == _End{}(std::forward<_Tp>(__t)));
478 template<
typename _Tp>
479 static constexpr
bool
482 if constexpr (__member_empty<_Tp>)
483 return noexcept(std::declval<_Tp>().
empty());
484 else if constexpr (__size0_empty<_Tp>)
485 return noexcept(_Size{}(std::declval<_Tp>()) == 0);
487 return noexcept(
bool(_Begin{}(std::declval<_Tp>())
488 == _End{}(std::declval<_Tp>())));
492 template<
typename _Tp>
493 requires __member_empty<_Tp> || __size0_empty<_Tp>
494 || __eq_iter_empty<_Tp>
496 operator()(_Tp&& __e)
const noexcept(_S_noexcept<_Tp>())
498 if constexpr (__member_empty<_Tp>)
499 return bool(std::forward<_Tp>(__e).
empty());
500 else if constexpr (__size0_empty<_Tp>)
501 return _Size{}(std::forward<_Tp>(__e)) == 0;
503 return bool(_Begin{}(std::forward<_Tp>(__e))
504 == _End{}(std::forward<_Tp>(__e)));
508 template<
typename _Tp>
509 concept __pointer_to_object = is_pointer_v<_Tp>
510 && is_object_v<remove_pointer_t<_Tp>>;
512 template<
typename _Tp>
513 concept __member_data = is_lvalue_reference_v<_Tp>
514 && requires(_Tp __t) { { __t.data() } -> __pointer_to_object; };
516 template<
typename _Tp>
517 concept __begin_data = requires(_Tp&& __t)
518 { { _Begin{}(std::forward<_Tp>(__t)) } -> contiguous_iterator; };
523 template<
typename _Tp>
524 static constexpr
bool
527 if constexpr (__member_data<_Tp>)
528 return noexcept(__decay_copy(std::declval<_Tp>().
data()));
530 return noexcept(_Begin{}(std::declval<_Tp>()));
534 template<__maybe_borrowed_range _Tp>
535 requires __member_data<_Tp> || __begin_data<_Tp>
537 operator()(_Tp&& __e)
const noexcept(_S_noexcept<_Tp>())
539 if constexpr (__member_data<_Tp>)
542 return std::to_address(_Begin{}(std::forward<_Tp>(__e)));
548 template<
typename _Tp>
550 operator()(_Tp&& __e)
const
551 noexcept(noexcept(_Data{}(__cust_access::__as_const((_Tp&&)__e))))
552 requires requires { _Data{}(__cust_access::__as_const((_Tp&&)__e)); }
554 return _Data{}(__cust_access::__as_const(std::forward<_Tp>(__e)));
560 inline namespace __cust
562 inline constexpr __cust_access::_Begin
begin{};
563 inline constexpr __cust_access::_End
end{};
564 inline constexpr __cust_access::_CBegin
cbegin{};
565 inline constexpr __cust_access::_CEnd
cend{};
566 inline constexpr __cust_access::_RBegin
rbegin{};
567 inline constexpr __cust_access::_REnd
rend{};
568 inline constexpr __cust_access::_CRBegin
crbegin{};
569 inline constexpr __cust_access::_CREnd
crend{};
570 inline constexpr __cust_access::_Size
size{};
571 inline constexpr __cust_access::_SSize ssize{};
572 inline constexpr __cust_access::_Empty
empty{};
573 inline constexpr __cust_access::_Data
data{};
574 inline constexpr __cust_access::_CData cdata{};
578 template<
typename _Tp>
579 concept range = requires(_Tp& __t)
586 template<
typename _Tp>
587 concept borrowed_range
588 = range<_Tp> && __detail::__maybe_borrowed_range<_Tp>;
590 template<
typename _Tp>
591 using iterator_t = std::__detail::__range_iter_t<_Tp>;
593 template<range _Range>
594 using sentinel_t = decltype(
ranges::end(std::declval<_Range&>()));
596 template<range _Range>
597 using range_difference_t = iter_difference_t<iterator_t<_Range>>;
599 template<range _Range>
600 using range_value_t = iter_value_t<iterator_t<_Range>>;
602 template<range _Range>
603 using range_reference_t = iter_reference_t<iterator_t<_Range>>;
605 template<range _Range>
606 using range_rvalue_reference_t
607 = iter_rvalue_reference_t<iterator_t<_Range>>;
610 template<
typename _Tp>
611 concept sized_range = range<_Tp>
614 template<sized_range _Range>
615 using range_size_t = decltype(
ranges::size(std::declval<_Range&>()));
618 struct view_base { };
621 template<
typename _Tp>
622 inline constexpr
bool enable_view = derived_from<_Tp, view_base>;
625 template<
typename _Tp>
627 = range<_Tp> && movable<_Tp> && default_initializable<_Tp>
633 template<
typename _Range,
typename _Tp>
635 = range<_Range> && output_iterator<iterator_t<_Range>, _Tp>;
638 template<
typename _Tp>
639 concept input_range = range<_Tp> && input_iterator<iterator_t<_Tp>>;
642 template<
typename _Tp>
643 concept forward_range
644 = input_range<_Tp> && forward_iterator<iterator_t<_Tp>>;
647 template<
typename _Tp>
648 concept bidirectional_range
649 = forward_range<_Tp> && bidirectional_iterator<iterator_t<_Tp>>;
652 template<
typename _Tp>
653 concept random_access_range
654 = bidirectional_range<_Tp> && random_access_iterator<iterator_t<_Tp>>;
657 template<
typename _Tp>
658 concept contiguous_range
659 = random_access_range<_Tp> && contiguous_iterator<iterator_t<_Tp>>
660 && requires(_Tp& __t)
662 {
ranges::data(__t) } -> same_as<add_pointer_t<range_reference_t<_Tp>>>;
666 template<
typename _Tp>
668 = range<_Tp> && same_as<iterator_t<_Tp>, sentinel_t<_Tp>>;
671 template<
typename _Tp>
672 concept viewable_range = range<_Tp>
673 && (borrowed_range<_Tp> || view<remove_cvref_t<_Tp>>);
677 template<input_or_output_iterator _It>
679 advance(_It& __it, iter_difference_t<_It> __n)
681 if constexpr (random_access_iterator<_It>)
683 else if constexpr (bidirectional_iterator<_It>)
705 __glibcxx_assert(__n >= 0);
711 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
713 advance(_It& __it, _Sent __bound)
715 if constexpr (assignable_from<_It&, _Sent>)
717 else if constexpr (sized_sentinel_for<_Sent, _It>)
718 ranges::advance(__it, __bound - __it);
721 while (__it != __bound)
726 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
727 constexpr iter_difference_t<_It>
728 advance(_It& __it, iter_difference_t<_It> __n, _Sent __bound)
730 if constexpr (sized_sentinel_for<_Sent, _It>)
732 const auto __diff = __bound - __it;
733 #ifdef __cpp_lib_is_constant_evaluated
734 if (std::is_constant_evaluated()
735 && !(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0)))
736 throw "inconsistent directions for distance and bound";
739 __glibcxx_assert(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0));
740 const auto __absdiff = __diff < 0 ? -__diff : __diff;
741 const auto __absn = __n < 0 ? -__n : __n;;
742 if (__absn >= __absdiff)
744 ranges::advance(__it, __bound);
749 ranges::advance(__it, __n);
753 else if (__it == __bound || __n == 0)
754 return iter_difference_t<_It>(0);
757 iter_difference_t<_It> __m = 0;
763 while (__m != __n && __it != __bound);
766 else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>)
768 iter_difference_t<_It> __m = 0;
774 while (__m != __n && __it != __bound);
780 __glibcxx_assert(__n >= 0);
785 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
786 constexpr iter_difference_t<_It>
787 distance(_It __first, _Sent __last)
789 if constexpr (sized_sentinel_for<_Sent, _It>)
790 return __last - __first;
793 iter_difference_t<_It> __n = 0;
794 while (__first != __last)
803 template<range _Range>
804 constexpr range_difference_t<_Range>
805 distance(_Range&& __r)
807 if constexpr (sized_range<_Range>)
808 return static_cast<range_difference_t<_Range>
>(
ranges::size(__r));
813 template<input_or_output_iterator _It>
821 template<input_or_output_iterator _It>
823 next(_It __x, iter_difference_t<_It> __n)
825 ranges::advance(__x, __n);
829 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
831 next(_It __x, _Sent __bound)
833 ranges::advance(__x, __bound);
837 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
839 next(_It __x, iter_difference_t<_It> __n, _Sent __bound)
841 ranges::advance(__x, __n, __bound);
845 template<b
idirectional_iterator _It>
853 template<b
idirectional_iterator _It>
855 prev(_It __x, iter_difference_t<_It> __n)
857 ranges::advance(__x, -__n);
861 template<b
idirectional_iterator _It>
863 prev(_It __x, iter_difference_t<_It> __n, _It __bound)
865 ranges::advance(__x, -__n, __bound);
872 constexpr dangling() noexcept = default;
873 template<typename... _Args>
874 constexpr dangling(_Args&&...) noexcept { }
877 template<range _Range>
878 using borrowed_iterator_t = conditional_t<borrowed_range<_Range>,
883 _GLIBCXX_END_NAMESPACE_VERSION
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
constexpr reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
ISO C++ entities toplevel namespace is std.
constexpr auto crend(const _Container &__cont) -> decltype(std::rend(__cont))
Return a reverse iterator pointing one past the first element of the const container.
constexpr auto rend(_Container &__cont) -> decltype(__cont.rend())
Return a reverse iterator pointing one past the first element of the container.
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
constexpr auto rbegin(_Container &__cont) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
constexpr auto crbegin(const _Container &__cont) -> decltype(std::rbegin(__cont))
Return a reverse iterator pointing to the last element of the const container.
constexpr auto data(_Container &__cont) noexcept(noexcept(__cont.data())) -> decltype(__cont.data())
Return the data pointer of a container.
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.