On Mon, Nov 24, 2025 at 3:23 PM Patrick Palka <[email protected]> wrote:
> On Mon, 24 Nov 2025, Tomasz Kaminski wrote: > > > > > > > On Mon, Nov 24, 2025 at 5:44 AM Patrick Palka <[email protected]> wrote: > > 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. > > > > From my reading of the paper the requirements were relaxed per iterator > > parameters, and not algorithm, so in particular input range of > unique_copy > > should be relaxed (__unique_copy_1 uses iterator_traits<T>::value_type), > > but c++20 may use readable_traits. > > I thuoght we can rely on iterator_traits being properly defined even for > C++20 iterators? That's because all C++20 iterators are legacy input > iterators so https://eel.is/c++draft/iterator.traits#3.2 applies, and > the member types will be defined appropriately. So we don't need to > change any existing uses of value_type, difference_type, reference etc. > Ah, yes I forgot about the primary template, thanks. > > > > > I think I would handle this second batch (iterators with input and > output range), > > in a separate commit. > > > > 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.) > > > > I think that user defined iterators may just specify the concept as > random_access_iterator, > > and really on concept check to reduce the concept as appropriate. We try > hard to not > > lie in the interator_concept tag, but the paper clearly states that > concept is what is checked. > > > > But this also affects the previous prev/next optimization, so I think we > should handle it in separate patch. > > Makes sense. > > > > > 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 > > > > 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 > > (__detail::__iter_category_converts_to_concept) > > (__detail::__promotable_iterator): Move to ... > > * include/bits/stl_iterator_base_types.h: ... here. > > (__iter_concept_or_category): New. > > (__is_any_random_access_iter): 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) [C++20]: Use ranges::iter_move(iter) > instead > > of std::move(*iter). > > * testsuite/25_algorithms/find_end/p2408r5.cc: New test. > > * testsuite/25_algorithms/sample/p2408r5.cc: New test. > > * testsuite/25_algorithms/search_n/p2408r5.cc: New test. > > * testsuite/25_algorithms/unique_copy/p2408r5.cc: New test. > > > > I would really preffer for the test to be named after what is tested > > (C++20 only iterator) instead of paper. I do not remember the numbers > > by hearth, co naming it c++20_iter or something similar sounds better to > me. > > To me it's similar to the common practice of naming a test after the PR > we're fixing, but definitely a more descriptive name is preferable. > > > > > --- > > 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 | 22 ------ > > .../include/bits/stl_iterator_base_types.h | 74 > +++++++++++++++++++ > > 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 | 13 +++- > > .../25_algorithms/find_end/p2408r5.cc | 23 ++++++ > > .../testsuite/25_algorithms/sample/p2408r5.cc | 23 ++++++ > > .../25_algorithms/search_n/p2408r5.cc | 21 ++++++ > > .../25_algorithms/unique_copy/p2408r5.cc | 33 +++++++++ > > 15 files changed, 234 insertions(+), 56 deletions(-) > > create mode 100644 > libstdc++-v3/testsuite/25_algorithms/find_end/p2408r5.cc > > create mode 100644 > libstdc++-v3/testsuite/25_algorithms/sample/p2408r5.cc > > create mode 100644 > libstdc++-v3/testsuite/25_algorithms/search_n/p2408r5.cc > > create mode 100644 > libstdc++-v3/testsuite/25_algorithms/unique_copy/p2408r5.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..c8b73e8e6c66 100644 > > --- a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h > > +++ b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h > > @@ -130,28 +130,6 @@ _GLIBCXX_END_NAMESPACE_CONTAINER > > __distance(_OutputIterator, _OutputIterator, > output_iterator_tag) = delete; > > #endif > > > > -#ifdef __glibcxx_concepts > > -namespace __detail > > -{ > > - // Satisfied if ITER_TRAITS(Iter)::iterator_category is valid > and is > > - // at least as strong as ITER_TRAITS(Iter)::iterator_concept. > > - template<typename _Iter> > > - concept __iter_category_converts_to_concept > > - = convertible_to<typename > __iter_traits<_Iter>::iterator_category, > > - typename > __iter_traits<_Iter>::iterator_concept>; > > - > > - // Satisfied if the type is a C++20 iterator that defines > iterator_concept, > > - // and its iterator_concept is stronger than its > iterator_category (if any). > > - // Used by std::distance and std::advance to detect iterators > which should > > - // dispatch based on their C++20 concept not their C++17 > category. > > - template<typename _Iter> > > - concept __promotable_iterator > > - = input_iterator<_Iter> > > - && requires { typename > __iter_traits<_Iter>::iterator_concept; } > > - && ! __iter_category_converts_to_concept<_Iter>; > > -} // namespace __detail > > -#endif > > - > > /** > > * @brief A generalization of pointer arithmetic. > > * @param __first An input iterator. > > diff --git a/libstdc++-v3/include/bits/stl_iterator_base_types.h > b/libstdc++-v3/include/bits/stl_iterator_base_types.h > > index 0c34ad792f7a..1b6b3fae4520 100644 > > --- a/libstdc++-v3/include/bits/stl_iterator_base_types.h > > +++ b/libstdc++-v3/include/bits/stl_iterator_base_types.h > > @@ -281,6 +281,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > { enum { __value = __is_base_of(random_access_iterator_tag, > _Cat) }; }; > > #endif > > > > +#ifdef __glibcxx_concepts > > +namespace __detail > > +{ > > + // Satisfied if ITER_TRAITS(Iter)::iterator_category is valid > and is > > + // at least as strong as ITER_TRAITS(Iter)::iterator_concept. > > + template<typename _Iter> > > + concept __iter_category_converts_to_concept > > + = convertible_to<typename > __iter_traits<_Iter>::iterator_category, > > + typename > __iter_traits<_Iter>::iterator_concept>; > > + > > + // Satisfied if the type is a C++20 iterator that defines > iterator_concept, > > + // and its iterator_concept is stronger than its > iterator_category (if any). > > + // Used by std::distance and std::advance to detect iterators > which should > > + // dispatch based on their C++20 concept not their C++17 > category. > > + template<typename _Iter> > > + concept __promotable_iterator > > + = input_iterator<_Iter> > > + && requires { typename > __iter_traits<_Iter>::iterator_concept; } > > + && ! __iter_category_converts_to_concept<_Iter>; > > +} // namespace __detail > > +#endif > > + > > +#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> > > + consteval 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 > > + > > _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..8809d1db22c9 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,11 @@ namespace __detail > > { > > if (__first != __last) > > { > > +#if __cpp_lib_algorithm_iterator_requirements // C++ >= 20 > > > > + auto __init = ranges::iter_move(__first); > > > > The auto here does not work if the range is proxy range (zip_view), > > in once of the discussion we considered having something like: > > template<typename _It> > > iter_value_t<_It> __iter_move_val(const _It& __it) > > { return ranges::iter_move(__it); } > > We can also have declaration for __iter_move_for C++98 or earlier. > > template<typename _It> > > iterator_traits<_It>::value_type > > iter_value_t<_It> __iter_move_val(const _It& __it) > > { return __GLIBCXX_MOVE(*__it); } > > Oops, will fix and add a test. > > > > > Pelase consider adding test with proxy ranges. > > > > +#else > > auto __init = std::move(*__first); > > > > +#endif > > *__result++ = __init; > > ++__first; > > if (__first != __last) > > diff --git > a/libstdc++-v3/testsuite/25_algorithms/find_end/p2408r5.cc > b/libstdc++-v3/testsuite/25_algorithms/find_end/p2408r5.cc > > new file mode 100644 > > index 000000000000..687d8021a57a > > --- /dev/null > > +++ b/libstdc++-v3/testsuite/25_algorithms/find_end/p2408r5.cc > > @@ -0,0 +1,23 @@ > > +// Verify std::find_end 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 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/p2408r5.cc > b/libstdc++-v3/testsuite/25_algorithms/sample/p2408r5.cc > > new file mode 100644 > > index 000000000000..7f8a798fef96 > > --- /dev/null > > +++ b/libstdc++-v3/testsuite/25_algorithms/sample/p2408r5.cc > > @@ -0,0 +1,23 @@ > > +// Verify std::sample is Ranges 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/p2408r5.cc > b/libstdc++-v3/testsuite/25_algorithms/search_n/p2408r5.cc > > new file mode 100644 > > index 000000000000..9787358e6674 > > --- /dev/null > > +++ b/libstdc++-v3/testsuite/25_algorithms/search_n/p2408r5.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/p2408r5.cc > b/libstdc++-v3/testsuite/25_algorithms/unique_copy/p2408r5.cc > > new file mode 100644 > > index 000000000000..9ecd5ff7c7e2 > > --- /dev/null > > +++ b/libstdc++-v3/testsuite/25_algorithms/unique_copy/p2408r5.cc > > @@ -0,0 +1,33 @@ > > +// Verify std::unique_copy is Ranges 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 s(buf); > > + auto jt = std::unique_copy(it, it+10, s.begin()); > > + return true; > > +} > > + > > +static_assert(test01()); > > -- > > 2.52.0.51.gdebbc87557 > > > > > >
