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::__range_iter_t;
97 template<
typename _Tp>
101 if constexpr (is_array_v<remove_reference_t<_Tp>>)
103 else if constexpr (__member_begin<_Tp>)
110 template<__maybe_borrowed_range _Tp>
114 operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
116 if constexpr (is_array_v<remove_reference_t<_Tp>>)
118 static_assert(is_lvalue_reference_v<_Tp>);
121 else if constexpr (__member_begin<_Tp>)
128 template<
typename _Tp>
129 concept __member_end = requires(_Tp& __t)
131 { __decay_copy(__t.end()) } -> sentinel_for<__range_iter_t<_Tp>>;
135 void end(
auto&) =
delete;
136 void end(
const auto&) =
delete;
138 template<
typename _Tp>
139 concept __adl_end = __class_or_enum<remove_reference_t<_Tp>>
140 && requires(_Tp& __t)
142 { __decay_copy(
end(__t)) } -> sentinel_for<__range_iter_t<_Tp>>;
148 template<
typename _Tp>
149 static constexpr
bool
152 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
154 else if constexpr (__member_end<_Tp>)
161 template<__maybe_borrowed_range _Tp>
163 || __member_end<_Tp> || __adl_end<_Tp>
165 operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
167 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
169 static_assert(is_lvalue_reference_v<_Tp>);
170 return __t + extent_v<remove_reference_t<_Tp>>;
172 else if constexpr (__member_end<_Tp>)
180 template<
typename _To,
typename _Tp>
181 constexpr decltype(
auto)
182 __as_const(_Tp& __t) noexcept
184 static_assert(std::is_same_v<_To&, _Tp&>);
186 if constexpr (is_lvalue_reference_v<_To>)
187 return const_cast<const _Tp&
>(__t);
189 return static_cast<const _Tp&&
>(__t);
194 template<
typename _Tp>
196 operator()(_Tp&& __e)
const
197 noexcept(noexcept(_Begin{}(__cust_access::__as_const<_Tp>(__e))))
198 requires requires { _Begin{}(__cust_access::__as_const<_Tp>(__e)); }
200 return _Begin{}(__cust_access::__as_const<_Tp>(__e));
206 template<
typename _Tp>
208 operator()(_Tp&& __e)
const
209 noexcept(noexcept(_End{}(__cust_access::__as_const<_Tp>(__e))))
210 requires requires { _End{}(__cust_access::__as_const<_Tp>(__e)); }
212 return _End{}(__cust_access::__as_const<_Tp>(__e));
216 template<
typename _Tp>
217 concept __member_rbegin = requires(_Tp& __t)
219 { __decay_copy(__t.rbegin()) } -> input_or_output_iterator;
222 void rbegin(
auto&) =
delete;
223 void rbegin(
const auto&) =
delete;
225 template<
typename _Tp>
226 concept __adl_rbegin = __class_or_enum<remove_reference_t<_Tp>>
227 && requires(_Tp& __t)
229 { __decay_copy(
rbegin(__t)) } -> input_or_output_iterator;
232 template<
typename _Tp>
233 concept __reversable = requires(_Tp& __t)
235 { _Begin{}(__t) } -> bidirectional_iterator;
236 { _End{}(__t) } -> same_as<decltype(_Begin{}(__t))>;
242 template<
typename _Tp>
243 static constexpr
bool
246 if constexpr (__member_rbegin<_Tp>)
247 return noexcept(__decay_copy(std::declval<_Tp&>().
rbegin()));
248 else if constexpr (__adl_rbegin<_Tp>)
249 return noexcept(__decay_copy(
rbegin(std::declval<_Tp&>())));
252 if constexpr (noexcept(_End{}(std::declval<_Tp&>())))
254 using _It = decltype(_End{}(std::declval<_Tp&>()));
256 return is_nothrow_copy_constructible_v<_It>;
264 template<__maybe_borrowed_range _Tp>
265 requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp>
267 operator()(_Tp&& __t)
const
268 noexcept(_S_noexcept<_Tp&>())
270 if constexpr (__member_rbegin<_Tp>)
272 else if constexpr (__adl_rbegin<_Tp>)
279 template<
typename _Tp>
280 concept __member_rend = requires(_Tp& __t)
282 { __decay_copy(__t.rend()) }
283 -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>;
286 void rend(
auto&) =
delete;
287 void rend(
const auto&) =
delete;
289 template<
typename _Tp>
290 concept __adl_rend = __class_or_enum<remove_reference_t<_Tp>>
291 && requires(_Tp& __t)
293 { __decay_copy(
rend(__t)) }
294 -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>;
300 template<
typename _Tp>
301 static constexpr
bool
304 if constexpr (__member_rend<_Tp>)
305 return noexcept(__decay_copy(std::declval<_Tp&>().
rend()));
306 else if constexpr (__adl_rend<_Tp>)
307 return noexcept(__decay_copy(
rend(std::declval<_Tp&>())));
310 if constexpr (noexcept(_Begin{}(std::declval<_Tp&>())))
312 using _It = decltype(_Begin{}(std::declval<_Tp&>()));
314 return is_nothrow_copy_constructible_v<_It>;
322 template<__maybe_borrowed_range _Tp>
323 requires __member_rend<_Tp> || __adl_rend<_Tp> || __reversable<_Tp>
325 operator()(_Tp&& __t)
const
326 noexcept(_S_noexcept<_Tp&>())
328 if constexpr (__member_rend<_Tp>)
330 else if constexpr (__adl_rend<_Tp>)
339 template<
typename _Tp>
341 operator()(_Tp&& __e)
const
342 noexcept(noexcept(_RBegin{}(__cust_access::__as_const<_Tp>(__e))))
343 requires requires { _RBegin{}(__cust_access::__as_const<_Tp>(__e)); }
345 return _RBegin{}(__cust_access::__as_const<_Tp>(__e));
351 template<
typename _Tp>
353 operator()(_Tp&& __e)
const
354 noexcept(noexcept(_REnd{}(__cust_access::__as_const<_Tp>(__e))))
355 requires requires { _REnd{}(__cust_access::__as_const<_Tp>(__e)); }
357 return _REnd{}(__cust_access::__as_const<_Tp>(__e));
361 template<
typename _Tp>
362 concept __member_size = !disable_sized_range<remove_cvref_t<_Tp>>
363 && requires(_Tp& __t)
365 { __decay_copy(__t.size()) } -> __detail::__is_integer_like;
368 void size(
auto&) =
delete;
369 void size(
const auto&) =
delete;
371 template<
typename _Tp>
372 concept __adl_size = __class_or_enum<remove_reference_t<_Tp>>
373 && !disable_sized_range<remove_cvref_t<_Tp>>
374 && requires(_Tp& __t)
376 { __decay_copy(
size(__t)) } -> __detail::__is_integer_like;
379 template<
typename _Tp>
380 concept __sentinel_size = requires(_Tp& __t)
382 { _Begin{}(__t) } -> forward_iterator;
384 { _End{}(__t) } -> sized_sentinel_for<decltype(_Begin{}(__t))>;
386 __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
392 template<
typename _Tp>
393 static constexpr
bool
396 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
398 else if constexpr (__member_size<_Tp>)
400 else if constexpr (__adl_size<_Tp>)
402 else if constexpr (__sentinel_size<_Tp>)
403 return noexcept(_End{}(std::declval<_Tp&>())
404 - _Begin{}(std::declval<_Tp&>()));
408 template<
typename _Tp>
409 requires is_bounded_array_v<remove_reference_t<_Tp>>
410 || __member_size<_Tp> || __adl_size<_Tp> || __sentinel_size<_Tp>
412 operator()(_Tp&& __t)
const noexcept(_S_noexcept<_Tp&>())
414 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
416 else if constexpr (__member_size<_Tp>)
418 else if constexpr (__adl_size<_Tp>)
420 else if constexpr (__sentinel_size<_Tp>)
421 return __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
429 template<
typename _Tp>
430 requires requires (_Tp& __t) { _Size{}(__t); }
432 operator()(_Tp&& __t)
const noexcept(noexcept(_Size{}(__t)))
434 auto __size = _Size{}(__t);
435 using __size_type = decltype(__size);
437 if constexpr (integral<__size_type>)
440 if constexpr (__int_traits<__size_type>::__digits
441 < __int_traits<ptrdiff_t>::__digits)
442 return static_cast<ptrdiff_t
>(__size);
444 return static_cast<make_signed_t<__size_type>
>(__size);
446 #if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
448 else if constexpr (__detail::__is_int128<__size_type>)
449 return static_cast<__int128
>(__size);
452 return __detail::__max_diff_type(__size);
456 template<
typename _Tp>
457 concept __member_empty = requires(_Tp& __t) { bool(__t.empty()); };
459 template<
typename _Tp>
460 concept __size0_empty = requires(_Tp& __t) { _Size{}(__t) == 0; };
462 template<
typename _Tp>
463 concept __eq_iter_empty = requires(_Tp& __t)
465 { _Begin{}(__t) } -> forward_iterator;
467 bool(_Begin{}(__t) == _End{}(__t));
473 template<
typename _Tp>
474 static constexpr
bool
477 if constexpr (__member_empty<_Tp>)
478 return noexcept(
bool(std::declval<_Tp&>().
empty()));
479 else if constexpr (__size0_empty<_Tp>)
480 return noexcept(_Size{}(std::declval<_Tp&>()) == 0);
482 return noexcept(
bool(_Begin{}(std::declval<_Tp&>())
483 == _End{}(std::declval<_Tp&>())));
487 template<
typename _Tp>
488 requires __member_empty<_Tp> || __size0_empty<_Tp>
489 || __eq_iter_empty<_Tp>
491 operator()(_Tp&& __t)
const noexcept(_S_noexcept<_Tp&>())
493 if constexpr (__member_empty<_Tp>)
494 return bool(__t.empty());
495 else if constexpr (__size0_empty<_Tp>)
496 return _Size{}(__t) == 0;
498 return bool(_Begin{}(__t) == _End{}(__t));
502 template<
typename _Tp>
503 concept __pointer_to_object = is_pointer_v<_Tp>
504 && is_object_v<remove_pointer_t<_Tp>>;
506 template<
typename _Tp>
507 concept __member_data = requires(_Tp& __t)
509 { __decay_copy(__t.data()) } -> __pointer_to_object;
512 template<
typename _Tp>
513 concept __begin_data = contiguous_iterator<__range_iter_t<_Tp>>;
518 template<
typename _Tp>
519 static constexpr
bool
522 if constexpr (__member_data<_Tp>)
523 return noexcept(__decay_copy(std::declval<_Tp&>().
data()));
525 return noexcept(_Begin{}(std::declval<_Tp&>()));
529 template<__maybe_borrowed_range _Tp>
530 requires __member_data<_Tp> || __begin_data<_Tp>
532 operator()(_Tp&& __t)
const noexcept(_S_noexcept<_Tp>())
534 if constexpr (__member_data<_Tp>)
537 return std::to_address(_Begin{}(__t));
543 template<
typename _Tp>
545 operator()(_Tp&& __e)
const
546 noexcept(noexcept(_Data{}(__cust_access::__as_const<_Tp>(__e))))
547 requires requires { _Data{}(__cust_access::__as_const<_Tp>(__e)); }
549 return _Data{}(__cust_access::__as_const<_Tp>(__e));
555 inline namespace __cust
557 inline constexpr __cust_access::_Begin
begin{};
558 inline constexpr __cust_access::_End
end{};
559 inline constexpr __cust_access::_CBegin
cbegin{};
560 inline constexpr __cust_access::_CEnd
cend{};
561 inline constexpr __cust_access::_RBegin
rbegin{};
562 inline constexpr __cust_access::_REnd
rend{};
563 inline constexpr __cust_access::_CRBegin
crbegin{};
564 inline constexpr __cust_access::_CREnd
crend{};
565 inline constexpr __cust_access::_Size
size{};
566 inline constexpr __cust_access::_SSize ssize{};
567 inline constexpr __cust_access::_Empty
empty{};
568 inline constexpr __cust_access::_Data
data{};
569 inline constexpr __cust_access::_CData cdata{};
573 template<
typename _Tp>
574 concept range = requires(_Tp& __t)
581 template<
typename _Tp>
582 concept borrowed_range
583 = range<_Tp> && __detail::__maybe_borrowed_range<_Tp>;
585 template<
typename _Tp>
586 using iterator_t = std::__detail::__range_iter_t<_Tp>;
588 template<range _Range>
589 using sentinel_t = decltype(
ranges::end(std::declval<_Range&>()));
591 template<range _Range>
592 using range_difference_t = iter_difference_t<iterator_t<_Range>>;
594 template<range _Range>
595 using range_value_t = iter_value_t<iterator_t<_Range>>;
597 template<range _Range>
598 using range_reference_t = iter_reference_t<iterator_t<_Range>>;
600 template<range _Range>
601 using range_rvalue_reference_t
602 = iter_rvalue_reference_t<iterator_t<_Range>>;
605 template<
typename _Tp>
606 concept sized_range = range<_Tp>
609 template<sized_range _Range>
610 using range_size_t = decltype(
ranges::size(std::declval<_Range&>()));
613 struct view_base { };
616 template<
typename _Tp>
617 inline constexpr
bool enable_view = derived_from<_Tp, view_base>;
620 template<
typename _Tp>
622 = range<_Tp> && movable<_Tp> && enable_view<_Tp>;
627 template<
typename _Range,
typename _Tp>
629 = range<_Range> && output_iterator<iterator_t<_Range>, _Tp>;
632 template<
typename _Tp>
633 concept input_range = range<_Tp> && input_iterator<iterator_t<_Tp>>;
636 template<
typename _Tp>
637 concept forward_range
638 = input_range<_Tp> && forward_iterator<iterator_t<_Tp>>;
641 template<
typename _Tp>
642 concept bidirectional_range
643 = forward_range<_Tp> && bidirectional_iterator<iterator_t<_Tp>>;
646 template<
typename _Tp>
647 concept random_access_range
648 = bidirectional_range<_Tp> && random_access_iterator<iterator_t<_Tp>>;
651 template<
typename _Tp>
652 concept contiguous_range
653 = random_access_range<_Tp> && contiguous_iterator<iterator_t<_Tp>>
654 && requires(_Tp& __t)
656 {
ranges::data(__t) } -> same_as<add_pointer_t<range_reference_t<_Tp>>>;
660 template<
typename _Tp>
662 = range<_Tp> && same_as<iterator_t<_Tp>, sentinel_t<_Tp>>;
665 template<
typename _Tp>
666 concept viewable_range = range<_Tp>
667 && ((view<remove_cvref_t<_Tp>> && constructible_from<remove_cvref_t<_Tp>, _Tp>)
668 || (!view<remove_cvref_t<_Tp>> && borrowed_range<_Tp>));
674 template<input_or_output_iterator _It>
676 operator()(_It& __it, iter_difference_t<_It> __n)
const
678 if constexpr (random_access_iterator<_It>)
680 else if constexpr (bidirectional_iterator<_It>)
702 __glibcxx_assert(__n >= 0);
708 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
710 operator()(_It& __it, _Sent __bound)
const
712 if constexpr (assignable_from<_It&, _Sent>)
714 else if constexpr (sized_sentinel_for<_Sent, _It>)
715 (*this)(__it, __bound - __it);
718 while (__it != __bound)
723 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
724 constexpr iter_difference_t<_It>
725 operator()(_It& __it, iter_difference_t<_It> __n, _Sent __bound)
const
727 if constexpr (sized_sentinel_for<_Sent, _It>)
729 const auto __diff = __bound - __it;
733 else if (__diff > 0 ? __n >= __diff : __n <= __diff)
735 (*this)(__it, __bound);
738 else if (__n != 0) [[likely]]
741 __glibcxx_assert(__n < 0 == __diff < 0);
749 else if (__it == __bound || __n == 0)
753 iter_difference_t<_It> __m = 0;
759 while (__m != __n && __it != __bound);
762 else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>)
764 iter_difference_t<_It> __m = 0;
770 while (__m != __n && __it != __bound);
776 __glibcxx_assert(__n >= 0);
782 inline constexpr __advance_fn
advance{};
786 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
787 constexpr iter_difference_t<_It>
788 operator()(_It __first, _Sent __last)
const
790 if constexpr (sized_sentinel_for<_Sent, _It>)
791 return __last - __first;
794 iter_difference_t<_It> __n = 0;
795 while (__first != __last)
804 template<range _Range>
805 constexpr range_difference_t<_Range>
806 operator()(_Range&& __r)
const
808 if constexpr (sized_range<_Range>)
809 return static_cast<range_difference_t<_Range>
>(
ranges::size(__r));
815 inline constexpr __distance_fn
distance{};
819 template<input_or_output_iterator _It>
821 operator()(_It __x)
const
827 template<input_or_output_iterator _It>
829 operator()(_It __x, iter_difference_t<_It> __n)
const
835 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
837 operator()(_It __x, _Sent __bound)
const
843 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
845 operator()(_It __x, iter_difference_t<_It> __n, _Sent __bound)
const
852 inline constexpr __next_fn next{};
856 template<b
idirectional_iterator _It>
858 operator()(_It __x)
const
864 template<b
idirectional_iterator _It>
866 operator()(_It __x, iter_difference_t<_It> __n)
const
872 template<b
idirectional_iterator _It>
874 operator()(_It __x, iter_difference_t<_It> __n, _It __bound)
const
881 inline constexpr __prev_fn prev{};
886 constexpr dangling() noexcept = default;
887 template<typename... _Args>
888 constexpr dangling(_Args&&...) noexcept { }
891 template<range _Range>
892 using borrowed_iterator_t = conditional_t<borrowed_range<_Range>,
897 _GLIBCXX_END_NAMESPACE_VERSION
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
auto declval() noexcept -> decltype(__declval< _Tp >(0))
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first 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 iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
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 void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
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>.