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 && same_as<_Iter1, _Sent1>)
89 return (*this)(__first1.base(), __last1.base(),
90 std::
move(__first2), std::
move(__last2),
92 std::
move(__proj1), std::
move(__proj2));
93 else if constexpr (__detail::__is_normal_iterator<_Iter2>
94 && same_as<_Iter2, _Sent2>)
95 return (*this)(std::
move(__first1), std::
move(__last1),
96 __first2.base(), __last2.base(),
98 std::
move(__proj1), std::
move(__proj2));
99 else if constexpr (sized_sentinel_for<_Sent1, _Iter1>
100 && sized_sentinel_for<_Sent2, _Iter2>)
107 using _ValueType1 = iter_value_t<_Iter1>;
108 using _ValueType2 = iter_value_t<_Iter2>;
109 constexpr
bool __use_memcmp
110 = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
111 && __memcmpable<_Iter1, _Iter2>::__value
112 && is_same_v<_Pred, ranges::equal_to>
113 && is_same_v<_Proj1, identity>
114 && is_same_v<_Proj2, identity>);
115 if constexpr (__use_memcmp)
117 if (
const size_t __len = (__last1 - __first1))
118 return !std::__memcmp(__first1, __first2, __len);
123 for (; __first1 != __last1; ++__first1, (void)++__first2)
124 if (!(
bool)std::__invoke(__pred,
125 std::__invoke(__proj1, *__first1),
126 std::__invoke(__proj2, *__first2)))
133 for (; __first1 != __last1 && __first2 != __last2;
134 ++__first1, (void)++__first2)
135 if (!(
bool)std::__invoke(__pred,
136 std::__invoke(__proj1, *__first1),
137 std::__invoke(__proj2, *__first2)))
139 return __first1 == __last1 && __first2 == __last2;
143 template<input_range _Range1, input_range _Range2,
144 typename _Pred = ranges::equal_to,
145 typename _Proj1 = identity,
typename _Proj2 = identity>
146 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
147 _Pred, _Proj1, _Proj2>
149 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
150 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
159 inline constexpr __equal_fn equal{};
161 template<
typename _Iter,
typename _Out>
164 [[no_unique_address]] _Iter in;
165 [[no_unique_address]] _Out out;
167 template<
typename _Iter2,
typename _Out2>
168 requires convertible_to<const _Iter&, _Iter2>
169 && convertible_to<const _Out&, _Out2>
171 operator in_out_result<_Iter2, _Out2>()
const &
172 {
return {in, out}; }
174 template<
typename _Iter2,
typename _Out2>
175 requires convertible_to<_Iter, _Iter2>
176 && convertible_to<_Out, _Out2>
178 operator in_out_result<_Iter2, _Out2>() &&
182 template<
typename _Iter,
typename _Out>
183 using copy_result = in_out_result<_Iter, _Out>;
185 template<
typename _Iter,
typename _Out>
186 using move_result = in_out_result<_Iter, _Out>;
188 template<
typename _Iter1,
typename _Iter2>
189 using move_backward_result = in_out_result<_Iter1, _Iter2>;
191 template<
typename _Iter1,
typename _Iter2>
192 using copy_backward_result = in_out_result<_Iter1, _Iter2>;
194 template<
bool _IsMove,
195 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
196 bidirectional_iterator _Out>
198 ? indirectly_movable<_Iter, _Out>
199 : indirectly_copyable<_Iter, _Out>)
201 move_backward_result<_Iter, _Out>,
202 copy_backward_result<_Iter, _Out>>
203 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result);
205 template<
bool _IsMove,
206 input_iterator _Iter, sentinel_for<_Iter> _Sent,
207 weakly_incrementable _Out>
209 ? indirectly_movable<_Iter, _Out>
210 : indirectly_copyable<_Iter, _Out>)
212 move_result<_Iter, _Out>,
213 copy_result<_Iter, _Out>>
214 __copy_or_move(_Iter __first, _Sent __last, _Out __result)
218 using __detail::__is_move_iterator;
219 using __detail::__is_reverse_iterator;
220 using __detail::__is_normal_iterator;
221 if constexpr (__is_move_iterator<_Iter> && same_as<_Iter, _Sent>)
224 = ranges::__copy_or_move<true>(
std::move(__first).base(),
229 else if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent>
230 && __is_reverse_iterator<_Out>)
233 = ranges::__copy_or_move_backward<_IsMove>(
std::move(__last).base(),
236 return {reverse_iterator{
std::move(__in)},
239 else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>)
242 = ranges::__copy_or_move<_IsMove>(__first.base(), __last.base(),
244 return {decltype(__first){__in},
std::move(__out)};
246 else if constexpr (__is_normal_iterator<_Out>)
249 = ranges::__copy_or_move<_IsMove>(__first, __last, __result.base());
250 return {
std::move(__in), decltype(__result){__out}};
252 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
254 #ifdef __cpp_lib_is_constant_evaluated
255 if (!std::is_constant_evaluated())
258 if constexpr (__memcpyable<_Iter, _Out>::__value)
260 using _ValueTypeI = iter_value_t<_Iter>;
261 static_assert(_IsMove
262 ? is_move_assignable_v<_ValueTypeI>
263 : is_copy_assignable_v<_ValueTypeI>);
264 auto __num = __last - __first;
266 __builtin_memmove(__result, __first,
267 sizeof(_ValueTypeI) * __num);
268 return {__first + __num, __result + __num};
272 for (
auto __n = __last - __first; __n > 0; --__n)
274 if constexpr (_IsMove)
277 *__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 using __detail::__is_reverse_iterator;
362 using __detail::__is_normal_iterator;
363 if constexpr (__is_reverse_iterator<_Iter> && same_as<_Iter, _Sent>
364 && __is_reverse_iterator<_Out>)
367 = ranges::__copy_or_move<_IsMove>(
std::move(__last).base(),
370 return {reverse_iterator{
std::move(__in)},
373 else if constexpr (__is_normal_iterator<_Iter> && same_as<_Iter, _Sent>)
376 = ranges::__copy_or_move_backward<_IsMove>(__first.base(),
379 return {decltype(__first){__in},
std::move(__out)};
381 else if constexpr (__is_normal_iterator<_Out>)
384 = ranges::__copy_or_move_backward<_IsMove>(
std::move(__first),
387 return {
std::move(__in), decltype(__result){__out}};
389 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
391 #ifdef __cpp_lib_is_constant_evaluated
392 if (!std::is_constant_evaluated())
395 if constexpr (__memcpyable<_Out, _Iter>::__value)
397 using _ValueTypeI = iter_value_t<_Iter>;
398 static_assert(_IsMove
399 ? is_move_assignable_v<_ValueTypeI>
400 : is_copy_assignable_v<_ValueTypeI>);
401 auto __num = __last - __first;
403 __builtin_memmove(__result - __num, __first,
404 sizeof(_ValueTypeI) * __num);
405 return {__first + __num, __result - __num};
409 auto __lasti = ranges::next(__first, __last);
410 auto __tail = __lasti;
412 for (
auto __n = __last - __first; __n > 0; --__n)
416 if constexpr (_IsMove)
425 auto __lasti = ranges::next(__first, __last);
426 auto __tail = __lasti;
428 while (__first != __tail)
432 if constexpr (_IsMove)
441 struct __copy_backward_fn
443 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
444 b
idirectional_iterator _Iter2>
445 requires indirectly_copyable<_Iter1, _Iter2>
446 constexpr copy_backward_result<_Iter1, _Iter2>
447 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result)
const
449 return ranges::__copy_or_move_backward<false>(
std::move(__first),
454 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
455 requires indirectly_copyable<iterator_t<_Range>, _Iter>
456 constexpr copy_backward_result<borrowed_iterator_t<_Range>, _Iter>
457 operator()(_Range&& __r, _Iter __result)
const
464 inline constexpr __copy_backward_fn copy_backward{};
466 struct __move_backward_fn
468 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
469 b
idirectional_iterator _Iter2>
470 requires indirectly_movable<_Iter1, _Iter2>
471 constexpr move_backward_result<_Iter1, _Iter2>
472 operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result)
const
474 return ranges::__copy_or_move_backward<true>(
std::move(__first),
479 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
480 requires indirectly_movable<iterator_t<_Range>, _Iter>
481 constexpr move_backward_result<borrowed_iterator_t<_Range>, _Iter>
482 operator()(_Range&& __r, _Iter __result)
const
491 template<
typename _Iter,
typename _Out>
492 using copy_n_result = in_out_result<_Iter, _Out>;
496 template<input_iterator _Iter, weakly_incrementable _Out>
497 requires indirectly_copyable<_Iter, _Out>
498 constexpr copy_n_result<_Iter, _Out>
499 operator()(_Iter __first, iter_difference_t<_Iter> __n,
502 if constexpr (random_access_iterator<_Iter>)
503 return ranges::copy(__first, __first + __n, std::
move(__result));
506 for (; __n > 0; --__n, (void)++__result, (
void)++__first)
507 *__result = *__first;
513 inline constexpr __copy_n_fn copy_n{};
517 template<
typename _Tp, output_iterator<const _Tp&> _Out>
519 operator()(_Out __first, iter_difference_t<_Out> __n,
520 const _Tp& __value)
const
528 if constexpr (is_pointer_v<_Out>
530 && __is_byte<remove_pointer_t<_Out>>::__value
533 __builtin_memset(__first, static_cast<unsigned char>(__value), __n);
534 return __first + __n;
536 else if constexpr (is_scalar_v<_Tp>)
538 const auto __tmp = __value;
539 for (; __n > 0; --__n, (void)++__first)
545 for (; __n > 0; --__n, (void)++__first)
552 inline constexpr __fill_n_fn fill_n{};
556 template<
typename _Tp,
557 output_iterator<const _Tp&> _Out, sentinel_for<_Out> _Sent>
559 operator()(_Out __first, _Sent __last,
const _Tp& __value)
const
563 if constexpr (sized_sentinel_for<_Sent, _Out>)
565 const auto __len = __last - __first;
566 return ranges::fill_n(__first, __len, __value);
568 else if constexpr (is_scalar_v<_Tp>)
570 const auto __tmp = __value;
571 for (; __first != __last; ++__first)
577 for (; __first != __last; ++__first)
583 template<
typename _Tp, output_range<const _Tp&> _Range>
584 constexpr borrowed_iterator_t<_Range>
585 operator()(_Range&& __r,
const _Tp& __value)
const
591 inline constexpr __fill_fn fill{};
593 _GLIBCXX_END_NAMESPACE_VERSION
597 #endif // _RANGES_ALGOBASE_H
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
typename conditional< _Cond, _Iftrue, _Iffalse >::type conditional_t
Alias template for conditional.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
constexpr _BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.