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>() &&
99 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
100 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
101 typename _Pred = ranges::equal_to,
102 typename _Proj1 =
identity,
typename _Proj2 =
identity>
103 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
105 operator()(_Iter1 __first1, _Sent1 __last1,
106 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
107 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
111 if constexpr (__detail::__is_normal_iterator<_Iter1>
112 && same_as<_Iter1, _Sent1>)
113 return (*
this)(__first1.base(), __last1.base(),
117 else if constexpr (__detail::__is_normal_iterator<_Iter2>
118 && same_as<_Iter2, _Sent2>)
120 __first2.base(), __last2.base(),
123 else if constexpr (sized_sentinel_for<_Sent1, _Iter1>
124 && sized_sentinel_for<_Sent2, _Iter2>)
126 auto __d1 = ranges::distance(__first1, __last1);
127 auto __d2 = ranges::distance(__first2, __last2);
131 using _ValueType1 = iter_value_t<_Iter1>;
132 constexpr bool __use_memcmp
133 = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
134 && __memcmpable<_Iter1, _Iter2>::__value
135 && is_same_v<_Pred, ranges::equal_to>
136 && is_same_v<_Proj1, identity>
137 && is_same_v<_Proj2, identity>);
138 if constexpr (__use_memcmp)
140 if (
const size_t __len = (__last1 - __first1))
141 return !std::__memcmp(__first1, __first2, __len);
146 for (; __first1 != __last1; ++__first1, (void)++__first2)
156 for (; __first1 != __last1 && __first2 != __last2;
157 ++__first1, (void)++__first2)
162 return __first1 == __last1 && __first2 == __last2;
166 template<input_range _Range1, input_range _Range2,
167 typename _Pred = ranges::equal_to,
168 typename _Proj1 = identity,
typename _Proj2 = identity>
169 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
170 _Pred, _Proj1, _Proj2>
172 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
173 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
177 if constexpr (sized_range<_Range1>)
178 if constexpr (sized_range<_Range2>)
179 if (ranges::distance(__r1) != ranges::distance(__r2))
182 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
183 ranges::begin(__r2), ranges::end(__r2),
189 inline constexpr __equal_fn equal{};
191 template<
typename _Iter,
typename _Out>
194 [[no_unique_address]] _Iter in;
195 [[no_unique_address]] _Out out;
197 template<
typename _Iter2,
typename _Out2>
198 requires convertible_to<const _Iter&, _Iter2>
199 && convertible_to<const _Out&, _Out2>
201 operator in_out_result<_Iter2, _Out2>() const &
202 {
return {in, out}; }
204 template<
typename _Iter2,
typename _Out2>
205 requires convertible_to<_Iter, _Iter2>
206 && convertible_to<_Out, _Out2>
208 operator in_out_result<_Iter2, _Out2>() &&
212 template<
typename _Iter,
typename _Out>
213 using copy_result = in_out_result<_Iter, _Out>;
215 template<
typename _Iter,
typename _Out>
216 using move_result = in_out_result<_Iter, _Out>;
218 template<
typename _Iter1,
typename _Iter2>
219 using move_backward_result = in_out_result<_Iter1, _Iter2>;
221 template<
typename _Iter1,
typename _Iter2>
222 using copy_backward_result = in_out_result<_Iter1, _Iter2>;
224 template<
bool _IsMove,
225 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
226 bidirectional_iterator _Out>
228 ? indirectly_movable<_Iter, _Out>
229 : indirectly_copyable<_Iter, _Out>)
230 constexpr __conditional_t<_IsMove,
231 move_backward_result<_Iter, _Out>,
232 copy_backward_result<_Iter, _Out>>
233 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result);
235 template<
bool _IsMove,
236 input_iterator _Iter, sentinel_for<_Iter> _Sent,
237 weakly_incrementable _Out>
239 ? indirectly_movable<_Iter, _Out>
240 : indirectly_copyable<_Iter, _Out>)
241 constexpr __conditional_t<_IsMove,
242 move_result<_Iter, _Out>,
243 copy_result<_Iter, _Out>>
244 __copy_or_move(_Iter __first, _Sent __last, _Out __result)
248 using __detail::__is_move_iterator;
249 using __detail::__is_reverse_iterator;
250 using __detail::__is_normal_iterator;
251 if constexpr (__is_move_iterator<_Iter> && same_as<_Iter, _Sent>)
254 = ranges::__copy_or_move<true>(
std::move(__first).base(),
259 else if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent>
260 && __is_reverse_iterator<_Out>)
263 = ranges::__copy_or_move_backward<_IsMove>(
std::move(__last).base(),
266 return {reverse_iterator{
std::move(__in)},
269 else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>)
272 = ranges::__copy_or_move<_IsMove>(__first.base(), __last.base(),
274 return {
decltype(__first){__in},
std::move(__out)};
276 else if constexpr (__is_normal_iterator<_Out>)
279 = ranges::__copy_or_move<_IsMove>(
std::move(__first), __last, __result.base());
280 return {
std::move(__in),
decltype(__result){__out}};
282 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
284 if (!std::__is_constant_evaluated())
286 if constexpr (__memcpyable<_Out, _Iter>::__value)
288 using _ValueTypeI = iter_value_t<_Iter>;
289 auto __num = __last - __first;
290 if (__num > 1) [[likely]]
291 __builtin_memmove(__result, __first,
292 sizeof(_ValueTypeI) * __num);
294 std::__assign_one<_IsMove>(__result, __first);
295 return {__first + __num, __result + __num};
299 for (
auto __n = __last - __first; __n > 0; --__n)
301 std::__assign_one<_IsMove>(__result, __first);
309 while (__first != __last)
311 std::__assign_one<_IsMove>(__result, __first);
321 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
322 weakly_incrementable _Out>
323 requires indirectly_copyable<_Iter, _Out>
324 constexpr copy_result<_Iter, _Out>
325 operator()(_Iter __first, _Sent __last, _Out __result)
const
327 return ranges::__copy_or_move<false>(
std::move(__first),
332 template<input_range _Range, weakly_incrementable _Out>
333 requires indirectly_copyable<iterator_t<_Range>, _Out>
334 constexpr copy_result<borrowed_iterator_t<_Range>, _Out>
335 operator()(_Range&& __r, _Out __result)
const
337 return (*
this)(ranges::begin(__r), ranges::end(__r),
342 inline constexpr __copy_fn copy{};
346 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
347 weakly_incrementable _Out>
348 requires indirectly_movable<_Iter, _Out>
349 constexpr move_result<_Iter, _Out>
350 operator()(_Iter __first, _Sent __last, _Out __result)
const
352 return ranges::__copy_or_move<true>(
std::move(__first),
357 template<input_range _Range, weakly_incrementable _Out>
358 requires indirectly_movable<iterator_t<_Range>, _Out>
359 constexpr move_result<borrowed_iterator_t<_Range>, _Out>
360 operator()(_Range&& __r, _Out __result)
const
362 return (*
this)(ranges::begin(__r), ranges::end(__r),
367 inline constexpr __move_fn
move{};
369 template<
bool _IsMove,
370 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
371 bidirectional_iterator _Out>
373 ? indirectly_movable<_Iter, _Out>
374 : indirectly_copyable<_Iter, _Out>)
375 constexpr __conditional_t<_IsMove,
376 move_backward_result<_Iter, _Out>,
377 copy_backward_result<_Iter, _Out>>
378 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result)
382 using __detail::__is_reverse_iterator;
383 using __detail::__is_normal_iterator;
384 if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent>
385 && __is_reverse_iterator<_Out>)
388 = ranges::__copy_or_move<_IsMove>(
std::move(__last).base(),
391 return {reverse_iterator{
std::move(__in)},
394 else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>)
397 = ranges::__copy_or_move_backward<_IsMove>(__first.base(),
400 return {
decltype(__first){__in},
std::move(__out)};
402 else if constexpr (__is_normal_iterator<_Out>)
405 = ranges::__copy_or_move_backward<_IsMove>(
std::move(__first),
408 return {
std::move(__in),
decltype(__result){__out}};
410 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
412 if (!std::__is_constant_evaluated())
414 if constexpr (__memcpyable<_Out, _Iter>::__value)
416 using _ValueTypeI = iter_value_t<_Iter>;
417 auto __num = __last - __first;
419 if (__num > 1) [[likely]]
420 __builtin_memmove(__result, __first,
421 sizeof(_ValueTypeI) * __num);
423 std::__assign_one<_IsMove>(__result, __first);
424 return {__first + __num, __result};
428 auto __lasti = ranges::next(__first, __last);
429 auto __tail = __lasti;
431 for (
auto __n = __last - __first; __n > 0; --__n)
435 std::__assign_one<_IsMove>(__result, __tail);
441 auto __lasti = ranges::next(__first, __last);
442 auto __tail = __lasti;
444 while (__first != __tail)
448 std::__assign_one<_IsMove>(__result, __tail);
454 struct __copy_backward_fn
456 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
457 b
idirectional_iterator _Iter2>
458 requires indirectly_copyable<_Iter1, _Iter2>
459 constexpr copy_backward_result<_Iter1, _Iter2>
460 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result)
const
462 return ranges::__copy_or_move_backward<false>(
std::move(__first),
467 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
468 requires indirectly_copyable<iterator_t<_Range>, _Iter>
469 constexpr copy_backward_result<borrowed_iterator_t<_Range>, _Iter>
470 operator()(_Range&& __r, _Iter __result)
const
472 return (*
this)(ranges::begin(__r), ranges::end(__r),
477 inline constexpr __copy_backward_fn copy_backward{};
479 struct __move_backward_fn
481 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
482 b
idirectional_iterator _Iter2>
483 requires indirectly_movable<_Iter1, _Iter2>
484 constexpr move_backward_result<_Iter1, _Iter2>
485 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result)
const
487 return ranges::__copy_or_move_backward<true>(
std::move(__first),
492 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
493 requires indirectly_movable<iterator_t<_Range>, _Iter>
494 constexpr move_backward_result<borrowed_iterator_t<_Range>, _Iter>
495 operator()(_Range&& __r, _Iter __result)
const
497 return (*
this)(ranges::begin(__r), ranges::end(__r),
504 template<
typename _Iter,
typename _Out>
505 using copy_n_result = in_out_result<_Iter, _Out>;
509 template<input_iterator _Iter, weakly_incrementable _Out>
510 requires indirectly_copyable<_Iter, _Out>
511 constexpr copy_n_result<_Iter, _Out>
512 operator()(_Iter __first, iter_difference_t<_Iter> __n,
515 if constexpr (random_access_iterator<_Iter>)
518 return ranges::copy(__first, __first + __n,
std::move(__result));
522 for (; __n > 0; --__n, (void)++__result, (void)++__first)
523 *__result = *__first;
529 inline constexpr __copy_n_fn copy_n{};
533 template<
typename _Out,
534 typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>)>
535 requires output_iterator<_Out, const _Tp&>
537 operator()(_Out __first, iter_difference_t<_Out> __n,
538 const _Tp& __value)
const
545 if constexpr (is_scalar_v<_Tp>)
548 if constexpr (is_pointer_v<_Out>
550 && __is_byte<remove_pointer_t<_Out>>::__value
553 if (!std::__is_constant_evaluated())
555 __builtin_memset(__first,
556 static_cast<unsigned char>(__value),
558 return __first + __n;
562 const auto __tmp = __value;
563 for (; __n > 0; --__n, (void)++__first)
569 for (; __n > 0; --__n, (void)++__first)
576 inline constexpr __fill_n_fn fill_n{};
580 template<
typename _Out,
581 sentinel_for<_Out> _Sent,
582 typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>)>
583 requires output_iterator<_Out, const _Tp&>
585 operator()(_Out __first, _Sent __last,
const _Tp& __value)
const
589 if constexpr (sized_sentinel_for<_Sent, _Out>)
591 const auto __len = __last - __first;
592 return ranges::fill_n(
std::move(__first), __len, __value);
594 else if constexpr (is_scalar_v<_Tp>)
596 const auto __tmp = __value;
597 for (; __first != __last; ++__first)
603 for (; __first != __last; ++__first)
609 template<
typename _Range,
610 typename _Tp _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>)>
611 requires output_range<_Range, const _Tp&>
612 constexpr borrowed_iterator_t<_Range>
613 operator()(_Range&& __r,
const _Tp& __value)
const
615 return (*
this)(ranges::begin(__r), ranges::end(__r), __value);
619 inline constexpr __fill_fn fill{};
621_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.
ISO C++ entities toplevel namespace is std.