30#ifndef _RANGES_ALGOBASE_H
31#define _RANGES_ALGOBASE_H 1
33#if __cplusplus > 201703L
43namespace std _GLIBCXX_VISIBILITY(default)
45_GLIBCXX_BEGIN_NAMESPACE_VERSION
50 template<
typename _Tp>
51 constexpr inline bool __is_normal_iterator =
false;
53 template<
typename _Iterator,
typename _Container>
55 __is_normal_iterator<__gnu_cxx::__normal_iterator<_Iterator,
58 template<
typename _Tp>
59 constexpr inline bool __is_reverse_iterator =
false;
61 template<
typename _Iterator>
63 __is_reverse_iterator<reverse_iterator<_Iterator>> =
true;
65 template<
typename _Tp>
66 constexpr inline bool __is_move_iterator =
false;
68 template<
typename _Iterator>
70 __is_move_iterator<move_iterator<_Iterator>> =
true;
75 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
76 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
77 typename _Pred = ranges::equal_to,
78 typename _Proj1 =
identity,
typename _Proj2 =
identity>
79 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
81 operator()(_Iter1 __first1, _Sent1 __last1,
82 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
83 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
87 if constexpr (__detail::__is_normal_iterator<_Iter1>
88 && same_as<_Iter1, _Sent1>)
89 return (*
this)(__first1.base(), __last1.base(),
93 else if constexpr (__detail::__is_normal_iterator<_Iter2>
94 && same_as<_Iter2, _Sent2>)
96 __first2.base(), __last2.base(),
99 else if constexpr (sized_sentinel_for<_Sent1, _Iter1>
100 && sized_sentinel_for<_Sent2, _Iter2>)
102 auto __d1 = ranges::distance(__first1, __last1);
103 auto __d2 = ranges::distance(__first2, __last2);
107 using _ValueType1 = iter_value_t<_Iter1>;
108 constexpr bool __use_memcmp
109 = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
110 && __memcmpable<_Iter1, _Iter2>::__value
111 && is_same_v<_Pred, ranges::equal_to>
112 && is_same_v<_Proj1, identity>
113 && is_same_v<_Proj2, identity>);
114 if constexpr (__use_memcmp)
116 if (
const size_t __len = (__last1 - __first1))
117 return !std::__memcmp(__first1, __first2, __len);
122 for (; __first1 != __last1; ++__first1, (void)++__first2)
132 for (; __first1 != __last1 && __first2 != __last2;
133 ++__first1, (void)++__first2)
138 return __first1 == __last1 && __first2 == __last2;
142 template<input_range _Range1, input_range _Range2,
143 typename _Pred = ranges::equal_to,
144 typename _Proj1 = identity,
typename _Proj2 = identity>
145 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
146 _Pred, _Proj1, _Proj2>
148 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
149 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
153 if constexpr (sized_range<_Range1>)
154 if constexpr (sized_range<_Range2>)
155 if (ranges::distance(__r1) != ranges::distance(__r2))
158 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
159 ranges::begin(__r2), ranges::end(__r2),
165 inline constexpr __equal_fn equal{};
167 template<
typename _Iter,
typename _Out>
170 [[no_unique_address]] _Iter in;
171 [[no_unique_address]] _Out out;
173 template<
typename _Iter2,
typename _Out2>
174 requires convertible_to<const _Iter&, _Iter2>
175 && convertible_to<const _Out&, _Out2>
177 operator in_out_result<_Iter2, _Out2>() const &
178 {
return {in, out}; }
180 template<
typename _Iter2,
typename _Out2>
181 requires convertible_to<_Iter, _Iter2>
182 && convertible_to<_Out, _Out2>
184 operator in_out_result<_Iter2, _Out2>() &&
188 template<
typename _Iter,
typename _Out>
189 using copy_result = in_out_result<_Iter, _Out>;
191 template<
typename _Iter,
typename _Out>
192 using move_result = in_out_result<_Iter, _Out>;
194 template<
typename _Iter1,
typename _Iter2>
195 using move_backward_result = in_out_result<_Iter1, _Iter2>;
197 template<
typename _Iter1,
typename _Iter2>
198 using copy_backward_result = in_out_result<_Iter1, _Iter2>;
200 template<
bool _IsMove,
201 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
202 bidirectional_iterator _Out>
204 ? indirectly_movable<_Iter, _Out>
205 : indirectly_copyable<_Iter, _Out>)
206 constexpr __conditional_t<_IsMove,
207 move_backward_result<_Iter, _Out>,
208 copy_backward_result<_Iter, _Out>>
209 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result);
211 template<
bool _IsMove,
212 input_iterator _Iter, sentinel_for<_Iter> _Sent,
213 weakly_incrementable _Out>
215 ? indirectly_movable<_Iter, _Out>
216 : indirectly_copyable<_Iter, _Out>)
217 constexpr __conditional_t<_IsMove,
218 move_result<_Iter, _Out>,
219 copy_result<_Iter, _Out>>
220 __copy_or_move(_Iter __first, _Sent __last, _Out __result)
224 using __detail::__is_move_iterator;
225 using __detail::__is_reverse_iterator;
226 using __detail::__is_normal_iterator;
227 if constexpr (__is_move_iterator<_Iter> && same_as<_Iter, _Sent>)
230 = ranges::__copy_or_move<true>(
std::move(__first).base(),
235 else if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent>
236 && __is_reverse_iterator<_Out>)
239 = ranges::__copy_or_move_backward<_IsMove>(
std::move(__last).base(),
242 return {reverse_iterator{
std::move(__in)},
245 else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>)
248 = ranges::__copy_or_move<_IsMove>(__first.base(), __last.base(),
250 return {
decltype(__first){__in},
std::move(__out)};
252 else if constexpr (__is_normal_iterator<_Out>)
255 = ranges::__copy_or_move<_IsMove>(
std::move(__first), __last, __result.base());
256 return {
std::move(__in),
decltype(__result){__out}};
258 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
260 if (!std::__is_constant_evaluated())
262 if constexpr (__memcpyable<_Out, _Iter>::__value)
264 using _ValueTypeI = iter_value_t<_Iter>;
265 static_assert(_IsMove
266 ? is_move_assignable_v<_ValueTypeI>
267 : is_copy_assignable_v<_ValueTypeI>);
268 auto __num = __last - __first;
270 __builtin_memmove(__result, __first,
271 sizeof(_ValueTypeI) * __num);
272 return {__first + __num, __result + __num};
276 for (
auto __n = __last - __first; __n > 0; --__n)
278 if constexpr (_IsMove)
281 *__result = *__first;
289 while (__first != __last)
291 if constexpr (_IsMove)
294 *__result = *__first;
304 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
305 weakly_incrementable _Out>
306 requires indirectly_copyable<_Iter, _Out>
307 constexpr copy_result<_Iter, _Out>
308 operator()(_Iter __first, _Sent __last, _Out __result)
const
310 return ranges::__copy_or_move<false>(
std::move(__first),
315 template<input_range _Range, weakly_incrementable _Out>
316 requires indirectly_copyable<iterator_t<_Range>, _Out>
317 constexpr copy_result<borrowed_iterator_t<_Range>, _Out>
318 operator()(_Range&& __r, _Out __result)
const
320 return (*
this)(ranges::begin(__r), ranges::end(__r),
325 inline constexpr __copy_fn copy{};
329 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
330 weakly_incrementable _Out>
331 requires indirectly_movable<_Iter, _Out>
332 constexpr move_result<_Iter, _Out>
333 operator()(_Iter __first, _Sent __last, _Out __result)
const
335 return ranges::__copy_or_move<true>(
std::move(__first),
340 template<input_range _Range, weakly_incrementable _Out>
341 requires indirectly_movable<iterator_t<_Range>, _Out>
342 constexpr move_result<borrowed_iterator_t<_Range>, _Out>
343 operator()(_Range&& __r, _Out __result)
const
345 return (*
this)(ranges::begin(__r), ranges::end(__r),
350 inline constexpr __move_fn
move{};
352 template<
bool _IsMove,
353 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
354 bidirectional_iterator _Out>
356 ? indirectly_movable<_Iter, _Out>
357 : indirectly_copyable<_Iter, _Out>)
358 constexpr __conditional_t<_IsMove,
359 move_backward_result<_Iter, _Out>,
360 copy_backward_result<_Iter, _Out>>
361 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result)
365 using __detail::__is_reverse_iterator;
366 using __detail::__is_normal_iterator;
367 if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent>
368 && __is_reverse_iterator<_Out>)
371 = ranges::__copy_or_move<_IsMove>(
std::move(__last).base(),
374 return {reverse_iterator{
std::move(__in)},
377 else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>)
380 = ranges::__copy_or_move_backward<_IsMove>(__first.base(),
383 return {
decltype(__first){__in},
std::move(__out)};
385 else if constexpr (__is_normal_iterator<_Out>)
388 = ranges::__copy_or_move_backward<_IsMove>(
std::move(__first),
391 return {
std::move(__in),
decltype(__result){__out}};
393 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
395 if (!std::__is_constant_evaluated())
397 if constexpr (__memcpyable<_Out, _Iter>::__value)
399 using _ValueTypeI = iter_value_t<_Iter>;
400 static_assert(_IsMove
401 ? is_move_assignable_v<_ValueTypeI>
402 : is_copy_assignable_v<_ValueTypeI>);
403 auto __num = __last - __first;
405 __builtin_memmove(__result - __num, __first,
406 sizeof(_ValueTypeI) * __num);
407 return {__first + __num, __result - __num};
411 auto __lasti = ranges::next(__first, __last);
412 auto __tail = __lasti;
414 for (
auto __n = __last - __first; __n > 0; --__n)
418 if constexpr (_IsMove)
427 auto __lasti = ranges::next(__first, __last);
428 auto __tail = __lasti;
430 while (__first != __tail)
434 if constexpr (_IsMove)
443 struct __copy_backward_fn
445 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
446 b
idirectional_iterator _Iter2>
447 requires indirectly_copyable<_Iter1, _Iter2>
448 constexpr copy_backward_result<_Iter1, _Iter2>
449 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result)
const
451 return ranges::__copy_or_move_backward<false>(
std::move(__first),
456 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
457 requires indirectly_copyable<iterator_t<_Range>, _Iter>
458 constexpr copy_backward_result<borrowed_iterator_t<_Range>, _Iter>
459 operator()(_Range&& __r, _Iter __result)
const
461 return (*
this)(ranges::begin(__r), ranges::end(__r),
466 inline constexpr __copy_backward_fn copy_backward{};
468 struct __move_backward_fn
470 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
471 b
idirectional_iterator _Iter2>
472 requires indirectly_movable<_Iter1, _Iter2>
473 constexpr move_backward_result<_Iter1, _Iter2>
474 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result)
const
476 return ranges::__copy_or_move_backward<true>(
std::move(__first),
481 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
482 requires indirectly_movable<iterator_t<_Range>, _Iter>
483 constexpr move_backward_result<borrowed_iterator_t<_Range>, _Iter>
484 operator()(_Range&& __r, _Iter __result)
const
486 return (*
this)(ranges::begin(__r), ranges::end(__r),
493 template<
typename _Iter,
typename _Out>
494 using copy_n_result = in_out_result<_Iter, _Out>;
498 template<input_iterator _Iter, weakly_incrementable _Out>
499 requires indirectly_copyable<_Iter, _Out>
500 constexpr copy_n_result<_Iter, _Out>
501 operator()(_Iter __first, iter_difference_t<_Iter> __n,
504 if constexpr (random_access_iterator<_Iter>)
507 return ranges::copy(__first, __first + __n,
std::move(__result));
511 for (; __n > 0; --__n, (void)++__result, (void)++__first)
512 *__result = *__first;
518 inline constexpr __copy_n_fn copy_n{};
522 template<
typename _Tp, output_iterator<const _Tp&> _Out>
524 operator()(_Out __first, iter_difference_t<_Out> __n,
525 const _Tp& __value)
const
532 if constexpr (is_scalar_v<_Tp>)
535 if constexpr (is_pointer_v<_Out>
537 && __is_byte<remove_pointer_t<_Out>>::__value
540 if (!std::__is_constant_evaluated())
542 __builtin_memset(__first,
543 static_cast<unsigned char>(__value),
545 return __first + __n;
549 const auto __tmp = __value;
550 for (; __n > 0; --__n, (void)++__first)
556 for (; __n > 0; --__n, (void)++__first)
563 inline constexpr __fill_n_fn fill_n{};
567 template<
typename _Tp,
568 output_iterator<const _Tp&> _Out, sentinel_for<_Out> _Sent>
570 operator()(_Out __first, _Sent __last,
const _Tp& __value)
const
574 if constexpr (sized_sentinel_for<_Sent, _Out>)
576 const auto __len = __last - __first;
577 return ranges::fill_n(
std::move(__first), __len, __value);
579 else if constexpr (is_scalar_v<_Tp>)
581 const auto __tmp = __value;
582 for (; __first != __last; ++__first)
588 for (; __first != __last; ++__first)
594 template<
typename _Tp, output_range<const _Tp&> _Range>
595 constexpr borrowed_iterator_t<_Range>
596 operator()(_Range&& __r,
const _Tp& __value)
const
598 return (*
this)(ranges::begin(__r), ranges::end(__r), __value);
602 inline constexpr __fill_fn fill{};
604_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.