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 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. --- 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); +#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
