On Tue, 25 Nov 2025, Tomasz Kaminski wrote:
>
>
> On Tue, Nov 25, 2025 at 3:23 PM Patrick Palka <[email protected]> wrote:
> On Tue, 25 Nov 2025, Tomasz Kaminski wrote:
>
> >
> >
> > On Tue, Nov 25, 2025 at 3:07 PM Patrick Palka <[email protected]>
> wrote:
> > 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 would assume that this constructor would get elided anyway, so this
> would be not
> > observable. And we already require a copy constructor to compile.
>
> Ah ok, makes sense.
>
> > I guess we could defined __iter_move_val as a macro
> (_GLIBCXX_ITER_MOVE)
> > to avoid this extra copy?
> >
> > This would reduce a lot of boilerplace (conditional noexcept), if we
> define it as
> > simply static_cast<iter_value_t>(ranges::iter_move), and there would
> be only pre-C++20
> > and post-C++20 versions.
>
> The pre-C++20 macro would look pretty ugly:
>
> #define _GLIBCXX_ITER_MOVE(__it) \
> typename
> iterator_traits<__remove_cvref(__decltype(__it))>::value_type(_GLIBCXX_MOVE(*__it))
>
> But we do not need the case to iterator_traits<...>::value_type pre-C++20. I
> mean,
> auto __x = _GLIBCXX_ITER_MOVE(*__it);
> Will work correctly with just _GLIBCXX_MOVE(*__it), and such cast will add
> the same additional elidable copy as we have currently.
Makes sense, like so then?
changes in v6: replace __iter_move_val with _GLIBCXX_ITER_MOVE macro
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.
(_GLIBCXX_ITER_MOVE): 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 _GLIBCXX_ITER_MOVE 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 | 62 +++++++++++++++++++
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, 245 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..44816eb8e569 100644
--- a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
+++ b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
@@ -317,6 +317,68 @@ 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.
+#define _GLIBCXX_ITER_MOVE(__it) \
+ std::iter_value_t<decltype(__it)>(std::ranges::iter_move(__it))
+#else
+#define _GLIBCXX_ITER_MOVE(__it) _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..830a458bfd26 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 = _GLIBCXX_ITER_MOVE(__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.84.g6ab38b7e9c
