On Wed, May 28, 2025 at 4:27 PM Patrick Palka <ppa...@redhat.com> wrote:
>
> >
> >
> > On Tue, May 20, 2025 at 6:32 PM Patrick Palka <ppa...@redhat.com> wrote:
> > On Tue, 20 May 2025, Tomasz Kaminski wrote:
> >
> > > I think I do not have any more suggestions for cases to check,
> so the impl LGTM.
> >
> > It's cool how many optimizations we came up with for this
> algorithm :)
> >
> > >
> > > On Tue, May 20, 2025 at 4:33 PM Patrick Palka <ppa...@redhat.com>
> wrote:
> > > Changes in v5:
> > > * dispatch to starts_with for the both-bidi/common range
> case
> > >
> > > Changes in v4:
> > > * optimize the both-bidi/common ranges case, as
> suggested by
> > > Tomasz
> > > * add tests for that code path
> > >
> > > Changes in v3:
> > > * Use the forward_range code path for a (non-sized)
> bidirectional
> > > haystack, since it's slightly fewer
> increments/decrements
> > > overall.
> > > * Fix wrong iter_difference_t cast in starts_with.
> > >
> > > Changes in v2:
> > > Addressed Tomasz's review comments, namely:
> > > * Added explicit iter_difference_t casts
> > > * Made _S_impl member private
> > > * Optimized sized bidirectional case of ends_with
> > > * Rearranged control flow of starts_with::_S_impl
> > >
> > > Still left to do:
> > > * Add tests for integer-class types
> > > * Still working on a better commit description ;)
> > >
> > > -- >8 --
> > >
> > > libstdc++-v3/ChangeLog:
> > >
> > > * include/bits/ranges_algo.h (__starts_with_fn,
> starts_with):
> > > Define.
> > > (__ends_with_fn, ends_with): Define.
> > > * include/bits/version.def
> (ranges_starts_ends_with): Define.
> > > * include/bits/version.h: Regenerate.
> > > * include/std/algorithm: Provide
> __cpp_lib_ranges_starts_ends_with.
> > > * src/c++23/std.cc.in (ranges::starts_with):
> Export.
> > > (ranges::ends_with): Export.
> > > * testsuite/25_algorithms/ends_with/1.cc: New test.
> > > * testsuite/25_algorithms/starts_with/1.cc: New
> test.
> > > ---
> > > libstdc++-v3/include/bits/ranges_algo.h | 247
> ++++++++++++++++++
> > > libstdc++-v3/include/bits/version.def | 8 +
> > > libstdc++-v3/include/bits/version.h | 10 +
> > > libstdc++-v3/include/std/algorithm | 1 +
> > > libstdc++-v3/src/c++23/std.cc.in | 4 +
> > > .../testsuite/25_algorithms/ends_with/1.cc | 135
> ++++++++++
> > > .../testsuite/25_algorithms/starts_with/1.cc | 128
> +++++++++
> > > 7 files changed, 533 insertions(+)
> > > create mode 100644
> libstdc++-v3/testsuite/25_algorithms/ends_with/1.cc
> > > create mode 100644
> libstdc++-v3/testsuite/25_algorithms/starts_with/1.cc
> > >
> > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h
> b/libstdc++-v3/include/bits/ranges_algo.h
> > > index f36e7dd59911..60f7bf841f3f 100644
> > > --- a/libstdc++-v3/include/bits/ranges_algo.h
> > > +++ b/libstdc++-v3/include/bits/ranges_algo.h
> > > @@ -438,6 +438,253 @@ namespace ranges
> > >
> > > inline constexpr __search_n_fn search_n{};
> > >
> > > +#if __glibcxx_ranges_starts_ends_with // C++ >= 23
> > > + struct __starts_with_fn
> > > + {
> > > + template<input_iterator _Iter1, sentinel_for<_Iter1>
> _Sent1,
> > > + input_iterator _Iter2, sentinel_for<_Iter2>
> _Sent2,
> > > + typename _Pred = ranges::equal_to,
> > > + typename _Proj1 = identity, typename _Proj2 =
> identity>
> > > + requires indirectly_comparable<_Iter1, _Iter2,
> _Pred, _Proj1, _Proj2>
> > > + constexpr bool
> > > + operator()(_Iter1 __first1, _Sent1 __last1,
> > > + _Iter2 __first2, _Sent2 __last2, _Pred
> __pred = {},
> > > + _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
> const
> > > + {
> > > + iter_difference_t<_Iter1> __n1 = -1;
> > > + iter_difference_t<_Iter2> __n2 = -1;
> > > + if constexpr (sized_sentinel_for<_Sent1, _Iter1>)
> > > + __n1 = __last1 - __first1;
> > > + if constexpr (sized_sentinel_for<_Sent2, _Iter2>)
> > > + __n2 = __last2 - __first2;
> > > + return _S_impl(std::move(__first1), __last1, __n1,
> > > + std::move(__first2), __last2, __n2,
> > > + std::move(__pred),
> > > + std::move(__proj1),
> std::move(__proj2));
> > > + }
> > > +
> > > + template<input_range _Range1, input_range _Range2,
> > > + typename _Pred = ranges::equal_to,
> > > + typename _Proj1 = identity, typename _Proj2 =
> identity>
> > > + requires indirectly_comparable<iterator_t<_Range1>,
> iterator_t<_Range2>,
> > > + _Pred, _Proj1, _Proj2>
> > > + constexpr bool
> > > + operator()(_Range1&& __r1, _Range2&& __r2, _Pred
> __pred = {},
> > > + _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
> const
> > > + {
> > > + range_difference_t<_Range1> __n1 = -1;
> > > + range_difference_t<_Range1> __n2 = -1;
> > > + if constexpr (sized_range<_Range1>)
> > > + __n1 = ranges::size(__r1);
> > > + if constexpr (sized_range<_Range2>)
> > > + __n2 = ranges::size(__r2);
> > > + return _S_impl(ranges::begin(__r1),
> ranges::end(__r1), __n1,
> > > + ranges::begin(__r2),
> ranges::end(__r2), __n2,
> > > + std::move(__pred),
> > > + std::move(__proj1),
> std::move(__proj2));
> > > + }
> > > +
> > > + private:
> > > + template<typename _Iter1, typename _Sent1, typename
> _Iter2, typename _Sent2,
> > > + typename _Pred,
> > > + typename _Proj1, typename _Proj2>
> > > + static constexpr bool
> > > + _S_impl(_Iter1 __first1, _Sent1 __last1,
> iter_difference_t<_Iter1> __n1,
> > > + _Iter2 __first2, _Sent2 __last2,
> iter_difference_t<_Iter2> __n2,
> > > + _Pred __pred, _Proj1 __proj1, _Proj2 __proj2)
> > > + {
> > > + if (__first2 == __last2) [[unlikely]]
> > > + return true;
> > > + else if (__n1 == -1 || __n2 == -1)
> > > + return ranges::mismatch(std::move(__first1),
> __last1,
> > > + std::move(__first2),
> __last2,
> > > + std::move(__pred),
> > > + std::move(__proj1),
> std::move(__proj2)).in2 == __last2;
> > > + else if (__n1 < __n2)
> > > + return false;
> > > + else if constexpr (random_access_iterator<_Iter1>)
> > > + return ranges::equal(__first1, __first1 +
> iter_difference_t<_Iter1>(__n2),
> > > + std::move(__first2),
> __last2,
> > > + std::move(__pred),
> > > + std::move(__proj1),
> std::move(__proj2));
> > > + else
> > > + return
> ranges::equal(counted_iterator(std::move(__first1),
> > > +
> iter_difference_t<_Iter1>(__n2)),
> > > + default_sentinel,
> > > + std::move(__first2),
> __last2,
> > > + std::move(__pred),
> > > + std::move(__proj1),
> std::move(__proj2));
> > > + }
> > > +
> > > + friend struct __ends_with_fn;
> > > + };
> > > +
> > > + inline constexpr __starts_with_fn starts_with{};
> > > +
> > > + struct __ends_with_fn
> > > + {
> > > + template<input_iterator _Iter1, sentinel_for<_Iter1>
> _Sent1,
> > > + input_iterator _Iter2, sentinel_for<_Iter2>
> _Sent2,
> > > + typename _Pred = ranges::equal_to,
> > > + typename _Proj1 = identity, typename _Proj2 =
> identity>
> > > + requires (forward_iterator<_Iter1> ||
> sized_sentinel_for<_Sent1, _Iter1>)
> > > + && (forward_iterator<_Iter2> ||
> sized_sentinel_for<_Sent2, _Iter2>)
> > > + && indirectly_comparable<_Iter1, _Iter2, _Pred,
> _Proj1, _Proj2>
> > > + constexpr bool
> > > + operator()(_Iter1 __first1, _Sent1 __last1,
> > > + _Iter2 __first2, _Sent2 __last2, _Pred
> __pred = {},
> > > + _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
> const
> > > + {
> > > + iter_difference_t<_Iter1> __n1 = -1;
> > > + iter_difference_t<_Iter2> __n2 = -1;
> > > + if constexpr (sized_sentinel_for<_Sent1, _Iter1>)
> > > + __n1 = __last1 - __first1;
> > > + if constexpr (sized_sentinel_for<_Sent2, _Iter2>)
> > > + __n2 = __last2 - __first2;
> > > + return _S_impl(std::move(__first1), __last1, __n1,
> > > + std::move(__first2), __last2, __n2,
> > > + std::move(__pred),
> > > + std::move(__proj1),
> std::move(__proj2));
> > > + }
> > > +
> > > + template<input_range _Range1, input_range _Range2,
> > > + typename _Pred = ranges::equal_to,
> > > + typename _Proj1 = identity, typename _Proj2 =
> identity>
> > > + requires (forward_range<_Range1> ||
> sized_range<_Range1>)
> > > + && (forward_range<_Range2> || sized_range<_Range2>)
> > > + && indirectly_comparable<iterator_t<_Range1>,
> iterator_t<_Range2>,
> > > + _Pred, _Proj1, _Proj2>
> > > + constexpr bool
> > > + operator()(_Range1&& __r1, _Range2&& __r2, _Pred
> __pred = {},
> > > + _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
> const
> > > + {
> > > + range_difference_t<_Range1> __n1 = -1;
> > > + range_difference_t<_Range1> __n2 = -1;
> > > + if constexpr (sized_range<_Range1>)
> > > + __n1 = ranges::size(__r1);
> > > + if constexpr (sized_range<_Range2>)
> > > + __n2 = ranges::size(__r2);
> > > + return _S_impl(ranges::begin(__r1),
> ranges::end(__r1), __n1,
> > > + ranges::begin(__r2),
> ranges::end(__r2), __n2,
> > > + std::move(__pred),
> > > + std::move(__proj1),
> std::move(__proj2));
> > > + }
> > > +
> > > + private:
> > > + template<typename _Iter1, typename _Sent1,
> > > + typename _Iter2, typename _Sent2,
> > > + typename _Pred,
> > > + typename _Proj1, typename _Proj2>
> > > + static constexpr bool
> > > + _S_impl(_Iter1 __first1, _Sent1 __last1,
> iter_difference_t<_Iter1> __n1,
> > > + _Iter2 __first2, _Sent2 __last2,
> iter_difference_t<_Iter2> __n2,
> > > + _Pred __pred, _Proj1 __proj1, _Proj2 __proj2)
> > > + {
> > > + if constexpr (bidirectional_iterator<_Iter1> &&
> same_as<_Iter1, _Sent1>
> > > + && bidirectional_iterator<_Iter2> &&
> same_as<_Iter2, _Sent2>
> > > + && !random_access_iterator<_Iter1>
> > > + && !random_access_iterator<_Iter2>)
> > > Could we extract bidirectional_iterator<_Iter1> &&
> same_as<_Iter1, _Sent1> && !random_access_iterator<_Iter1>
> > > to some exposition only variable template (maybe in the
> class)?
> >
> > In the latest version of the patch I removed the second
> > random_access_iterator check (because I think we still want to
> dispatch
> > to starts_with with a bidi haystack and random access needle). Do
> > you think it's still worthwhile to factor out the check?
> >
> > I do not think this is necessary.
>
> Thanks for the thorough review, here is the patch so far, complete with
> a proper commit message. Does it look OK for trunk?.
>
Could you look into having a test with integer-class distance type, not
necessarily
all paths, but sized ones.
Outside of that is LGTM.
>
> -- >8 --
>
> This implements ranges::starts_with and ranges::ends_with from the C++23
> paper P1659R3. The logic of these algorithms is contained in an _S_impl
> member function that takes optional size parameters __n1 and __n2 of the
> two ranges, where -1 means the corresponding size is not known.
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/ranges_algo.h (__starts_with_fn, starts_with):
> Define.
> (__ends_with_fn, ends_with): Define.
> * include/bits/version.def (ranges_starts_ends_with): Define.
> * include/bits/version.h: Regenerate.
> * include/std/algorithm: Provide __cpp_lib_ranges_starts_ends_with.
> * src/c++23/std.cc.in (ranges::starts_with): Export.
> (ranges::ends_with): Export.
> * testsuite/25_algorithms/ends_with/1.cc: New test.
> * testsuite/25_algorithms/starts_with/1.cc: New test.
>
> Reviewed-by: Tomasz Kamiński <tkami...@redhat.com>
> ---
> libstdc++-v3/include/bits/ranges_algo.h | 248 ++++++++++++++++++
> libstdc++-v3/include/bits/version.def | 8 +
> libstdc++-v3/include/bits/version.h | 10 +
> libstdc++-v3/include/std/algorithm | 1 +
> libstdc++-v3/src/c++23/std.cc.in | 4 +
> .../testsuite/25_algorithms/ends_with/1.cc | 135 ++++++++++
> .../testsuite/25_algorithms/starts_with/1.cc | 128 +++++++++
> 7 files changed, 534 insertions(+)
> create mode 100644 libstdc++-v3/testsuite/25_algorithms/ends_with/1.cc
> create mode 100644 libstdc++-v3/testsuite/25_algorithms/starts_with/1.cc
>
> diff --git a/libstdc++-v3/include/bits/ranges_algo.h
> b/libstdc++-v3/include/bits/ranges_algo.h
> index f36e7dd59911..ac5ef1e38520 100644
> --- a/libstdc++-v3/include/bits/ranges_algo.h
> +++ b/libstdc++-v3/include/bits/ranges_algo.h
> @@ -438,6 +438,254 @@ namespace ranges
>
> inline constexpr __search_n_fn search_n{};
>
> +#if __glibcxx_ranges_starts_ends_with // C++ >= 23
> + struct __starts_with_fn
> + {
> + template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
> + input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
> + typename _Pred = ranges::equal_to,
> + typename _Proj1 = identity, typename _Proj2 = identity>
> + requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1,
> _Proj2>
> + constexpr bool
> + operator()(_Iter1 __first1, _Sent1 __last1,
> + _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
> + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
> + {
> + iter_difference_t<_Iter1> __n1 = -1;
> + iter_difference_t<_Iter2> __n2 = -1;
> + if constexpr (sized_sentinel_for<_Sent1, _Iter1>)
> + __n1 = __last1 - __first1;
> + if constexpr (sized_sentinel_for<_Sent2, _Iter2>)
> + __n2 = __last2 - __first2;
> + return _S_impl(std::move(__first1), __last1, __n1,
> + std::move(__first2), __last2, __n2,
> + std::move(__pred),
> + std::move(__proj1), std::move(__proj2));
> + }
> +
> + template<input_range _Range1, input_range _Range2,
> + typename _Pred = ranges::equal_to,
> + typename _Proj1 = identity, typename _Proj2 = identity>
> + requires indirectly_comparable<iterator_t<_Range1>,
> iterator_t<_Range2>,
> + _Pred, _Proj1, _Proj2>
> + constexpr bool
> + operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
> + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
> + {
> + range_difference_t<_Range1> __n1 = -1;
> + range_difference_t<_Range1> __n2 = -1;
> + if constexpr (sized_range<_Range1>)
> + __n1 = ranges::size(__r1);
> + if constexpr (sized_range<_Range2>)
> + __n2 = ranges::size(__r2);
> + return _S_impl(ranges::begin(__r1), ranges::end(__r1), __n1,
> + ranges::begin(__r2), ranges::end(__r2), __n2,
> + std::move(__pred),
> + std::move(__proj1), std::move(__proj2));
> + }
> +
> + private:
> + template<typename _Iter1, typename _Sent1, typename _Iter2, typename
> _Sent2,
> + typename _Pred,
> + typename _Proj1, typename _Proj2>
> + static constexpr bool
> + _S_impl(_Iter1 __first1, _Sent1 __last1, iter_difference_t<_Iter1>
> __n1,
> + _Iter2 __first2, _Sent2 __last2, iter_difference_t<_Iter2>
> __n2,
> + _Pred __pred, _Proj1 __proj1, _Proj2 __proj2)
> + {
> + if (__first2 == __last2) [[unlikely]]
> + return true;
> + else if (__n1 == -1 || __n2 == -1)
> + return ranges::mismatch(std::move(__first1), __last1,
> + std::move(__first2), __last2,
> + std::move(__pred),
> + std::move(__proj1),
> std::move(__proj2)).in2 == __last2;
> + else if (__n1 < __n2)
> + return false;
> + else if constexpr (random_access_iterator<_Iter1>)
> + return ranges::equal(__first1, __first1 +
> iter_difference_t<_Iter1>(__n2),
> + std::move(__first2), __last2,
> + std::move(__pred),
> + std::move(__proj1), std::move(__proj2));
> + else
> + return ranges::equal(counted_iterator(std::move(__first1),
> +
> iter_difference_t<_Iter1>(__n2)),
> + default_sentinel,
> + std::move(__first2), __last2,
> + std::move(__pred),
> + std::move(__proj1), std::move(__proj2));
> + }
> +
> + friend struct __ends_with_fn;
> + };
> +
> + inline constexpr __starts_with_fn starts_with{};
> +
> + struct __ends_with_fn
> + {
> + template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
> + input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
> + typename _Pred = ranges::equal_to,
> + typename _Proj1 = identity, typename _Proj2 = identity>
> + requires (forward_iterator<_Iter1> || sized_sentinel_for<_Sent1,
> _Iter1>)
> + && (forward_iterator<_Iter2> || sized_sentinel_for<_Sent2, _Iter2>)
> + && indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
> + constexpr bool
> + operator()(_Iter1 __first1, _Sent1 __last1,
> + _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
> + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
> + {
> + iter_difference_t<_Iter1> __n1 = -1;
> + iter_difference_t<_Iter2> __n2 = -1;
> + if constexpr (sized_sentinel_for<_Sent1, _Iter1>)
> + __n1 = __last1 - __first1;
> + if constexpr (sized_sentinel_for<_Sent2, _Iter2>)
> + __n2 = __last2 - __first2;
> + return _S_impl(std::move(__first1), __last1, __n1,
> + std::move(__first2), __last2, __n2,
> + std::move(__pred),
> + std::move(__proj1), std::move(__proj2));
> + }
> +
> + template<input_range _Range1, input_range _Range2,
> + typename _Pred = ranges::equal_to,
> + typename _Proj1 = identity, typename _Proj2 = identity>
> + requires (forward_range<_Range1> || sized_range<_Range1>)
> + && (forward_range<_Range2> || sized_range<_Range2>)
> + && indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
> + _Pred, _Proj1, _Proj2>
> + constexpr bool
> + operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
> + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
> + {
> + range_difference_t<_Range1> __n1 = -1;
> + range_difference_t<_Range1> __n2 = -1;
> + if constexpr (sized_range<_Range1>)
> + __n1 = ranges::size(__r1);
> + if constexpr (sized_range<_Range2>)
> + __n2 = ranges::size(__r2);
> + return _S_impl(ranges::begin(__r1), ranges::end(__r1), __n1,
> + ranges::begin(__r2), ranges::end(__r2), __n2,
> + std::move(__pred),
> + std::move(__proj1), std::move(__proj2));
> + }
> +
> + private:
> + template<typename _Iter1, typename _Sent1,
> + typename _Iter2, typename _Sent2,
> + typename _Pred,
> + typename _Proj1, typename _Proj2>
> + static constexpr bool
> + _S_impl(_Iter1 __first1, _Sent1 __last1, iter_difference_t<_Iter1>
> __n1,
> + _Iter2 __first2, _Sent2 __last2, iter_difference_t<_Iter2>
> __n2,
> + _Pred __pred, _Proj1 __proj1, _Proj2 __proj2)
> + {
> + if constexpr (!random_access_iterator<_Iter1>
> + && bidirectional_iterator<_Iter1> && same_as<_Iter1,
> _Sent1>
> + && bidirectional_iterator<_Iter2> && same_as<_Iter2,
> _Sent2>)
> + return starts_with._S_impl(std::make_reverse_iterator(__last1),
> + std::make_reverse_iterator(__first1),
> + __n1,
> + std::make_reverse_iterator(__last2),
> + std::make_reverse_iterator(__first2),
> + __n2,
> + std::move(__pred),
> + std::move(__proj1),
> std::move(__proj2));
> +
> + if (__first2 == __last2) [[unlikely]]
> + return true;
> +
> + if constexpr (forward_iterator<_Iter2>)
> + if (__n2 == -1)
> + __n2 = ranges::distance(__first2, __last2);
> +
> + // __glibcxx_assert(__n2 != -1);
> +
> + if (__n1 != -1)
> + {
> + if (__n1 < __n2)
> + return false;
> + auto __shift = __n1 - iter_difference_t<_Iter1>(__n2);
> + if (random_access_iterator<_Iter1>
> + || !bidirectional_iterator<_Iter1>
> + || !same_as<_Iter1, _Sent1>
> + || __shift < __n2)
> + {
> + ranges::advance(__first1, __shift);
> + return ranges::equal(std::move(__first1), __last1,
> + std::move(__first2), __last2,
> + std::move(__pred),
> + std::move(__proj1),
> std::move(__proj2));
> + }
> + }
> +
> + if constexpr (bidirectional_iterator<_Iter1> && same_as<_Iter1,
> _Sent1>)
> + {
> + _Iter1 __it1 = __last1;
> + if (__n1 != -1)
> + ranges::advance(__it1, -iter_difference_t<_Iter1>(__n2));
> + else
> + {
> + // We can't use ranges::advance if the haystack size is
> + // unknown, since we need to detect and return false if
> + // it's smaller than the needle.
> + iter_difference_t<_Iter2> __m = __n2;
> + while (__m != 0 && __it1 != __first1)
> + {
> + --__m;
> + --__it1;
> + }
> + if (__m != 0)
> + return false;
> + }
> + return ranges::equal(__it1, __last1,
> + std::move(__first2), __last2,
> + std::move(__pred),
> + std::move(__proj1), std::move(__proj2));
> + }
> + else if constexpr (forward_iterator<_Iter1>)
> + {
> + // __glibcxx_assert(__n1 == -1);
> + _Iter1 __prev_first1;
> + __n1 = 0;
> + while (true)
> + {
> + iter_difference_t<_Iter2> __m = __n2;
> + _Iter1 __it1 = __first1;
> + while (__m != 0 && __it1 != __last1)
> + {
> + ++__n1;
> + --__m;
> + ++__it1;
> + }
> + if (__m != 0)
> + {
> + // __glibcxx_assert(__it1 == __last1);
> + if (__n1 < __n2)
> + return false;
> + __first1 = ranges::next(__prev_first1,
> + iter_difference_t<_Iter1>(__n2
> - __m));
> + break;
> + }
> + __prev_first1 = __first1;
> + __first1 = __it1;
> + }
> + return ranges::equal(__first1, __last1,
> + std::move(__first2), __last2,
> + std::move(__pred),
> + std::move(__proj1), std::move(__proj2));
> + }
> + else
> + // If the haystack is non-forward then it must be sized, in
> which case
> + // we already returned via the __n1 != 1 case.
> + __builtin_unreachable();
> + }
> +
> + };
> +
> + inline constexpr __ends_with_fn ends_with{};
> +#endif // __glibcxx_ranges_starts_ends_with
> +
> struct __find_end_fn
> {
> template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
> diff --git a/libstdc++-v3/include/bits/version.def
> b/libstdc++-v3/include/bits/version.def
> index 6ca148f0488f..8db1967cc184 100644
> --- a/libstdc++-v3/include/bits/version.def
> +++ b/libstdc++-v3/include/bits/version.def
> @@ -1660,6 +1660,14 @@ ftms = {
> };
> };
>
> +ftms = {
> + name = ranges_starts_ends_with;
> + values = {
> + v = 202106;
> + cxxmin = 23;
> + };
> +};
> +
> ftms = {
> name = constexpr_bitset;
> values = {
> diff --git a/libstdc++-v3/include/bits/version.h
> b/libstdc++-v3/include/bits/version.h
> index 48a090c14a3d..3749528633f2 100644
> --- a/libstdc++-v3/include/bits/version.h
> +++ b/libstdc++-v3/include/bits/version.h
> @@ -1848,6 +1848,16 @@
> #endif /* !defined(__cpp_lib_ranges_find_last) &&
> defined(__glibcxx_want_ranges_find_last) */
> #undef __glibcxx_want_ranges_find_last
>
> +#if !defined(__cpp_lib_ranges_starts_ends_with)
> +# if (__cplusplus >= 202100L)
> +# define __glibcxx_ranges_starts_ends_with 202106L
> +# if defined(__glibcxx_want_all) ||
> defined(__glibcxx_want_ranges_starts_ends_with)
> +# define __cpp_lib_ranges_starts_ends_with 202106L
> +# endif
> +# endif
> +#endif /* !defined(__cpp_lib_ranges_starts_ends_with) &&
> defined(__glibcxx_want_ranges_starts_ends_with) */
> +#undef __glibcxx_want_ranges_starts_ends_with
> +
> #if !defined(__cpp_lib_constexpr_bitset)
> # if (__cplusplus >= 202100L) && _GLIBCXX_HOSTED &&
> (__cpp_constexpr_dynamic_alloc)
> # define __glibcxx_constexpr_bitset 202202L
> diff --git a/libstdc++-v3/include/std/algorithm
> b/libstdc++-v3/include/std/algorithm
> index 321a5e22d86b..1563cdf2b17c 100644
> --- a/libstdc++-v3/include/std/algorithm
> +++ b/libstdc++-v3/include/std/algorithm
> @@ -74,6 +74,7 @@
> #define __glibcxx_want_ranges_contains
> #define __glibcxx_want_ranges_find_last
> #define __glibcxx_want_ranges_fold
> +#define __glibcxx_want_ranges_starts_ends_with
> #define __glibcxx_want_robust_nonmodifying_seq_ops
> #define __glibcxx_want_sample
> #define __glibcxx_want_shift
> diff --git a/libstdc++-v3/src/c++23/std.cc.in b/libstdc++-v3/src/c++23/
> std.cc.in
> index 417c8a1a5626..2e4b3f75234f 100644
> --- a/libstdc++-v3/src/c++23/std.cc.in
> +++ b/libstdc++-v3/src/c++23/std.cc.in
> @@ -506,6 +506,10 @@ export namespace std
> using ranges::find_last;
> using ranges::find_last_if;
> using ranges::find_last_if_not;
> +#endif
> +#if __cpp_lib_ranges_starts_ends_with
> + using ranges::starts_with;
> + using ranges::ends_with;
> #endif
> }
> }
> diff --git a/libstdc++-v3/testsuite/25_algorithms/ends_with/1.cc
> b/libstdc++-v3/testsuite/25_algorithms/ends_with/1.cc
> new file mode 100644
> index 000000000000..462e3179a001
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/25_algorithms/ends_with/1.cc
> @@ -0,0 +1,135 @@
> +// { dg-do run { target c++23 } }
> +
> +#include <algorithm>
> +
> +#include <testsuite_hooks.h>
> +#include <testsuite_iterators.h>
> +
> +namespace ranges = std::ranges;
> +
> +template<typename Range1, typename Range2>
> +void
> +test01()
> +{
> + int n[] = {1,2,3,4,5,6,7,8,9,10};
> +
> + Range1 haystack(n, n+10);
> + Range2 needle(n+7, n+10);
> + VERIFY( ranges::ends_with(haystack, needle) );
> +
> + haystack = Range1(n);
> + needle = Range2(n, n+10);
> + VERIFY( ranges::ends_with(haystack, needle) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+6, n+9);
> + VERIFY( !ranges::ends_with(haystack, needle) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+6, n+9);
> + VERIFY( ranges::ends_with(haystack, needle,
> + [](int n, int m) { return std::abs(n - m) <=
> 1; }) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+6, n+9);
> + VERIFY( ranges::ends_with(haystack, needle,
> + ranges::equal_to{},
> + [](int n) { return n - 1; }) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+6, n+9);
> + VERIFY( ranges::ends_with(haystack, needle,
> + ranges::equal_to{},
> + std::identity{},
> + [](int n) { return n + 1; }) );
> +
> + haystack = Range1(n, n+5);
> + needle = Range2(n, n+10);
> + VERIFY( !ranges::ends_with(haystack, needle) );
> +}
> +
> +template<typename Range1, typename Range2>
> +void
> +test02()
> +{
> + int n[] = {1,2,3,4,5,6,7,8,9,10};
> +
> + Range1 haystack(n, n+10);
> + Range2 needle(n+7, n+10);
> + VERIFY( ranges::ends_with(haystack.begin(), haystack.end(),
> + needle.begin(), needle.end()) );
> +
> + haystack = Range1(n);
> + needle = Range2(n, n+10);
> + VERIFY( ranges::ends_with(haystack.begin(), haystack.end(),
> + needle.begin(), needle.end()) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+6, n+9);
> + VERIFY( !ranges::ends_with(haystack.begin(), haystack.end(),
> + needle.begin(), needle.end()) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+6, n+9);
> + VERIFY( ranges::ends_with(haystack.begin(), haystack.end(),
> + needle.begin(), needle.end(),
> + [](int n, int m) { return std::abs(n - m) <=
> 1; }) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+6, n+9);
> + VERIFY( ranges::ends_with(haystack.begin(), haystack.end(),
> + needle.begin(), needle.end(),
> + ranges::equal_to{},
> + [](int n) { return n - 1; }) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+6, n+9);
> + VERIFY( ranges::ends_with(haystack.begin(), haystack.end(),
> + needle.begin(), needle.end(),
> + ranges::equal_to{},
> + std::identity{},
> + [](int n) { return n + 1; }) );
> +
> + haystack = Range1(n, n+5);
> + needle = Range2(n, n+10);
> + VERIFY( !ranges::ends_with(haystack.begin(), haystack.end(),
> + needle.begin(), needle.end()) );
> +
> + haystack = Range1(n, n+5);
> + needle = Range2(n+10, n+10);
> + VERIFY( ranges::ends_with(haystack.begin(), haystack.end(),
> + needle.begin(), needle.end()) );
> +}
> +
> +int
> +main()
> +{
> + using namespace __gnu_test;
> + using forward = test_forward_range<int>;
> + using bidirectional_common = bidirectional_container<int>;
> + using input_sized = test_input_sized_range<int>;
> + using input_sized_sent = test_sized_range_sized_sent<int,
> input_iterator_wrapper>;
> + using random_access = test_random_access_range<int>;
> + using random_access_sized = test_random_access_sized_range<int>;
> + using random_access_sized_sent = test_sized_range_sized_sent<int,
> random_access_iterator_wrapper>;
> +
> + test01<forward, forward>();
> + test01<random_access, random_access>();
> + test02<forward, forward>();
> + test02<random_access, random_access>();
> +
> + test01<bidirectional_common, bidirectional_common>();
> + test02<bidirectional_common, bidirectional_common>();
> + test01<bidirectional_common, forward>();
> + test02<bidirectional_common, forward>();
> +
> + test01<input_sized, input_sized>();
> + test01<random_access_sized, random_access_sized>();
> + // test02<input_sized, input_sized>(); constraint violation
> + test02<random_access_sized, random_access_sized>();
> +
> + test01<input_sized_sent, input_sized_sent>();
> + test01<random_access_sized_sent, random_access_sized_sent>();
> + test02<input_sized_sent, input_sized_sent>();
> + test02<random_access_sized_sent, random_access_sized_sent>();
> +}
> diff --git a/libstdc++-v3/testsuite/25_algorithms/starts_with/1.cc
> b/libstdc++-v3/testsuite/25_algorithms/starts_with/1.cc
> new file mode 100644
> index 000000000000..805f31ea2b03
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/25_algorithms/starts_with/1.cc
> @@ -0,0 +1,128 @@
> +// { dg-do run { target c++23 } }
> +
> +#include <algorithm>
> +
> +#include <testsuite_hooks.h>
> +#include <testsuite_iterators.h>
> +
> +namespace ranges = std::ranges;
> +
> +template<typename Range1, typename Range2>
> +void
> +test01()
> +{
> + int n[] = {1,2,3,4,5,6,7,8,9,10};
> +
> + Range1 haystack(n, n+10);
> + Range2 needle(n, n+3);
> + VERIFY( ranges::starts_with(haystack, needle) );
> +
> + haystack = Range1(n);
> + needle = Range2(n, n+10);
> + VERIFY( ranges::starts_with(haystack, needle) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+1, n+4);
> + VERIFY( !ranges::starts_with(haystack, needle) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+1, n+4);
> + VERIFY( ranges::starts_with(haystack, needle,
> + [](int n, int m) { return std::abs(n - m) <=
> 1; }) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+1, n+4);
> + VERIFY( ranges::starts_with(haystack, needle,
> + ranges::equal_to{},
> + [](int n) { return n + 1; }) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+1, n+4);
> + VERIFY( ranges::starts_with(haystack, needle,
> + ranges::equal_to{},
> + std::identity{},
> + [](int n) { return n - 1; }) );
> +
> + haystack = Range1(n, n+5);
> + needle = Range2(n, n+10);
> + VERIFY( !ranges::starts_with(haystack, needle) );
> +
> + haystack = Range1(n, n+5);
> + needle = Range2(n+10, n+10);
> + VERIFY( ranges::starts_with(haystack, needle) );
> +}
> +
> +template<typename Range1, typename Range2>
> +void
> +test02()
> +{
> + int n[] = {1,2,3,4,5,6,7,8,9,10};
> +
> + Range1 haystack(n, n+10);
> + Range2 needle(n, n+3);
> + VERIFY( ranges::starts_with(haystack.begin(), haystack.end(),
> + needle.begin(), needle.end()) );
> +
> + haystack = Range1(n);
> + needle = Range2(n, n+10);
> + VERIFY( ranges::starts_with(haystack.begin(), haystack.end(),
> + needle.begin(), needle.end()) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+1, n+4);
> + VERIFY( !ranges::starts_with(haystack.begin(), haystack.end(),
> + needle.begin(), needle.end()) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+1, n+4);
> + VERIFY( ranges::starts_with(haystack.begin(), haystack.end(),
> + needle.begin(), needle.end(),
> + [](int n, int m) { return std::abs(n - m) <=
> 1; }) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+1, n+4);
> + VERIFY( ranges::starts_with(haystack.begin(), haystack.end(),
> + needle.begin(), needle.end(),
> + ranges::equal_to{},
> + [](int n) { return n + 1; }) );
> +
> + haystack = Range1(n);
> + needle = Range2(n+1, n+4);
> + VERIFY( ranges::starts_with(haystack.begin(), haystack.end(),
> + needle.begin(), needle.end(),
> + ranges::equal_to{},
> + std::identity{},
> + [](int n) { return n - 1; }) );
> +
> + haystack = Range1(n, n+5);
> + needle = Range2(n, n+10);
> + VERIFY( !ranges::starts_with(haystack.begin(), haystack.end(),
> + needle.begin(), needle.end()) );
> +}
> +
> +int
> +main()
> +{
> + using namespace __gnu_test;
> + using input = test_input_range<int>;
> + using input_sized = test_input_sized_range<int>;
> + using input_sized_sent = test_sized_range_sized_sent<int,
> input_iterator_wrapper>;
> + using random_access = test_random_access_range<int>;
> + using random_access_sized = test_random_access_sized_range<int>;
> + using random_access_sized_sent = test_sized_range_sized_sent<int,
> random_access_iterator_wrapper>;
> +
> + test01<input, input>();
> + test01<random_access, random_access>();
> + test02<input, input>();
> + test02<random_access, random_access>();
> +
> + test01<input_sized, input_sized>();
> + test01<random_access_sized, random_access_sized>();
> + test02<input_sized, input_sized>();
> + test02<random_access_sized, random_access_sized>();
> +
> + test01<input_sized_sent, input_sized_sent>();
> + test01<random_access_sized_sent, random_access_sized_sent>();
> + test02<input_sized_sent, input_sized_sent>();
> + test02<random_access_sized_sent, random_access_sized_sent>();
> +}
> --
> 2.49.0.654.g845c48a16a
>
