public inbox for libstdc++@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH] libstdc++: Fix condition for memoizing reverse_view::begin() [PR100621]
@ 2021-05-17 16:17 Patrick Palka
  2021-05-17 16:47 ` Jonathan Wakely
  0 siblings, 1 reply; 2+ messages in thread
From: Patrick Palka @ 2021-05-17 16:17 UTC (permalink / raw)
  To: gcc-patches; +Cc: libstdc++, Patrick Palka

A range being a random access range is not a sufficient condition for
ranges::next(iter, sent) to have constant time complexity; the range
must also have a sized sentinel.  This adjusts the memoization condition
for reverse_view accordingly.

Tested on x86_64-pc-linxu-gnu, does this look OK for trunk?  Doesn't
seem to be worth backporting.

libstdc++-v3/ChangeLog:

	* include/std/ranges (reverse_view::_S_needs_cached_begin):
	Set to false if the underlying non-common random-access range
	doesn't have a sized sentinel.
---
 libstdc++-v3/include/std/ranges | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index bf52074ca05..e93469ca3b4 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -3340,7 +3340,9 @@ namespace views::__adaptor
     {
     private:
       static constexpr bool _S_needs_cached_begin
-	= !common_range<_Vp> && !random_access_range<_Vp>;
+	= !common_range<_Vp> && !(random_access_range<_Vp>
+				  && sized_sentinel_for<sentinel_t<_Vp>,
+							iterator_t<_Vp>>);
 
       [[no_unique_address]]
 	__detail::__maybe_present_t<_S_needs_cached_begin,
-- 
2.31.1.621.g97eea85a0a


^ permalink raw reply	[flat|nested] 2+ messages in thread

* Re: [PATCH] libstdc++: Fix condition for memoizing reverse_view::begin() [PR100621]
  2021-05-17 16:17 [PATCH] libstdc++: Fix condition for memoizing reverse_view::begin() [PR100621] Patrick Palka
@ 2021-05-17 16:47 ` Jonathan Wakely
  0 siblings, 0 replies; 2+ messages in thread
From: Jonathan Wakely @ 2021-05-17 16:47 UTC (permalink / raw)
  To: Patrick Palka; +Cc: gcc-patches, libstdc++

On 17/05/21 12:17 -0400, Patrick Palka via Libstdc++ wrote:
>A range being a random access range is not a sufficient condition for
>ranges::next(iter, sent) to have constant time complexity; the range
>must also have a sized sentinel.  This adjusts the memoization condition
>for reverse_view accordingly.
>
>Tested on x86_64-pc-linxu-gnu, does this look OK for trunk?  Doesn't
>seem to be worth backporting.

OK for trunk. I agree the backports probably aren't needed, but if
it causes anybody problems we can do it later.


>libstdc++-v3/ChangeLog:
>
>	* include/std/ranges (reverse_view::_S_needs_cached_begin):
>	Set to false if the underlying non-common random-access range
>	doesn't have a sized sentinel.
>---
> libstdc++-v3/include/std/ranges | 4 +++-
> 1 file changed, 3 insertions(+), 1 deletion(-)
>
>diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
>index bf52074ca05..e93469ca3b4 100644
>--- a/libstdc++-v3/include/std/ranges
>+++ b/libstdc++-v3/include/std/ranges
>@@ -3340,7 +3340,9 @@ namespace views::__adaptor
>     {
>     private:
>       static constexpr bool _S_needs_cached_begin
>-	= !common_range<_Vp> && !random_access_range<_Vp>;
>+	= !common_range<_Vp> && !(random_access_range<_Vp>
>+				  && sized_sentinel_for<sentinel_t<_Vp>,
>+							iterator_t<_Vp>>);
>
>       [[no_unique_address]]
> 	__detail::__maybe_present_t<_S_needs_cached_begin,
>-- 
>2.31.1.621.g97eea85a0a
>


^ permalink raw reply	[flat|nested] 2+ messages in thread

end of thread, other threads:[~2021-05-17 16:47 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-05-17 16:17 [PATCH] libstdc++: Fix condition for memoizing reverse_view::begin() [PR100621] Patrick Palka
2021-05-17 16:47 ` Jonathan Wakely

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).