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 && __memcmpable<_Iter1, _Iter2>::__value
108 && is_same_v<_Pred, ranges::equal_to>
109 && is_same_v<_Proj1, identity>
110 && is_same_v<_Proj2, identity>);
111 if constexpr (__use_memcmp)
113 if (
const size_t __len = (__last1 - __first1))
114 return !std::__memcmp(__first1, __first2, __len);
119 for (; __first1 != __last1; ++__first1, (void)++__first2)
129 for (; __first1 != __last1 && __first2 != __last2;
130 ++__first1, (void)++__first2)
135 return __first1 == __last1 && __first2 == __last2;
139 template<input_range _Range1, input_range _Range2,
140 typename _Pred = ranges::equal_to,
141 typename _Proj1 = identity,
typename _Proj2 = identity>
142 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
143 _Pred, _Proj1, _Proj2>
145 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
146 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
155 inline constexpr __equal_fn equal{};
157 template<
typename _Iter,
typename _Out>
160 [[no_unique_address]] _Iter in;
161 [[no_unique_address]] _Out out;
163 template<
typename _Iter2,
typename _Out2>
164 requires convertible_to<const _Iter&, _Iter2>
165 && convertible_to<const _Out&, _Out2>
167 operator in_out_result<_Iter2, _Out2>() const &
168 {
return {in, out}; }
170 template<
typename _Iter2,
typename _Out2>
171 requires convertible_to<_Iter, _Iter2>
172 && convertible_to<_Out, _Out2>
174 operator in_out_result<_Iter2, _Out2>() &&
178 template<
typename _Iter,
typename _Out>
179 using copy_result = in_out_result<_Iter, _Out>;
181 template<
typename _Iter,
typename _Out>
182 using move_result = in_out_result<_Iter, _Out>;
184 template<
typename _Iter1,
typename _Iter2>
185 using move_backward_result = in_out_result<_Iter1, _Iter2>;
187 template<
typename _Iter1,
typename _Iter2>
188 using copy_backward_result = in_out_result<_Iter1, _Iter2>;
190 template<
bool _IsMove,
191 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
192 bidirectional_iterator _Out>
194 ? indirectly_movable<_Iter, _Out>
195 : indirectly_copyable<_Iter, _Out>)
197 move_backward_result<_Iter, _Out>,
198 copy_backward_result<_Iter, _Out>>
199 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result);
201 template<
bool _IsMove,
202 input_iterator _Iter, sentinel_for<_Iter> _Sent,
203 weakly_incrementable _Out>
205 ? indirectly_movable<_Iter, _Out>
206 : indirectly_copyable<_Iter, _Out>)
208 move_result<_Iter, _Out>,
209 copy_result<_Iter, _Out>>
210 __copy_or_move(_Iter __first, _Sent __last, _Out __result)
214 constexpr
bool __normal_iterator_p
215 = (__detail::__is_normal_iterator<_Iter>
216 || __detail::__is_normal_iterator<_Out>);
217 constexpr
bool __reverse_p
218 = (__detail::__is_reverse_iterator<_Iter>
219 && __detail::__is_reverse_iterator<_Out>);
220 constexpr
bool __move_iterator_p = __detail::__is_move_iterator<_Iter>;
221 if constexpr (__move_iterator_p)
224 = ranges::__copy_or_move<true>(
std::move(__first).base(),
229 else if constexpr (__reverse_p)
232 = ranges::__copy_or_move_backward<_IsMove>(__last.base(),
235 return {reverse_iterator{
std::move(__in)},
238 else if constexpr (__normal_iterator_p)
241 = ranges::__copy_or_move<_IsMove>(std::__niter_base(__first),
242 std::__niter_base(__last),
243 std::__niter_base(__result));
244 return {std::__niter_wrap(__first,
std::move(__in)),
245 std::__niter_wrap(__result,
std::move(__out))};
247 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
249 #ifdef __cpp_lib_is_constant_evaluated
250 if (!std::is_constant_evaluated())
253 if constexpr (__memcpyable<_Iter, _Out>::__value)
255 using _ValueTypeI = iter_value_t<_Iter>;
256 static_assert(_IsMove
257 ? is_move_assignable_v<_ValueTypeI>
258 : is_copy_assignable_v<_ValueTypeI>);
259 auto __num = __last - __first;
261 __builtin_memmove(__result, __first,
262 sizeof(_ValueTypeI) * __num);
263 return {__first + __num, __result + __num};
267 for (
auto __n = __last - __first; __n > 0; --__n)
269 if constexpr (_IsMove)
272 *__result = *__first;
280 while (__first != __last)
282 if constexpr (_IsMove)
285 *__result = *__first;
295 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
296 weakly_incrementable _Out>
297 requires indirectly_copyable<_Iter, _Out>
298 constexpr copy_result<_Iter, _Out>
299 operator()(_Iter __first, _Sent __last, _Out __result)
const
301 return ranges::__copy_or_move<false>(
std::move(__first),
306 template<input_range _Range, weakly_incrementable _Out>
307 requires indirectly_copyable<iterator_t<_Range>, _Out>
308 constexpr copy_result<borrowed_iterator_t<_Range>, _Out>
309 operator()(_Range&& __r, _Out __result)
const
316 inline constexpr __copy_fn copy{};
320 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
321 weakly_incrementable _Out>
322 requires indirectly_movable<_Iter, _Out>
323 constexpr move_result<_Iter, _Out>
324 operator()(_Iter __first, _Sent __last, _Out __result)
const
326 return ranges::__copy_or_move<true>(
std::move(__first),
331 template<input_range _Range, weakly_incrementable _Out>
332 requires indirectly_movable<iterator_t<_Range>, _Out>
333 constexpr move_result<borrowed_iterator_t<_Range>, _Out>
334 operator()(_Range&& __r, _Out __result)
const
341 inline constexpr __move_fn
move{};
343 template<
bool _IsMove,
344 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
345 bidirectional_iterator _Out>
347 ? indirectly_movable<_Iter, _Out>
348 : indirectly_copyable<_Iter, _Out>)
350 move_backward_result<_Iter, _Out>,
351 copy_backward_result<_Iter, _Out>>
352 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result)
356 constexpr
bool __normal_iterator_p
357 = (__detail::__is_normal_iterator<_Iter>
358 || __detail::__is_normal_iterator<_Out>);
359 constexpr
bool __reverse_p
360 = (__detail::__is_reverse_iterator<_Iter>
361 && __detail::__is_reverse_iterator<_Out>);
362 if constexpr (__reverse_p)
365 = ranges::__copy_or_move<_IsMove>(__last.base(),
368 return {reverse_iterator{
std::move(__in)},
371 else if constexpr (__normal_iterator_p)
374 = ranges::__copy_or_move_backward<_IsMove>
375 (std::__niter_base(__first),
376 std::__niter_base(__last),
377 std::__niter_base(__result));
378 return {std::__niter_wrap(__first,
std::move(__in)),
379 std::__niter_wrap(__result,
std::move(__out))};
381 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
383 #ifdef __cpp_lib_is_constant_evaluated
384 if (!std::is_constant_evaluated())
387 if constexpr (__memcpyable<_Out, _Iter>::__value)
389 using _ValueTypeI = iter_value_t<_Iter>;
390 static_assert(_IsMove
391 ? is_move_assignable_v<_ValueTypeI>
392 : is_copy_assignable_v<_ValueTypeI>);
393 auto __num = __last - __first;
395 __builtin_memmove(__result - __num, __first,
396 sizeof(_ValueTypeI) * __num);
397 return {__first + __num, __result - __num};
401 auto __lasti = ranges::next(__first, __last);
402 auto __tail = __lasti;
404 for (
auto __n = __last - __first; __n > 0; --__n)
408 if constexpr (_IsMove)
417 auto __lasti = ranges::next(__first, __last);
418 auto __tail = __lasti;
420 while (__first != __tail)
424 if constexpr (_IsMove)
433 struct __copy_backward_fn
435 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
436 b
idirectional_iterator _Iter2>
437 requires indirectly_copyable<_Iter1, _Iter2>
438 constexpr copy_backward_result<_Iter1, _Iter2>
439 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result)
const
441 return ranges::__copy_or_move_backward<false>(
std::move(__first),
446 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
447 requires indirectly_copyable<iterator_t<_Range>, _Iter>
448 constexpr copy_backward_result<borrowed_iterator_t<_Range>, _Iter>
449 operator()(_Range&& __r, _Iter __result)
const
456 inline constexpr __copy_backward_fn copy_backward{};
458 struct __move_backward_fn
460 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
461 b
idirectional_iterator _Iter2>
462 requires indirectly_movable<_Iter1, _Iter2>
463 constexpr move_backward_result<_Iter1, _Iter2>
464 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result)
const
466 return ranges::__copy_or_move_backward<true>(
std::move(__first),
471 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
472 requires indirectly_movable<iterator_t<_Range>, _Iter>
473 constexpr move_backward_result<borrowed_iterator_t<_Range>, _Iter>
474 operator()(_Range&& __r, _Iter __result)
const
483 template<
typename _Iter,
typename _Out>
484 using copy_n_result = in_out_result<_Iter, _Out>;
488 template<input_iterator _Iter, weakly_incrementable _Out>
489 requires indirectly_copyable<_Iter, _Out>
490 constexpr copy_n_result<_Iter, _Out>
491 operator()(_Iter __first, iter_difference_t<_Iter> __n,
494 if constexpr (random_access_iterator<_Iter>)
495 return ranges::copy(__first, __first + __n,
std::move(__result));
498 for (; __n > 0; --__n, (void)++__result, (
void)++__first)
499 *__result = *__first;
505 inline constexpr __copy_n_fn copy_n{};
509 template<
typename _Tp, output_iterator<const _Tp&> _Out>
511 operator()(_Out __first, iter_difference_t<_Out> __n,
512 const _Tp& __value)
const
520 if constexpr (is_pointer_v<_Out>
522 && __is_byte<remove_pointer_t<_Out>>::__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 borrowed_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