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;
96 template<
typename _Tp>
100 if constexpr (is_array_v<remove_reference_t<_Tp>>)
102 else if constexpr (__member_begin<_Tp>)
103 return noexcept(__decay_copy(
std::declval<_Tp&>().
begin()));
105 return noexcept(__decay_copy(
begin(
std::declval<_Tp&>())));
109 template<__maybe_borrowed_range _Tp>
113 operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
115 if constexpr (is_array_v<remove_reference_t<_Tp>>)
117 static_assert(is_lvalue_reference_v<_Tp>);
120 else if constexpr (__member_begin<_Tp>)
127 template<
typename _Tp>
128 concept __member_end = requires(_Tp& __t)
130 { __decay_copy(__t.end()) }
131 -> sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__t)))>;
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)) }
143 -> sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__t)))>;
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>)
156 return noexcept(__decay_copy(
std::declval<_Tp&>().
end()));
158 return noexcept(__decay_copy(
end(
std::declval<_Tp&>())));
162 template<__maybe_borrowed_range _Tp>
164 || __member_end<_Tp> || __adl_end<_Tp>
166 operator()(_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>)
181 template<
typename _To,
typename _Tp>
182 constexpr decltype(
auto)
183 __as_const(_Tp& __t) noexcept
185 static_assert(std::is_same_v<_To&, _Tp&>);
187 if constexpr (is_lvalue_reference_v<_To>)
188 return const_cast<const _Tp&
>(__t);
190 return static_cast<const _Tp&&
>(__t);
195 template<
typename _Tp>
197 operator()(_Tp&& __e)
const 198 noexcept(noexcept(_Begin{}(__cust_access::__as_const<_Tp>(__e))))
199 requires requires { _Begin{}(__cust_access::__as_const<_Tp>(__e)); }
201 return _Begin{}(__cust_access::__as_const<_Tp>(__e));
207 template<
typename _Tp>
209 operator()(_Tp&& __e)
const 210 noexcept(noexcept(_End{}(__cust_access::__as_const<_Tp>(__e))))
211 requires requires { _End{}(__cust_access::__as_const<_Tp>(__e)); }
213 return _End{}(__cust_access::__as_const<_Tp>(__e));
217 template<
typename _Tp>
218 concept __member_rbegin = requires(_Tp& __t)
220 { __decay_copy(__t.rbegin()) } -> input_or_output_iterator;
223 void rbegin(
auto&) =
delete;
224 void rbegin(
const auto&) =
delete;
226 template<
typename _Tp>
227 concept __adl_rbegin = __class_or_enum<remove_reference_t<_Tp>>
228 && requires(_Tp& __t)
230 { __decay_copy(
rbegin(__t)) } -> input_or_output_iterator;
233 template<
typename _Tp>
234 concept __reversable = requires(_Tp& __t)
236 { _Begin{}(__t) } -> bidirectional_iterator;
237 { _End{}(__t) } -> same_as<decltype(_Begin{}(__t))>;
243 template<
typename _Tp>
244 static constexpr
bool 247 if constexpr (__member_rbegin<_Tp>)
248 return noexcept(__decay_copy(std::declval<_Tp&>().
rbegin()));
249 else if constexpr (__adl_rbegin<_Tp>)
250 return noexcept(__decay_copy(
rbegin(std::declval<_Tp&>())));
253 if constexpr (noexcept(_End{}(std::declval<_Tp&>())))
255 using _It = decltype(_End{}(std::declval<_Tp&>()));
257 return is_nothrow_copy_constructible_v<_It>;
265 template<__maybe_borrowed_range _Tp>
266 requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp>
268 operator()(_Tp&& __t)
const 269 noexcept(_S_noexcept<_Tp&>())
271 if constexpr (__member_rbegin<_Tp>)
273 else if constexpr (__adl_rbegin<_Tp>)
280 template<
typename _Tp>
281 concept __member_rend = requires(_Tp& __t)
283 { __decay_copy(__t.rend()) }
284 -> sentinel_for<decltype(_RBegin{}(__t))>;
287 void rend(
auto&) =
delete;
288 void rend(
const auto&) =
delete;
290 template<
typename _Tp>
291 concept __adl_rend = __class_or_enum<remove_reference_t<_Tp>>
292 && requires(_Tp& __t)
294 { __decay_copy(
rend(__t)) }
295 -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>;
301 template<
typename _Tp>
302 static constexpr
bool 305 if constexpr (__member_rend<_Tp>)
306 return noexcept(__decay_copy(std::declval<_Tp&>().
rend()));
307 else if constexpr (__adl_rend<_Tp>)
308 return noexcept(__decay_copy(
rend(std::declval<_Tp&>())));
311 if constexpr (noexcept(_Begin{}(std::declval<_Tp&>())))
313 using _It = decltype(_Begin{}(std::declval<_Tp&>()));
315 return is_nothrow_copy_constructible_v<_It>;
323 template<__maybe_borrowed_range _Tp>
324 requires __member_rend<_Tp> || __adl_rend<_Tp> || __reversable<_Tp>
326 operator()(_Tp&& __t)
const 327 noexcept(_S_noexcept<_Tp&>())
329 if constexpr (__member_rend<_Tp>)
331 else if constexpr (__adl_rend<_Tp>)
340 template<
typename _Tp>
342 operator()(_Tp&& __e)
const 343 noexcept(noexcept(_RBegin{}(__cust_access::__as_const<_Tp>(__e))))
344 requires requires { _RBegin{}(__cust_access::__as_const<_Tp>(__e)); }
346 return _RBegin{}(__cust_access::__as_const<_Tp>(__e));
352 template<
typename _Tp>
354 operator()(_Tp&& __e)
const 355 noexcept(noexcept(_REnd{}(__cust_access::__as_const<_Tp>(__e))))
356 requires requires { _REnd{}(__cust_access::__as_const<_Tp>(__e)); }
358 return _REnd{}(__cust_access::__as_const<_Tp>(__e));
362 template<
typename _Tp>
363 concept __member_size = !disable_sized_range<remove_cvref_t<_Tp>>
364 && requires(_Tp& __t)
366 { __decay_copy(__t.size()) } -> __detail::__is_integer_like;
369 void size(
auto&) =
delete;
370 void size(
const auto&) =
delete;
372 template<
typename _Tp>
373 concept __adl_size = __class_or_enum<remove_reference_t<_Tp>>
374 && !disable_sized_range<remove_cvref_t<_Tp>>
375 && requires(_Tp& __t)
377 { __decay_copy(
size(__t)) } -> __detail::__is_integer_like;
380 template<
typename _Tp>
381 concept __sentinel_size = requires(_Tp& __t)
383 { _Begin{}(__t) } -> forward_iterator;
385 { _End{}(__t) } -> sized_sentinel_for<decltype(_Begin{}(__t))>;
387 __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
393 template<
typename _Tp>
394 static constexpr
bool 397 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
399 else if constexpr (__member_size<_Tp>)
400 return noexcept(__decay_copy(
std::declval<_Tp&>().
size()));
401 else if constexpr (__adl_size<_Tp>)
402 return noexcept(__decay_copy(
size(
std::declval<_Tp&>())));
403 else if constexpr (__sentinel_size<_Tp>)
404 return noexcept(_End{}(std::declval<_Tp&>())
405 - _Begin{}(std::declval<_Tp&>()));
409 template<
typename _Tp>
410 requires is_bounded_array_v<remove_reference_t<_Tp>>
411 || __member_size<_Tp> || __adl_size<_Tp> || __sentinel_size<_Tp>
413 operator()(_Tp&& __t)
const noexcept(_S_noexcept<_Tp&>())
415 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
417 else if constexpr (__member_size<_Tp>)
419 else if constexpr (__adl_size<_Tp>)
421 else if constexpr (__sentinel_size<_Tp>)
422 return __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
430 template<
typename _Tp>
431 requires requires (_Tp& __t) { _Size{}(__t); }
433 operator()(_Tp&& __t)
const noexcept(noexcept(_Size{}(__t)))
435 auto __size = _Size{}(__t);
436 using __size_type = decltype(__size);
438 if constexpr (integral<__size_type>)
441 if constexpr (__int_traits<__size_type>::__digits
442 < __int_traits<ptrdiff_t>::__digits)
443 return static_cast<ptrdiff_t
>(__size);
445 return static_cast<make_signed_t<__size_type>
>(__size);
447 #if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__ 449 else if constexpr (__detail::__is_int128<__size_type>)
450 return static_cast<__int128
>(__size);
453 return __detail::__max_diff_type(__size);
457 template<
typename _Tp>
458 concept __member_empty = requires(_Tp& __t) { bool(__t.empty()); };
460 template<
typename _Tp>
461 concept __size0_empty = requires(_Tp& __t) { _Size{}(__t) == 0; };
463 template<
typename _Tp>
464 concept __eq_iter_empty = requires(_Tp& __t)
466 { _Begin{}(__t) } -> forward_iterator;
468 bool(_Begin{}(__t) == _End{}(__t));
474 template<
typename _Tp>
475 static constexpr
bool 478 if constexpr (__member_empty<_Tp>)
479 return noexcept(std::declval<_Tp&>().
empty());
480 else if constexpr (__size0_empty<_Tp>)
481 return noexcept(_Size{}(std::declval<_Tp&>()) == 0);
483 return noexcept(
bool(_Begin{}(std::declval<_Tp&>())
484 == _End{}(std::declval<_Tp&>())));
488 template<
typename _Tp>
489 requires __member_empty<_Tp> || __size0_empty<_Tp>
490 || __eq_iter_empty<_Tp>
492 operator()(_Tp&& __t)
const noexcept(_S_noexcept<_Tp&>())
494 if constexpr (__member_empty<_Tp>)
495 return bool(__t.empty());
496 else if constexpr (__size0_empty<_Tp>)
497 return _Size{}(__t) == 0;
499 return bool(_Begin{}(__t) == _End{}(__t));
503 template<
typename _Tp>
504 concept __pointer_to_object = is_pointer_v<_Tp>
505 && is_object_v<remove_pointer_t<_Tp>>;
507 template<
typename _Tp>
508 concept __member_data = requires(_Tp& __t)
510 { __cust_access::__decay_copy(__t.data()) } -> __pointer_to_object;
513 template<
typename _Tp>
514 concept __begin_data = requires(_Tp& __t)
515 { { _Begin{}(__t) } -> contiguous_iterator; };
520 template<
typename _Tp>
521 static constexpr
bool 524 if constexpr (__member_data<_Tp>)
525 return noexcept(__decay_copy(std::declval<_Tp&>().
data()));
527 return noexcept(_Begin{}(std::declval<_Tp&>()));
531 template<__maybe_borrowed_range _Tp>
532 requires __member_data<_Tp> || __begin_data<_Tp>
534 operator()(_Tp&& __t)
const noexcept(_S_noexcept<_Tp>())
536 if constexpr (__member_data<_Tp>)
539 return std::to_address(_Begin{}(__t));
545 template<
typename _Tp>
547 operator()(_Tp&& __e)
const 548 noexcept(noexcept(_Data{}(__cust_access::__as_const<_Tp>(__e))))
549 requires requires { _Data{}(__cust_access::__as_const<_Tp>(__e)); }
551 return _Data{}(__cust_access::__as_const<_Tp>(__e));
557 inline namespace __cust
559 inline constexpr __cust_access::_Begin
begin{};
560 inline constexpr __cust_access::_End
end{};
561 inline constexpr __cust_access::_CBegin
cbegin{};
562 inline constexpr __cust_access::_CEnd
cend{};
563 inline constexpr __cust_access::_RBegin
rbegin{};
564 inline constexpr __cust_access::_REnd
rend{};
565 inline constexpr __cust_access::_CRBegin
crbegin{};
566 inline constexpr __cust_access::_CREnd
crend{};
567 inline constexpr __cust_access::_Size
size{};
568 inline constexpr __cust_access::_SSize ssize{};
569 inline constexpr __cust_access::_Empty
empty{};
570 inline constexpr __cust_access::_Data
data{};
571 inline constexpr __cust_access::_CData cdata{};
575 template<
typename _Tp>
576 concept range = requires(_Tp& __t)
583 template<
typename _Tp>
584 concept borrowed_range
585 = range<_Tp> && __detail::__maybe_borrowed_range<_Tp>;
587 template<
typename _Tp>
588 using iterator_t = std::__detail::__range_iter_t<_Tp>;
590 template<range _Range>
591 using sentinel_t = decltype(
ranges::end(std::declval<_Range&>()));
593 template<range _Range>
594 using range_difference_t = iter_difference_t<iterator_t<_Range>>;
596 template<range _Range>
597 using range_value_t = iter_value_t<iterator_t<_Range>>;
599 template<range _Range>
600 using range_reference_t = iter_reference_t<iterator_t<_Range>>;
602 template<range _Range>
603 using range_rvalue_reference_t
604 = iter_rvalue_reference_t<iterator_t<_Range>>;
607 template<
typename _Tp>
608 concept sized_range = range<_Tp>
611 template<sized_range _Range>
612 using range_size_t = decltype(
ranges::size(std::declval<_Range&>()));
615 struct view_base { };
618 template<
typename _Tp>
619 inline constexpr
bool enable_view = derived_from<_Tp, view_base>;
622 template<
typename _Tp>
624 = range<_Tp> && movable<_Tp> && default_initializable<_Tp>
630 template<
typename _Range,
typename _Tp>
632 = range<_Range> && output_iterator<iterator_t<_Range>, _Tp>;
635 template<
typename _Tp>
636 concept input_range = range<_Tp> && input_iterator<iterator_t<_Tp>>;
639 template<
typename _Tp>
640 concept forward_range
641 = input_range<_Tp> && forward_iterator<iterator_t<_Tp>>;
644 template<
typename _Tp>
645 concept bidirectional_range
646 = forward_range<_Tp> && bidirectional_iterator<iterator_t<_Tp>>;
649 template<
typename _Tp>
650 concept random_access_range
651 = bidirectional_range<_Tp> && random_access_iterator<iterator_t<_Tp>>;
654 template<
typename _Tp>
655 concept contiguous_range
656 = random_access_range<_Tp> && contiguous_iterator<iterator_t<_Tp>>
657 && requires(_Tp& __t)
659 {
ranges::data(__t) } -> same_as<add_pointer_t<range_reference_t<_Tp>>>;
663 template<
typename _Tp>
665 = range<_Tp> && same_as<iterator_t<_Tp>, sentinel_t<_Tp>>;
668 template<
typename _Tp>
669 concept viewable_range = range<_Tp>
670 && (borrowed_range<_Tp> || view<remove_cvref_t<_Tp>>);
676 template<input_or_output_iterator _It>
678 operator()(_It& __it, iter_difference_t<_It> __n)
const 680 if constexpr (random_access_iterator<_It>)
682 else if constexpr (bidirectional_iterator<_It>)
704 __glibcxx_assert(__n >= 0);
710 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
712 operator()(_It& __it, _Sent __bound)
const 714 if constexpr (assignable_from<_It&, _Sent>)
716 else if constexpr (sized_sentinel_for<_Sent, _It>)
717 (*this)(__it, __bound - __it);
720 while (__it != __bound)
725 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
726 constexpr iter_difference_t<_It>
727 operator()(_It& __it, iter_difference_t<_It> __n, _Sent __bound)
const 729 if constexpr (sized_sentinel_for<_Sent, _It>)
731 const auto __diff = __bound - __it;
734 __glibcxx_assert(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0));
735 const auto __absdiff = __diff < 0 ? -__diff : __diff;
736 const auto __absn = __n < 0 ? -__n : __n;;
737 if (__absn >= __absdiff)
739 (*this)(__it, __bound);
748 else if (__it == __bound || __n == 0)
752 iter_difference_t<_It> __m = 0;
758 while (__m != __n && __it != __bound);
761 else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>)
763 iter_difference_t<_It> __m = 0;
769 while (__m != __n && __it != __bound);
775 __glibcxx_assert(__n >= 0);
781 inline constexpr __advance_fn advance{};
785 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
786 constexpr iter_difference_t<_It>
787 operator()(_It __first, _Sent __last)
const 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 operator()(_Range&& __r)
const 807 if constexpr (sized_range<_Range>)
808 return static_cast<range_difference_t<_Range>
>(
ranges::size(__r));
814 inline constexpr __distance_fn distance{};
818 template<input_or_output_iterator _It>
820 operator()(_It __x)
const 826 template<input_or_output_iterator _It>
828 operator()(_It __x, iter_difference_t<_It> __n)
const 830 ranges::advance(__x, __n);
834 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
836 operator()(_It __x, _Sent __bound)
const 838 ranges::advance(__x, __bound);
842 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
844 operator()(_It __x, iter_difference_t<_It> __n, _Sent __bound)
const 846 ranges::advance(__x, __n, __bound);
851 inline constexpr __next_fn next{};
855 template<b
idirectional_iterator _It>
857 operator()(_It __x)
const 863 template<b
idirectional_iterator _It>
865 operator()(_It __x, iter_difference_t<_It> __n)
const 867 ranges::advance(__x, -__n);
871 template<b
idirectional_iterator _It>
873 operator()(_It __x, iter_difference_t<_It> __n, _It __bound)
const 875 ranges::advance(__x, -__n, __bound);
880 inline constexpr __prev_fn prev{};
885 constexpr dangling() noexcept = default;
886 template<typename... _Args>
887 constexpr dangling(_Args&&...) noexcept { }
890 template<range _Range>
891 using borrowed_iterator_t = conditional_t<borrowed_range<_Range>,
896 _GLIBCXX_END_NAMESPACE_VERSION
898 #endif // library concepts 900 #endif // _GLIBCXX_RANGES_BASE_H constexpr auto crend(const _Container &__cont) -> decltype(std::rend(__cont))
Return a reverse iterator pointing one past the first element of the const container.
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
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.
constexpr auto data(_Container &__cont) noexcept(noexcept(__cont.data())) -> decltype(__cont.data())
Return the data pointer of a 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 rbegin(_Container &__cont) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
constexpr reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
ISO C++ entities toplevel namespace is std.
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.