30 #ifndef _GLIBCXX_RANGES
31 #define _GLIBCXX_RANGES 1
33 #if __cplusplus > 201703L
35 #pragma GCC system_header
39 #if __cpp_lib_concepts
53 namespace std _GLIBCXX_VISIBILITY(default)
55 _GLIBCXX_BEGIN_NAMESPACE_VERSION
69 template<
typename _Tp>
70 concept __deep_const_range = range<_Tp> && range<const _Tp>
71 && same_as<range_reference_t<_Tp>, range_reference_t<const _Tp>>;
73 template<
typename _Tp>
74 inline constexpr
bool __enable_view_impl
75 = derived_from<_Tp, view_base> || (!__deep_const_range<_Tp>);
77 template<
typename _Tp>
78 inline constexpr
bool __enable_view_impl<std::initializer_list<_Tp>>
83 template<
typename _Tp>
84 inline constexpr
bool enable_view
85 = __detail::__enable_view_impl<remove_cv_t<_Tp>>;
87 template<
typename _Tp>
89 = range<_Tp> && movable<_Tp> && default_initializable<_Tp>
93 template<
typename _Tp>
94 concept viewable_range = range<_Tp>
95 && (safe_range<_Tp> || view<decay_t<_Tp>>);
99 template<
typename _Range>
100 concept __simple_view = view<_Range> && range<const _Range>
101 && same_as<iterator_t<_Range>, iterator_t<const _Range>>
102 && same_as<sentinel_t<_Range>, sentinel_t<const _Range>>;
104 template<
typename _It>
105 concept __has_arrow = input_iterator<_It>
106 && (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); });
108 template<
typename _Tp,
typename _Up>
109 concept __not_same_as
110 = !same_as<remove_cvref_t<_Tp>, remove_cvref_t<_Up>>;
113 template<
typename _Derived>
114 requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
115 class view_interface :
public view_base
118 constexpr _Derived& _M_derived() noexcept
120 static_assert(derived_from<_Derived, view_interface<_Derived>>);
121 static_assert(view<_Derived>);
122 return static_cast<_Derived&>(*
this);
125 constexpr
const _Derived& _M_derived() const noexcept
127 static_assert(derived_from<_Derived, view_interface<_Derived>>);
128 static_assert(view<_Derived>);
129 return static_cast<const _Derived&>(*
this);
134 empty() requires forward_range<_Derived>
138 empty() const requires forward_range<const _Derived>
142 operator bool() requires requires { ranges::empty(_M_derived()); }
143 {
return !ranges::empty(_M_derived()); }
146 operator bool() const requires requires { ranges::empty(_M_derived()); }
147 {
return !ranges::empty(_M_derived()); }
150 data() requires contiguous_iterator<iterator_t<_Derived>>
155 requires range<const _Derived>
156 && contiguous_iterator<iterator_t<const _Derived>>
161 requires forward_range<_Derived>
162 && sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>>
167 requires forward_range<const _Derived>
168 && sized_sentinel_for<sentinel_t<const _Derived>,
169 iterator_t<const _Derived>>
172 constexpr decltype(
auto)
173 front() requires forward_range<_Derived>
175 __glibcxx_assert(!empty());
179 constexpr decltype(
auto)
180 front() const requires forward_range<const _Derived>
182 __glibcxx_assert(!empty());
186 constexpr decltype(
auto)
188 requires bidirectional_range<_Derived> && common_range<_Derived>
190 __glibcxx_assert(!empty());
194 constexpr decltype(
auto)
196 requires bidirectional_range<const _Derived>
197 && common_range<const _Derived>
199 __glibcxx_assert(!empty());
203 template<random_access_range _Range = _Derived>
204 constexpr decltype(
auto)
205 operator[](range_difference_t<_Range> __n)
208 template<random_access_range _Range = const _Derived>
209 constexpr decltype(
auto)
210 operator[](range_difference_t<_Range> __n)
const
216 template<
typename _Tp>
218 = !is_reference_v<_Tp> && requires(_Tp __t)
220 typename tuple_size<_Tp>::type;
221 requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>;
222 typename tuple_element_t<0, remove_const_t<_Tp>>;
223 typename tuple_element_t<1, remove_const_t<_Tp>>;
224 { get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>;
225 { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
228 template<
typename _Tp,
typename _Up,
typename _Vp>
229 concept __pair_like_convertible_to
230 = !range<_Tp> && __pair_like<remove_reference_t<_Tp>>
231 && requires(_Tp&& __t)
233 { get<0>(std::forward<_Tp>(__t)) } -> convertible_to<_Up>;
234 { get<1>(std::forward<_Tp>(__t)) } -> convertible_to<_Vp>;
237 template<
typename _Tp,
typename _Up,
typename _Vp>
238 concept __pair_like_convertible_from
239 = !range<_Tp> && __pair_like<_Tp>
240 && constructible_from<_Tp, _Up, _Vp>;
242 template<
typename _Tp>
243 concept __iterator_sentinel_pair
244 = !range<_Tp> && __pair_like<_Tp>
245 && sentinel_for<tuple_element_t<1, _Tp>, tuple_element_t<0, _Tp>>;
247 template<
typename _Tp,
bool _MaxDiff = same_as<_Tp, __max_diff_type>>
248 using __make_unsigned_like_t
249 = conditional_t<_MaxDiff, __max_size_type, make_unsigned_t<_Tp>>;
253 enum class subrange_kind : bool { unsized, sized };
255 template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
256 subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
257 ? subrange_kind::sized : subrange_kind::unsized>
258 requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
259 class subrange :
public view_interface<subrange<_It, _Sent, _Kind>>
262 static constexpr
bool _S_store_size
263 = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;
265 _It _M_begin = _It();
266 _Sent _M_end = _Sent();
268 template<
typename,
bool = _S_store_size>
272 template<
typename _Tp>
273 struct _Size<_Tp, true>
274 { __detail::__make_unsigned_like_t<_Tp> _M_size; };
276 [[no_unique_address]] _Size<iter_difference_t<_It>> _M_size = {};
279 subrange() =
default;
282 subrange(_It __i, _Sent __s) requires (!_S_store_size)
283 : _M_begin(
std::
move(__i)), _M_end(__s)
287 subrange(_It __i, _Sent __s,
288 __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
289 requires (_Kind == subrange_kind::sized)
290 : _M_begin(
std::
move(__i)), _M_end(__s)
292 using __detail::__to_unsigned_like;
294 if constexpr (_S_store_size)
295 _M_size._M_size = __n;
298 template<__detail::__not_same_as<subrange> _Rng>
299 requires safe_range<_Rng>
300 && convertible_to<iterator_t<_Rng>, _It>
301 && convertible_to<sentinel_t<_Rng>, _Sent>
303 subrange(_Rng&& __r) requires (!_S_store_size || sized_range<_Rng>)
306 if constexpr (_S_store_size)
307 _M_size._M_size = ranges::size(__r);
310 template<safe_range _Rng>
311 requires convertible_to<iterator_t<_Rng>, _It>
312 && convertible_to<sentinel_t<_Rng>, _Sent>
315 __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
316 requires (_Kind == subrange_kind::sized)
320 template<__detail::__not_same_as<subrange> _PairLike>
321 requires __detail::__pair_like_convertible_to<_PairLike, _It, _Sent>
323 subrange(_PairLike&& __r) requires (!_S_store_size)
324 : subrange{std::get<0>(std::forward<_PairLike>(__r)),
325 std::get<1>(std::forward<_PairLike>(__r))}
328 template<__detail::__pair_like_convertible_to<_It, _Sent> _PairLike>
330 subrange(_PairLike&& __r,
331 __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
332 requires (_Kind == subrange_kind::sized)
333 : subrange{std::get<0>(std::forward<_PairLike>(__r)),
334 std::get<1>(std::forward<_PairLike>(__r)), __n}
337 template<__detail::__not_same_as<subrange> _PairLike>
338 requires __detail::__pair_like_convertible_from<_PairLike,
const _It&,
341 operator _PairLike()
const
342 {
return _PairLike(_M_begin, _M_end); }
345 begin() const requires copyable<_It>
348 [[nodiscard]] constexpr _It
349 begin() requires (!copyable<_It>)
352 constexpr _Sent
end()
const {
return _M_end; }
354 constexpr
bool empty()
const {
return _M_begin == _M_end; }
356 constexpr __detail::__make_unsigned_like_t<iter_difference_t<_It>>
357 size() const requires (_Kind == subrange_kind::sized)
359 if constexpr (_S_store_size)
360 return _M_size._M_size;
362 return __detail::__to_unsigned_like(_M_end - _M_begin);
365 [[nodiscard]] constexpr subrange
366 next(iter_difference_t<_It> __n = 1) const &
367 requires forward_iterator<_It>
374 [[nodiscard]] constexpr subrange
375 next(iter_difference_t<_It> __n = 1) &&
381 [[nodiscard]] constexpr subrange
382 prev(iter_difference_t<_It> __n = 1) const
383 requires bidirectional_iterator<_It>
386 __tmp.advance(--__n);
391 advance(iter_difference_t<_It> __n)
393 if constexpr (_S_store_size)
397 _M_size._M_size -= __detail::__to_unsigned_like(__d);
399 _M_size._M_size += __detail::__to_unsigned_like(-__d);
407 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
409 __detail::__make_unsigned_like_t<iter_difference_t<_It>>)
410 -> subrange<_It, _Sent, subrange_kind::sized>;
412 template<__detail::__iterator_sentinel_pair _Pr>
414 -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>>;
416 template<__detail::__iterator_sentinel_pair _Pr>
417 subrange(_Pr, __detail::__make_unsigned_like_t<iter_difference_t<
418 tuple_element_t<0, _Pr>>>)
419 -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>,
420 subrange_kind::sized>;
422 template<safe_range _Rng>
424 -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>,
426 || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
427 ? subrange_kind::sized : subrange_kind::unsized>;
429 template<safe_range _Rng>
431 __detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
432 -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>;
434 template<
size_t _Num,
class _It,
class _Sent, subrange_kind _Kind>
437 get(const subrange<_It, _Sent, _Kind>& __r)
439 if constexpr (_Num == 0)
445 template<
size_t _Num, class _It, class _Sent, subrange_kind _Kind>
448 get(subrange<_It, _Sent, _Kind>&& __r)
450 if constexpr (_Num == 0)
456 template<input_or_output_iterator _It, sentinel_for<_It> _Sent,
458 inline constexpr
bool
459 enable_safe_range<subrange<_It, _Sent, _Kind>> = true;
470 constexpr dangling() noexcept = default;
471 template<typename... _Args>
472 constexpr dangling(_Args&&...) noexcept { }
475 template<range _Range>
476 using safe_iterator_t = conditional_t<safe_range<_Range>,
480 template<range _Range>
481 using safe_subrange_t = conditional_t<safe_range<_Range>,
482 subrange<iterator_t<_Range>>,
485 template<
typename _Tp> requires is_object_v<_Tp>
487 :
public view_interface<empty_view<_Tp>>
490 static constexpr _Tp*
begin() noexcept {
return nullptr; }
491 static constexpr _Tp*
end() noexcept {
return nullptr; }
492 static constexpr _Tp* data() noexcept {
return nullptr; }
493 static constexpr
size_t size() noexcept {
return 0; }
494 static constexpr
bool empty() noexcept {
return true; }
497 template<
typename _Tp>
498 inline constexpr
bool enable_safe_range<empty_view<_Tp>> =
true;
502 template<copy_constructible _Tp> requires is_object_v<_Tp>
503 struct __box : std::optional<_Tp>
505 using std::optional<_Tp>::optional;
509 noexcept(is_nothrow_default_constructible_v<_Tp>)
510 requires default_initializable<_Tp>
514 using std::optional<_Tp>::operator=;
517 operator=(
const __box& __that)
518 noexcept(is_nothrow_copy_constructible_v<_Tp>)
519 requires (!assignable_from<_Tp&, const _Tp&>)
522 this->emplace(*__that);
529 operator=(__box&& __that)
530 noexcept(is_nothrow_move_constructible_v<_Tp>)
531 requires (!assignable_from<_Tp&, _Tp>)
544 template<copy_constructible _Tp> requires is_object_v<_Tp>
545 class single_view :
public view_interface<single_view<_Tp>>
548 single_view() =
default;
551 single_view(
const _Tp& __t)
556 single_view(_Tp&& __t)
560 template<
typename... _Args>
561 requires constructible_from<_Tp, _Args...>
563 single_view(in_place_t, _Args&&... __args)
564 : _M_value{
in_place, std::forward<_Args>(__args)...}
572 begin() const noexcept
577 {
return data() + 1; }
581 {
return data() + 1; }
583 static constexpr
size_t
589 {
return _M_value.operator->(); }
592 data() const noexcept
593 {
return _M_value.operator->(); }
596 __detail::__box<_Tp> _M_value;
601 template<
typename _Wp>
602 constexpr
auto __to_signed_like(_Wp __w) noexcept
604 if constexpr (!integral<_Wp>)
605 return iter_difference_t<_Wp>();
606 else if constexpr (
sizeof(iter_difference_t<_Wp>) >
sizeof(_Wp))
607 return iter_difference_t<_Wp>(__w);
608 else if constexpr (
sizeof(ptrdiff_t) >
sizeof(_Wp))
609 return ptrdiff_t(__w);
610 else if constexpr (
sizeof(
long long) >
sizeof(_Wp))
611 return (
long long)(__w);
612 #ifdef __SIZEOF_INT128__
613 else if constexpr (__SIZEOF_INT128__ >
sizeof(_Wp))
614 return __int128(__w);
617 return __max_diff_type(__w);
620 template<
typename _Wp>
621 using __iota_diff_t = decltype(__to_signed_like(std::declval<_Wp>()));
623 template<
typename _It>
624 concept __decrementable = incrementable<_It>
627 { --__i } -> same_as<_It&>;
628 { __i-- } -> same_as<_It>;
631 template<
typename _It>
632 concept __advanceable = __decrementable<_It> && totally_ordered<_It>
633 && requires( _It __i,
const _It __j,
const __iota_diff_t<_It> __n)
635 { __i += __n } -> same_as<_It&>;
636 { __i -= __n } -> same_as<_It&>;
640 { __j - __j } -> convertible_to<__iota_diff_t<_It>>;
645 template<weakly_incrementable _Winc,
646 semiregular _Bound = unreachable_sentinel_t>
647 requires std::__detail::__weakly_eq_cmp_with<_Winc, _Bound>
648 class iota_view :
public view_interface<iota_view<_Winc, _Bound>>
657 using namespace __detail;
658 if constexpr (__advanceable<_Winc>)
659 return random_access_iterator_tag{};
660 else if constexpr (__decrementable<_Winc>)
661 return bidirectional_iterator_tag{};
662 else if constexpr (incrementable<_Winc>)
663 return forward_iterator_tag{};
665 return input_iterator_tag{};
669 using iterator_category = decltype(_S_iter_cat());
670 using value_type = _Winc;
671 using difference_type = __detail::__iota_diff_t<_Winc>;
673 _Iterator() =
default;
676 _Iterator(_Winc __value)
677 : _M_value(__value) { }
680 operator*() const noexcept(is_nothrow_copy_constructible_v<_Winc>)
695 operator++(
int) requires incrementable<_Winc>
703 operator--() requires __detail::__decrementable<_Winc>
710 operator--(
int) requires __detail::__decrementable<_Winc>
718 operator+=(difference_type __n) requires __detail::__advanceable<_Winc>
720 using namespace __detail;
721 if constexpr (__is_integer_like<_Winc>
722 && !__is_signed_integer_like<_Winc>)
724 if (__n >= difference_type(0))
725 _M_value += static_cast<_Winc>(__n);
727 _M_value -= static_cast<_Winc>(-__n);
735 operator-=(difference_type __n) requires __detail::__advanceable<_Winc>
737 using namespace __detail;
738 if constexpr (__is_integer_like<_Winc>
739 && !__is_signed_integer_like<_Winc>)
741 if (__n >= difference_type(0))
742 _M_value -= static_cast<_Winc>(__n);
744 _M_value += static_cast<_Winc>(-__n);
752 operator[](difference_type __n)
const
753 requires __detail::__advanceable<_Winc>
754 {
return _Winc(_M_value + __n); }
756 friend constexpr
bool
757 operator==(
const _Iterator& __x,
const _Iterator& __y)
758 requires equality_comparable<_Winc>
759 {
return __x._M_value == __y._M_value; }
761 friend constexpr
bool
762 operator<(
const _Iterator& __x,
const _Iterator& __y)
763 requires totally_ordered<_Winc>
764 {
return __x._M_value < __y._M_value; }
766 friend constexpr
bool
767 operator>(
const _Iterator& __x,
const _Iterator& __y)
768 requires totally_ordered<_Winc>
769 {
return __y < __x; }
771 friend constexpr
bool
772 operator<=(
const _Iterator& __x,
const _Iterator& __y)
773 requires totally_ordered<_Winc>
774 {
return !(__y < __x); }
776 friend constexpr
bool
777 operator>=(
const _Iterator& __x,
const _Iterator& __y)
778 requires totally_ordered<_Winc>
779 {
return !(__x < __y); }
781 #ifdef __cpp_lib_threeway_comparison
782 friend constexpr compare_three_way_result_t<_Winc>
783 operator<=>(
const _Iterator& __x,
const _Iterator& __y)
784 requires totally_ordered<_Winc> && three_way_comparable<_Winc>
785 {
return __x._M_value <=> __y._M_value; }
788 friend constexpr _Iterator
789 operator+(_Iterator __i, difference_type __n)
790 requires __detail::__advanceable<_Winc>
791 {
return __i += __n; }
793 friend constexpr _Iterator
794 operator+(difference_type __n, _Iterator __i)
795 requires __detail::__advanceable<_Winc>
796 {
return __i += __n; }
798 friend constexpr _Iterator
799 operator-(_Iterator __i, difference_type __n)
800 requires __detail::__advanceable<_Winc>
801 {
return __i -= __n; }
803 friend constexpr difference_type
804 operator-(
const _Iterator& __x,
const _Iterator& __y)
805 requires __detail::__advanceable<_Winc>
807 using namespace __detail;
808 using _Dt = difference_type;
809 if constexpr (__is_integer_like<_Winc>)
811 if constexpr (__is_signed_integer_like<_Winc>)
812 return _Dt(_Dt(__x._M_value) - _Dt(__y._M_value));
814 return (__y._M_value > __x._M_value)
815 ? _Dt(-_Dt(__y._M_value - __x._M_value))
816 : _Dt(__x._M_value - __y._M_value);
819 return __x._M_value - __y._M_value;
823 _Winc _M_value = _Winc();
829 _Bound _M_bound = _Bound();
832 _Sentinel() =
default;
835 _Sentinel(_Bound __bound)
836 : _M_bound(__bound) { }
838 friend constexpr
bool
839 operator==(
const _Iterator& __x,
const _Sentinel& __y)
840 {
return __x._M_value == __y._M_bound; }
842 friend constexpr iter_difference_t<_Winc>
843 operator-(
const _Iterator& __x,
const _Sentinel& __y)
844 requires sized_sentinel_for<_Bound, _Winc>
845 {
return __x._M_value - __y._M_bound; }
847 friend constexpr iter_difference_t<_Winc>
848 operator-(
const _Sentinel& __x,
const _Iterator& __y)
849 requires sized_sentinel_for<_Bound, _Winc>
850 {
return -(__y - __x); }
853 _Winc _M_value = _Winc();
854 _Bound _M_bound = _Bound();
857 iota_view() =
default;
860 iota_view(_Winc __value)
865 iota_view(type_identity_t<_Winc> __value,
866 type_identity_t<_Bound> __bound)
867 : _M_value(__value), _M_bound(__bound)
869 if constexpr (totally_ordered_with<_Winc, _Bound>)
870 __glibcxx_assert(
bool(__value <= __bound) );
874 begin()
const {
return _Iterator{_M_value}; }
879 if constexpr (same_as<_Bound, unreachable_sentinel_t>)
880 return unreachable_sentinel;
882 return _Sentinel{_M_bound};
886 end() const requires same_as<_Winc, _Bound>
887 {
return _Iterator{_M_bound}; }
891 requires (same_as<_Winc, _Bound> && __detail::__advanceable<_Winc>)
892 || (integral<_Winc> && integral<_Bound>)
893 || sized_sentinel_for<_Bound, _Winc>
895 using namespace __detail;
896 if constexpr (__is_integer_like<_Winc> && __is_integer_like<_Bound>)
897 return (_M_value < 0)
899 ? __to_unsigned_like(-_M_value) - __to_unsigned_like(-_M_bound)
900 : __to_unsigned_like(_M_bound) + __to_unsigned_like(-_M_value))
901 : __to_unsigned_like(_M_bound) - __to_unsigned_like(_M_value);
903 return __to_unsigned_like(_M_bound - _M_value);
907 template<
typename _Winc,
typename _Bound>
908 requires (!__detail::__is_integer_like<_Winc>
909 || !__detail::__is_integer_like<_Bound>
910 || (__detail::__is_signed_integer_like<_Winc>
911 == __detail::__is_signed_integer_like<_Bound>))
912 iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>;
914 template<weakly_incrementable _Winc, semiregular _Bound>
915 inline constexpr
bool enable_safe_range<iota_view<_Winc, _Bound>> =
true;
919 template<
typename _Tp>
920 inline constexpr empty_view<_Tp> empty{};
924 template<
typename _Tp>
926 operator()(_Tp&& __e)
const
927 {
return single_view{std::forward<_Tp>(__e)}; }
930 inline constexpr _Single single{};
934 template<
typename _Tp>
936 operator()(_Tp&& __e)
const
937 {
return iota_view{std::forward<_Tp>(__e)}; }
939 template<
typename _Tp,
typename _Up>
941 operator()(_Tp&& __e, _Up&& __f)
const
942 {
return iota_view{std::forward<_Tp>(__e), std::forward<_Tp>(__f)}; }
945 inline constexpr _Iota
iota{};
949 _GLIBCXX_END_NAMESPACE_VERSION
951 #endif // library concepts