30 #ifndef _RANGES_ALGOBASE_H
31 #define _RANGES_ALGOBASE_H 1
33 #if __cplusplus > 201703L
42 #if __cpp_lib_concepts
43 namespace 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 || __detail::__is_normal_iterator<_Iter2>)
89 return (*
this)(std::__niter_base(
std::move(__first1)),
95 else if constexpr (sized_sentinel_for<_Sent1, _Iter1>
96 && sized_sentinel_for<_Sent2, _Iter2>)
103 using _ValueType1 = iter_value_t<_Iter1>;
104 using _ValueType2 = iter_value_t<_Iter2>;
105 constexpr
bool __use_memcmp
106 = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
107 && is_same_v<_ValueType1, _ValueType2>
108 && is_pointer_v<_Iter1>
109 && is_pointer_v<_Iter2>
110 && is_same_v<_Pred, ranges::equal_to>
111 && is_same_v<_Proj1, identity>
112 && is_same_v<_Proj2, identity>);
113 if constexpr (__use_memcmp)
115 if (
const size_t __len = (__last1 - __first1))
116 return !std::__memcmp(__first1, __first2, __len);
121 for (; __first1 != __last1; ++__first1, (void)++__first2)
131 for (; __first1 != __last1 && __first2 != __last2;
132 ++__first1, (void)++__first2)
137 return __first1 == __last1 && __first2 == __last2;
141 template<input_range _Range1, input_range _Range2,
142 typename _Pred = ranges::equal_to,
143 typename _Proj1 = identity,
typename _Proj2 = identity>
144 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
145 _Pred, _Proj1, _Proj2>
147 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
148 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
157 inline constexpr __equal_fn equal{};
159 template<
typename _Iter,
typename _Out>
162 [[no_unique_address]] _Iter in;
163 [[no_unique_address]] _Out out;
165 template<
typename _Iter2,
typename _Out2>
166 requires convertible_to<const _Iter&, _Iter2>
167 && convertible_to<const _Out&, _Out2>
169 operator in_out_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>
176 operator in_out_result<_Iter2, _Out2>() &&
180 template<
typename _Iter,
typename _Out>
181 using copy_result = in_out_result<_Iter, _Out>;
183 template<
typename _Iter,
typename _Out>
184 using move_result = in_out_result<_Iter, _Out>;
186 template<
typename _Iter1,
typename _Iter2>
187 using move_backward_result = in_out_result<_Iter1, _Iter2>;
189 template<
typename _Iter1,
typename _Iter2>
190 using copy_backward_result = in_out_result<_Iter1, _Iter2>;
192 template<
bool _IsMove,
193 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
194 bidirectional_iterator _Out>
196 ? indirectly_movable<_Iter, _Out>
197 : indirectly_copyable<_Iter, _Out>)
199 move_backward_result<_Iter, _Out>,
200 copy_backward_result<_Iter, _Out>>
201 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result);
203 template<
bool _IsMove,
204 input_iterator _Iter, sentinel_for<_Iter> _Sent,
205 weakly_incrementable _Out>
207 ? indirectly_movable<_Iter, _Out>
208 : indirectly_copyable<_Iter, _Out>)
210 move_result<_Iter, _Out>,
211 copy_result<_Iter, _Out>>
212 __copy_or_move(_Iter __first, _Sent __last, _Out __result)
216 constexpr
bool __normal_iterator_p
217 = (__detail::__is_normal_iterator<_Iter>
218 || __detail::__is_normal_iterator<_Out>);
219 constexpr
bool __reverse_p
220 = (__detail::__is_reverse_iterator<_Iter>
221 && __detail::__is_reverse_iterator<_Out>);
222 constexpr
bool __move_iterator_p = __detail::__is_move_iterator<_Iter>;
223 if constexpr (__move_iterator_p)
226 = ranges::__copy_or_move<true>(
std::move(__first).base(),
231 else if constexpr (__reverse_p)
234 = ranges::__copy_or_move_backward<_IsMove>(__last.base(),
237 return {reverse_iterator{
std::move(__in)},
240 else if constexpr (__normal_iterator_p)
243 = ranges::__copy_or_move<_IsMove>(std::__niter_base(__first),
244 std::__niter_base(__last),
245 std::__niter_base(__result));
246 return {std::__niter_wrap(__first,
std::move(__in)),
247 std::__niter_wrap(__result,
std::move(__out))};
249 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
251 using _ValueTypeI = iter_value_t<_Iter>;
252 using _ValueTypeO = iter_value_t<_Out>;
253 constexpr
bool __use_memmove
254 = (is_trivially_copyable_v<_ValueTypeI>
255 && is_same_v<_ValueTypeI, _ValueTypeO>
256 && is_pointer_v<_Iter>
257 && is_pointer_v<_Out>);
259 if constexpr (__use_memmove)
261 static_assert(_IsMove
262 ? is_move_assignable_v<_ValueTypeI>
263 : is_copy_assignable_v<_ValueTypeI>);
264 auto __num = __last - __first;
266 std::__memmove<_IsMove>(__result, __first, __num);
267 return {__first + __num, __result + __num};
271 for (
auto __n = __last - __first; __n > 0; --__n)
273 if constexpr (_IsMove)
276 *__result = *__first;
285 while (__first != __last)
287 if constexpr (_IsMove)
290 *__result = *__first;
300 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
301 weakly_incrementable _Out>
302 requires indirectly_copyable<_Iter, _Out>
303 constexpr copy_result<_Iter, _Out>
304 operator()(_Iter __first, _Sent __last, _Out __result)
const
306 return ranges::__copy_or_move<false>(
std::move(__first),
311 template<input_range _Range, weakly_incrementable _Out>
312 requires indirectly_copyable<iterator_t<_Range>, _Out>
313 constexpr copy_result<borrowed_iterator_t<_Range>, _Out>
314 operator()(_Range&& __r, _Out __result)
const
321 inline constexpr __copy_fn copy{};
325 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
326 weakly_incrementable _Out>
327 requires indirectly_movable<_Iter, _Out>
328 constexpr move_result<_Iter, _Out>
329 operator()(_Iter __first, _Sent __last, _Out __result)
const
331 return ranges::__copy_or_move<true>(
std::move(__first),
336 template<input_range _Range, weakly_incrementable _Out>
337 requires indirectly_movable<iterator_t<_Range>, _Out>
338 constexpr move_result<borrowed_iterator_t<_Range>, _Out>
339 operator()(_Range&& __r, _Out __result)
const
346 inline constexpr __move_fn
move{};
348 template<
bool _IsMove,
349 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
350 bidirectional_iterator _Out>
352 ? indirectly_movable<_Iter, _Out>
353 : indirectly_copyable<_Iter, _Out>)
355 move_backward_result<_Iter, _Out>,
356 copy_backward_result<_Iter, _Out>>
357 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result)
361 constexpr
bool __normal_iterator_p
362 = (__detail::__is_normal_iterator<_Iter>
363 || __detail::__is_normal_iterator<_Out>);
364 constexpr
bool __reverse_p
365 = (__detail::__is_reverse_iterator<_Iter>
366 && __detail::__is_reverse_iterator<_Out>);
367 if constexpr (__reverse_p)
370 = ranges::__copy_or_move<_IsMove>(__last.base(),
373 return {reverse_iterator{
std::move(__in)},
376 else if constexpr (__normal_iterator_p)
379 = ranges::__copy_or_move_backward<_IsMove>
380 (std::__niter_base(__first),
381 std::__niter_base(__last),
382 std::__niter_base(__result));
383 return {std::__niter_wrap(__first,
std::move(__in)),
384 std::__niter_wrap(__result,
std::move(__out))};
386 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
388 using _ValueTypeI = iter_value_t<_Iter>;
389 using _ValueTypeO = iter_value_t<_Out>;
390 constexpr
bool __use_memmove
391 = (is_trivially_copyable_v<_ValueTypeI>
392 && is_same_v<_ValueTypeI, _ValueTypeO>
393 && is_pointer_v<_Iter>
394 && is_pointer_v<_Out>);
395 if constexpr (__use_memmove)
397 static_assert(_IsMove
398 ? is_move_assignable_v<_ValueTypeI>
399 : is_copy_assignable_v<_ValueTypeI>);
400 auto __num = __last - __first;
402 std::__memmove<_IsMove>(__result - __num, __first, __num);
403 return {__first + __num, __result - __num};
407 auto __lasti = ranges::next(__first, __last);
408 auto __tail = __lasti;
410 for (
auto __n = __last - __first; __n > 0; --__n)
414 if constexpr (_IsMove)
424 auto __lasti = ranges::next(__first, __last);
425 auto __tail = __lasti;
427 while (__first != __tail)
431 if constexpr (_IsMove)
440 struct __copy_backward_fn
442 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
443 b
idirectional_iterator _Iter2>
444 requires indirectly_copyable<_Iter1, _Iter2>
445 constexpr copy_backward_result<_Iter1, _Iter2>
446 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result)
const
448 return ranges::__copy_or_move_backward<false>(
std::move(__first),
453 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
454 requires indirectly_copyable<iterator_t<_Range>, _Iter>
455 constexpr copy_backward_result<borrowed_iterator_t<_Range>, _Iter>
456 operator()(_Range&& __r, _Iter __result)
const
463 inline constexpr __copy_backward_fn copy_backward{};
465 struct __move_backward_fn
467 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
468 b
idirectional_iterator _Iter2>
469 requires indirectly_movable<_Iter1, _Iter2>
470 constexpr move_backward_result<_Iter1, _Iter2>
471 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result)
const
473 return ranges::__copy_or_move_backward<true>(
std::move(__first),
478 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
479 requires indirectly_movable<iterator_t<_Range>, _Iter>
480 constexpr move_backward_result<borrowed_iterator_t<_Range>, _Iter>
481 operator()(_Range&& __r, _Iter __result)
const
490 template<
typename _Iter,
typename _Out>
491 using copy_n_result = in_out_result<_Iter, _Out>;
495 template<input_iterator _Iter, weakly_incrementable _Out>
496 requires indirectly_copyable<_Iter, _Out>
497 constexpr copy_n_result<_Iter, _Out>
498 operator()(_Iter __first, iter_difference_t<_Iter> __n,
501 if constexpr (random_access_iterator<_Iter>)
502 return ranges::copy(__first, __first + __n,
std::move(__result));
505 for (; __n > 0; --__n, (void)++__result, (
void)++__first)
506 *__result = *__first;
512 inline constexpr __copy_n_fn copy_n{};
516 template<
typename _Tp, output_iterator<const _Tp&> _Out>
518 operator()(_Out __first, iter_difference_t<_Out> __n,
519 const _Tp& __value)
const
527 if constexpr (is_pointer_v<_Out> && __is_byte<_Tp>::__value)
529 __builtin_memset(__first, static_cast<unsigned char>(__value), __n);
530 return __first + __n;
532 else if constexpr (is_scalar_v<_Tp>)
534 const auto __tmp = __value;
535 for (; __n > 0; --__n, (void)++__first)
541 for (; __n > 0; --__n, (void)++__first)
548 inline constexpr __fill_n_fn fill_n{};
552 template<
typename _Tp,
553 output_iterator<const _Tp&> _Out, sentinel_for<_Out> _Sent>
555 operator()(_Out __first, _Sent __last,
const _Tp& __value)
const
559 if constexpr (sized_sentinel_for<_Sent, _Out>)
561 const auto __len = __last - __first;
562 return ranges::fill_n(__first, __len, __value);
564 else if constexpr (is_scalar_v<_Tp>)
566 const auto __tmp = __value;
567 for (; __first != __last; ++__first)
573 for (; __first != __last; ++__first)
579 template<
typename _Tp, output_range<const _Tp&> _Range>
580 constexpr borrowed_iterator_t<_Range>
581 operator()(_Range&& __r,
const _Tp& __value)
const
587 inline constexpr __fill_fn fill{};
589 _GLIBCXX_END_NAMESPACE_VERSION
593 #endif // _RANGES_ALGOBASE_H