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>>;
191 enum class subrange_kind : bool { unsized, sized };
194 template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
195 subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
196 ? subrange_kind::sized : subrange_kind::unsized>
197 requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
198 class subrange :
public view_interface<subrange<_It, _Sent, _Kind>>
202 static const bool _S_store_size
203 = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;
205 _It _M_begin = _It();
206 [[no_unique_address]] _Sent _M_end = _Sent();
209 = __detail::__make_unsigned_like_t<iter_difference_t<_It>>;
211 template<
typename,
bool = _S_store_size>
215 template<
typename _Tp>
216 struct _Size<_Tp, true>
219 [[no_unique_address]] _Size<__size_type> _M_size = {};
222 subrange() =
default;
225 subrange(__detail::__convertible_to_non_slicing<_It>
auto __i, _Sent __s)
226 requires (!_S_store_size)
227 : _M_begin(
std::
move(__i)), _M_end(__s)
231 subrange(__detail::__convertible_to_non_slicing<_It>
auto __i, _Sent __s,
233 requires (_Kind == subrange_kind::sized)
234 : _M_begin(
std::
move(__i)), _M_end(__s)
236 if constexpr (_S_store_size)
237 _M_size._M_size = __n;
240 template<__detail::__not_same_as<subrange> _Rng>
241 requires borrowed_range<_Rng>
242 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
243 && convertible_to<sentinel_t<_Rng>, _Sent>
245 subrange(_Rng&& __r) requires _S_store_size && sized_range<_Rng>
249 template<__detail::__not_same_as<subrange> _Rng>
250 requires borrowed_range<_Rng>
251 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
252 && convertible_to<sentinel_t<_Rng>, _Sent>
254 subrange(_Rng&& __r) requires (!_S_store_size)
255 : subrange(ranges::
begin(__r), ranges::
end(__r))
258 template<borrowed_range _Rng>
259 requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
260 && convertible_to<sentinel_t<_Rng>, _Sent>
262 subrange(_Rng&& __r, __size_type __n)
263 requires (_Kind == subrange_kind::sized)
267 template<__detail::__not_same_as<subrange> _PairLike>
268 requires __detail::__pair_like_convertible_from<_PairLike,
const _It&,
271 operator _PairLike()
const 272 {
return _PairLike(_M_begin, _M_end); }
275 begin() const requires copyable<_It>
278 [[nodiscard]] constexpr _It
279 begin() requires (!copyable<_It>)
282 constexpr _Sent
end()
const {
return _M_end; }
284 constexpr
bool empty()
const {
return _M_begin == _M_end; }
286 constexpr __size_type
287 size() const requires (_Kind == subrange_kind::sized)
289 if constexpr (_S_store_size)
290 return _M_size._M_size;
292 return __detail::__to_unsigned_like(_M_end - _M_begin);
295 [[nodiscard]] constexpr subrange
296 next(iter_difference_t<_It> __n = 1) const &
297 requires forward_iterator<_It>
304 [[nodiscard]] constexpr subrange
305 next(iter_difference_t<_It> __n = 1) &&
311 [[nodiscard]] constexpr subrange
312 prev(iter_difference_t<_It> __n = 1) const
313 requires bidirectional_iterator<_It>
321 advance(iter_difference_t<_It> __n)
325 if constexpr (bidirectional_iterator<_It>)
329 if constexpr (_S_store_size)
330 _M_size._M_size += __detail::__to_unsigned_like(-__n);
334 __glibcxx_assert(__n >= 0);
336 if constexpr (_S_store_size)
337 _M_size._M_size -= __detail::__to_unsigned_like(__d);
342 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
343 subrange(_It, _Sent) -> subrange<_It, _Sent>;
345 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
347 __detail::__make_unsigned_like_t<iter_difference_t<_It>>)
348 -> subrange<_It, _Sent, subrange_kind::sized>;
350 template<borrowed_range _Rng>
352 -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>,
354 || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
355 ? subrange_kind::sized : subrange_kind::unsized>;
357 template<borrowed_range _Rng>
359 __detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
360 -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>;
362 template<
size_t _Num,
class _It,
class _Sent, subrange_kind _Kind>
365 get(const subrange<_It, _Sent, _Kind>& __r)
367 if constexpr (_Num == 0)
373 template<
size_t _Num, class _It, class _Sent, subrange_kind _Kind>
376 get(subrange<_It, _Sent, _Kind>&& __r)
378 if constexpr (_Num == 0)
384 template<input_or_output_iterator _It, sentinel_for<_It> _Sent,
386 inline constexpr
bool 387 enable_borrowed_range<subrange<_It, _Sent, _Kind>> = true;
389 template<range _Range>
390 using borrowed_subrange_t =
conditional_t<borrowed_range<_Range>,
391 subrange<iterator_t<_Range>>,
401 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
402 typename _Proj =
identity>
403 requires indirect_binary_predicate<ranges::equal_to,
404 projected<_Iter, _Proj>,
const _Tp*>
406 operator()(_Iter __first, _Sent __last,
407 const _Tp& __value, _Proj __proj = {})
const 409 while (__first != __last
415 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
416 requires indirect_binary_predicate<ranges::equal_to,
417 projected<iterator_t<_Range>, _Proj>,
419 constexpr borrowed_iterator_t<_Range>
420 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const 427 inline constexpr __find_fn find{};
431 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
432 typename _Proj =
identity,
433 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
435 operator()(_Iter __first, _Sent __last,
436 _Pred __pred, _Proj __proj = {})
const 438 while (__first != __last
444 template<input_range _Range,
typename _Proj = identity,
445 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
447 constexpr borrowed_iterator_t<_Range>
448 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const 455 inline constexpr __find_if_fn find_if{};
457 struct __find_if_not_fn
459 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
460 typename _Proj =
identity,
461 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
463 operator()(_Iter __first, _Sent __last,
464 _Pred __pred, _Proj __proj = {})
const 466 while (__first != __last
472 template<input_range _Range,
typename _Proj = identity,
473 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
475 constexpr borrowed_iterator_t<_Range>
476 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const 483 inline constexpr __find_if_not_fn find_if_not{};
485 template<
typename _Iter1,
typename _Iter2>
488 [[no_unique_address]] _Iter1 in1;
489 [[no_unique_address]] _Iter2 in2;
491 template<
typename _IIter1,
typename _IIter2>
492 requires convertible_to<const _Iter1&, _IIter1>
493 && convertible_to<const _Iter2&, _IIter2>
495 operator in_in_result<_IIter1, _IIter2>()
const &
496 {
return {in1, in2}; }
498 template<
typename _IIter1,
typename _IIter2>
499 requires convertible_to<_Iter1, _IIter1>
500 && convertible_to<_Iter2, _IIter2>
502 operator in_in_result<_IIter1, _IIter2>() &&
506 template<
typename _Iter1,
typename _Iter2>
507 using mismatch_result = in_in_result<_Iter1, _Iter2>;
511 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
512 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
513 typename _Pred = ranges::equal_to,
514 typename _Proj1 =
identity,
typename _Proj2 =
identity>
515 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
516 constexpr mismatch_result<_Iter1, _Iter2>
517 operator()(_Iter1 __first1, _Sent1 __last1,
518 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
519 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 521 while (__first1 != __last1 && __first2 != __last2
532 template<input_range _Range1, input_range _Range2,
533 typename _Pred = ranges::equal_to,
534 typename _Proj1 = identity,
typename _Proj2 = identity>
535 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
536 _Pred, _Proj1, _Proj2>
537 constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>>
538 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
539 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 548 inline constexpr __mismatch_fn mismatch{};
552 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
553 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
554 typename _Pred = ranges::equal_to,
555 typename _Proj1 =
identity,
typename _Proj2 =
identity>
556 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
557 constexpr subrange<_Iter1>
558 operator()(_Iter1 __first1, _Sent1 __last1,
559 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
560 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 562 if (__first1 == __last1 || __first2 == __last2)
563 return {__first1, __first1};
569 if (__first1 == __last1)
570 return {__first1, __first1};
577 auto __cur1 = __first1;
578 auto __cur2 = __first2;
581 if (++__cur2 == __last2)
582 return {__first1, ++__cur1};
583 if (++__cur1 == __last1)
584 return {__cur1, __cur1};
596 template<forward_range _Range1, forward_range _Range2,
597 typename _Pred = ranges::equal_to,
598 typename _Proj1 = identity,
typename _Proj2 = identity>
599 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
600 _Pred, _Proj1, _Proj2>
601 constexpr borrowed_subrange_t<_Range1>
602 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
603 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 612 inline constexpr __search_fn search{};
617 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
618 struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
619 : integral_constant<size_t, 2>
622 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
623 struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
624 {
using type = _Iter; };
626 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
627 struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
628 {
using type = _Sent; };
630 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
631 struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>>
632 {
using type = _Iter; };
634 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
635 struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>>
636 {
using type = _Sent; };
638 _GLIBCXX_END_NAMESPACE_VERSION
640 #endif // library concepts 642 #endif // _RANGES_UTIL_H constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
constexpr auto data(_Container &__cont) noexcept(noexcept(__cont.data())) -> decltype(__cont.data())
Return the data pointer of a container.
constexpr __invoke_result< _Callable, _Args... >::type __invoke(_Callable &&__fn, _Args &&... __args) noexcept(__is_nothrow_invocable< _Callable, _Args... >::value)
Invoke a callable object.
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
typename conditional< _Cond, _Iftrue, _Iffalse >::type conditional_t
Alias template for conditional.
ISO C++ entities toplevel namespace is std.