On Tue, 25 Nov 2025, Tomasz Kaminski wrote:
>
>
> On Tue, Nov 25, 2025 at 2:58 PM Patrick Palka <[email protected]> wrote:
> On Tue, 25 Nov 2025, Tomasz Kaminski wrote:
>
> >
> >
> > On Tue, Nov 25, 2025 at 2:28 PM Patrick Palka <[email protected]>
> wrote:
> > changes in v4: define the new helpers in
> stl_iterator_base_funcs.h
> > rather than stl_iterator_base_types.h. also define an
> __iter_move_val
> > helper
> >
> > changes v3: add inclusive_scan test using zip's proxy iterator.
> rename
> > tests from p2408r5.cc to c++20_iter.cc
> >
> > changes v2: more tests, and the one-argument version of
> > __iter_concept_or_category is now constexpr instead of
> > consteval
> >
> > -- >8 --
> >
> > From the paper's abstract:
> >
> > Change the iterator requirements for non-Ranges algorithms.
> For
> > forward iterators and above that are constant iterators,
> instead of
> > requiring that iterators meet certain Cpp17...Iterator
> requirements,
> > require that the iterators model certain iterator concepts.
> This makes
> > iterators from several standard views usable with non-Ranges
> > algorithms that require forward iterators or above, such as
> the
> > parallel overloads of most algorithms.
> >
> > This patch narrowly implements P2408R5 in C++23 mode and C++20
> mode
> > (as an extension). "Narrowly" because just as in the paper, we
> don't
> > attempt to relax the requirements of mutable iterators even
> though it's
> > possible in theory. Note that the PSTL algorithm requirements
> have
> > already been relaxed in r15-3650. And we don't bother touching
> the
> > deprecated parallel mode algorithms under include/parallel.
> >
> > The main workhorse of this paper is a new helper
> > __iterator_concept_or_category that replaces existing uses of
> > __iterator_category and iterator_traits::iterator_category with
> constant
> > iterators. This new helper considers both the iterator_concept
> and
> > iterator_category of the given iterator and returns the former
> if it's
> > at least as strong as the latter. It's implemented in terms of
> the
> > __promotable_iterator concept added in r16-2588 that made
> std::advance
> > etc aware of C++20 iterators. Note that this helper doesn't
> check the
> > actual C++20 iterator concepts (which check syntactic
> requirements along
> > with iterator_concept if it's defined) and instead just checks
> for, and
> > fully trusts, the iterator_concept defined by the iterator
> type. This
> > is a slight deviation from the paper but IMHO it's consistent
> with the
> > existing trusting of iterator_category and should be good
> enough in
> > practice, though it means C++20 iterators that don't define
> > iterator_concept will not be recognized as such by this helper
> even if
> > they otherwise model the std::foo_iterator concept. (An
> undefined
> > iterator_concept effectively defaults to
> random_access_iterator_tag.)
> >
> > Most of the changes made here are effectively optimizations
> that don't
> > have a semantic impact, e.g. for std::reduce. I added tests
> for a
> > couple of algorithms where these changes are observable.
> >
> > The new __iterator_concept_or_category helper can probably also
> be used
> > to fix PR100070 "Standard library container iterator-pair
> constructors
> > should check C++20 iterator concepts".
> >
> > As a follow-up to this patch we should either remove the
> Boost-style
> > concept checks, or relax them accordingly. It seems we're
> leaning
> > towards removing them outright; see this thread:
> > https://gcc.gnu.org/pipermail/libstdc++/2025-May/061568.html
> >
> > As suggested by Tomasz, this patch also introduces an
> __iter_move_val
> > wrapper around ranges::iter_move that also converts to the
> iterator's
> > value type and is usable before C++20 as well.
> >
> > PR libstdc++/113299
> >
> > libstdc++-v3/ChangeLog:
> >
> > * include/bits/deque.tcc (__copy_move_a1): Constrain
> with
> > __is_any_random_access_iter instead of
> __is_random_access_iter.
> > (__copy_move_backward_a1): Likewise.
> > (__equal_aux1): Likewise.
> > * include/bits/stl_algo.h (__search_n): Use
> > __iter_concept_or_category instead of
> __iterator_category
> > or iterator_traits::iterator_category.
> > (find_end): Likewise.
> > (__is_permutation): Likewise.
> > (for_each_n): Likewise.
> > (unique_copy): Likewise, for constant iterators.
> > (sample): Likewise, for constant iterators.
> > * include/bits/stl_algobase.h (__copy_move_a1): Adjust
> > deque-based forward declaration accordingly.
> > (__copy_move_backward_a1): Likewise.
> > (__equal_aux1): Likewise.
> > (__lexicographical_compare_impl): Use
> > __iter_concept_or_category instead of
> __iterator_category or
> > iterator_traits::iterator_category.
> > (__equal4): Likewise.
> > * include/bits/stl_iterator_base_funcs.h
> > (__iter_concept_or_category): New.
> > (__is_any_random_access_iter): New.
> > (__iter_move_val): New.
> > * include/bits/stl_uninitialized.h
> (uninitialized_copy_n):
> > Use __iterator_concept_or_category instead of
> > __iterator_category for the constant iterator __first.
> > (__uninitialized_copy_n_pair): Likewise.
> > * include/bits/version.def
> (algorithm_iterator_requirements):
> > Define.
> > * include/bits/version.h: Regenerate.
> > * include/std/algorithm: Provide the FTM
> > __cpp_lib_algorithm_iterator_requirements.
> > * include/std/memory: Likewise.
> > * include/std/numeric: Likewise.
> > (reduce): Use __is_any_random_access_iter instead of
> > __is_random_access_iter.
> > (transform_reduce): Likewise.
> > (inclusive_scan): Use __iter_move_val instead of
> std::move.
> > * testsuite/25_algorithms/find_end/c++20_iter.cc: New
> test.
> > * testsuite/25_algorithms/sample/c++20_iter.cc: New
> test.
> > * testsuite/25_algorithms/search_n/c++20_iter.cc: New
> test.
> > * testsuite/25_algorithms/unique_copy/c++20_iter.cc:
> New test.
> > * testsuite/26_numerics/inclusive_scan/c++20_iter.cc:
> New test.
> > ---
> > libstdc++-v3/include/bits/deque.tcc | 8 +--
> > libstdc++-v3/include/bits/stl_algo.h | 28 ++++----
> > libstdc++-v3/include/bits/stl_algobase.h | 20 +++---
> > .../include/bits/stl_iterator_base_funcs.h | 70
> +++++++++++++++++++
> > libstdc++-v3/include/bits/stl_uninitialized.h | 4 +-
> > libstdc++-v3/include/bits/version.def | 9 +++
> > libstdc++-v3/include/bits/version.h | 10 +++
> > libstdc++-v3/include/std/algorithm | 1 +
> > libstdc++-v3/include/std/memory | 1 +
> > libstdc++-v3/include/std/numeric | 11 +--
> > .../25_algorithms/find_end/c++20_iter.cc | 23 ++++++
> > .../25_algorithms/sample/c++20_iter.cc | 23 ++++++
> > .../25_algorithms/search_n/c++20_iter.cc | 21 ++++++
> > .../25_algorithms/unique_copy/c++20_iter.cc | 33 +++++++++
> > .../26_numerics/inclusive_scan/c++20_iter.cc | 26 +++++++
> > 15 files changed, 253 insertions(+), 35 deletions(-)
> > create mode 100644
> libstdc++-v3/testsuite/25_algorithms/find_end/c++20_iter.cc
> > create mode 100644
> libstdc++-v3/testsuite/25_algorithms/sample/c++20_iter.cc
> > create mode 100644
> libstdc++-v3/testsuite/25_algorithms/search_n/c++20_iter.cc
> > create mode 100644
> libstdc++-v3/testsuite/25_algorithms/unique_copy/c++20_iter.cc
> > create mode 100644
> libstdc++-v3/testsuite/26_numerics/inclusive_scan/c++20_iter.cc
> >
> > diff --git a/libstdc++-v3/include/bits/deque.tcc
> b/libstdc++-v3/include/bits/deque.tcc
> > index 20b23fffc9e1..e409f3a3fc57 100644
> > --- a/libstdc++-v3/include/bits/deque.tcc
> > +++ b/libstdc++-v3/include/bits/deque.tcc
> > @@ -1225,7 +1225,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> >
> > template<bool _IsMove, typename _II, typename _Tp>
> > typename __gnu_cxx::__enable_if<
> > - __is_random_access_iter<_II>::__value,
> > + __is_any_random_access_iter<_II>::__value,
> > _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
> >::__type
> > __copy_move_a1(_II __first, _II __last,
> > _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&,
> _Tp*> __result)
> > @@ -1347,7 +1347,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> >
> > template<bool _IsMove, typename _II, typename _Tp>
> > typename __gnu_cxx::__enable_if<
> > - __is_random_access_iter<_II>::__value,
> > + __is_any_random_access_iter<_II>::__value,
> > _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
> >::__type
> > __copy_move_backward_a1(_II __first, _II __last,
> > _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&,
> _Tp*> __result)
> > @@ -1406,7 +1406,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> >
> > template<typename _Tp, typename _Ref, typename _Ptr,
> typename _II>
> > typename __gnu_cxx::__enable_if<
> > - __is_random_access_iter<_II>::__value, bool>::__type
> > + __is_any_random_access_iter<_II>::__value, bool>::__type
> > __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref,
> _Ptr> __first1,
> > _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref,
> _Ptr> __last1,
> > _II __first2)
> > @@ -1422,7 +1422,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> >
> > template<typename _II, typename _Tp, typename _Ref, typename
> _Ptr>
> > typename __gnu_cxx::__enable_if<
> > - __is_random_access_iter<_II>::__value, bool>::__type
> > + __is_any_random_access_iter<_II>::__value, bool>::__type
> > __equal_aux1(_II __first1, _II __last1,
> > _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref,
> _Ptr> __first2)
> > {
> > diff --git a/libstdc++-v3/include/bits/stl_algo.h
> b/libstdc++-v3/include/bits/stl_algo.h
> > index bbd1800af779..0d8f7af9d272 100644
> > --- a/libstdc++-v3/include/bits/stl_algo.h
> > +++ b/libstdc++-v3/include/bits/stl_algo.h
> > @@ -226,7 +226,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> > return std::__find_if(__first, __last, __unary_pred);
> >
> > return std::__search_n_aux(__first, __last, __count,
> __unary_pred,
> > -
> std::__iterator_category(__first));
> > +
> std::__iter_concept_or_category(__first));
> > }
> >
> > // find_end for forward iterators.
> > @@ -337,8 +337,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> > __glibcxx_requires_valid_range(__first2, __last2);
> >
> > return std::__find_end(__first1, __last1, __first2,
> __last2,
> > - std::__iterator_category(__first1),
> > - std::__iterator_category(__first2),
> > +
> std::__iter_concept_or_category(__first1),
> > +
> std::__iter_concept_or_category(__first2),
> > __gnu_cxx::__ops::equal_to());
> > }
> >
> > @@ -388,8 +388,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> > __glibcxx_requires_valid_range(__first2, __last2);
> >
> > return std::__find_end(__first1, __last1, __first2,
> __last2,
> > - std::__iterator_category(__first1),
> > - std::__iterator_category(__first2),
> > +
> std::__iter_concept_or_category(__first1),
> > +
> std::__iter_concept_or_category(__first2),
> > __comp);
> > }
> >
> > @@ -3495,9 +3495,9 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> > _BinaryPredicate __pred)
> > {
> > using _Cat1
> > - = typename
> iterator_traits<_ForwardIterator1>::iterator_category;
> > + =
> __decltype(std::__iter_concept_or_category<_ForwardIterator1>());
> > using _Cat2
> > - = typename
> iterator_traits<_ForwardIterator2>::iterator_category;
> > + =
> __decltype(std::__iter_concept_or_category<_ForwardIterator2>());
> > using _It1_is_RA = is_same<_Cat1,
> random_access_iterator_tag>;
> > using _It2_is_RA = is_same<_Cat2,
> random_access_iterator_tag>;
> > constexpr bool __ra_iters = __and_<_It1_is_RA,
> _It2_is_RA>::value;
> > @@ -3800,7 +3800,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> > for_each_n(_InputIterator __first, _Size __n, _Function
> __f)
> > {
> > auto __n2 = std::__size_to_integer(__n);
> > - using _Cat = typename
> iterator_traits<_InputIterator>::iterator_category;
> > + using _Cat =
> __decltype(std::__iter_concept_or_category<_InputIterator>());
> > if constexpr (is_base_of_v<random_access_iterator_tag,
> _Cat>)
> > {
> > if (__n2 <= 0)
> > @@ -4450,7 +4450,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> > return __result;
> > return std::__unique_copy(__first, __last, __result,
> > __gnu_cxx::__ops::equal_to(),
> > -
> std::__iterator_category(__first));
> > +
> std::__iter_concept_or_category(__first));
> > }
> >
> > /**
> > @@ -4491,7 +4491,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> > if (__first == __last)
> > return __result;
> > return std::__unique_copy(__first, __last, __result,
> __binary_pred,
> > -
> std::__iterator_category(__first));
> > +
> std::__iter_concept_or_category(__first));
> > }
> >
> > #if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED
> > @@ -5881,10 +5881,10 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> > _SampleIterator __out, _Distance __n,
> > _UniformRandomBitGenerator&& __g)
> > {
> > - using __pop_cat = typename
> > -
> std::iterator_traits<_PopulationIterator>::iterator_category;
> > - using __samp_cat = typename
> > -
> std::iterator_traits<_SampleIterator>::iterator_category;
> > + using __pop_cat
> > + =
> __decltype(std::__iter_concept_or_category<_PopulationIterator>());
> > + using __samp_cat
> > + = typename
> iterator_traits<_SampleIterator>::iterator_category;
> >
> > static_assert(
> > __or_<is_convertible<__pop_cat, forward_iterator_tag>,
> > diff --git a/libstdc++-v3/include/bits/stl_algobase.h
> b/libstdc++-v3/include/bits/stl_algobase.h
> > index 443cbef76dee..701910afd837 100644
> > --- a/libstdc++-v3/include/bits/stl_algobase.h
> > +++ b/libstdc++-v3/include/bits/stl_algobase.h
> > @@ -480,7 +480,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> >
> > template<bool _IsMove, typename _II, typename _Tp>
> > typename __gnu_cxx::__enable_if<
> > - __is_random_access_iter<_II>::__value,
> > + __is_any_random_access_iter<_II>::__value,
> > _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
> >::__type
> > __copy_move_a1(_II, _II,
> _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
> >
> > @@ -769,7 +769,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> >
> > template<bool _IsMove, typename _II, typename _Tp>
> > typename __gnu_cxx::__enable_if<
> > - __is_random_access_iter<_II>::__value,
> > + __is_any_random_access_iter<_II>::__value,
> > _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
> >::__type
> > __copy_move_backward_a1(_II, _II,
> >
> _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
> > @@ -1219,7 +1219,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> >
> > template<typename _Tp, typename _Ref, typename _Ptr,
> typename _II>
> > typename __gnu_cxx::__enable_if<
> > - __is_random_access_iter<_II>::__value, bool>::__type
> > + __is_any_random_access_iter<_II>::__value, bool>::__type
> > __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref,
> _Ptr>,
> > _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref,
> _Ptr>,
> > _II);
> > @@ -1233,7 +1233,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> >
> > template<typename _II, typename _Tp, typename _Ref, typename
> _Ptr>
> > typename __gnu_cxx::__enable_if<
> > - __is_random_access_iter<_II>::__value, bool>::__type
> > + __is_any_random_access_iter<_II>::__value, bool>::__type
> > __equal_aux1(_II, _II,
> > _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref,
> _Ptr>);
> >
> > @@ -1332,8 +1332,8 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> > _II2 __first2, _II2 __last2,
> > _Compare __comp)
> > {
> > - typedef typename
> iterator_traits<_II1>::iterator_category _Category1;
> > - typedef typename
> iterator_traits<_II2>::iterator_category _Category2;
> > + typedef
> __decltype(std::__iter_concept_or_category<_II1>()) _Category1;
> > + typedef
> __decltype(std::__iter_concept_or_category<_II2>()) _Category2;
> > typedef std::__lc_rai<_Category1, _Category2> __rai_type;
> >
> > __last1 = __rai_type::__newlast1(__first1, __last1,
> __first2, __last2);
> > @@ -1649,8 +1649,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> > __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2
> __last2)
> > {
> > using _RATag = random_access_iterator_tag;
> > - using _Cat1 = typename
> iterator_traits<_II1>::iterator_category;
> > - using _Cat2 = typename
> iterator_traits<_II2>::iterator_category;
> > + using _Cat1 =
> __decltype(std::__iter_concept_or_category<_II1>());
> > + using _Cat2 =
> __decltype(std::__iter_concept_or_category<_II2>());
> > using _RAIters = __and_<is_same<_Cat1, _RATag>,
> is_same<_Cat2, _RATag>>;
> > if constexpr (_RAIters::value)
> > {
> > @@ -1676,8 +1676,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> > _BinaryPredicate __binary_pred)
> > {
> > using _RATag = random_access_iterator_tag;
> > - using _Cat1 = typename
> iterator_traits<_II1>::iterator_category;
> > - using _Cat2 = typename
> iterator_traits<_II2>::iterator_category;
> > + using _Cat1 =
> __decltype(std::__iter_concept_or_category<_II1>());
> > + using _Cat2 =
> __decltype(std::__iter_concept_or_category<_II2>());
> > using _RAIters = __and_<is_same<_Cat1, _RATag>,
> is_same<_Cat2, _RATag>>;
> > if constexpr (_RAIters::value)
> > {
> > diff --git
> a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
> b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
> > index 7c80e1423e45..da5945727093 100644
> > --- a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
> > +++ b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
> > @@ -317,6 +317,76 @@ namespace __detail
> >
> > #endif // C++11
> >
> > +#if __glibcxx_algorithm_iterator_requirements // C++ >= 20
> > + template<typename _Iter>
> > + consteval auto
> > + __iter_concept_or_category()
> > + {
> > + if constexpr (__detail::__promotable_iterator<_Iter>)
> > + {
> > + using __type =
> __detail::__iter_traits<_Iter>::iterator_concept;
> > + if constexpr (derived_from<__type,
> random_access_iterator_tag>)
> > + return random_access_iterator_tag{};
> > + else
> > + return __type{};
> > + }
> > + else
> > + return typename
> iterator_traits<_Iter>::iterator_category{};
> > + }
> > +
> > + template<typename _Iter>
> > + __attribute__((__always_inline__))
> > + constexpr auto
> > + __iter_concept_or_category(const _Iter&)
> > + { return std::__iter_concept_or_category<_Iter>(); }
> > +#else
> > + template<typename _Iter>
> > + __attribute__((__always_inline__))
> > + inline _GLIBCXX_CONSTEXPR
> > + typename iterator_traits<_Iter>::iterator_category
> > + __iter_concept_or_category()
> > + { return typename
> iterator_traits<_Iter>::iterator_category(); }
> > +
> > + template<typename _Iter>
> > + __attribute__((__always_inline__))
> > + inline _GLIBCXX_CONSTEXPR
> > + typename iterator_traits<_Iter>::iterator_category
> > + __iter_concept_or_category(const _Iter&)
> > + { return typename
> iterator_traits<_Iter>::iterator_category(); }
> > +#endif
> > +
> > +#if __cplusplus >= 201103L
> > + // Like __is_random_access_iter, but based off of
> __iter_concept_or_category
> > + // instead of iterator_traits::iterator_category.
> > + template<typename _Iter,
> > + typename _Cat =
> __decltype(__iter_concept_or_category<_Iter>())>
> > + struct __is_any_random_access_iter
> > + : is_base_of<random_access_iterator_tag, _Cat>
> > + { enum { __value = __is_any_random_access_iter::value }; };
> > +#else
> > + template<typename _Iter,
> > + typename _Cat =
> __decltype(__iter_concept_or_category<_Iter>())>
> > + struct __is_any_random_access_iter
> > + { enum { __value =
> __is_base_of(random_access_iterator_tag, _Cat) }; };
> > +#endif
> > +
> > +#if __cplusplus >= 202002L
> > + // A wrapper around ranges::iter_move that also converts to
> the iterator's
> > + // value type.
> > + template<typename _Iter>
> > + [[nodiscard]] constexpr iter_value_t<_Iter>
> > + __iter_move_val(const _Iter& __it)
> > + noexcept(noexcept(ranges::iter_move(__it)))
> >
> > We also need && is_nothrow_cosntructible_v<iter_value_t<_Iter>,
> iter_rvalue_reference_t<_Iter>>>,
> > or just noexcept(iter_value_t<_Iter>(ranges::iter_move(__it)))
> > + { return ranges::iter_move(__it); }
> > +#else
> > + template<typename _Iter>
> > + _GLIBCXX_NODISCARD inline _GLIBCXX_CONSTEXPR
> > + typename iterator_traits<_Iter>::value_type
> > + __iter_move_val(const _Iter& __it)
> > + _GLIBCXX_NOEXCEPT_IF(noexcept(_GLIBCXX_MOVE(*__it)))
> >
> > Similar here, may have _Vt as the defaulted second template
> parameter.
>
> Good catch. Default template arguments on function templates aren't
> supported in C++98, so it seems cleanest to just have three definitinons
> of __iter_move_val:
>
> Thanks. LGTM now.
Thanks for the review.
I noticed shortly after submitting this latest version that using
__iter_move_val might introduce an extra copy in C++98 mode compared to
using _GLIBCXX_MOVE directly, I think. I wonder how much we care?
I guess we could defined __iter_move_val as a macro (_GLIBCXX_ITER_MOVE)
to avoid this extra copy?
>
> -- >8 --
>
> Subject: [PATCH v5] libstdc++: Implement P2408R5 Ranges iterators as
> inputs to
> non-Ranges algorithms
>
> changes in v5: correct __iter_move_val's noexcept-spec
>
> changes in v4: define the new helpers in stl_iterator_base_funcs.h
> rather than stl_iterator_base_types.h. also define an __iter_move_val
> helper
>
> changes v3: add inclusive_scan test using zip's proxy iterator. rename
> tests from p2408r5.cc to c++20_iter.cc
>
> changes v2: more tests, and the one-argument version of
> __iter_concept_or_category is now constexpr instead of
> consteval
>
> -- >8 --
>
> PR libstdc++/113299
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/deque.tcc (__copy_move_a1): Constrain with
> __is_any_random_access_iter instead of __is_random_access_iter.
> (__copy_move_backward_a1): Likewise.
> (__equal_aux1): Likewise.
> * include/bits/stl_algo.h (__search_n): Use
> __iter_concept_or_category instead of __iterator_category
> or iterator_traits::iterator_category.
> (find_end): Likewise.
> (__is_permutation): Likewise.
> (for_each_n): Likewise.
> (unique_copy): Likewise, for constant iterators.
> (sample): Likewise, for constant iterators.
> * include/bits/stl_algobase.h (__copy_move_a1): Adjust
> deque-based forward declaration accordingly.
> (__copy_move_backward_a1): Likewise.
> (__equal_aux1): Likewise.
> (__lexicographical_compare_impl): Use
> __iter_concept_or_category instead of __iterator_category or
> iterator_traits::iterator_category.
> (__equal4): Likewise.
> * include/bits/stl_iterator_base_funcs.h
> (__iter_concept_or_category): New.
> (__is_any_random_access_iter): New.
> (__iter_move_val): New.
> * include/bits/stl_uninitialized.h (uninitialized_copy_n):
> Use __iterator_concept_or_category instead of
> __iterator_category for the constant iterator __first.
> (__uninitialized_copy_n_pair): Likewise.
> * include/bits/version.def (algorithm_iterator_requirements):
> Define.
> * include/bits/version.h: Regenerate.
> * include/std/algorithm: Provide the FTM
> __cpp_lib_algorithm_iterator_requirements.
> * include/std/memory: Likewise.
> * include/std/numeric: Likewise.
> (reduce): Use __is_any_random_access_iter instead of
> __is_random_access_iter.
> (transform_reduce): Likewise.
> (inclusive_scan): Use __iter_move_val instead of std::move.
> * testsuite/25_algorithms/find_end/c++20_iter.cc: New test.
> * testsuite/25_algorithms/sample/c++20_iter.cc: New test.
> * testsuite/25_algorithms/search_n/c++20_iter.cc: New test.
> * testsuite/25_algorithms/unique_copy/c++20_iter.cc: New test.
> * testsuite/26_numerics/inclusive_scan/c++20_iter.cc: New test.
> ---
> libstdc++-v3/include/bits/deque.tcc | 8 +-
> libstdc++-v3/include/bits/stl_algo.h | 28 +++----
> libstdc++-v3/include/bits/stl_algobase.h | 20 ++---
> .../include/bits/stl_iterator_base_funcs.h | 75 +++++++++++++++++++
> libstdc++-v3/include/bits/stl_uninitialized.h | 4 +-
> libstdc++-v3/include/bits/version.def | 9 +++
> libstdc++-v3/include/bits/version.h | 10 +++
> libstdc++-v3/include/std/algorithm | 1 +
> libstdc++-v3/include/std/memory | 1 +
> libstdc++-v3/include/std/numeric | 11 +--
> .../25_algorithms/find_end/c++20_iter.cc | 23 ++++++
> .../25_algorithms/sample/c++20_iter.cc | 23 ++++++
> .../25_algorithms/search_n/c++20_iter.cc | 21 ++++++
> .../25_algorithms/unique_copy/c++20_iter.cc | 33 ++++++++
> .../26_numerics/inclusive_scan/c++20_iter.cc | 26 +++++++
> 15 files changed, 258 insertions(+), 35 deletions(-)
> create mode 100644
> libstdc++-v3/testsuite/25_algorithms/find_end/c++20_iter.cc
> create mode 100644
> libstdc++-v3/testsuite/25_algorithms/sample/c++20_iter.cc
> create mode 100644
> libstdc++-v3/testsuite/25_algorithms/search_n/c++20_iter.cc
> create mode 100644
> libstdc++-v3/testsuite/25_algorithms/unique_copy/c++20_iter.cc
> create mode 100644
> libstdc++-v3/testsuite/26_numerics/inclusive_scan/c++20_iter.cc
>
> diff --git a/libstdc++-v3/include/bits/deque.tcc
> b/libstdc++-v3/include/bits/deque.tcc
> index 20b23fffc9e1..e409f3a3fc57 100644
> --- a/libstdc++-v3/include/bits/deque.tcc
> +++ b/libstdc++-v3/include/bits/deque.tcc
> @@ -1225,7 +1225,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>
> template<bool _IsMove, typename _II, typename _Tp>
> typename __gnu_cxx::__enable_if<
> - __is_random_access_iter<_II>::__value,
> + __is_any_random_access_iter<_II>::__value,
> _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
> __copy_move_a1(_II __first, _II __last,
> _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
> __result)
> @@ -1347,7 +1347,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>
> template<bool _IsMove, typename _II, typename _Tp>
> typename __gnu_cxx::__enable_if<
> - __is_random_access_iter<_II>::__value,
> + __is_any_random_access_iter<_II>::__value,
> _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
> __copy_move_backward_a1(_II __first, _II __last,
> _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
> __result)
> @@ -1406,7 +1406,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>
> template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
> typename __gnu_cxx::__enable_if<
> - __is_random_access_iter<_II>::__value, bool>::__type
> + __is_any_random_access_iter<_II>::__value, bool>::__type
> __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>
> __first1,
> _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>
> __last1,
> _II __first2)
> @@ -1422,7 +1422,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>
> template<typename _II, typename _Tp, typename _Ref, typename _Ptr>
> typename __gnu_cxx::__enable_if<
> - __is_random_access_iter<_II>::__value, bool>::__type
> + __is_any_random_access_iter<_II>::__value, bool>::__type
> __equal_aux1(_II __first1, _II __last1,
> _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>
> __first2)
> {
> diff --git a/libstdc++-v3/include/bits/stl_algo.h
> b/libstdc++-v3/include/bits/stl_algo.h
> index bbd1800af779..0d8f7af9d272 100644
> --- a/libstdc++-v3/include/bits/stl_algo.h
> +++ b/libstdc++-v3/include/bits/stl_algo.h
> @@ -226,7 +226,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> return std::__find_if(__first, __last, __unary_pred);
>
> return std::__search_n_aux(__first, __last, __count,
> __unary_pred,
> - std::__iterator_category(__first));
> +
> std::__iter_concept_or_category(__first));
> }
>
> // find_end for forward iterators.
> @@ -337,8 +337,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> __glibcxx_requires_valid_range(__first2, __last2);
>
> return std::__find_end(__first1, __last1, __first2, __last2,
> - std::__iterator_category(__first1),
> - std::__iterator_category(__first2),
> + std::__iter_concept_or_category(__first1),
> + std::__iter_concept_or_category(__first2),
> __gnu_cxx::__ops::equal_to());
> }
>
> @@ -388,8 +388,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> __glibcxx_requires_valid_range(__first2, __last2);
>
> return std::__find_end(__first1, __last1, __first2, __last2,
> - std::__iterator_category(__first1),
> - std::__iterator_category(__first2),
> + std::__iter_concept_or_category(__first1),
> + std::__iter_concept_or_category(__first2),
> __comp);
> }
>
> @@ -3495,9 +3495,9 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> _BinaryPredicate __pred)
> {
> using _Cat1
> - = typename
> iterator_traits<_ForwardIterator1>::iterator_category;
> + =
> __decltype(std::__iter_concept_or_category<_ForwardIterator1>());
> using _Cat2
> - = typename
> iterator_traits<_ForwardIterator2>::iterator_category;
> + =
> __decltype(std::__iter_concept_or_category<_ForwardIterator2>());
> using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
> using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
> constexpr bool __ra_iters = __and_<_It1_is_RA,
> _It2_is_RA>::value;
> @@ -3800,7 +3800,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> for_each_n(_InputIterator __first, _Size __n, _Function __f)
> {
> auto __n2 = std::__size_to_integer(__n);
> - using _Cat = typename
> iterator_traits<_InputIterator>::iterator_category;
> + using _Cat =
> __decltype(std::__iter_concept_or_category<_InputIterator>());
> if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
> {
> if (__n2 <= 0)
> @@ -4450,7 +4450,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> return __result;
> return std::__unique_copy(__first, __last, __result,
> __gnu_cxx::__ops::equal_to(),
> - std::__iterator_category(__first));
> +
> std::__iter_concept_or_category(__first));
> }
>
> /**
> @@ -4491,7 +4491,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> if (__first == __last)
> return __result;
> return std::__unique_copy(__first, __last, __result,
> __binary_pred,
> - std::__iterator_category(__first));
> +
> std::__iter_concept_or_category(__first));
> }
>
> #if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED
> @@ -5881,10 +5881,10 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> _SampleIterator __out, _Distance __n,
> _UniformRandomBitGenerator&& __g)
> {
> - using __pop_cat = typename
> - std::iterator_traits<_PopulationIterator>::iterator_category;
> - using __samp_cat = typename
> - std::iterator_traits<_SampleIterator>::iterator_category;
> + using __pop_cat
> + =
> __decltype(std::__iter_concept_or_category<_PopulationIterator>());
> + using __samp_cat
> + = typename iterator_traits<_SampleIterator>::iterator_category;
>
> static_assert(
> __or_<is_convertible<__pop_cat, forward_iterator_tag>,
> diff --git a/libstdc++-v3/include/bits/stl_algobase.h
> b/libstdc++-v3/include/bits/stl_algobase.h
> index 443cbef76dee..701910afd837 100644
> --- a/libstdc++-v3/include/bits/stl_algobase.h
> +++ b/libstdc++-v3/include/bits/stl_algobase.h
> @@ -480,7 +480,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>
> template<bool _IsMove, typename _II, typename _Tp>
> typename __gnu_cxx::__enable_if<
> - __is_random_access_iter<_II>::__value,
> + __is_any_random_access_iter<_II>::__value,
> _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
> __copy_move_a1(_II, _II, _GLIBCXX_STD_C::_Deque_iterator<_Tp,
> _Tp&, _Tp*>);
>
> @@ -769,7 +769,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>
> template<bool _IsMove, typename _II, typename _Tp>
> typename __gnu_cxx::__enable_if<
> - __is_random_access_iter<_II>::__value,
> + __is_any_random_access_iter<_II>::__value,
> _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
> __copy_move_backward_a1(_II, _II,
> _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&,
> _Tp*>);
> @@ -1219,7 +1219,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>
> template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
> typename __gnu_cxx::__enable_if<
> - __is_random_access_iter<_II>::__value, bool>::__type
> + __is_any_random_access_iter<_II>::__value, bool>::__type
> __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
> _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
> _II);
> @@ -1233,7 +1233,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>
> template<typename _II, typename _Tp, typename _Ref, typename _Ptr>
> typename __gnu_cxx::__enable_if<
> - __is_random_access_iter<_II>::__value, bool>::__type
> + __is_any_random_access_iter<_II>::__value, bool>::__type
> __equal_aux1(_II, _II,
> _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>);
>
> @@ -1332,8 +1332,8 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> _II2 __first2, _II2 __last2,
> _Compare __comp)
> {
> - typedef typename iterator_traits<_II1>::iterator_category
> _Category1;
> - typedef typename iterator_traits<_II2>::iterator_category
> _Category2;
> + typedef __decltype(std::__iter_concept_or_category<_II1>())
> _Category1;
> + typedef __decltype(std::__iter_concept_or_category<_II2>())
> _Category2;
> typedef std::__lc_rai<_Category1, _Category2> __rai_type;
>
> __last1 = __rai_type::__newlast1(__first1, __last1, __first2,
> __last2);
> @@ -1649,8 +1649,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
> {
> using _RATag = random_access_iterator_tag;
> - using _Cat1 = typename iterator_traits<_II1>::iterator_category;
> - using _Cat2 = typename iterator_traits<_II2>::iterator_category;
> + using _Cat1 =
> __decltype(std::__iter_concept_or_category<_II1>());
> + using _Cat2 =
> __decltype(std::__iter_concept_or_category<_II2>());
> using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2,
> _RATag>>;
> if constexpr (_RAIters::value)
> {
> @@ -1676,8 +1676,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> _BinaryPredicate __binary_pred)
> {
> using _RATag = random_access_iterator_tag;
> - using _Cat1 = typename iterator_traits<_II1>::iterator_category;
> - using _Cat2 = typename iterator_traits<_II2>::iterator_category;
> + using _Cat1 =
> __decltype(std::__iter_concept_or_category<_II1>());
> + using _Cat2 =
> __decltype(std::__iter_concept_or_category<_II2>());
> using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2,
> _RATag>>;
> if constexpr (_RAIters::value)
> {
> diff --git a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
> b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
> index 7c80e1423e45..47fc4c84490c 100644
> --- a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
> +++ b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
> @@ -317,6 +317,81 @@ namespace __detail
>
> #endif // C++11
>
> +#if __glibcxx_algorithm_iterator_requirements // C++ >= 20
> + template<typename _Iter>
> + consteval auto
> + __iter_concept_or_category()
> + {
> + if constexpr (__detail::__promotable_iterator<_Iter>)
> + {
> + using __type =
> __detail::__iter_traits<_Iter>::iterator_concept;
> + if constexpr (derived_from<__type,
> random_access_iterator_tag>)
> + return random_access_iterator_tag{};
> + else
> + return __type{};
> + }
> + else
> + return typename iterator_traits<_Iter>::iterator_category{};
> + }
> +
> + template<typename _Iter>
> + __attribute__((__always_inline__))
> + constexpr auto
> + __iter_concept_or_category(const _Iter&)
> + { return std::__iter_concept_or_category<_Iter>(); }
> +#else
> + template<typename _Iter>
> + __attribute__((__always_inline__))
> + inline _GLIBCXX_CONSTEXPR
> + typename iterator_traits<_Iter>::iterator_category
> + __iter_concept_or_category()
> + { return typename iterator_traits<_Iter>::iterator_category(); }
> +
> + template<typename _Iter>
> + __attribute__((__always_inline__))
> + inline _GLIBCXX_CONSTEXPR
> + typename iterator_traits<_Iter>::iterator_category
> + __iter_concept_or_category(const _Iter&)
> + { return typename iterator_traits<_Iter>::iterator_category(); }
> +#endif
> +
> +#if __cplusplus >= 201103L
> + // Like __is_random_access_iter, but based off of
> __iter_concept_or_category
> + // instead of iterator_traits::iterator_category.
> + template<typename _Iter,
> + typename _Cat =
> __decltype(__iter_concept_or_category<_Iter>())>
> + struct __is_any_random_access_iter
> + : is_base_of<random_access_iterator_tag, _Cat>
> + { enum { __value = __is_any_random_access_iter::value }; };
> +#else
> + template<typename _Iter,
> + typename _Cat =
> __decltype(__iter_concept_or_category<_Iter>())>
> + struct __is_any_random_access_iter
> + { enum { __value = __is_base_of(random_access_iterator_tag, _Cat)
> }; };
> +#endif
> +
> +#if __cplusplus >= 202002L
> + // A wrapper around ranges::iter_move that also converts to the
> iterator's
> + // value type.
> + template<typename _Iter>
> + [[nodiscard]] constexpr iter_value_t<_Iter>
> + __iter_move_val(const _Iter& __it)
> + noexcept(noexcept(iter_value_t<_Iter>(ranges::iter_move(__it))))
> + { return ranges::iter_move(__it); }
> +#elif __cplusplus >= 201103L
> + template<typename _Iter,
> + typename _Tp = typename iterator_traits<_Iter>::value_type>
> + [[nodiscard]] constexpr _Tp
> + __iter_move_val(const _Iter& __it)
> + noexcept(noexcept(_Tp(std::move(*__it))))
> + { return std::move(*__it); }
> +#else
> + template<typename _Iter>
> + inline typename iterator_traits<_Iter>::value_type
> + __iter_move_val(const _Iter& __it)
> + { return *__it; }
> +#endif
> +
> _GLIBCXX_END_NAMESPACE_VERSION
> } // namespace
>
> diff --git a/libstdc++-v3/include/bits/stl_uninitialized.h
> b/libstdc++-v3/include/bits/stl_uninitialized.h
> index 70a564659814..96f740e86e7b 100644
> --- a/libstdc++-v3/include/bits/stl_uninitialized.h
> +++ b/libstdc++-v3/include/bits/stl_uninitialized.h
> @@ -1177,7 +1177,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> uninitialized_copy_n(_InputIterator __first, _Size __n,
> _ForwardIterator __result)
> { return std::__uninitialized_copy_n(__first, __n, __result,
> -
> std::__iterator_category(__first)); }
> +
> std::__iter_concept_or_category(__first)); }
>
> /// @cond undocumented
> template<typename _InputIterator, typename _Size, typename
> _ForwardIterator>
> @@ -1188,7 +1188,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> {
> return
> std::__uninitialized_copy_n_pair(__first, __n, __result,
> -
> std::__iterator_category(__first));
> +
> std::__iter_concept_or_category(__first));
> }
> /// @endcond
> #endif
> diff --git a/libstdc++-v3/include/bits/version.def
> b/libstdc++-v3/include/bits/version.def
> index 29ecf15c7e39..9177af610b16 100644
> --- a/libstdc++-v3/include/bits/version.def
> +++ b/libstdc++-v3/include/bits/version.def
> @@ -1972,6 +1972,15 @@ ftms = {
> };
> };
>
> +ftms = {
> + name = algorithm_iterator_requirements;
> + values = {
> + v = 202207;
> + // P2408R5 is a C++23 feature, but we support it in C++20.
> + cxxmin = 20;
> + };
> +};
> +
> ftms = {
> name = algorithm_default_value_type;
> values = {
> diff --git a/libstdc++-v3/include/bits/version.h
> b/libstdc++-v3/include/bits/version.h
> index 5901d27113d7..3a930db2239b 100644
> --- a/libstdc++-v3/include/bits/version.h
> +++ b/libstdc++-v3/include/bits/version.h
> @@ -2206,6 +2206,16 @@
> #endif /* !defined(__cpp_lib_observable_checkpoint) */
> #undef __glibcxx_want_observable_checkpoint
>
> +#if !defined(__cpp_lib_algorithm_iterator_requirements)
> +# if (__cplusplus >= 202002L)
> +# define __glibcxx_algorithm_iterator_requirements 202207L
> +# if defined(__glibcxx_want_all) ||
> defined(__glibcxx_want_algorithm_iterator_requirements)
> +# define __cpp_lib_algorithm_iterator_requirements 202207L
> +# endif
> +# endif
> +#endif /* !defined(__cpp_lib_algorithm_iterator_requirements) */
> +#undef __glibcxx_want_algorithm_iterator_requirements
> +
> #if !defined(__cpp_lib_algorithm_default_value_type)
> # if (__cplusplus > 202302L)
> # define __glibcxx_algorithm_default_value_type 202403L
> diff --git a/libstdc++-v3/include/std/algorithm
> b/libstdc++-v3/include/std/algorithm
> index 1563cdf2b17c..a39474df8b1d 100644
> --- a/libstdc++-v3/include/std/algorithm
> +++ b/libstdc++-v3/include/std/algorithm
> @@ -66,6 +66,7 @@
> #endif
>
> #define __glibcxx_want_algorithm_default_value_type
> +#define __glibcxx_want_algorithm_iterator_requirements
> #define __glibcxx_want_clamp
> #define __glibcxx_want_constexpr_algorithms
> #define __glibcxx_want_freestanding_algorithm
> diff --git a/libstdc++-v3/include/std/memory
> b/libstdc++-v3/include/std/memory
> index 9763760b8d61..52056d2f02a5 100644
> --- a/libstdc++-v3/include/std/memory
> +++ b/libstdc++-v3/include/std/memory
> @@ -102,6 +102,7 @@
> #endif
>
> #define __glibcxx_want_addressof_constexpr
> +#define __glibcxx_want_algorithm_iterator_requirements
> #define __glibcxx_want_allocator_traits_is_always_equal
> #define __glibcxx_want_assume_aligned
> #define __glibcxx_want_atomic_shared_ptr
> diff --git a/libstdc++-v3/include/std/numeric
> b/libstdc++-v3/include/std/numeric
> index cbabf031216e..c9faac485050 100644
> --- a/libstdc++-v3/include/std/numeric
> +++ b/libstdc++-v3/include/std/numeric
> @@ -81,6 +81,7 @@
> # include <limits>
> #endif
>
> +#define __glibcxx_want_algorithm_iterator_requirements
> #define __glibcxx_want_constexpr_numeric
> #define __glibcxx_want_gcd
> #define __glibcxx_want_gcd_lcm
> @@ -298,7 +299,7 @@ namespace __detail
> static_assert(is_invocable_r_v<_Tp, _BinaryOperation&, __ref,
> _Tp&>);
> static_assert(is_invocable_r_v<_Tp, _BinaryOperation&, _Tp&,
> _Tp&>);
> static_assert(is_invocable_r_v<_Tp, _BinaryOperation&, __ref,
> __ref>);
> - if constexpr (__is_random_access_iter<_InputIterator>::value)
> + if constexpr (__is_any_random_access_iter<_InputIterator>::value)
> {
> while ((__last - __first) >= 4)
> {
> @@ -378,8 +379,8 @@ namespace __detail
> _BinaryOperation1 __binary_op1,
> _BinaryOperation2 __binary_op2)
> {
> - if constexpr (__and_v<__is_random_access_iter<_InputIterator1>,
> - __is_random_access_iter<_InputIterator2>>)
> + if constexpr
> (__and_v<__is_any_random_access_iter<_InputIterator1>,
> +
> __is_any_random_access_iter<_InputIterator2>>)
> {
> while ((__last1 - __first1) >= 4)
> {
> @@ -445,7 +446,7 @@ namespace __detail
> transform_reduce(_InputIterator __first, _InputIterator __last,
> _Tp __init,
> _BinaryOperation __binary_op, _UnaryOperation
> __unary_op)
> {
> - if constexpr (__is_random_access_iter<_InputIterator>::value)
> + if constexpr (__is_any_random_access_iter<_InputIterator>::value)
> {
> while ((__last - __first) >= 4)
> {
> @@ -582,7 +583,7 @@ namespace __detail
> {
> if (__first != __last)
> {
> - auto __init = std::move(*__first);
> + auto __init = std::__iter_move_val(__first);
> *__result++ = __init;
> ++__first;
> if (__first != __last)
> diff --git
> a/libstdc++-v3/testsuite/25_algorithms/find_end/c++20_iter.cc
> b/libstdc++-v3/testsuite/25_algorithms/find_end/c++20_iter.cc
> new file mode 100644
> index 000000000000..6bd1cead1c36
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/25_algorithms/find_end/c++20_iter.cc
> @@ -0,0 +1,23 @@
> +// Verify std::find_end is C++20 iterator aware as per P2408R5.
> +// { dg-do compile { target c++20 } }
> +
> +#include <algorithm>
> +#include <ranges>
> +#include <testsuite_hooks.h>
> +
> +constexpr bool
> +test01()
> +{
> + auto r = std::views::iota(0, 10);
> + auto s = std::views::iota(5, 10);
> + auto it = r.begin();
> + auto jt = s.begin();
> + static_assert( std::random_access_iterator<decltype(it)>);
> + static_assert(
> std::same_as<std::iterator_traits<decltype(it)>::iterator_category,
> + std::input_iterator_tag> );
> + it = std::find_end(it, it+10, jt, jt+5);
> + VERIFY( it == r.begin() + 5 );
> + return true;
> +}
> +
> +static_assert(test01());
> diff --git a/libstdc++-v3/testsuite/25_algorithms/sample/c++20_iter.cc
> b/libstdc++-v3/testsuite/25_algorithms/sample/c++20_iter.cc
> new file mode 100644
> index 000000000000..3933b3a2a2c2
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/25_algorithms/sample/c++20_iter.cc
> @@ -0,0 +1,23 @@
> +// Verify std::sample is C++20 iterator aware as per P2408R5.
> +// { dg-do compile { target c++20 } }
> +
> +#include <algorithm>
> +#include <random>
> +#include <ranges>
> +#include <testsuite_hooks.h>
> +#include <testsuite_iterators.h>
> +
> +std::mt19937 rng;
> +
> +void
> +test01()
> +{
> + auto r = std::views::iota(10);
> + auto it = r.begin();
> + static_assert( std::random_access_iterator<decltype(it)>);
> + static_assert(
> std::same_as<std::iterator_traits<decltype(it)>::iterator_category,
> + std::input_iterator_tag> );
> + int buf[10];
> + __gnu_test::output_container<int> s(buf);
> + std::sample(it, it+10, s.begin(), 10, rng);
> +}
> diff --git
> a/libstdc++-v3/testsuite/25_algorithms/search_n/c++20_iter.cc
> b/libstdc++-v3/testsuite/25_algorithms/search_n/c++20_iter.cc
> new file mode 100644
> index 000000000000..9787358e6674
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/25_algorithms/search_n/c++20_iter.cc
> @@ -0,0 +1,21 @@
> +// Verify std::search_n is Ranges iterator aware as per P2408R5.
> +// { dg-do compile { target c++20 } }
> +
> +#include <algorithm>
> +#include <ranges>
> +#include <testsuite_hooks.h>
> +
> +constexpr bool
> +test01()
> +{
> + auto r = std::views::iota(0, 10);
> + auto it = r.begin();
> + static_assert( std::random_access_iterator<decltype(it)>);
> + static_assert(
> std::same_as<std::iterator_traits<decltype(it)>::iterator_category,
> + std::input_iterator_tag> );
> + it = std::search_n(it, it+10, 1, 5);
> + VERIFY( it == r.begin() + 5 );
> + return true;
> +}
> +
> +static_assert(test01());
> diff --git
> a/libstdc++-v3/testsuite/25_algorithms/unique_copy/c++20_iter.cc
> b/libstdc++-v3/testsuite/25_algorithms/unique_copy/c++20_iter.cc
> new file mode 100644
> index 000000000000..20017ced8672
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/25_algorithms/unique_copy/c++20_iter.cc
> @@ -0,0 +1,33 @@
> +// Verify std::unique_copy is C++20 iterator aware as per P2408R5.
> +// { dg-do compile { target c++20 } }
> +
> +#include <algorithm>
> +#include <ranges>
> +#include <testsuite_hooks.h>
> +#include <testsuite_iterators.h>
> +
> +struct noncopyable
> +{
> + constexpr operator int() { return 42; }
> + noncopyable() = default;
> + noncopyable(const noncopyable&) = delete;
> + noncopyable& operator=(const noncopyable&) = delete;
> + friend auto operator<=>(const noncopyable&, const noncopyable&) =
> default;
> +};
> +
> +constexpr bool
> +test01()
> +{
> + auto r = std::views::iota(10)
> + | std::views::transform([](int) { return noncopyable{}; });
> + auto it = r.begin();
> + static_assert( std::random_access_iterator<decltype(it)>);
> + static_assert(
> std::same_as<std::iterator_traits<decltype(it)>::iterator_category,
> + std::input_iterator_tag> );
> + int buf[10];
> + __gnu_test::input_container<int> s(buf);
> + auto jt = std::unique_copy(it, it+10, s.begin());
> + return true;
> +}
> +
> +static_assert(test01());
> diff --git
> a/libstdc++-v3/testsuite/26_numerics/inclusive_scan/c++20_iter.cc
> b/libstdc++-v3/testsuite/26_numerics/inclusive_scan/c++20_iter.cc
> new file mode 100644
> index 000000000000..d8f2781fc669
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/26_numerics/inclusive_scan/c++20_iter.cc
> @@ -0,0 +1,26 @@
> +// Verify std::inclusive_scan is C++20 iterator aware as per P2408R5.
> +// { dg-do compile { target c++23 } }
> +
> +#include <numeric>
> +#include <ranges>
> +#include <testsuite_hooks.h>
> +
> +constexpr bool
> +test01()
> +{
> + int x[10] = {1,2,3,4,5,6,7,8,9,10};
> + auto r = std::views::zip(x);
> + auto it = r.begin();
> + static_assert( std::random_access_iterator<decltype(it)>);
> + static_assert(
> std::same_as<std::iterator_traits<decltype(it)>::iterator_category,
> + std::input_iterator_tag> );
> + std::tuple<int> y[10];
> + std::inclusive_scan(it, it+10, y,
> + [](std::tuple<int> a, std::tuple<int> b) ->
> std::tuple<int> {
> + return std::get<0>(a) + std::get<0>(b);
> + });
> + VERIFY( std::get<0>(y[9]) == 55 );
> + return true;
> +}
> +
> +static_assert(test01());
> --
> 2.52.0.51.gdebbc87557
>
>
>
