1 // Core algorithmic facilities -*- C++ -*-
3 // Copyright (C) 2020-2024 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file bits/ranges_algobase.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{algorithm}
30 #ifndef _RANGES_ALGOBASE_H
31 #define _RANGES_ALGOBASE_H 1
33 #if __cplusplus > 201703L
36 #include <bits/stl_iterator_base_funcs.h>
37 #include <bits/stl_iterator.h>
38 #include <bits/stl_algobase.h> // __memcpy
39 #include <bits/ranges_base.h> // ranges::begin, ranges::range etc.
40 #include <bits/invoke.h> // __invoke
41 #include <bits/cpp_type_traits.h> // __is_byte
42 #include <bits/stl_algobase.h> // __memcmp
44 #if __cpp_lib_concepts
45 namespace std
_GLIBCXX_VISIBILITY(default)
47 _GLIBCXX_BEGIN_NAMESPACE_VERSION
52 template<typename _Tp
>
53 constexpr inline bool __is_normal_iterator
= false;
55 template<typename _Iterator
, typename _Container
>
57 __is_normal_iterator
<__gnu_cxx::__normal_iterator
<_Iterator
,
60 template<typename _Tp
>
61 constexpr inline bool __is_reverse_iterator
= false;
63 template<typename _Iterator
>
65 __is_reverse_iterator
<reverse_iterator
<_Iterator
>> = true;
67 template<typename _Tp
>
68 constexpr inline bool __is_move_iterator
= false;
70 template<typename _Iterator
>
72 __is_move_iterator
<move_iterator
<_Iterator
>> = true;
73 } // namespace __detail
75 #if __glibcxx_ranges_iota >= 202202L // C++ >= 23
76 template<typename _Out
, typename _Tp
>
77 struct out_value_result
79 [[no_unique_address
]] _Out out
;
80 [[no_unique_address
]] _Tp value
;
82 template<typename _Out2
, typename _Tp2
>
83 requires convertible_to
<const _Out
&, _Out2
>
84 && convertible_to
<const _Tp
&, _Tp2
>
86 operator out_value_result
<_Out2
, _Tp2
>() const &
87 { return {out
, value
}; }
89 template<typename _Out2
, typename _Tp2
>
90 requires convertible_to
<_Out
, _Out2
>
91 && convertible_to
<_Tp
, _Tp2
>
93 operator out_value_result
<_Out2
, _Tp2
>() &&
94 { return {std::move(out
), std::move(value
)}; }
96 #endif // __glibcxx_ranges_iota
100 template<input_iterator _Iter1
, sentinel_for
<_Iter1
> _Sent1
,
101 input_iterator _Iter2
, sentinel_for
<_Iter2
> _Sent2
,
102 typename _Pred
= ranges::equal_to
,
103 typename _Proj1
= identity
, typename _Proj2
= identity
>
104 requires indirectly_comparable
<_Iter1
, _Iter2
, _Pred
, _Proj1
, _Proj2
>
106 operator()(_Iter1 __first1
, _Sent1 __last1
,
107 _Iter2 __first2
, _Sent2 __last2
, _Pred __pred
= {},
108 _Proj1 __proj1
= {}, _Proj2 __proj2
= {}) const
110 // TODO: implement more specializations to at least have parity with
112 if constexpr (__detail::__is_normal_iterator
<_Iter1
>
113 && same_as
<_Iter1
, _Sent1
>)
114 return (*this)(__first1
.base(), __last1
.base(),
115 std::move(__first2
), std::move(__last2
),
117 std::move(__proj1
), std::move(__proj2
));
118 else if constexpr (__detail::__is_normal_iterator
<_Iter2
>
119 && same_as
<_Iter2
, _Sent2
>)
120 return (*this)(std::move(__first1
), std::move(__last1
),
121 __first2
.base(), __last2
.base(),
123 std::move(__proj1
), std::move(__proj2
));
124 else if constexpr (sized_sentinel_for
<_Sent1
, _Iter1
>
125 && sized_sentinel_for
<_Sent2
, _Iter2
>)
127 auto __d1
= ranges::distance(__first1
, __last1
);
128 auto __d2
= ranges::distance(__first2
, __last2
);
132 using _ValueType1
= iter_value_t
<_Iter1
>;
133 constexpr bool __use_memcmp
134 = ((is_integral_v
<_ValueType1
> || is_pointer_v
<_ValueType1
>)
135 && __memcmpable
<_Iter1
, _Iter2
>::__value
136 && is_same_v
<_Pred
, ranges::equal_to
>
137 && is_same_v
<_Proj1
, identity
>
138 && is_same_v
<_Proj2
, identity
>);
139 if constexpr (__use_memcmp
)
141 if (const size_t __len
= (__last1
- __first1
))
142 return !std::__memcmp(__first1
, __first2
, __len
);
147 for (; __first1
!= __last1
; ++__first1
, (void)++__first2
)
148 if (!(bool)std::__invoke(__pred
,
149 std::__invoke(__proj1
, *__first1
),
150 std::__invoke(__proj2
, *__first2
)))
157 for (; __first1
!= __last1
&& __first2
!= __last2
;
158 ++__first1
, (void)++__first2
)
159 if (!(bool)std::__invoke(__pred
,
160 std::__invoke(__proj1
, *__first1
),
161 std::__invoke(__proj2
, *__first2
)))
163 return __first1
== __last1
&& __first2
== __last2
;
167 template<input_range _Range1
, input_range _Range2
,
168 typename _Pred
= ranges::equal_to
,
169 typename _Proj1
= identity
, typename _Proj2
= identity
>
170 requires indirectly_comparable
<iterator_t
<_Range1
>, iterator_t
<_Range2
>,
171 _Pred
, _Proj1
, _Proj2
>
173 operator()(_Range1
&& __r1
, _Range2
&& __r2
, _Pred __pred
= {},
174 _Proj1 __proj1
= {}, _Proj2 __proj2
= {}) const
176 return (*this)(ranges::begin(__r1
), ranges::end(__r1
),
177 ranges::begin(__r2
), ranges::end(__r2
),
179 std::move(__proj1
), std::move(__proj2
));
183 inline constexpr __equal_fn equal
{};
185 template<typename _Iter
, typename _Out
>
188 [[no_unique_address
]] _Iter in
;
189 [[no_unique_address
]] _Out out
;
191 template<typename _Iter2
, typename _Out2
>
192 requires convertible_to
<const _Iter
&, _Iter2
>
193 && convertible_to
<const _Out
&, _Out2
>
195 operator in_out_result
<_Iter2
, _Out2
>() const &
196 { return {in
, out
}; }
198 template<typename _Iter2
, typename _Out2
>
199 requires convertible_to
<_Iter
, _Iter2
>
200 && convertible_to
<_Out
, _Out2
>
202 operator in_out_result
<_Iter2
, _Out2
>() &&
203 { return {std::move(in
), std::move(out
)}; }
206 template<typename _Iter
, typename _Out
>
207 using copy_result
= in_out_result
<_Iter
, _Out
>;
209 template<typename _Iter
, typename _Out
>
210 using move_result
= in_out_result
<_Iter
, _Out
>;
212 template<typename _Iter1
, typename _Iter2
>
213 using move_backward_result
= in_out_result
<_Iter1
, _Iter2
>;
215 template<typename _Iter1
, typename _Iter2
>
216 using copy_backward_result
= in_out_result
<_Iter1
, _Iter2
>;
218 template<bool _IsMove
,
219 bidirectional_iterator _Iter
, sentinel_for
<_Iter
> _Sent
,
220 bidirectional_iterator _Out
>
222 ? indirectly_movable
<_Iter
, _Out
>
223 : indirectly_copyable
<_Iter
, _Out
>)
224 constexpr __conditional_t
<_IsMove
,
225 move_backward_result
<_Iter
, _Out
>,
226 copy_backward_result
<_Iter
, _Out
>>
227 __copy_or_move_backward(_Iter __first
, _Sent __last
, _Out __result
);
229 template<bool _IsMove
,
230 input_iterator _Iter
, sentinel_for
<_Iter
> _Sent
,
231 weakly_incrementable _Out
>
233 ? indirectly_movable
<_Iter
, _Out
>
234 : indirectly_copyable
<_Iter
, _Out
>)
235 constexpr __conditional_t
<_IsMove
,
236 move_result
<_Iter
, _Out
>,
237 copy_result
<_Iter
, _Out
>>
238 __copy_or_move(_Iter __first
, _Sent __last
, _Out __result
)
240 // TODO: implement more specializations to be at least on par with
241 // std::copy/std::move.
242 using __detail::__is_move_iterator
;
243 using __detail::__is_reverse_iterator
;
244 using __detail::__is_normal_iterator
;
245 if constexpr (__is_move_iterator
<_Iter
> && same_as
<_Iter
, _Sent
>)
248 = ranges::__copy_or_move
<true>(std::move(__first
).base(),
249 std::move(__last
).base(),
250 std::move(__result
));
251 return {move_iterator
{std::move(__in
)}, std::move(__out
)};
253 else if constexpr (__is_reverse_iterator
<_Iter
> && same_as
<_Iter
, _Sent
>
254 && __is_reverse_iterator
<_Out
>)
257 = ranges::__copy_or_move_backward
<_IsMove
>(std::move(__last
).base(),
258 std::move(__first
).base(),
259 std::move(__result
).base());
260 return {reverse_iterator
{std::move(__in
)},
261 reverse_iterator
{std::move(__out
)}};
263 else if constexpr (__is_normal_iterator
<_Iter
> && same_as
<_Iter
, _Sent
>)
266 = ranges::__copy_or_move
<_IsMove
>(__first
.base(), __last
.base(),
267 std::move(__result
));
268 return {decltype(__first
){__in
}, std::move(__out
)};
270 else if constexpr (__is_normal_iterator
<_Out
>)
273 = ranges::__copy_or_move
<_IsMove
>(std::move(__first
), __last
, __result
.base());
274 return {std::move(__in
), decltype(__result
){__out
}};
276 else if constexpr (sized_sentinel_for
<_Sent
, _Iter
>)
278 if (!std::__is_constant_evaluated())
280 if constexpr (__memcpyable
<_Iter
, _Out
>::__value
)
282 using _ValueTypeI
= iter_value_t
<_Iter
>;
283 static_assert(_IsMove
284 ? is_move_assignable_v
<_ValueTypeI
>
285 : is_copy_assignable_v
<_ValueTypeI
>);
286 auto __num
= __last
- __first
;
288 __builtin_memmove(__result
, __first
,
289 sizeof(_ValueTypeI
) * __num
);
290 return {__first
+ __num
, __result
+ __num
};
294 for (auto __n
= __last
- __first
; __n
> 0; --__n
)
296 if constexpr (_IsMove
)
297 *__result
= std::move(*__first
);
299 *__result
= *__first
;
303 return {std::move(__first
), std::move(__result
)};
307 while (__first
!= __last
)
309 if constexpr (_IsMove
)
310 *__result
= std::move(*__first
);
312 *__result
= *__first
;
316 return {std::move(__first
), std::move(__result
)};
322 template<input_iterator _Iter
, sentinel_for
<_Iter
> _Sent
,
323 weakly_incrementable _Out
>
324 requires indirectly_copyable
<_Iter
, _Out
>
325 constexpr copy_result
<_Iter
, _Out
>
326 operator()(_Iter __first
, _Sent __last
, _Out __result
) const
328 return ranges::__copy_or_move
<false>(std::move(__first
),
330 std::move(__result
));
333 template<input_range _Range
, weakly_incrementable _Out
>
334 requires indirectly_copyable
<iterator_t
<_Range
>, _Out
>
335 constexpr copy_result
<borrowed_iterator_t
<_Range
>, _Out
>
336 operator()(_Range
&& __r
, _Out __result
) const
338 return (*this)(ranges::begin(__r
), ranges::end(__r
),
339 std::move(__result
));
343 inline constexpr __copy_fn copy
{};
347 template<input_iterator _Iter
, sentinel_for
<_Iter
> _Sent
,
348 weakly_incrementable _Out
>
349 requires indirectly_movable
<_Iter
, _Out
>
350 constexpr move_result
<_Iter
, _Out
>
351 operator()(_Iter __first
, _Sent __last
, _Out __result
) const
353 return ranges::__copy_or_move
<true>(std::move(__first
),
355 std::move(__result
));
358 template<input_range _Range
, weakly_incrementable _Out
>
359 requires indirectly_movable
<iterator_t
<_Range
>, _Out
>
360 constexpr move_result
<borrowed_iterator_t
<_Range
>, _Out
>
361 operator()(_Range
&& __r
, _Out __result
) const
363 return (*this)(ranges::begin(__r
), ranges::end(__r
),
364 std::move(__result
));
368 inline constexpr __move_fn move
{};
370 template<bool _IsMove
,
371 bidirectional_iterator _Iter
, sentinel_for
<_Iter
> _Sent
,
372 bidirectional_iterator _Out
>
374 ? indirectly_movable
<_Iter
, _Out
>
375 : indirectly_copyable
<_Iter
, _Out
>)
376 constexpr __conditional_t
<_IsMove
,
377 move_backward_result
<_Iter
, _Out
>,
378 copy_backward_result
<_Iter
, _Out
>>
379 __copy_or_move_backward(_Iter __first
, _Sent __last
, _Out __result
)
381 // TODO: implement more specializations to be at least on par with
382 // std::copy_backward/std::move_backward.
383 using __detail::__is_reverse_iterator
;
384 using __detail::__is_normal_iterator
;
385 if constexpr (__is_reverse_iterator
<_Iter
> && same_as
<_Iter
, _Sent
>
386 && __is_reverse_iterator
<_Out
>)
389 = ranges::__copy_or_move
<_IsMove
>(std::move(__last
).base(),
390 std::move(__first
).base(),
391 std::move(__result
).base());
392 return {reverse_iterator
{std::move(__in
)},
393 reverse_iterator
{std::move(__out
)}};
395 else if constexpr (__is_normal_iterator
<_Iter
> && same_as
<_Iter
, _Sent
>)
398 = ranges::__copy_or_move_backward
<_IsMove
>(__first
.base(),
400 std::move(__result
));
401 return {decltype(__first
){__in
}, std::move(__out
)};
403 else if constexpr (__is_normal_iterator
<_Out
>)
406 = ranges::__copy_or_move_backward
<_IsMove
>(std::move(__first
),
409 return {std::move(__in
), decltype(__result
){__out
}};
411 else if constexpr (sized_sentinel_for
<_Sent
, _Iter
>)
413 if (!std::__is_constant_evaluated())
415 if constexpr (__memcpyable
<_Out
, _Iter
>::__value
)
417 using _ValueTypeI
= iter_value_t
<_Iter
>;
418 static_assert(_IsMove
419 ? is_move_assignable_v
<_ValueTypeI
>
420 : is_copy_assignable_v
<_ValueTypeI
>);
421 auto __num
= __last
- __first
;
423 __builtin_memmove(__result
- __num
, __first
,
424 sizeof(_ValueTypeI
) * __num
);
425 return {__first
+ __num
, __result
- __num
};
429 auto __lasti
= ranges::next(__first
, __last
);
430 auto __tail
= __lasti
;
432 for (auto __n
= __last
- __first
; __n
> 0; --__n
)
436 if constexpr (_IsMove
)
437 *__result
= std::move(*__tail
);
441 return {std::move(__lasti
), std::move(__result
)};
445 auto __lasti
= ranges::next(__first
, __last
);
446 auto __tail
= __lasti
;
448 while (__first
!= __tail
)
452 if constexpr (_IsMove
)
453 *__result
= std::move(*__tail
);
457 return {std::move(__lasti
), std::move(__result
)};
461 struct __copy_backward_fn
463 template<bidirectional_iterator _Iter1
, sentinel_for
<_Iter1
> _Sent1
,
464 bidirectional_iterator _Iter2
>
465 requires indirectly_copyable
<_Iter1
, _Iter2
>
466 constexpr copy_backward_result
<_Iter1
, _Iter2
>
467 operator()(_Iter1 __first
, _Sent1 __last
, _Iter2 __result
) const
469 return ranges::__copy_or_move_backward
<false>(std::move(__first
),
471 std::move(__result
));
474 template<bidirectional_range _Range
, bidirectional_iterator _Iter
>
475 requires indirectly_copyable
<iterator_t
<_Range
>, _Iter
>
476 constexpr copy_backward_result
<borrowed_iterator_t
<_Range
>, _Iter
>
477 operator()(_Range
&& __r
, _Iter __result
) const
479 return (*this)(ranges::begin(__r
), ranges::end(__r
),
480 std::move(__result
));
484 inline constexpr __copy_backward_fn copy_backward
{};
486 struct __move_backward_fn
488 template<bidirectional_iterator _Iter1
, sentinel_for
<_Iter1
> _Sent1
,
489 bidirectional_iterator _Iter2
>
490 requires indirectly_movable
<_Iter1
, _Iter2
>
491 constexpr move_backward_result
<_Iter1
, _Iter2
>
492 operator()(_Iter1 __first
, _Sent1 __last
, _Iter2 __result
) const
494 return ranges::__copy_or_move_backward
<true>(std::move(__first
),
496 std::move(__result
));
499 template<bidirectional_range _Range
, bidirectional_iterator _Iter
>
500 requires indirectly_movable
<iterator_t
<_Range
>, _Iter
>
501 constexpr move_backward_result
<borrowed_iterator_t
<_Range
>, _Iter
>
502 operator()(_Range
&& __r
, _Iter __result
) const
504 return (*this)(ranges::begin(__r
), ranges::end(__r
),
505 std::move(__result
));
509 inline constexpr __move_backward_fn move_backward
{};
511 template<typename _Iter
, typename _Out
>
512 using copy_n_result
= in_out_result
<_Iter
, _Out
>;
516 template<input_iterator _Iter
, weakly_incrementable _Out
>
517 requires indirectly_copyable
<_Iter
, _Out
>
518 constexpr copy_n_result
<_Iter
, _Out
>
519 operator()(_Iter __first
, iter_difference_t
<_Iter
> __n
,
522 if constexpr (random_access_iterator
<_Iter
>)
525 return ranges::copy(__first
, __first
+ __n
, std::move(__result
));
529 for (; __n
> 0; --__n
, (void)++__result
, (void)++__first
)
530 *__result
= *__first
;
532 return {std::move(__first
), std::move(__result
)};
536 inline constexpr __copy_n_fn copy_n
{};
540 template<typename _Tp
, output_iterator
<const _Tp
&> _Out
>
542 operator()(_Out __first
, iter_difference_t
<_Out
> __n
,
543 const _Tp
& __value
) const
545 // TODO: implement more specializations to be at least on par with
550 if constexpr (is_scalar_v
<_Tp
>)
552 // TODO: Generalize this optimization to contiguous iterators.
553 if constexpr (is_pointer_v
<_Out
>
554 // Note that __is_byte already implies !is_volatile.
555 && __is_byte
<remove_pointer_t
<_Out
>>::__value
558 if (!std::__is_constant_evaluated())
560 __builtin_memset(__first
,
561 static_cast<unsigned char>(__value
),
563 return __first
+ __n
;
567 const auto __tmp
= __value
;
568 for (; __n
> 0; --__n
, (void)++__first
)
574 for (; __n
> 0; --__n
, (void)++__first
)
581 inline constexpr __fill_n_fn fill_n
{};
585 template<typename _Tp
,
586 output_iterator
<const _Tp
&> _Out
, sentinel_for
<_Out
> _Sent
>
588 operator()(_Out __first
, _Sent __last
, const _Tp
& __value
) const
590 // TODO: implement more specializations to be at least on par with
592 if constexpr (sized_sentinel_for
<_Sent
, _Out
>)
594 const auto __len
= __last
- __first
;
595 return ranges::fill_n(__first
, __len
, __value
);
597 else if constexpr (is_scalar_v
<_Tp
>)
599 const auto __tmp
= __value
;
600 for (; __first
!= __last
; ++__first
)
606 for (; __first
!= __last
; ++__first
)
612 template<typename _Tp
, output_range
<const _Tp
&> _Range
>
613 constexpr borrowed_iterator_t
<_Range
>
614 operator()(_Range
&& __r
, const _Tp
& __value
) const
616 return (*this)(ranges::begin(__r
), ranges::end(__r
), __value
);
620 inline constexpr __fill_fn fill
{};
622 _GLIBCXX_END_NAMESPACE_VERSION
626 #endif // _RANGES_ALGOBASE_H