31#define _RANGES_UTIL_H 1
33#if __cplusplus > 201703L
38#ifdef __glibcxx_ranges
39namespace std _GLIBCXX_VISIBILITY(default)
41_GLIBCXX_BEGIN_NAMESPACE_VERSION
48 template<
typename _Range>
49 concept __simple_view = view<_Range> && range<const _Range>
50 && same_as<iterator_t<_Range>, iterator_t<const _Range>>
51 && same_as<sentinel_t<_Range>, sentinel_t<const _Range>>;
53 template<
typename _It>
54 concept __has_arrow = input_iterator<_It>
55 && (is_pointer_v<_It> ||
requires(_It __it) { __it.operator->(); });
57 using std::__detail::__different_from;
61 template<
typename _Derived>
62 requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
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);
81 _S_bool(
bool)
noexcept;
83 template<
typename _Tp>
86 noexcept(
noexcept(_S_bool(ranges::begin(__t) == ranges::end(__t))))
87 {
return ranges::begin(__t) == ranges::end(__t); }
89 template<
typename _Tp>
92 noexcept(
noexcept(ranges::end(__t) - ranges::begin(__t)))
93 {
return ranges::end(__t) - ranges::begin(__t); }
98 noexcept(
noexcept(_S_empty(_M_derived())))
99 requires forward_range<_Derived> && (!sized_range<_Derived>)
100 {
return _S_empty(_M_derived()); }
104 noexcept(
noexcept(ranges::size(_M_derived()) == 0))
105 requires sized_range<_Derived>
106 {
return ranges::size(_M_derived()) == 0; }
110 noexcept(
noexcept(_S_empty(_M_derived())))
111 requires forward_range<const _Derived> && (!sized_range<const _Derived>)
112 {
return _S_empty(_M_derived()); }
116 noexcept(
noexcept(ranges::size(_M_derived()) == 0))
117 requires sized_range<const _Derived>
118 {
return ranges::size(_M_derived()) == 0; }
121 operator bool()
noexcept(
noexcept(ranges::empty(_M_derived())))
122 requires requires { ranges::empty(_M_derived()); }
123 {
return !ranges::empty(_M_derived()); }
126 operator bool()
const noexcept(
noexcept(ranges::empty(_M_derived())))
127 requires requires { ranges::empty(_M_derived()); }
128 {
return !ranges::empty(_M_derived()); }
131 data()
noexcept(
noexcept(ranges::begin(_M_derived())))
132 requires contiguous_iterator<iterator_t<_Derived>>
136 data()
const noexcept(
noexcept(ranges::begin(_M_derived())))
137 requires range<const _Derived>
138 && contiguous_iterator<iterator_t<const _Derived>>
142 size()
noexcept(
noexcept(_S_size(_M_derived())))
143 requires forward_range<_Derived>
144 && sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>>
145 {
return _S_size(_M_derived()); }
148 size()
const noexcept(
noexcept(_S_size(_M_derived())))
149 requires forward_range<const _Derived>
150 && sized_sentinel_for<sentinel_t<const _Derived>,
151 iterator_t<const _Derived>>
152 {
return _S_size(_M_derived()); }
154 constexpr decltype(
auto)
155 front()
requires forward_range<_Derived>
157 __glibcxx_assert(!empty());
158 return *ranges::begin(_M_derived());
161 constexpr decltype(
auto)
162 front()
const requires forward_range<const _Derived>
164 __glibcxx_assert(!empty());
165 return *ranges::begin(_M_derived());
168 constexpr decltype(
auto)
170 requires bidirectional_range<_Derived> && common_range<_Derived>
172 __glibcxx_assert(!empty());
173 return *ranges::prev(ranges::end(_M_derived()));
176 constexpr decltype(
auto)
178 requires bidirectional_range<const _Derived>
179 && common_range<const _Derived>
181 __glibcxx_assert(!empty());
182 return *ranges::prev(ranges::end(_M_derived()));
185 template<random_access_range _Range = _Derived>
186 constexpr decltype(
auto)
187 operator[](range_difference_t<_Range> __n)
188 {
return ranges::begin(_M_derived())[__n]; }
190 template<random_access_range _Range = const _Derived>
191 constexpr decltype(
auto)
192 operator[](range_difference_t<_Range> __n)
const
193 {
return ranges::begin(_M_derived())[__n]; }
195#if __cplusplus > 202002L
197 cbegin()
requires input_range<_Derived>
198 {
return ranges::cbegin(_M_derived()); }
201 cbegin()
const requires input_range<const _Derived>
202 {
return ranges::cbegin(_M_derived()); }
205 cend()
requires input_range<_Derived>
206 {
return ranges::cend(_M_derived()); }
209 cend()
const requires input_range<const _Derived>
210 {
return ranges::cend(_M_derived()); }
216 template<
typename _From,
typename _To>
217 concept __uses_nonqualification_pointer_conversion
218 = is_pointer_v<_From> && is_pointer_v<_To>
219 && !convertible_to<remove_pointer_t<_From>(*)[],
222 template<
typename _From,
typename _To>
223 concept __convertible_to_non_slicing = convertible_to<_From, _To>
224 && !__uses_nonqualification_pointer_conversion<decay_t<_From>,
227#if __glibcxx_tuple_like
231 template<
typename _Tp>
233 = !is_reference_v<_Tp> &&
requires(_Tp __t)
237 typename tuple_element_t<0, remove_const_t<_Tp>>;
238 typename tuple_element_t<1, remove_const_t<_Tp>>;
239 { get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>;
240 { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
244 template<
typename _Tp,
typename _Up,
typename _Vp>
245 concept __pair_like_convertible_from
246 = !range<_Tp> && !is_reference_v<_Vp> && __pair_like<_Tp>
247 && constructible_from<_Tp, _Up, _Vp>
248 && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>>
249 && convertible_to<_Vp, tuple_element_t<1, _Tp>>;
253 namespace views {
struct _Drop; }
255 enum class subrange_kind :
bool { unsized, sized };
258 template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
259 subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
260 ? subrange_kind::sized : subrange_kind::unsized>
261 requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
265 static constexpr bool _S_store_size
266 = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;
268 friend struct views::_Drop;
270 _It _M_begin = _It();
271 [[no_unique_address]] _Sent _M_end = _Sent();
274 = __detail::__make_unsigned_like_t<iter_difference_t<_It>>;
276 template<
typename _Tp,
bool = _S_store_size>
279 [[__gnu__::__always_inline__]]
280 constexpr _Size(_Tp = {}) { }
283 template<
typename _Tp>
284 struct _Size<_Tp, true>
286 [[__gnu__::__always_inline__]]
287 constexpr _Size(_Tp __s = {}) : _M_size(__s) { }
292 [[no_unique_address]] _Size<__size_type> _M_size = {};
295 subrange()
requires default_initializable<_It> =
default;
298 subrange(__detail::__convertible_to_non_slicing<_It>
auto __i, _Sent __s)
299 noexcept(is_nothrow_constructible_v<_It,
decltype(__i)>
300 && is_nothrow_constructible_v<_Sent, _Sent&>)
301 requires (!_S_store_size)
306 subrange(__detail::__convertible_to_non_slicing<_It>
auto __i, _Sent __s,
308 noexcept(is_nothrow_constructible_v<_It,
decltype(__i)>
309 && is_nothrow_constructible_v<_Sent, _Sent&>)
310 requires (_Kind == subrange_kind::sized)
311 : _M_begin(
std::move(__i)), _M_end(__s), _M_size(__n)
314 template<__detail::__different_from<subrange> _Rng>
315 requires borrowed_range<_Rng>
316 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
317 && convertible_to<sentinel_t<_Rng>, _Sent>
320 noexcept(
noexcept(
subrange(__r, ranges::size(__r))))
321 requires _S_store_size && sized_range<_Rng>
325 template<__detail::__different_from<subrange> _Rng>
326 requires borrowed_range<_Rng>
327 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
328 && convertible_to<sentinel_t<_Rng>, _Sent>
331 noexcept(
noexcept(
subrange(ranges::begin(__r), ranges::end(__r))))
332 requires (!_S_store_size)
333 :
subrange(ranges::begin(__r), ranges::end(__r))
336 template<borrowed_range _Rng>
337 requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
338 && convertible_to<sentinel_t<_Rng>, _Sent>
340 subrange(_Rng&& __r, __size_type __n)
341 noexcept(
noexcept(
subrange(ranges::begin(__r), ranges::end(__r), __n)))
342 requires (_Kind == subrange_kind::sized)
343 :
subrange{ranges::begin(__r), ranges::end(__r), __n}
346 template<__detail::__different_from<subrange> _PairLike>
347 requires __detail::__pair_like_convertible_from<_PairLike,
const _It&,
350 operator _PairLike()
const
351 {
return _PairLike(_M_begin, _M_end); }
354 begin()
const requires copyable<_It>
357 [[nodiscard]]
constexpr _It
358 begin()
requires (!copyable<_It>)
361 constexpr _Sent
end()
const {
return _M_end; }
363 constexpr bool empty()
const {
return _M_begin == _M_end; }
365 constexpr __size_type
366 size()
const requires (_Kind == subrange_kind::sized)
368 if constexpr (_S_store_size)
369 return _M_size._M_size;
371 return __detail::__to_unsigned_like(_M_end - _M_begin);
375 next(iter_difference_t<_It> __n = 1)
const &
376 requires forward_iterator<_It>
384 next(iter_difference_t<_It> __n = 1) &&
391 prev(iter_difference_t<_It> __n = 1)
const
392 requires bidirectional_iterator<_It>
400 advance(iter_difference_t<_It> __n)
404 if constexpr (bidirectional_iterator<_It>)
407 ranges::advance(_M_begin, __n);
408 if constexpr (_S_store_size)
409 _M_size._M_size += __detail::__to_unsigned_like(-__n);
413 __glibcxx_assert(__n >= 0);
414 auto __d = __n - ranges::advance(_M_begin, __n, _M_end);
415 if constexpr (_S_store_size)
416 _M_size._M_size -= __detail::__to_unsigned_like(__d);
421 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
424 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
426 __detail::__make_unsigned_like_t<iter_difference_t<_It>>)
429 template<borrowed_range _Rng>
433 || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
434 ? subrange_kind::sized : subrange_kind::unsized>;
436 template<borrowed_range _Rng>
438 __detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
444 template<
size_t _Num,
class _It,
class _Sent, subrange_kind _Kind>
445 requires ((_Num == 0 && copyable<_It>) || _Num == 1)
449 if constexpr (_Num == 0)
455 template<
size_t _Num,
class _It,
class _Sent, subrange_kind _Kind>
458 get(subrange<_It, _Sent, _Kind>&& __r)
460 if constexpr (_Num == 0)
466 template<
typename _It,
typename _Sent, subrange_kind _Kind>
467 inline constexpr bool
468 enable_borrowed_range<subrange<_It, _Sent, _Kind>> =
true;
470 template<range _Range>
471 using borrowed_subrange_t = __conditional_t<borrowed_range<_Range>,
472 subrange<iterator_t<_Range>>,
476 template<
typename _Iter,
typename _Sent, subrange_kind _Kind>
477 inline constexpr bool __detail::__is_subrange<subrange<_Iter, _Sent, _Kind>> =
true;
480#if __glibcxx_tuple_like
482 template<
typename _It,
typename _Sent, ranges::subrange_kind _Kind>
483 inline constexpr bool __is_tuple_like_v<ranges::subrange<_It, _Sent, _Kind>> =
true;
492 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
493 typename _Proj =
identity>
494 requires indirect_binary_predicate<ranges::equal_to,
495 projected<_Iter, _Proj>,
const _Tp*>
497 operator()(_Iter __first, _Sent __last,
498 const _Tp& __value, _Proj __proj = {})
const
500 while (__first != __last
506 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
507 requires indirect_binary_predicate<ranges::equal_to,
508 projected<iterator_t<_Range>, _Proj>,
510 constexpr borrowed_iterator_t<_Range>
511 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
513 return (*
this)(ranges::begin(__r), ranges::end(__r),
518 inline constexpr __find_fn find{};
522 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
523 typename _Proj =
identity,
524 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
526 operator()(_Iter __first, _Sent __last,
527 _Pred __pred, _Proj __proj = {})
const
529 while (__first != __last
535 template<input_range _Range,
typename _Proj = identity,
536 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
538 constexpr borrowed_iterator_t<_Range>
539 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
541 return (*
this)(ranges::begin(__r), ranges::end(__r),
546 inline constexpr __find_if_fn find_if{};
548 struct __find_if_not_fn
550 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
551 typename _Proj =
identity,
552 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
554 operator()(_Iter __first, _Sent __last,
555 _Pred __pred, _Proj __proj = {})
const
557 while (__first != __last
563 template<input_range _Range,
typename _Proj = identity,
564 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
566 constexpr borrowed_iterator_t<_Range>
567 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
569 return (*
this)(ranges::begin(__r), ranges::end(__r),
574 inline constexpr __find_if_not_fn find_if_not{};
576 template<
typename _Iter1,
typename _Iter2>
579 [[no_unique_address]] _Iter1 in1;
580 [[no_unique_address]] _Iter2 in2;
582 template<
typename _IIter1,
typename _IIter2>
583 requires convertible_to<const _Iter1&, _IIter1>
584 && convertible_to<const _Iter2&, _IIter2>
586 operator in_in_result<_IIter1, _IIter2>() const &
587 {
return {in1, in2}; }
589 template<
typename _IIter1,
typename _IIter2>
590 requires convertible_to<_Iter1, _IIter1>
591 && convertible_to<_Iter2, _IIter2>
593 operator in_in_result<_IIter1, _IIter2>() &&
597 template<
typename _Iter1,
typename _Iter2>
598 using mismatch_result = in_in_result<_Iter1, _Iter2>;
602 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
603 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
604 typename _Pred = ranges::equal_to,
605 typename _Proj1 =
identity,
typename _Proj2 =
identity>
606 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
607 constexpr mismatch_result<_Iter1, _Iter2>
608 operator()(_Iter1 __first1, _Sent1 __last1,
609 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
610 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
612 while (__first1 != __last1 && __first2 != __last2
623 template<input_range _Range1, input_range _Range2,
624 typename _Pred = ranges::equal_to,
625 typename _Proj1 = identity,
typename _Proj2 = identity>
626 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
627 _Pred, _Proj1, _Proj2>
628 constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>>
629 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
630 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
632 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
633 ranges::begin(__r2), ranges::end(__r2),
639 inline constexpr __mismatch_fn mismatch{};
643 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
644 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
645 typename _Pred = ranges::equal_to,
646 typename _Proj1 =
identity,
typename _Proj2 =
identity>
647 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
648 constexpr subrange<_Iter1>
649 operator()(_Iter1 __first1, _Sent1 __last1,
650 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
651 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
653 if (__first1 == __last1 || __first2 == __last2)
654 return {__first1, __first1};
660 if (__first1 == __last1)
661 return {__first1, __first1};
668 auto __cur1 = __first1;
669 auto __cur2 = __first2;
672 if (++__cur2 == __last2)
673 return {__first1, ++__cur1};
674 if (++__cur1 == __last1)
675 return {__cur1, __cur1};
687 template<forward_range _Range1, forward_range _Range2,
688 typename _Pred = ranges::equal_to,
689 typename _Proj1 = identity,
typename _Proj2 = identity>
690 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
691 _Pred, _Proj1, _Proj2>
692 constexpr borrowed_subrange_t<_Range1>
693 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
694 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
696 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
697 ranges::begin(__r2), ranges::end(__r2),
703 inline constexpr __search_fn search{};
707 template<
typename _Tp,
typename _Proj = identity,
708 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
709 _Comp = ranges::less>
711 operator()(
const _Tp& __a,
const _Tp& __b,
712 _Comp __comp = {}, _Proj __proj = {})
const
722 template<input_range _Range,
typename _Proj = identity,
723 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
724 _Comp = ranges::less>
725 requires indirectly_copyable_storable<iterator_t<_Range>,
726 range_value_t<_Range>*>
727 constexpr range_value_t<_Range>
728 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
730 auto __first = ranges::begin(__r);
731 auto __last = ranges::end(__r);
732 __glibcxx_assert(__first != __last);
733 auto __result = *__first;
734 while (++__first != __last)
736 auto&& __tmp = *__first;
745 template<copyable _Tp,
typename _Proj = identity,
746 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
747 _Comp = ranges::less>
749 operator()(initializer_list<_Tp> __r,
750 _Comp __comp = {}, _Proj __proj = {})
const
752 return (*
this)(ranges::subrange(__r),
757 inline constexpr __min_fn min{};
759 struct __adjacent_find_fn
761 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
762 typename _Proj =
identity,
763 indirect_binary_predicate<projected<_Iter, _Proj>,
764 projected<_Iter, _Proj>> _Pred
767 operator()(_Iter __first, _Sent __last,
768 _Pred __pred = {}, _Proj __proj = {})
const
770 if (__first == __last)
772 auto __next = __first;
773 for (; ++__next != __last; __first = __next)
783 template<forward_range _Range,
typename _Proj = identity,
784 indirect_binary_predicate<
785 projected<iterator_t<_Range>, _Proj>,
786 projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to>
787 constexpr borrowed_iterator_t<_Range>
788 operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {})
const
790 return (*
this)(ranges::begin(__r), ranges::end(__r),
795 inline constexpr __adjacent_find_fn adjacent_find{};
801 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
802 struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
803 : integral_constant<size_t, 2>
806 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
807 struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
808 {
using type = _Iter; };
810 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
811 struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
812 {
using type = _Sent; };
814 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
815 struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>>
816 {
using type = _Iter; };
818 template<
typename _Iter,
typename _Sent, ranges::subrange_kind _Kind>
819 struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>>
820 {
using type = _Sent; };
822_GLIBCXX_END_NAMESPACE_VERSION
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
typename remove_pointer< _Tp >::type remove_pointer_t
Alias template for remove_pointer.
typename decay< _Tp >::type decay_t
Alias template for decay.
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.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
_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.