31#define _RANGES_UTIL_H 1
33#if __cplusplus > 201703L
38#if __glibcxx_tuple_like
42#ifdef __glibcxx_ranges
43namespace std _GLIBCXX_VISIBILITY(default)
45_GLIBCXX_BEGIN_NAMESPACE_VERSION
52 template<
typename _Range>
53 concept __simple_view = view<_Range> && range<const _Range>
54 && same_as<iterator_t<_Range>, iterator_t<const _Range>>
55 && same_as<sentinel_t<_Range>, sentinel_t<const _Range>>;
59 template<
typename _It>
60 concept __has_arrow = input_iterator<_It>
62 ||
requires(
const _It __it) { __it.operator->(); });
64 using std::__detail::__different_from;
68 template<
typename _Derived>
69 requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
73 constexpr _Derived& _M_derived()
noexcept
77 return static_cast<_Derived&
>(*this);
80 constexpr const _Derived& _M_derived()
const noexcept
84 return static_cast<const _Derived&
>(*this);
88 _S_bool(
bool)
noexcept;
90 template<
typename _Tp>
93 noexcept(
noexcept(_S_bool(ranges::begin(__t) == ranges::end(__t))))
94 {
return ranges::begin(__t) == ranges::end(__t); }
96 template<
typename _Tp>
99 noexcept(
noexcept(ranges::end(__t) - ranges::begin(__t)))
100 {
return ranges::end(__t) - ranges::begin(__t); }
105 noexcept(
noexcept(_S_empty(_M_derived())))
107 {
return _S_empty(_M_derived()); }
111 noexcept(
noexcept(ranges::size(_M_derived()) == 0))
113 {
return ranges::size(_M_derived()) == 0; }
117 noexcept(
noexcept(_S_empty(_M_derived())))
119 {
return _S_empty(_M_derived()); }
123 noexcept(
noexcept(ranges::size(_M_derived()) == 0))
125 {
return ranges::size(_M_derived()) == 0; }
128 operator bool()
noexcept(
noexcept(ranges::empty(_M_derived())))
129 requires requires { ranges::empty(_M_derived()); }
130 {
return !ranges::empty(_M_derived()); }
133 operator bool()
const noexcept(
noexcept(ranges::empty(_M_derived())))
134 requires requires { ranges::empty(_M_derived()); }
135 {
return !ranges::empty(_M_derived()); }
138 data()
noexcept(
noexcept(ranges::begin(_M_derived())))
143 data()
const noexcept(
noexcept(ranges::begin(_M_derived())))
149 size()
noexcept(
noexcept(_S_size(_M_derived())))
152 {
return _S_size(_M_derived()); }
155 size()
const noexcept(
noexcept(_S_size(_M_derived())))
159 {
return _S_size(_M_derived()); }
161 constexpr decltype(
auto)
164 __glibcxx_assert(!empty());
165 return *ranges::begin(_M_derived());
168 constexpr decltype(
auto)
171 __glibcxx_assert(!empty());
172 return *ranges::begin(_M_derived());
175 constexpr decltype(
auto)
179 __glibcxx_assert(!empty());
180 return *ranges::prev(ranges::end(_M_derived()));
183 constexpr decltype(
auto)
188 __glibcxx_assert(!empty());
189 return *ranges::prev(ranges::end(_M_derived()));
192 template<random_access_range _Range = _Derived>
193 constexpr decltype(
auto)
195 {
return ranges::begin(_M_derived())[__n]; }
197 template<random_access_range _Range = const _Derived>
198 constexpr decltype(
auto)
200 {
return ranges::begin(_M_derived())[__n]; }
202#if __cplusplus > 202002L
205 {
return ranges::cbegin(_M_derived()); }
209 {
return ranges::cbegin(_M_derived()); }
213 {
return ranges::cend(_M_derived()); }
217 {
return ranges::cend(_M_derived()); }
223 template<
typename _From,
typename _To>
224 concept __uses_nonqualification_pointer_conversion
229 template<
typename _From,
typename _To>
234#if __glibcxx_tuple_like
238 template<
typename _Tp>
247 {
get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
251 template<
typename _Tp,
typename _Up,
typename _Vp>
252 concept __pair_like_convertible_from
253 = !range<_Tp> && !is_reference_v<_Tp> && __pair_like<_Tp>
254 && constructible_from<_Tp, _Up, _Vp>
255 && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>>
256 && convertible_to<_Vp, tuple_element_t<1, _Tp>>;
260 namespace views {
struct _Drop; }
262 enum class subrange_kind :
bool { unsized, sized };
265 template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
266 subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
267 ? subrange_kind::sized : subrange_kind::unsized>
268 requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
272 static constexpr bool _S_store_size
275 friend struct views::_Drop;
277 _It _M_begin = _It();
281 = __detail::__make_unsigned_like_t<iter_difference_t<_It>>;
283 template<
typename _Tp,
bool = _S_store_size>
286 [[__gnu__::__always_inline__]]
287 constexpr _Size(_Tp = {}) { }
290 template<
typename _Tp>
291 struct _Size<_Tp,
true>
293 [[__gnu__::__always_inline__]]
294 constexpr _Size(_Tp
__s = {}) : _M_size(
__s) { }
305 subrange(__detail::__convertible_to_non_slicing<_It>
auto __i, _Sent
__s)
306 noexcept(is_nothrow_constructible_v<_It,
decltype(__i)>
308 requires (!_S_store_size)
313 subrange(__detail::__convertible_to_non_slicing<_It>
auto __i, _Sent
__s,
315 noexcept(is_nothrow_constructible_v<_It,
decltype(__i)>
317 requires (
_Kind == subrange_kind::sized)
321 template<__detail::__different_from<subrange> _Rng>
323 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
327 noexcept(
noexcept(
subrange(__r, ranges::size(__r))))
332 template<__detail::__different_from<subrange> _Rng>
334 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
338 noexcept(
noexcept(
subrange(ranges::begin(__r), ranges::end(__r))))
339 requires (!_S_store_size)
340 :
subrange(ranges::begin(__r), ranges::end(__r))
343 template<borrowed_range _Rng>
344 requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
348 noexcept(
noexcept(
subrange(ranges::begin(__r), ranges::end(__r), __n)))
349 requires (
_Kind == subrange_kind::sized)
350 :
subrange{ranges::begin(__r), ranges::end(__r), __n}
353 template<__detail::__different_from<subrange> _PairLike>
354 requires __detail::__pair_like_convertible_from<
_PairLike,
const _It&,
368 constexpr _Sent
end()
const {
return _M_end; }
370 constexpr bool empty()
const {
return _M_begin == _M_end; }
372 constexpr __size_type
373 size()
const requires (
_Kind == subrange_kind::sized)
375 if constexpr (_S_store_size)
376 return _M_size._M_size;
378 return __detail::__to_unsigned_like(_M_end - _M_begin);
414 ranges::advance(_M_begin, __n);
415 if constexpr (_S_store_size)
416 _M_size._M_size += __detail::__to_unsigned_like(-__n);
420 __glibcxx_assert(__n >= 0);
421 auto __d = __n - ranges::advance(_M_begin, __n, _M_end);
422 if constexpr (_S_store_size)
423 _M_size._M_size -= __detail::__to_unsigned_like(__d);
428 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
431 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
436 template<borrowed_range _Rng>
441 ? subrange_kind::sized : subrange_kind::unsized>;
443 template<borrowed_range _Rng>
451 template<
size_t _Num,
class _It,
class _Sent, subrange_kind _Kind>
456 if constexpr (
_Num == 0)
462 template<
size_t _Num,
class _It,
class _Sent, subrange_kind _Kind>
467 if constexpr (
_Num == 0)
473 template<
typename _It,
typename _Sent, subrange_kind _Kind>
474 inline constexpr bool
475 enable_borrowed_range<subrange<_It, _Sent, _Kind>> =
true;
477 template<range _Range>
478 using borrowed_subrange_t = __conditional_t<borrowed_range<_Range>,
479 subrange<iterator_t<_Range>>,
483 template<
typename _Iter,
typename _Sent, subrange_kind _Kind>
484 inline constexpr bool __detail::__is_subrange<subrange<_Iter, _Sent, _Kind>> =
true;
487#if __glibcxx_tuple_like
489 template<
typename _It,
typename _Sent, ranges::subrange_kind _Kind>
490 inline constexpr bool __is_tuple_like_v<ranges::subrange<_It, _Sent, _Kind>> =
true;
499 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
500 typename _Proj =
identity,
501 typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
502 requires indirect_binary_predicate<ranges::equal_to,
503 projected<_Iter, _Proj>,
const _Tp*>
505 operator()(_Iter __first, _Sent __last,
506 const _Tp& __value, _Proj __proj = {})
const
508 if constexpr (is_same_v<_Proj, identity>)
509 if constexpr(__can_use_memchr_for_find<iter_value_t<_Iter>, _Tp>)
510 if constexpr (sized_sentinel_for<_Sent, _Iter>)
511 if constexpr (contiguous_iterator<_Iter>)
512 if (!is_constant_evaluated())
514 using _Vt = iter_value_t<_Iter>;
515 auto __n = __last - __first;
516 if (
static_cast<_Vt
>(__value) == __value) [[likely]]
519 const size_t __nu =
static_cast<size_t>(__n);
520 const int __ival =
static_cast<int>(__value);
522 if (
auto __p1 = __builtin_memchr(__p0, __ival, __nu))
523 __n = (
const char*)__p1 - (
const char*)__p0;
525 return __first + __n;
528 while (__first != __last
534 template<input_range _Range,
typename _Proj = identity,
536 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)>
537 requires indirect_binary_predicate<ranges::equal_to,
538 projected<iterator_t<_Range>, _Proj>,
540 constexpr borrowed_iterator_t<_Range>
541 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
543 return (*
this)(ranges::begin(__r), ranges::end(__r),
548 inline constexpr __find_fn find{};
552 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
553 typename _Proj =
identity,
554 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
556 operator()(_Iter __first, _Sent __last,
557 _Pred __pred, _Proj __proj = {})
const
559 while (__first != __last
565 template<input_range _Range,
typename _Proj = identity,
566 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
568 constexpr borrowed_iterator_t<_Range>
569 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
571 return (*
this)(ranges::begin(__r), ranges::end(__r),
576 inline constexpr __find_if_fn find_if{};
578 struct __find_if_not_fn
580 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
581 typename _Proj =
identity,
582 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
584 operator()(_Iter __first, _Sent __last,
585 _Pred __pred, _Proj __proj = {})
const
587 while (__first != __last
593 template<input_range _Range,
typename _Proj = identity,
594 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
596 constexpr borrowed_iterator_t<_Range>
597 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
599 return (*
this)(ranges::begin(__r), ranges::end(__r),
604 inline constexpr __find_if_not_fn find_if_not{};
606 template<
typename _Iter1,
typename _Iter2>
609 [[no_unique_address]] _Iter1 in1;
610 [[no_unique_address]] _Iter2 in2;
612 template<
typename _IIter1,
typename _IIter2>
613 requires convertible_to<const _Iter1&, _IIter1>
614 && convertible_to<const _Iter2&, _IIter2>
616 operator in_in_result<_IIter1, _IIter2>() const &
617 {
return {in1, in2}; }
619 template<
typename _IIter1,
typename _IIter2>
620 requires convertible_to<_Iter1, _IIter1>
621 && convertible_to<_Iter2, _IIter2>
623 operator in_in_result<_IIter1, _IIter2>() &&
627 template<
typename _Iter1,
typename _Iter2>
628 using mismatch_result = in_in_result<_Iter1, _Iter2>;
632 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
633 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
634 typename _Pred = ranges::equal_to,
635 typename _Proj1 =
identity,
typename _Proj2 =
identity>
636 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
637 constexpr mismatch_result<_Iter1, _Iter2>
638 operator()(_Iter1 __first1, _Sent1 __last1,
639 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
640 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
642 while (__first1 != __last1 && __first2 != __last2
653 template<input_range _Range1, input_range _Range2,
654 typename _Pred = ranges::equal_to,
655 typename _Proj1 = identity,
typename _Proj2 = identity>
656 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
657 _Pred, _Proj1, _Proj2>
658 constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>>
659 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
660 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
662 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
663 ranges::begin(__r2), ranges::end(__r2),
669 inline constexpr __mismatch_fn mismatch{};
673 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
674 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
675 typename _Pred = ranges::equal_to,
676 typename _Proj1 =
identity,
typename _Proj2 =
identity>
677 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
678 constexpr subrange<_Iter1>
679 operator()(_Iter1 __first1, _Sent1 __last1,
680 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
681 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
683 if (__first1 == __last1 || __first2 == __last2)
684 return {__first1, __first1};
690 if (__first1 == __last1)
691 return {__first1, __first1};
698 auto __cur1 = __first1;
699 auto __cur2 = __first2;
702 if (++__cur2 == __last2)
703 return {__first1, ++__cur1};
704 if (++__cur1 == __last1)
705 return {__cur1, __cur1};
717 template<forward_range _Range1, forward_range _Range2,
718 typename _Pred = ranges::equal_to,
719 typename _Proj1 = identity,
typename _Proj2 = identity>
720 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
721 _Pred, _Proj1, _Proj2>
722 constexpr borrowed_subrange_t<_Range1>
723 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
724 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
726 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
727 ranges::begin(__r2), ranges::end(__r2),
733 inline constexpr __search_fn search{};
737 template<
typename _Tp,
typename _Proj = identity,
738 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
739 _Comp = ranges::less>
741 operator()(
const _Tp& __a,
const _Tp& __b,
742 _Comp __comp = {}, _Proj __proj = {})
const
752 template<input_range _Range,
typename _Proj = identity,
753 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
754 _Comp = ranges::less>
755 requires indirectly_copyable_storable<iterator_t<_Range>,
756 range_value_t<_Range>*>
757 constexpr range_value_t<_Range>
758 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
760 auto __first = ranges::begin(__r);
761 auto __last = ranges::end(__r);
762 __glibcxx_assert(__first != __last);
763 auto __result = *__first;
764 while (++__first != __last)
766 auto&& __tmp = *__first;
775 template<copyable _Tp,
typename _Proj = identity,
776 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
777 _Comp = ranges::less>
779 operator()(initializer_list<_Tp> __r,
780 _Comp __comp = {}, _Proj __proj = {})
const
782 return (*
this)(ranges::subrange(__r),
787 inline constexpr __min_fn min{};
789 struct __adjacent_find_fn
791 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
792 typename _Proj =
identity,
793 indirect_binary_predicate<projected<_Iter, _Proj>,
794 projected<_Iter, _Proj>> _Pred
797 operator()(_Iter __first, _Sent __last,
798 _Pred __pred = {}, _Proj __proj = {})
const
800 if (__first == __last)
802 auto __next = __first;
803 for (; ++__next != __last; __first = __next)
813 template<forward_range _Range,
typename _Proj = identity,
814 indirect_binary_predicate<
815 projected<iterator_t<_Range>, _Proj>,
816 projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to>
817 constexpr borrowed_iterator_t<_Range>
818 operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {})
const
820 return (*
this)(ranges::begin(__r), ranges::end(__r),
825 inline constexpr __adjacent_find_fn adjacent_find{};
831 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
832 struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
833 : integral_constant<size_t, 2>
836 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
837 struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
838 {
using type = _Iter; };
840 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
841 struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
842 {
using type = _Sent; };
844 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
845 struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>>
846 {
using type = _Iter; };
848 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
849 struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>>
850 {
using type = _Sent; };
852_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 void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
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.