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. > + { return _GLIBCXX_MOVE(*__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 > >
