31#define _RANGES_UTIL_H 1
33#if __cplusplus > 201703L
37#ifdef __cpp_lib_ranges
38namespace std _GLIBCXX_VISIBILITY(default)
40_GLIBCXX_BEGIN_NAMESPACE_VERSION
47 template<
typename _Range>
48 concept __simple_view = view<_Range> && range<const _Range>
49 && same_as<iterator_t<_Range>, iterator_t<const _Range>>
50 && same_as<sentinel_t<_Range>, sentinel_t<const _Range>>;
52 template<
typename _It>
53 concept __has_arrow = input_iterator<_It>
54 && (is_pointer_v<_It> ||
requires(_It __it) { __it.operator->(); });
56 using std::__detail::__different_from;
60 template<
typename _Derived>
61 requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
65 constexpr _Derived& _M_derived()
noexcept
69 return static_cast<_Derived&
>(*this);
72 constexpr const _Derived& _M_derived()
const noexcept
76 return static_cast<const _Derived&
>(*this);
80 _S_bool(
bool)
noexcept;
82 template<
typename _Tp>
85 noexcept(
noexcept(_S_bool(ranges::begin(__t) == ranges::end(__t))))
86 {
return ranges::begin(__t) == ranges::end(__t); }
88 template<
typename _Tp>
91 noexcept(
noexcept(ranges::end(__t) - ranges::begin(__t)))
92 {
return ranges::end(__t) - ranges::begin(__t); }
97 noexcept(
noexcept(_S_empty(_M_derived())))
99 {
return _S_empty(_M_derived()); }
103 noexcept(
noexcept(ranges::size(_M_derived()) == 0))
105 {
return ranges::size(_M_derived()) == 0; }
109 noexcept(
noexcept(_S_empty(_M_derived())))
111 {
return _S_empty(_M_derived()); }
115 noexcept(
noexcept(ranges::size(_M_derived()) == 0))
117 {
return ranges::size(_M_derived()) == 0; }
120 operator bool()
noexcept(
noexcept(ranges::empty(_M_derived())))
121 requires requires { ranges::empty(_M_derived()); }
122 {
return !ranges::empty(_M_derived()); }
125 operator bool()
const noexcept(
noexcept(ranges::empty(_M_derived())))
126 requires requires { ranges::empty(_M_derived()); }
127 {
return !ranges::empty(_M_derived()); }
130 data()
noexcept(
noexcept(ranges::begin(_M_derived())))
135 data()
const noexcept(
noexcept(ranges::begin(_M_derived())))
141 size()
noexcept(
noexcept(_S_size(_M_derived())))
144 {
return _S_size(_M_derived()); }
147 size()
const noexcept(
noexcept(_S_size(_M_derived())))
151 {
return _S_size(_M_derived()); }
153 constexpr decltype(
auto)
156 __glibcxx_assert(!empty());
157 return *ranges::begin(_M_derived());
160 constexpr decltype(
auto)
163 __glibcxx_assert(!empty());
164 return *ranges::begin(_M_derived());
167 constexpr decltype(
auto)
171 __glibcxx_assert(!empty());
172 return *ranges::prev(ranges::end(_M_derived()));
175 constexpr decltype(
auto)
180 __glibcxx_assert(!empty());
181 return *ranges::prev(ranges::end(_M_derived()));
184 template<random_access_range _Range = _Derived>
185 constexpr decltype(
auto)
187 {
return ranges::begin(_M_derived())[__n]; }
189 template<random_access_range _Range = const _Derived>
190 constexpr decltype(
auto)
192 {
return ranges::begin(_M_derived())[__n]; }
194#if __cplusplus > 202002L
197 {
return ranges::cbegin(_M_derived()); }
201 {
return ranges::cbegin(_M_derived()); }
205 {
return ranges::cend(_M_derived()); }
209 {
return ranges::cend(_M_derived()); }
215 template<
typename _From,
typename _To>
216 concept __uses_nonqualification_pointer_conversion
221 template<
typename _From,
typename _To>
226 template<
typename _Tp>
235 {
get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
238 template<
typename _Tp,
typename _Up,
typename _Vp>
239 concept __pair_like_convertible_from
240 = !range<_Tp> && __pair_like<_Tp>
241 && constructible_from<_Tp, _Up, _Vp>
242 && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>>
243 && convertible_to<_Vp, tuple_element_t<1, _Tp>>;
247 namespace views {
struct _Drop; }
249 enum class subrange_kind :
bool { unsized, sized };
252 template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
253 subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
254 ? subrange_kind::sized : subrange_kind::unsized>
255 requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
259 static constexpr bool _S_store_size
262 friend struct views::_Drop;
264 _It _M_begin = _It();
268 = __detail::__make_unsigned_like_t<iter_difference_t<_It>>;
270 template<
typename _Tp,
bool = _S_store_size>
273 [[__gnu__::__always_inline__]]
274 constexpr _Size(_Tp = {}) { }
277 template<
typename _Tp>
278 struct _Size<_Tp,
true>
280 [[__gnu__::__always_inline__]]
281 constexpr _Size(_Tp
__s = {}) : _M_size(
__s) { }
292 subrange(__detail::__convertible_to_non_slicing<_It>
auto __i, _Sent
__s)
293 noexcept(is_nothrow_constructible_v<_It,
decltype(__i)>
295 requires (!_S_store_size)
300 subrange(__detail::__convertible_to_non_slicing<_It>
auto __i, _Sent
__s,
302 noexcept(is_nothrow_constructible_v<_It,
decltype(__i)>
304 requires (
_Kind == subrange_kind::sized)
308 template<__detail::__different_from<subrange> _Rng>
310 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
314 noexcept(
noexcept(
subrange(__r, ranges::size(__r))))
319 template<__detail::__different_from<subrange> _Rng>
321 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
325 noexcept(
noexcept(
subrange(ranges::begin(__r), ranges::end(__r))))
326 requires (!_S_store_size)
327 :
subrange(ranges::begin(__r), ranges::end(__r))
330 template<borrowed_range _Rng>
331 requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
335 noexcept(
noexcept(
subrange(ranges::begin(__r), ranges::end(__r), __n)))
336 requires (
_Kind == subrange_kind::sized)
337 :
subrange{ranges::begin(__r), ranges::end(__r), __n}
340 template<__detail::__different_from<subrange> _PairLike>
341 requires __detail::__pair_like_convertible_from<
_PairLike,
const _It&,
355 constexpr _Sent
end()
const {
return _M_end; }
357 constexpr bool empty()
const {
return _M_begin == _M_end; }
359 constexpr __size_type
360 size()
const requires (
_Kind == subrange_kind::sized)
362 if constexpr (_S_store_size)
363 return _M_size._M_size;
365 return __detail::__to_unsigned_like(_M_end - _M_begin);
401 ranges::advance(_M_begin, __n);
402 if constexpr (_S_store_size)
403 _M_size._M_size += __detail::__to_unsigned_like(-__n);
407 __glibcxx_assert(__n >= 0);
408 auto __d = __n - ranges::advance(_M_begin, __n, _M_end);
409 if constexpr (_S_store_size)
410 _M_size._M_size -= __detail::__to_unsigned_like(__d);
415 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
418 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
423 template<borrowed_range _Rng>
428 ? subrange_kind::sized : subrange_kind::unsized>;
430 template<borrowed_range _Rng>
438 template<
size_t _Num,
class _It,
class _Sent, subrange_kind _Kind>
443 if constexpr (
_Num == 0)
449 template<
size_t _Num,
class _It,
class _Sent, subrange_kind _Kind>
454 if constexpr (
_Num == 0)
460 template<
typename _It,
typename _Sent, subrange_kind _Kind>
461 inline constexpr bool
462 enable_borrowed_range<subrange<_It, _Sent, _Kind>> =
true;
464 template<range _Range>
465 using borrowed_subrange_t = __conditional_t<borrowed_range<_Range>,
466 subrange<iterator_t<_Range>>,
476 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
477 typename _Proj =
identity>
478 requires indirect_binary_predicate<ranges::equal_to,
479 projected<_Iter, _Proj>,
const _Tp*>
481 operator()(_Iter __first, _Sent __last,
482 const _Tp& __value, _Proj __proj = {})
const
484 while (__first != __last
490 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
491 requires indirect_binary_predicate<ranges::equal_to,
492 projected<iterator_t<_Range>, _Proj>,
494 constexpr borrowed_iterator_t<_Range>
495 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
497 return (*
this)(ranges::begin(__r), ranges::end(__r),
502 inline constexpr __find_fn find{};
506 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
507 typename _Proj =
identity,
508 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
510 operator()(_Iter __first, _Sent __last,
511 _Pred __pred, _Proj __proj = {})
const
513 while (__first != __last
519 template<input_range _Range,
typename _Proj = identity,
520 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
522 constexpr borrowed_iterator_t<_Range>
523 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
525 return (*
this)(ranges::begin(__r), ranges::end(__r),
530 inline constexpr __find_if_fn find_if{};
532 struct __find_if_not_fn
534 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
535 typename _Proj =
identity,
536 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
538 operator()(_Iter __first, _Sent __last,
539 _Pred __pred, _Proj __proj = {})
const
541 while (__first != __last
547 template<input_range _Range,
typename _Proj = identity,
548 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
550 constexpr borrowed_iterator_t<_Range>
551 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
553 return (*
this)(ranges::begin(__r), ranges::end(__r),
558 inline constexpr __find_if_not_fn find_if_not{};
560 template<
typename _Iter1,
typename _Iter2>
563 [[no_unique_address]] _Iter1 in1;
564 [[no_unique_address]] _Iter2 in2;
566 template<
typename _IIter1,
typename _IIter2>
567 requires convertible_to<const _Iter1&, _IIter1>
568 && convertible_to<const _Iter2&, _IIter2>
570 operator in_in_result<_IIter1, _IIter2>() const &
571 {
return {in1, in2}; }
573 template<
typename _IIter1,
typename _IIter2>
574 requires convertible_to<_Iter1, _IIter1>
575 && convertible_to<_Iter2, _IIter2>
577 operator in_in_result<_IIter1, _IIter2>() &&
581 template<
typename _Iter1,
typename _Iter2>
582 using mismatch_result = in_in_result<_Iter1, _Iter2>;
586 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
587 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
588 typename _Pred = ranges::equal_to,
589 typename _Proj1 =
identity,
typename _Proj2 =
identity>
590 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
591 constexpr mismatch_result<_Iter1, _Iter2>
592 operator()(_Iter1 __first1, _Sent1 __last1,
593 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
594 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
596 while (__first1 != __last1 && __first2 != __last2
607 template<input_range _Range1, input_range _Range2,
608 typename _Pred = ranges::equal_to,
609 typename _Proj1 = identity,
typename _Proj2 = identity>
610 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
611 _Pred, _Proj1, _Proj2>
612 constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>>
613 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
614 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
616 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
617 ranges::begin(__r2), ranges::end(__r2),
623 inline constexpr __mismatch_fn mismatch{};
627 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
628 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
629 typename _Pred = ranges::equal_to,
630 typename _Proj1 =
identity,
typename _Proj2 =
identity>
631 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
632 constexpr subrange<_Iter1>
633 operator()(_Iter1 __first1, _Sent1 __last1,
634 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
635 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
637 if (__first1 == __last1 || __first2 == __last2)
638 return {__first1, __first1};
644 if (__first1 == __last1)
645 return {__first1, __first1};
652 auto __cur1 = __first1;
653 auto __cur2 = __first2;
656 if (++__cur2 == __last2)
657 return {__first1, ++__cur1};
658 if (++__cur1 == __last1)
659 return {__cur1, __cur1};
671 template<forward_range _Range1, forward_range _Range2,
672 typename _Pred = ranges::equal_to,
673 typename _Proj1 = identity,
typename _Proj2 = identity>
674 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
675 _Pred, _Proj1, _Proj2>
676 constexpr borrowed_subrange_t<_Range1>
677 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
678 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
680 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
681 ranges::begin(__r2), ranges::end(__r2),
687 inline constexpr __search_fn search{};
691 template<
typename _Tp,
typename _Proj = identity,
692 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
693 _Comp = ranges::less>
695 operator()(
const _Tp& __a,
const _Tp& __b,
696 _Comp __comp = {}, _Proj __proj = {})
const
706 template<input_range _Range,
typename _Proj = identity,
707 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
708 _Comp = ranges::less>
709 requires indirectly_copyable_storable<iterator_t<_Range>,
710 range_value_t<_Range>*>
711 constexpr range_value_t<_Range>
712 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
714 auto __first = ranges::begin(__r);
715 auto __last = ranges::end(__r);
716 __glibcxx_assert(__first != __last);
717 auto __result = *__first;
718 while (++__first != __last)
720 auto __tmp = *__first;
729 template<copyable _Tp,
typename _Proj = identity,
730 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
731 _Comp = ranges::less>
733 operator()(initializer_list<_Tp> __r,
734 _Comp __comp = {}, _Proj __proj = {})
const
736 return (*
this)(ranges::subrange(__r),
741 inline constexpr __min_fn min{};
743 struct __adjacent_find_fn
745 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
746 typename _Proj =
identity,
747 indirect_binary_predicate<projected<_Iter, _Proj>,
748 projected<_Iter, _Proj>> _Pred
751 operator()(_Iter __first, _Sent __last,
752 _Pred __pred = {}, _Proj __proj = {})
const
754 if (__first == __last)
756 auto __next = __first;
757 for (; ++__next != __last; __first = __next)
767 template<forward_range _Range,
typename _Proj = identity,
768 indirect_binary_predicate<
769 projected<iterator_t<_Range>, _Proj>,
770 projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to>
771 constexpr borrowed_iterator_t<_Range>
772 operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {})
const
774 return (*
this)(ranges::begin(__r), ranges::end(__r),
779 inline constexpr __adjacent_find_fn adjacent_find{};
785 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
786 struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
787 : integral_constant<size_t, 2>
790 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
791 struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
792 {
using type = _Iter; };
794 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
795 struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
796 {
using type = _Sent; };
798 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
799 struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>>
800 {
using type = _Iter; };
802 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
803 struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>>
804 {
using type = _Sent; };
806_GLIBCXX_END_NAMESPACE_VERSION
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
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.
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
ISO C++ entities toplevel namespace is std.
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 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.
The ranges::view_interface class template.
The ranges::subrange class template.
Finds the size of a given tuple type.
[concept.derived], concept derived_from
[concept.convertible], concept convertible_to
[concept.defaultinitializable], concept default_initializable
[range.range] The range concept.
[range.range] The borrowed_range concept.
[range.sized] The sized_range concept.
[range.view] The ranges::view concept.
A range for which ranges::begin returns an input iterator.
A range for which ranges::begin returns a forward iterator.
A range for which ranges::begin returns a bidirectional iterator.
A range for which ranges::begin and ranges::end return the same type.