30 #ifndef _RANGES_UTIL_H
31 #define _RANGES_UTIL_H 1
33 #if __cplusplus > 201703L
36 #ifdef __cpp_lib_ranges
37 namespace std _GLIBCXX_VISIBILITY(default)
39 _GLIBCXX_BEGIN_NAMESPACE_VERSION
46 template<
typename _Range>
47 concept __simple_view = view<_Range> && range<const _Range>
48 && same_as<iterator_t<_Range>, iterator_t<const _Range>>
49 && same_as<sentinel_t<_Range>, sentinel_t<const _Range>>;
51 template<
typename _It>
52 concept __has_arrow = input_iterator<_It>
53 && (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); });
55 template<
typename _Tp,
typename _Up>
57 = !same_as<remove_cvref_t<_Tp>, remove_cvref_t<_Up>>;
61 template<
typename _Derived>
62 requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
63 class view_interface :
public view_base
66 constexpr _Derived& _M_derived() noexcept
68 static_assert(derived_from<_Derived, view_interface<_Derived>>);
69 static_assert(view<_Derived>);
70 return static_cast<_Derived&
>(*this);
73 constexpr
const _Derived& _M_derived() const noexcept
75 static_assert(derived_from<_Derived, view_interface<_Derived>>);
76 static_assert(view<_Derived>);
77 return static_cast<const _Derived&
>(*this);
82 empty() requires forward_range<_Derived>
86 empty() const requires forward_range<const _Derived>
90 operator bool() requires requires {
ranges::empty(_M_derived()); }
94 operator bool() const requires requires {
ranges::empty(_M_derived()); }
98 data() requires contiguous_iterator<iterator_t<_Derived>>
103 requires range<const _Derived>
104 && contiguous_iterator<iterator_t<const _Derived>>
109 requires forward_range<_Derived>
110 && sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>>
115 requires forward_range<const _Derived>
116 && sized_sentinel_for<sentinel_t<const _Derived>,
117 iterator_t<const _Derived>>
120 constexpr decltype(
auto)
121 front() requires forward_range<_Derived>
123 __glibcxx_assert(!
empty());
127 constexpr decltype(
auto)
128 front() const requires forward_range<const _Derived>
130 __glibcxx_assert(!
empty());
134 constexpr decltype(
auto)
136 requires bidirectional_range<_Derived> && common_range<_Derived>
138 __glibcxx_assert(!
empty());
142 constexpr decltype(
auto)
144 requires bidirectional_range<const _Derived>
145 && common_range<const _Derived>
147 __glibcxx_assert(!
empty());
151 template<random_access_range _Range = _Derived>
152 constexpr decltype(
auto)
153 operator[](range_difference_t<_Range> __n)
156 template<random_access_range _Range = const _Derived>
157 constexpr decltype(
auto)
158 operator[](range_difference_t<_Range> __n)
const
164 template<
class _From,
class _To>
165 concept __convertible_to_non_slicing = convertible_to<_From, _To>
166 && !(is_pointer_v<decay_t<_From>> && is_pointer_v<decay_t<_To>>
167 && __not_same_as<remove_pointer_t<decay_t<_From>>,
168 remove_pointer_t<decay_t<_To>>>);
170 template<
typename _Tp>
172 = !is_reference_v<_Tp> && requires(_Tp __t)
174 typename tuple_size<_Tp>::type;
175 requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>;
176 typename tuple_element_t<0, remove_const_t<_Tp>>;
177 typename tuple_element_t<1, remove_const_t<_Tp>>;
178 { get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>;
179 { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
182 template<
typename _Tp,
typename _Up,
typename _Vp>
183 concept __pair_like_convertible_from
184 = !range<_Tp> && __pair_like<_Tp>
185 && constructible_from<_Tp, _Up, _Vp>
186 && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>>
187 && convertible_to<_Vp, tuple_element_t<1, _Tp>>;
189 template<
typename _Tp>
190 concept __iterator_sentinel_pair
191 = !range<_Tp> && __pair_like<_Tp>
192 && sentinel_for<tuple_element_t<1, _Tp>, tuple_element_t<0, _Tp>>;
196 enum class subrange_kind : bool { unsized, sized };
199 template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
200 subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
201 ? subrange_kind::sized : subrange_kind::unsized>
202 requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
203 class subrange :
public view_interface<subrange<_It, _Sent, _Kind>>
207 static const bool _S_store_size
208 = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;
210 _It _M_begin = _It();
211 [[no_unique_address]] _Sent _M_end = _Sent();
213 template<
typename,
bool = _S_store_size>
217 template<
typename _Tp>
218 struct _Size<_Tp, true>
219 { __detail::__make_unsigned_like_t<_Tp> _M_size; };
221 [[no_unique_address]] _Size<iter_difference_t<_It>> _M_size = {};
224 subrange() =
default;
227 subrange(__detail::__convertible_to_non_slicing<_It>
auto __i, _Sent __s)
228 requires (!_S_store_size)
229 : _M_begin(
std::
move(__i)), _M_end(__s)
233 subrange(__detail::__convertible_to_non_slicing<_It>
auto __i, _Sent __s,
234 __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
235 requires (_Kind == subrange_kind::sized)
236 : _M_begin(
std::
move(__i)), _M_end(__s)
238 using __detail::__to_unsigned_like;
239 __glibcxx_assert(__n == __to_unsigned_like(ranges::distance(__i, __s)));
240 if constexpr (_S_store_size)
241 _M_size._M_size = __n;
244 template<__detail::__not_same_as<subrange> _Rng>
245 requires borrowed_range<_Rng>
246 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
247 && convertible_to<sentinel_t<_Rng>, _Sent>
249 subrange(_Rng&& __r) requires _S_store_size && sized_range<_Rng>
253 template<__detail::__not_same_as<subrange> _Rng>
254 requires borrowed_range<_Rng>
255 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
256 && convertible_to<sentinel_t<_Rng>, _Sent>
258 subrange(_Rng&& __r) requires (!_S_store_size)
259 : subrange{ranges::
begin(__r), ranges::
end(__r)}
262 template<borrowed_range _Rng>
263 requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
264 && convertible_to<sentinel_t<_Rng>, _Sent>
267 __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
268 requires (_Kind == subrange_kind::sized)
269 : subrange{ranges::
begin(__r), ranges::
end(__r), __n}
272 template<__detail::__not_same_as<subrange> _PairLike>
273 requires __detail::__pair_like_convertible_from<_PairLike,
const _It&,
276 operator _PairLike()
const
277 {
return _PairLike(_M_begin, _M_end); }
280 begin() const requires copyable<_It>
283 [[nodiscard]] constexpr _It
284 begin() requires (!copyable<_It>)
287 constexpr _Sent
end()
const {
return _M_end; }
289 constexpr
bool empty()
const {
return _M_begin == _M_end; }
291 constexpr __detail::__make_unsigned_like_t<iter_difference_t<_It>>
292 size() const requires (_Kind == subrange_kind::sized)
294 if constexpr (_S_store_size)
295 return _M_size._M_size;
297 return __detail::__to_unsigned_like(_M_end - _M_begin);
300 [[nodiscard]] constexpr subrange
301 next(iter_difference_t<_It> __n = 1) const &
302 requires forward_iterator<_It>
309 [[nodiscard]] constexpr subrange
310 next(iter_difference_t<_It> __n = 1) &&
316 [[nodiscard]] constexpr subrange
317 prev(iter_difference_t<_It> __n = 1) const
318 requires bidirectional_iterator<_It>
326 advance(iter_difference_t<_It> __n)
330 if constexpr (bidirectional_iterator<_It>)
333 ranges::advance(_M_begin, __n);
334 if constexpr (_S_store_size)
335 _M_size._M_size += __detail::__to_unsigned_like(-__n);
339 __glibcxx_assert(__n >= 0);
340 auto __d = __n - ranges::advance(_M_begin, __n, _M_end);
341 if constexpr (_S_store_size)
342 _M_size._M_size -= __detail::__to_unsigned_like(__d);
347 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
348 subrange(_It, _Sent) -> subrange<_It, _Sent>;
350 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
352 __detail::__make_unsigned_like_t<iter_difference_t<_It>>)
353 -> subrange<_It, _Sent, subrange_kind::sized>;
355 template<__detail::__iterator_sentinel_pair _Pr>
357 -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>>;
359 template<__detail::__iterator_sentinel_pair _Pr>
360 subrange(_Pr, __detail::__make_unsigned_like_t<iter_difference_t<
361 tuple_element_t<0, _Pr>>>)
362 -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>,
363 subrange_kind::sized>;
365 template<borrowed_range _Rng>
367 -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>,
369 || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
370 ? subrange_kind::sized : subrange_kind::unsized>;
372 template<borrowed_range _Rng>
374 __detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
375 -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>;
377 template<
size_t _Num,
class _It,
class _Sent, subrange_kind _Kind>
380 get(const subrange<_It, _Sent, _Kind>& __r)
382 if constexpr (_Num == 0)
388 template<
size_t _Num, class _It, class _Sent, subrange_kind _Kind>
391 get(subrange<_It, _Sent, _Kind>&& __r)
393 if constexpr (_Num == 0)
399 template<input_or_output_iterator _It, sentinel_for<_It> _Sent,
401 inline constexpr
bool
402 enable_borrowed_range<subrange<_It, _Sent, _Kind>> = true;
404 template<range _Range>
405 using borrowed_subrange_t =
conditional_t<borrowed_range<_Range>,
406 subrange<iterator_t<_Range>>,
413 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
414 struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
415 : integral_constant<
size_t, 2>
418 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
419 struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
420 {
using type = _Iter; };
422 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
423 struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
424 {
using type = _Sent; };
426 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
427 struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>>
428 {
using type = _Iter; };
430 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
431 struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>>
432 {
using type = _Sent; };
434 _GLIBCXX_END_NAMESPACE_VERSION
typename conditional< _Cond, _Iftrue, _Iffalse >::type conditional_t
Alias template for conditional.
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.
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 size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
constexpr auto data(_Container &__cont) noexcept(noexcept(__cont.data())) -> decltype(__cont.data())
Return the data pointer of a container.