30 #ifndef _RANGES_ALGOBASE_H
31 #define _RANGES_ALGOBASE_H 1
33 #if __cplusplus > 201703L
43 #if __cpp_lib_concepts
44 namespace 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;
76 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
77 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
78 typename _Pred = ranges::equal_to,
79 typename _Proj1 =
identity,
typename _Proj2 =
identity>
80 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
82 operator()(_Iter1 __first1, _Sent1 __last1,
83 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
84 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
88 if constexpr (__detail::__is_normal_iterator<_Iter1>
89 || __detail::__is_normal_iterator<_Iter2>)
90 return (*
this)(std::__niter_base(
std::move(__first1)),
96 else if constexpr (sized_sentinel_for<_Sent1, _Iter1>
97 && sized_sentinel_for<_Sent2, _Iter2>)
104 using _ValueType1 = iter_value_t<_Iter1>;
105 using _ValueType2 = iter_value_t<_Iter2>;
106 constexpr
bool __use_memcmp
107 = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
108 && is_same_v<_ValueType1, _ValueType2>
109 && is_pointer_v<_Iter1>
110 && is_pointer_v<_Iter2>
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
158 inline constexpr __equal_fn equal{};
160 template<
typename _Iter,
typename _Out>
163 [[no_unique_address]] _Iter in;
164 [[no_unique_address]] _Out out;
166 template<
typename _Iter2,
typename _Out2>
167 requires convertible_to<const _Iter&, _Iter2>
168 && convertible_to<const _Out&, _Out2>
169 operator copy_result<_Iter2, _Out2>() const &
170 {
return {in, out}; }
172 template<
typename _Iter2,
typename _Out2>
173 requires convertible_to<_Iter, _Iter2>
174 && convertible_to<_Out, _Out2>
175 operator copy_result<_Iter2, _Out2>() &&
179 template<
typename _Iter,
typename _Out>
180 using move_result = copy_result<_Iter, _Out>;
182 template<
typename _Iter1,
typename _Iter2>
183 using move_backward_result = copy_result<_Iter1, _Iter2>;
185 template<
typename _Iter1,
typename _Iter2>
186 using copy_backward_result = copy_result<_Iter1, _Iter2>;
188 template<
bool _IsMove,
189 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
190 bidirectional_iterator _Out>
192 ? indirectly_movable<_Iter, _Out>
193 : indirectly_copyable<_Iter, _Out>)
195 move_backward_result<_Iter, _Out>,
196 copy_backward_result<_Iter, _Out>>
197 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result);
199 template<
bool _IsMove,
200 input_iterator _Iter, sentinel_for<_Iter> _Sent,
201 weakly_incrementable _Out>
203 ? indirectly_movable<_Iter, _Out>
204 : indirectly_copyable<_Iter, _Out>)
206 move_result<_Iter, _Out>,
207 copy_result<_Iter, _Out>>
208 __copy_or_move(_Iter __first, _Sent __last, _Out __result)
212 constexpr
bool __normal_iterator_p
213 = (__detail::__is_normal_iterator<_Iter>
214 || __detail::__is_normal_iterator<_Out>);
215 constexpr
bool __reverse_p
216 = (__detail::__is_reverse_iterator<_Iter>
217 && __detail::__is_reverse_iterator<_Out>);
218 constexpr
bool __move_iterator_p = __detail::__is_move_iterator<_Iter>;
219 if constexpr (__move_iterator_p)
222 = ranges::__copy_or_move<true>(
std::move(__first).base(),
227 else if constexpr (__reverse_p)
230 = ranges::__copy_or_move_backward<_IsMove>(__last.base(),
233 return {reverse_iterator{
std::move(__in)},
236 else if constexpr (__normal_iterator_p)
239 = ranges::__copy_or_move<_IsMove>(std::__niter_base(__first),
240 std::__niter_base(__last),
241 std::__niter_base(__result));
242 return {std::__niter_wrap(__first,
std::move(__in)),
243 std::__niter_wrap(__result,
std::move(__out))};
245 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
247 using _ValueTypeI = iter_value_t<_Iter>;
248 using _ValueTypeO = iter_value_t<_Out>;
249 constexpr
bool __use_memmove
250 = (is_trivially_copyable_v<_ValueTypeI>
251 && is_same_v<_ValueTypeI, _ValueTypeO>
252 && is_pointer_v<_Iter>
253 && is_pointer_v<_Out>);
255 if constexpr (__use_memmove)
257 static_assert(_IsMove
258 ? is_move_assignable_v<_ValueTypeI>
259 : is_copy_assignable_v<_ValueTypeI>);
260 auto __num = __last - __first;
262 std::__memmove<_IsMove>(__result, __first, __num);
263 return {__first + __num, __result + __num};
267 for (
auto __n = __last - __first; __n > 0; --__n)
269 if constexpr (_IsMove)
272 *__result = *__first;
281 while (__first != __last)
283 if constexpr (_IsMove)
286 *__result = *__first;
296 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
297 weakly_incrementable _Out>
298 requires indirectly_copyable<_Iter, _Out>
299 constexpr copy_result<_Iter, _Out>
300 operator()(_Iter __first, _Sent __last, _Out __result)
const
302 return ranges::__copy_or_move<false>(
std::move(__first),
307 template<input_range _Range, weakly_incrementable _Out>
308 requires indirectly_copyable<iterator_t<_Range>, _Out>
309 constexpr copy_result<safe_iterator_t<_Range>, _Out>
310 operator()(_Range&& __r, _Out __result)
const
317 inline constexpr __copy_fn copy{};
321 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
322 weakly_incrementable _Out>
323 requires indirectly_movable<_Iter, _Out>
324 constexpr move_result<_Iter, _Out>
325 operator()(_Iter __first, _Sent __last, _Out __result)
const
327 return ranges::__copy_or_move<true>(
std::move(__first),
332 template<input_range _Range, weakly_incrementable _Out>
333 requires indirectly_movable<iterator_t<_Range>, _Out>
334 constexpr move_result<safe_iterator_t<_Range>, _Out>
335 operator()(_Range&& __r, _Out __result)
const
342 inline constexpr __move_fn
move{};
344 template<
bool _IsMove,
345 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
346 bidirectional_iterator _Out>
348 ? indirectly_movable<_Iter, _Out>
349 : indirectly_copyable<_Iter, _Out>)
351 move_backward_result<_Iter, _Out>,
352 copy_backward_result<_Iter, _Out>>
353 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result)
357 constexpr
bool __normal_iterator_p
358 = (__detail::__is_normal_iterator<_Iter>
359 || __detail::__is_normal_iterator<_Out>);
360 constexpr
bool __reverse_p
361 = (__detail::__is_reverse_iterator<_Iter>
362 && __detail::__is_reverse_iterator<_Out>);
363 if constexpr (__reverse_p)
366 = ranges::__copy_or_move<_IsMove>(__last.base(),
369 return {reverse_iterator{
std::move(__in)},
372 else if constexpr (__normal_iterator_p)
375 = ranges::__copy_or_move_backward<_IsMove>
376 (std::__niter_base(__first),
377 std::__niter_base(__last),
378 std::__niter_base(__result));
379 return {std::__niter_wrap(__first,
std::move(__in)),
380 std::__niter_wrap(__result,
std::move(__out))};
382 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
384 using _ValueTypeI = iter_value_t<_Iter>;
385 using _ValueTypeO = iter_value_t<_Out>;
386 constexpr
bool __use_memmove
387 = (is_trivially_copyable_v<_ValueTypeI>
388 && is_same_v<_ValueTypeI, _ValueTypeO>
389 && is_pointer_v<_Iter>
390 && is_pointer_v<_Out>);
391 if constexpr (__use_memmove)
393 static_assert(_IsMove
394 ? is_move_assignable_v<_ValueTypeI>
395 : is_copy_assignable_v<_ValueTypeI>);
396 auto __num = __last - __first;
398 std::__memmove<_IsMove>(__result - __num, __first, __num);
399 return {__first + __num, __result - __num};
403 auto __lasti = ranges::next(__first, __last);
404 auto __tail = __lasti;
406 for (
auto __n = __last - __first; __n > 0; --__n)
410 if constexpr (_IsMove)
420 auto __lasti = ranges::next(__first, __last);
421 auto __tail = __lasti;
423 while (__first != __tail)
427 if constexpr (_IsMove)
436 struct __copy_backward_fn
438 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
439 b
idirectional_iterator _Iter2>
440 requires indirectly_copyable<_Iter1, _Iter2>
441 constexpr copy_backward_result<_Iter1, _Iter2>
442 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result)
const
444 return ranges::__copy_or_move_backward<false>(
std::move(__first),
449 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
450 requires indirectly_copyable<iterator_t<_Range>, _Iter>
451 constexpr copy_backward_result<safe_iterator_t<_Range>, _Iter>
452 operator()(_Range&& __r, _Iter __result)
const
459 inline constexpr __copy_backward_fn copy_backward{};
461 struct __move_backward_fn
463 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
464 b
idirectional_iterator _Iter2>
465 requires indirectly_movable<_Iter1, _Iter2>
466 constexpr move_backward_result<_Iter1, _Iter2>
467 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result)
const
469 return ranges::__copy_or_move_backward<true>(
std::move(__first),
474 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
475 requires indirectly_movable<iterator_t<_Range>, _Iter>
476 constexpr move_backward_result<safe_iterator_t<_Range>, _Iter>
477 operator()(_Range&& __r, _Iter __result)
const
486 template<
typename _Iter,
typename _Out>
487 using copy_n_result = copy_result<_Iter, _Out>;
491 template<input_iterator _Iter, weakly_incrementable _Out>
492 requires indirectly_copyable<_Iter, _Out>
493 constexpr copy_n_result<_Iter, _Out>
494 operator()(_Iter __first, iter_difference_t<_Iter> __n,
497 if constexpr (random_access_iterator<_Iter>)
498 return ranges::copy(__first, __first + __n,
std::move(__result));
501 for (; __n > 0; --__n, (void)++__result, (
void)++__first)
502 *__result = *__first;
508 inline constexpr __copy_n_fn copy_n{};
512 template<
typename _Tp, output_iterator<const _Tp&> _Out>
514 operator()(_Out __first, iter_difference_t<_Out> __n,
515 const _Tp& __value)
const
523 if constexpr (is_pointer_v<_Out> && __is_byte<_Tp>::__value)
525 __builtin_memset(__first,
static_cast<unsigned char>(__value), __n);
526 return __first + __n;
528 else if constexpr (is_scalar_v<_Tp>)
530 const auto __tmp = __value;
531 for (; __n > 0; --__n, (void)++__first)
537 for (; __n > 0; --__n, (void)++__first)
544 inline constexpr __fill_n_fn fill_n{};
548 template<
typename _Tp,
549 output_iterator<const _Tp&> _Out, sentinel_for<_Out> _Sent>
551 operator()(_Out __first, _Sent __last,
const _Tp& __value)
const
555 if constexpr (sized_sentinel_for<_Sent, _Out>)
557 const auto __len = __last - __first;
558 return ranges::fill_n(__first, __len, __value);
560 else if constexpr (is_scalar_v<_Tp>)
562 const auto __tmp = __value;
563 for (; __first != __last; ++__first)
569 for (; __first != __last; ++__first)
575 template<
typename _Tp, output_range<const _Tp&> _Range>
576 constexpr safe_iterator_t<_Range>
577 operator()(_Range&& __r,
const _Tp& __value)
const
583 inline constexpr __fill_fn fill{};
585 _GLIBCXX_END_NAMESPACE_VERSION
589 #endif // _RANGES_ALGOBASE_H