30#ifndef _RANGES_ALGOBASE_H
31#define _RANGES_ALGOBASE_H 1
33#if __cplusplus > 201703L
44namespace std _GLIBCXX_VISIBILITY(default)
46_GLIBCXX_BEGIN_NAMESPACE_VERSION
51 template<
typename _Tp>
52 constexpr inline bool __is_normal_iterator =
false;
54 template<
typename _Iterator,
typename _Container>
56 __is_normal_iterator<__gnu_cxx::__normal_iterator<_Iterator,
59 template<
typename _Tp>
60 constexpr inline bool __is_reverse_iterator =
false;
62 template<
typename _Iterator>
64 __is_reverse_iterator<reverse_iterator<_Iterator>> =
true;
66 template<
typename _Tp>
67 constexpr inline bool __is_move_iterator =
false;
69 template<
typename _Iterator>
71 __is_move_iterator<move_iterator<_Iterator>> =
true;
74#if __glibcxx_ranges_iota >= 202202L
75 template<
typename _Out,
typename _Tp>
76 struct out_value_result
78 [[no_unique_address]] _Out out;
79 [[no_unique_address]] _Tp value;
81 template<
typename _Out2,
typename _Tp2>
82 requires convertible_to<const _Out&, _Out2>
83 && convertible_to<const _Tp&, _Tp2>
85 operator out_value_result<_Out2, _Tp2>() const &
86 {
return {out, value}; }
88 template<
typename _Out2,
typename _Tp2>
89 requires convertible_to<_Out, _Out2>
90 && convertible_to<_Tp, _Tp2>
92 operator out_value_result<_Out2, _Tp2>() &&
96 template<
typename _Out,
typename _Tp>
97 using iota_result = out_value_result<_Out, _Tp>;
101 template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent, weakly_incrementable _Tp>
102 requires indirectly_writable<_Out, const _Tp&>
103 constexpr iota_result<_Out, _Tp>
104 operator()(_Out __first, _Sent __last, _Tp __value)
const
106 while (__first != __last)
108 *__first =
static_cast<const _Tp&
>(__value);
115 template<weakly_incrementable _Tp, output_range<const _Tp&> _Range>
116 constexpr iota_result<borrowed_iterator_t<_Range>, _Tp>
117 operator()(_Range&& __r, _Tp __value)
const
118 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__value)); }
121 inline constexpr __iota_fn
iota{};
126 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
127 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
128 typename _Pred = ranges::equal_to,
129 typename _Proj1 =
identity,
typename _Proj2 =
identity>
130 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
132 operator()(_Iter1 __first1, _Sent1 __last1,
133 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
134 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
138 if constexpr (__detail::__is_normal_iterator<_Iter1>
139 && same_as<_Iter1, _Sent1>)
140 return (*
this)(__first1.base(), __last1.base(),
144 else if constexpr (__detail::__is_normal_iterator<_Iter2>
145 && same_as<_Iter2, _Sent2>)
147 __first2.base(), __last2.base(),
150 else if constexpr (sized_sentinel_for<_Sent1, _Iter1>
151 && sized_sentinel_for<_Sent2, _Iter2>)
153 auto __d1 = ranges::distance(__first1, __last1);
154 auto __d2 = ranges::distance(__first2, __last2);
158 using _ValueType1 = iter_value_t<_Iter1>;
159 constexpr bool __use_memcmp
160 = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
161 && __memcmpable<_Iter1, _Iter2>::__value
162 && is_same_v<_Pred, ranges::equal_to>
163 && is_same_v<_Proj1, identity>
164 && is_same_v<_Proj2, identity>);
165 if constexpr (__use_memcmp)
167 if (
const size_t __len = (__last1 - __first1))
168 return !std::__memcmp(__first1, __first2, __len);
173 for (; __first1 != __last1; ++__first1, (void)++__first2)
183 for (; __first1 != __last1 && __first2 != __last2;
184 ++__first1, (void)++__first2)
189 return __first1 == __last1 && __first2 == __last2;
193 template<input_range _Range1, input_range _Range2,
194 typename _Pred = ranges::equal_to,
195 typename _Proj1 = identity,
typename _Proj2 = identity>
196 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
197 _Pred, _Proj1, _Proj2>
199 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
200 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
204 if constexpr (sized_range<_Range1>)
205 if constexpr (sized_range<_Range2>)
206 if (ranges::distance(__r1) != ranges::distance(__r2))
209 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
210 ranges::begin(__r2), ranges::end(__r2),
216 inline constexpr __equal_fn equal{};
220 template<
bool _IsMove,
typename _OutIter,
typename _InIter>
221 [[__gnu__::__always_inline__]]
223 __assign_one(_OutIter& __out, _InIter& __in)
225 if constexpr (_IsMove)
226 *__out = ranges::iter_move(__in);
232 template<
typename _Iter,
typename _Out>
235 [[no_unique_address]] _Iter in;
236 [[no_unique_address]] _Out out;
238 template<
typename _Iter2,
typename _Out2>
239 requires convertible_to<const _Iter&, _Iter2>
240 && convertible_to<const _Out&, _Out2>
242 operator in_out_result<_Iter2, _Out2>() const &
243 {
return {in, out}; }
245 template<
typename _Iter2,
typename _Out2>
246 requires convertible_to<_Iter, _Iter2>
247 && convertible_to<_Out, _Out2>
249 operator in_out_result<_Iter2, _Out2>() &&
253 template<
typename _Iter,
typename _Out>
254 using copy_result = in_out_result<_Iter, _Out>;
256 template<
typename _Iter,
typename _Out>
257 using move_result = in_out_result<_Iter, _Out>;
259 template<
typename _Iter1,
typename _Iter2>
260 using move_backward_result = in_out_result<_Iter1, _Iter2>;
262 template<
typename _Iter1,
typename _Iter2>
263 using copy_backward_result = in_out_result<_Iter1, _Iter2>;
265 template<
bool _IsMove,
266 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
267 bidirectional_iterator _Out>
269 ? indirectly_movable<_Iter, _Out>
270 : indirectly_copyable<_Iter, _Out>)
271 constexpr __conditional_t<_IsMove,
272 move_backward_result<_Iter, _Out>,
273 copy_backward_result<_Iter, _Out>>
274 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result);
276 template<
bool _IsMove,
277 input_iterator _Iter, sentinel_for<_Iter> _Sent,
278 weakly_incrementable _Out>
280 ? indirectly_movable<_Iter, _Out>
281 : indirectly_copyable<_Iter, _Out>)
282 constexpr __conditional_t<_IsMove,
283 move_result<_Iter, _Out>,
284 copy_result<_Iter, _Out>>
285 __copy_or_move(_Iter __first, _Sent __last, _Out __result)
289 using __detail::__is_move_iterator;
290 using __detail::__is_reverse_iterator;
291 using __detail::__is_normal_iterator;
292 if constexpr (__is_move_iterator<_Iter> && same_as<_Iter, _Sent>)
295 = ranges::__copy_or_move<true>(
std::move(__first).base(),
300 else if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent>
301 && __is_reverse_iterator<_Out>)
304 = ranges::__copy_or_move_backward<_IsMove>(
std::move(__last).base(),
307 return {reverse_iterator{
std::move(__in)},
310 else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>)
313 = ranges::__copy_or_move<_IsMove>(__first.base(), __last.base(),
315 return {
decltype(__first){__in},
std::move(__out)};
317 else if constexpr (__is_normal_iterator<_Out>)
320 = ranges::__copy_or_move<_IsMove>(
std::move(__first), __last, __result.base());
321 return {
std::move(__in),
decltype(__result){__out}};
323 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
325 if (!std::__is_constant_evaluated())
327 if constexpr (__memcpyable<_Out, _Iter>::__value)
329 using _ValueTypeI = iter_value_t<_Iter>;
330 auto __num = __last - __first;
331 if (__num > 1) [[likely]]
332 __builtin_memmove(__result, __first,
333 sizeof(_ValueTypeI) * __num);
335 __detail::__assign_one<_IsMove>(__result, __first);
336 return {__first + __num, __result + __num};
340 for (
auto __n = __last - __first; __n > 0; --__n)
342 __detail::__assign_one<_IsMove>(__result, __first);
350 while (__first != __last)
352 __detail::__assign_one<_IsMove>(__result, __first);
362 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
363 weakly_incrementable _Out>
364 requires indirectly_copyable<_Iter, _Out>
365 constexpr copy_result<_Iter, _Out>
366 operator()(_Iter __first, _Sent __last, _Out __result)
const
368 return ranges::__copy_or_move<false>(
std::move(__first),
373 template<input_range _Range, weakly_incrementable _Out>
374 requires indirectly_copyable<iterator_t<_Range>, _Out>
375 constexpr copy_result<borrowed_iterator_t<_Range>, _Out>
376 operator()(_Range&& __r, _Out __result)
const
378 return (*
this)(ranges::begin(__r), ranges::end(__r),
383 inline constexpr __copy_fn copy{};
387 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
388 weakly_incrementable _Out>
389 requires indirectly_movable<_Iter, _Out>
390 constexpr move_result<_Iter, _Out>
391 operator()(_Iter __first, _Sent __last, _Out __result)
const
393 return ranges::__copy_or_move<true>(
std::move(__first),
398 template<input_range _Range, weakly_incrementable _Out>
399 requires indirectly_movable<iterator_t<_Range>, _Out>
400 constexpr move_result<borrowed_iterator_t<_Range>, _Out>
401 operator()(_Range&& __r, _Out __result)
const
403 return (*
this)(ranges::begin(__r), ranges::end(__r),
408 inline constexpr __move_fn
move{};
410 template<
bool _IsMove,
411 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
412 bidirectional_iterator _Out>
414 ? indirectly_movable<_Iter, _Out>
415 : indirectly_copyable<_Iter, _Out>)
416 constexpr __conditional_t<_IsMove,
417 move_backward_result<_Iter, _Out>,
418 copy_backward_result<_Iter, _Out>>
419 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result)
423 using __detail::__is_reverse_iterator;
424 using __detail::__is_normal_iterator;
425 if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent>
426 && __is_reverse_iterator<_Out>)
429 = ranges::__copy_or_move<_IsMove>(
std::move(__last).base(),
432 return {reverse_iterator{
std::move(__in)},
435 else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>)
438 = ranges::__copy_or_move_backward<_IsMove>(__first.base(),
441 return {
decltype(__first){__in},
std::move(__out)};
443 else if constexpr (__is_normal_iterator<_Out>)
446 = ranges::__copy_or_move_backward<_IsMove>(
std::move(__first),
449 return {
std::move(__in),
decltype(__result){__out}};
451 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
453 if (!std::__is_constant_evaluated())
455 if constexpr (__memcpyable<_Out, _Iter>::__value)
457 using _ValueTypeI = iter_value_t<_Iter>;
458 auto __num = __last - __first;
460 if (__num > 1) [[likely]]
461 __builtin_memmove(__result, __first,
462 sizeof(_ValueTypeI) * __num);
464 __detail::__assign_one<_IsMove>(__result, __first);
465 return {__first + __num, __result};
469 auto __lasti = ranges::next(__first, __last);
470 auto __tail = __lasti;
472 for (
auto __n = __last - __first; __n > 0; --__n)
476 __detail::__assign_one<_IsMove>(__result, __tail);
482 auto __lasti = ranges::next(__first, __last);
483 auto __tail = __lasti;
485 while (__first != __tail)
489 __detail::__assign_one<_IsMove>(__result, __tail);
495 struct __copy_backward_fn
497 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
498 b
idirectional_iterator _Iter2>
499 requires indirectly_copyable<_Iter1, _Iter2>
500 constexpr copy_backward_result<_Iter1, _Iter2>
501 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result)
const
503 return ranges::__copy_or_move_backward<false>(
std::move(__first),
508 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
509 requires indirectly_copyable<iterator_t<_Range>, _Iter>
510 constexpr copy_backward_result<borrowed_iterator_t<_Range>, _Iter>
511 operator()(_Range&& __r, _Iter __result)
const
513 return (*
this)(ranges::begin(__r), ranges::end(__r),
518 inline constexpr __copy_backward_fn copy_backward{};
520 struct __move_backward_fn
522 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
523 b
idirectional_iterator _Iter2>
524 requires indirectly_movable<_Iter1, _Iter2>
525 constexpr move_backward_result<_Iter1, _Iter2>
526 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result)
const
528 return ranges::__copy_or_move_backward<true>(
std::move(__first),
533 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
534 requires indirectly_movable<iterator_t<_Range>, _Iter>
535 constexpr move_backward_result<borrowed_iterator_t<_Range>, _Iter>
536 operator()(_Range&& __r, _Iter __result)
const
538 return (*
this)(ranges::begin(__r), ranges::end(__r),
545 template<
typename _Iter,
typename _Out>
546 using copy_n_result = in_out_result<_Iter, _Out>;
550 template<input_iterator _Iter, weakly_incrementable _Out>
551 requires indirectly_copyable<_Iter, _Out>
552 constexpr copy_n_result<_Iter, _Out>
553 operator()(_Iter __first, iter_difference_t<_Iter> __n,
556 if constexpr (random_access_iterator<_Iter>)
559 return ranges::copy(__first, __first + __n,
std::move(__result));
563 for (; __n > 0; --__n, (void)++__result, (
void)++__first)
564 *__result = *__first;
570 inline constexpr __copy_n_fn copy_n{};
574 template<
typename _Tp, output_iterator<const _Tp&> _Out>
576 operator()(_Out __first, iter_difference_t<_Out> __n,
577 const _Tp& __value)
const
584 if constexpr (is_scalar_v<_Tp>)
587 if constexpr (is_pointer_v<_Out>
589 && __is_byte<remove_pointer_t<_Out>>::__value
592 if (!std::__is_constant_evaluated())
594 __builtin_memset(__first,
595 static_cast<unsigned char>(__value),
597 return __first + __n;
601 const auto __tmp = __value;
602 for (; __n > 0; --__n, (void)++__first)
608 for (; __n > 0; --__n, (void)++__first)
615 inline constexpr __fill_n_fn fill_n{};
619 template<
typename _Tp,
620 output_iterator<const _Tp&> _Out, sentinel_for<_Out> _Sent>
622 operator()(_Out __first, _Sent __last,
const _Tp& __value)
const
626 if constexpr (sized_sentinel_for<_Sent, _Out>)
628 const auto __len = __last - __first;
629 return ranges::fill_n(
std::move(__first), __len, __value);
631 else if constexpr (is_scalar_v<_Tp>)
633 const auto __tmp = __value;
634 for (; __first != __last; ++__first)
640 for (; __first != __last; ++__first)
646 template<
typename _Tp, output_range<const _Tp&> _Range>
647 constexpr borrowed_iterator_t<_Range>
648 operator()(_Range&& __r,
const _Tp& __value)
const
650 return (*
this)(ranges::begin(__r), ranges::end(__r), __value);
654 inline constexpr __fill_fn fill{};
656_GLIBCXX_END_NAMESPACE_VERSION
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 _BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
constexpr void iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
Create a range of sequentially increasing values.
ISO C++ entities toplevel namespace is std.